efx_exists_of_universal_least_good
For a positive number of agents and nonnegative additive values, if the last good is weakly least valuable for every agent, existence of EFX without it implies existence of EFX with it.
Statement
theorem efx_exists_of_universal_least_good {m n : ℕ} (hn : 0 < n) (u : Fin n → Fin (m+1) → ℝ) (hu : ∀ i g, 0 ≤ u i g) (hmin : ∀ (i : Fin n) (g : Fin m), u i (Fin.last m) ≤ u i g.castSucc) (h : ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g.castSucc) σ) : ∃ τ : Fin (m+1) → Fin n, is_efx_goods u τ
- Source
- Helper for efx_four_agents_additive_exists (OP-7), campaign session IN-404, 2026-11-01. Standard cycle elimination and ordered insertion, arXiv:1707.04769v3 Lemma 6.1 and Appendix B; no novelty claim.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- is_efx_goods_insert_of_unenvied_of_minAdding a good to an unenvied agent preserves EFX if every other agent values the new good no more than every old good in that recipient's…
- is_efx_goods_exists_unenviedFor a positive number of agents, any EFX allocation of nonnegative additive goods can be changed to another EFX allocation that weakly…
- 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.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- Used by 2
- efx_exists_of_common_pair_order_oddFor any positive number of agents and 2k+1 nonnegative additive goods, suppose every agent weakly prefers goods with smaller…
- efx_exists_of_null_last_goodFor a positive number of agents and nonnegative additive values, a good worth zero to every agent can be added while retaining existence…
The proof, explained
To extend an EFX allocation of $m$ goods to an additional good that is universally least valuable, we first obtain an EFX allocation of the first $m$ goods under which some agent $s$ is unenvied by all agents. We then assign the new good to agent $s$. Because $s$ was previously unenvied and the new good is weakly least valuable among all goods for every agent, the resulting allocation of all $m+1$ goods remains EFX.
There exists an EFX allocation $\tau$ of the first $m$ goods under which some agent $s$ is unenvied by everyone.
From the assumption that an EFX allocation of the first $m$ goods exists ($h$), let $\sigma$ be such an allocation. By `is_efx_goods_exists_unenvied`, there exists an EFX allocation $\tau$ of the first $m$ goods and an agent $s$ such that every agent $i$ weakly prefers their own bundle to $s$'s bundle.
uses
is_efx_goods_exists_unenviedobtain ⟨σ, hσ⟩ := h obtain ⟨τ, hτ, _, s, hs⟩ := is_efx_goods_exists_unenvied hn (fun i g => u i g.castSucc) (fun i g => hu i g.castSucc) σ hσ
The allocation extending $\tau$ by assigning the last good to agent $s$ is an EFX allocation of all $m+1$ goods.
We extend $\tau$ to all $m+1$ goods via `Fin.lastCases s τ`, assigning the last good to the unenvied agent $s$ and all other goods according to $\tau$. By `is_efx_goods_insert_of_unenvied_of_min`, adding a good to an unenvied agent preserves the EFX condition whenever every other agent values the new good weakly less than each item in $s$'s bundle. This condition is satisfied because the last good is assumed to be weakly least valuable among all goods for every agent ($hmin$).
uses
Fin.lastCases,is_efx_goods_insert_of_unenvied_of_minexact ⟨Fin.lastCases s τ, is_efx_goods_insert_of_unenvied_of_min u hu τ hτ s hs (fun i _ g _ => hmin i g)⟩
is_efx_goods_exists_unenvied- For any positive number of agents and nonnegative additive valuations, given an EFX allocation of goods, there exists an EFX allocation under which some agent $s$ is unenvied by all agents.
is_efx_goods_insert_of_unenvied_of_min- Given an EFX allocation of $m$ goods with an unenvied agent $s$, assigning an additional good to $s$ produces an EFX allocation of all $m+1$ goods, provided every other agent values the new good weakly less than every good in $s$'s bundle.
Fin.lastCases- Constructs a function on `Fin (m + 1)` by specifying its value at the last element `Fin.last m` and its values on the initial $m$ elements.
- The lemma `is_efx_goods_insert_of_unenvied_of_min` only requires that the new good is weakly less valuable than any good already in agent $s$'s bundle; the proof supplies the stronger hypothesis `hmin`, under which the last good is weakly least valuable among all goods.
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.
open Function Finsettheorem efx_exists_of_universal_least_good {m n : ℕ} (hn : 0 < n) (u : Fin n → Fin (m+1) → ℝ) (hu : ∀ i g, 0 ≤ u i g) (hmin : ∀ (i : Fin n) (g : Fin m), u i (Fin.last m) ≤ u i g.castSucc) (h : ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g.castSucc) σ) : ∃ τ : Fin (m+1) → Fin n, is_efx_goods u τ := by obtain ⟨σ, hσ⟩ := h obtain ⟨τ, hτ, _, s, hs⟩ := is_efx_goods_exists_unenvied hn (fun i g => u i g.castSucc) (fun i g => hu i g.castSucc) σ hσ exact ⟨Fin.lastCases s τ, is_efx_goods_insert_of_unenvied_of_min u hu τ hτ s hs (fun i _ g _ => hmin i g)⟩