efx_exists_of_null_last_good
For a positive number of agents and nonnegative additive values, a good worth zero to every agent can be added while retaining existence of a complete EFX allocation, with rearrangement allowed.
Statement
theorem efx_exists_of_null_last_good {m n : ℕ} (hn : 0 < n) (u : Fin n → Fin (m+1) → ℝ) (hu : ∀ i g, 0 ≤ u i g) (hzero : ∀ i, u i (Fin.last m) = 0) (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 2
- efx_exists_of_universal_least_goodFor a positive number of agents and nonnegative additive values, if the last good is weakly least valuable for every agent, existence of…
- 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…
The proof, explained
The proof reduces the goal to `efx_exists_of_universal_least_good`, which ensures that an EFX allocation on $m$ goods extends to $m+1$ goods whenever the additional good is valued weakly less than every existing good by all agents. Because valuations are nonnegative and the added good is valued at zero by all agents, it trivially satisfies this minimum-value condition.
It suffices to show that the additional good is valued weakly less than each of the first $m$ goods by every agent.
By `efx_exists_of_universal_least_good`, an EFX allocation on $m$ goods can be extended to an allocation on $m + 1$ goods provided the new good is weakly dominated in value by all existing goods for all agents.
uses
efx_exists_of_universal_least_goodapply efx_exists_of_universal_least_good hn u hu _ hThe additional good is valued at most as much as any of the first $m$ goods for every agent.
Fix an agent $i$ and any of the first $m$ goods $g$. By assumption (`hzero`), the value of the $(m+1)$-th good to agent $i$ is $0$. Since valuations are nonnegative by hypothesis (`hu`), agent $i$'s valuation for good $g$ is at least $0$, satisfying the condition $0 \le u(i, g)$.
intro i g rw [hzero i] exact hu i g.castSucc
efx_exists_of_universal_least_good- An EFX allocation can be extended to an additional good if that good is valued weakly less than every existing good by all agents.
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_null_last_good {m n : ℕ} (hn : 0 < n) (u : Fin n → Fin (m+1) → ℝ) (hu : ∀ i g, 0 ≤ u i g) (hzero : ∀ i, u i (Fin.last m) = 0) (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 apply efx_exists_of_universal_least_good hn u hu _ h intro i g rw [hzero i] exact hu i g.castSucc