is_efx_goods_scale
Multiplying each agent's additive valuation vector by a positive constant c_i > 0 preserves and reflects whether an allocation is EFX.
Statement
theorem is_efx_goods_scale {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) (c : Fin n → ℝ) (hc : ∀ i, 0 < c i) : is_efx_goods (fun i g => c i * u i g) σ ↔ is_efx_goods u σ
- Source
- step towards scaled_common_ratio_bivalued_efx_fpo_envyfreeable
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
The proof, explained
The proof shows that the EFX property of an allocation is invariant under scaling each agent's valuation vector by a strictly positive factor c_i > 0. It first establishes an auxiliary lemma showing that an additive valuation scales linearly by factoring c_i out of the sum over any bundle. It then proves both directions of the equivalence by applying this scaling identity to the envy-freeness comparisons and canceling or introducing the factor c_i via the strict monotonicity of positive multiplication.
For every agent i and bundle S, the scaled additive valuation satisfies v'_i(S) = c_i * v_i(S).
By definition, the additive valuation of a bundle S is the sum of the item valuations over S. Factoring the scalar c_i out of the sum using distributivity (`Finset.mul_sum`) shows that scaling each item's value by c_i scales the total bundle value by c_i.
uses
Finset.mul_sumhave h : ∀ (i : Fin n) (S : Finset (Fin m)), additive_valuation (fun g => c i * u i g) S = c i * additive_valuation (u i) S := by intro i S simp [additive_valuation, Finset.mul_sum]
The equivalence reduces to checking both directions of the definition of an EFX allocation.
Unfolding `is_efx_goods`, an allocation σ is EFX if for every pair of distinct agents i ≠ j and any good g in j's bundle, agent i values their own bundle at least as much as j's bundle with g removed. The `constructor` tactic splits the if-and-only-if into the forward and backward implications.
unfold is_efx_goods constructor
If the allocation is EFX under the scaled valuations, then it is EFX under the original valuations.
Assume the scaled valuation profile is EFX. For any distinct agents i ≠ j and item g in j's bundle, the hypothesis gives that i's scaled value for j's bundle without g is at most i's scaled value for their own bundle. Rewriting both values using the scaling lemma yields c_i * v_i(A_j \ {g}) ≤ c_i * v_i(A_i). Because c_i > 0, canceling c_i via `mul_le_mul_iff_of_pos_left` yields the unscaled EFX inequality.
uses
mul_le_mul_iff_of_pos_left· intro H i j hij g hg have h1 := H i j hij g hg rw [h, h] at h1 exact (mul_le_mul_iff_of_pos_left (hc i)).mp h1
If the allocation is EFX under the original valuations, then it is EFX under the scaled valuations.
Assume the allocation is EFX under the original valuations. For any distinct agents i ≠ j and item g in j's bundle, we have v_i(A_j \ {g}) ≤ v_i(A_i). Rewriting the goal using the scaling lemma expresses both sides as c_i times the unscaled bundle valuations. Since c_i > 0, multiplying the known inequality by c_i via `mul_le_mul_iff_of_pos_left` proves the scaled EFX inequality.
uses
mul_le_mul_iff_of_pos_left· intro H i j hij g hg have h1 := H i j hij g hg rw [h, h] exact (mul_le_mul_iff_of_pos_left (hc i)).mpr h1
Finset.mul_sum- Multiplication distributes over finite sums: a * ∑ x ∈ s, f x = ∑ x ∈ s, a * f x.
mul_le_mul_iff_of_pos_left- For a strictly positive factor a > 0, multiplication on the left preserves and reflects inequalities: a * b ≤ a * c ↔ b ≤ c.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The EFX property of an allocation is invariant under multiplying each agent's valuation vector by a positive constant. -/theorem is_efx_goods_scale {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) (c : Fin n → ℝ) (hc : ∀ i, 0 < c i) : is_efx_goods (fun i g => c i * u i g) σ ↔ is_efx_goods u σ := by have h : ∀ (i : Fin n) (S : Finset (Fin m)), additive_valuation (fun g => c i * u i g) S = c i * additive_valuation (u i) S := by intro i S simp [additive_valuation, Finset.mul_sum] unfold is_efx_goods constructor · intro H i j hij g hg have h1 := H i j hij g hg rw [h, h] at h1 exact (mul_le_mul_iff_of_pos_left (hc i)).mp h1 · intro H i j hij g hg have h1 := H i j hij g hg rw [h, h] exact (mul_le_mul_iff_of_pos_left (hc i)).mpr h1