is_alpha_ef1_goods_one_of_ef1_goods
If an allocation is exactly EF1 (in the is_ef1_goods sense) for nonnegative additive valuations, then it is 1-EF1 in the is_alpha_ef1_goods sense.
Statement
theorem is_alpha_ef1_goods_one_of_ef1_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) (hpos : ∀ i g, 0 ≤ u i g) (h : is_ef1_goods u σ) : is_alpha_ef1_goods u 1 σ- Source
- step towards op561_ratio_gt_sqrt5
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_ef1_goodsEF1 for goods: every agent i either does not envy agent j, or stops envying j after some single good is removed from j's bundle.
- is_alpha_ef1_goodsAn allocation of m indivisible goods to n agents is alpha-EF1 under additive valuations u if for every pair of distinct agents i and j…
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- 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
To show that an EF1 allocation is 1-EF1 for nonnegative additive valuations, consider any distinct agents i and j where j holds a nonempty bundle. By EF1, either agent i already does not envy agent j, or there is a good in j's bundle whose removal eliminates envy. In the first case, any good in j's bundle witnesses 1-EF1 because removing an item with nonnegative value cannot increase the bundle's value. In the second case, the good guaranteed by EF1 directly serves as the witness because scaling by 1 is the identity.
Fix two distinct agents i and j with j's bundle nonempty; by EF1, either i does not envy j, or some good in j's bundle eliminates envy.
To establish the definition of 1-EF1 (is_alpha_ef1_goods), we introduce arbitrary agents i and j, assuming i ≠ j and that j's bundle is nonempty (hjne). Applying the EF1 hypothesis (h) to i and j yields two cases: either agent i does not envy agent j at all (u_i(bundle(j)) ≤ u_i(bundle(i))), or there exists a good g in j's bundle whose removal eliminates envy.
intro i j _ hjne rcases h i j with hle | ⟨g, hg, hgle⟩
When agent i does not envy agent j, any good g₀ in j's bundle witnesses 1-EF1.
Since j's bundle is nonempty, we select an arbitrary good g₀ ∈ bundle(j) as the required witness (lines 4–5). Rewriting with one_mul simplifies 1 * u_i(...) to u_i(...) (line 6). To show u_i(bundle(j) \ {g₀}) ≤ u_i(bundle(i)), we establish the auxiliary inequality hsub: removing g₀ cannot increase the valuation (lines 7–13). By definition, the additive valuation is a sum over the bundle; because bundle(j) \ {g₀} ⊆ bundle(j) (by Finset.mem_of_mem_erase) and all valuations are nonnegative (hpos), Finset.sum_le_sum_of_subset_of_nonneg bounds the smaller sum by the original sum. Finally, linear arithmetic (linarith, line 14) combines hsub with the case hypothesis u_i(bundle(j)) ≤ u_i(bundle(i)) to close the goal by transitivity.
uses
one_mul,Finset.sum_le_sum_of_subset_of_nonneg,Finset.mem_of_mem_erase· obtain ⟨g0, hg0⟩ := hjne refine ⟨g0, hg0, ?_⟩ rw [one_mul] have hsub : additive_valuation (u i) ((bundle_of σ j).erase g0) ≤ additive_valuation (u i) (bundle_of σ j) := by dsimp [additive_valuation] apply Finset.sum_le_sum_of_subset_of_nonneg · intro x hx exact Finset.mem_of_mem_erase hx · intro x _ _ exact hpos i x linarith
When removing a good g eliminates envy, that good g directly witnesses 1-EF1.
In the second case, the EF1 hypothesis provides a specific good g ∈ bundle(j) whose removal eliminates envy. Using this g as the witness (line 15) and simplifying the multiplication by 1 via one_mul (line 16), the goal matches the EF1 hypothesis (hgle, line 17) directly.
uses
one_mul· refine ⟨g, hg, ?_⟩ rw [one_mul] exact hgle
one_mul- Multiplying any element by 1 on the left leaves it unchanged: 1 * a = a.
Finset.sum_le_sum_of_subset_of_nonneg- If s ⊆ t are finite sets and f is nonnegative on t \ s, then the sum of f over s is at most the sum of f over t.
Finset.mem_of_mem_erase- If an element belongs to a finite set with an element removed (s.erase a), then it belongs to the original set s.
- The definition of α-EF1 with α = 1 contains the formal factor 1 * additive_valuation ..., which requires an explicit rewrite using one_mul to match the unscaled valuation on paper.
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.
theorem is_alpha_ef1_goods_one_of_ef1_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) (hpos : ∀ i g, 0 ≤ u i g) (h : is_ef1_goods u σ) : is_alpha_ef1_goods u 1 σ := by intro i j _ hjne rcases h i j with hle | ⟨g, hg, hgle⟩ · obtain ⟨g0, hg0⟩ := hjne refine ⟨g0, hg0, ?_⟩ rw [one_mul] have hsub : additive_valuation (u i) ((bundle_of σ j).erase g0) ≤ additive_valuation (u i) (bundle_of σ j) := by dsimp [additive_valuation] apply Finset.sum_le_sum_of_subset_of_nonneg · intro x hx exact Finset.mem_of_mem_erase hx · intro x _ _ exact hpos i x linarith · refine ⟨g, hg, ?_⟩ rw [one_mul] exact hgle