efx_exists_of_two_universal_small_goods
For a positive number of agents with nonnegative real additive values, suppose each of the last two goods is weakly less valuable to every agent than each old good, and a complete EFX allocation of the old goods exists. Then a complete EFX allocation including both new goods exists.
Statement
theorem efx_exists_of_two_universal_small_goods {m n : ℕ} (hn : 0 < n) (u : Fin n → Fin (m+2) → ℝ) (hu : ∀ i g, 0 ≤ u i g) (hsmall₀ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last m).castSucc ≤ u i g.castSucc.castSucc) (hsmall₁ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last (m+1)) ≤ u i g.castSucc.castSucc) (h : ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g.castSucc.castSucc) σ) : ∃ τ : Fin (m+2) → Fin n, is_efx_goods u τ
- Source
- Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- efx_exists_of_two_universal_small_goods_irLet m and n be natural numbers with n positive. There are m+2 goods with nonnegative real additive values for n agents. Each agent 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…
- 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.
- Used by 1
- efx_exists_of_common_pair_order_evenFor any positive number of agents and an even number 2k of goods with nonnegative additive values, suppose every agent weakly prefers…
The proof, explained
The theorem reduces directly to a companion result, efx_exists_of_two_universal_small_goods_ir. From the existential hypothesis, we extract an initial EFX allocation σ of the first m goods. Applying the companion theorem to σ produces an extended allocation τ for all m+2 goods that is EFX, which immediately witnesses the existential claim.
We fix a complete EFX allocation σ for the initial m goods.
By the hypothesis h, there exists an allocation of the initial m goods that is EFX under the agents' valuations restricted to those goods. We choose such an allocation σ along with the certificate hσ that it is EFX.
obtain ⟨σ, hσ⟩ := hAn allocation τ for all m+2 goods is constructed and certified to be EFX, witnessing the goal.
We apply the companion theorem efx_exists_of_two_universal_small_goods_ir to σ and hσ. This theorem extends σ to an allocation τ of all m+2 goods that remains EFX (and also preserves bundles and guarantees weak utility improvements). Providing τ and its EFX certificate completes the existential proof.
uses
efx_exists_of_two_universal_small_goods_irobtain ⟨τ, hτ, _, _⟩ := efx_exists_of_two_universal_small_goods_ir hn u hu hsmall₀ hsmall₁ σ hσ exact ⟨τ, hτ⟩
efx_exists_of_two_universal_small_goods_ir- If n > 0 agents have nonnegative additive valuations and two additional goods are each universally weakly less valuable than any of the first m goods, then any complete EFX allocation of the first m goods can be extended to a complete EFX allocation of all m+2 goods that weakly increases each agent's valuation and keeps together goods previously allocated to the same agent.
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_two_universal_small_goods {m n : ℕ} (hn : 0 < n) (u : Fin n → Fin (m+2) → ℝ) (hu : ∀ i g, 0 ≤ u i g) (hsmall₀ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last m).castSucc ≤ u i g.castSucc.castSucc) (hsmall₁ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last (m+1)) ≤ u i g.castSucc.castSucc) (h : ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g.castSucc.castSucc) σ) : ∃ τ : Fin (m+2) → Fin n, is_efx_goods u τ := by obtain ⟨σ, hσ⟩ := h obtain ⟨τ, hτ, _, _⟩ := efx_exists_of_two_universal_small_goods_ir hn u hu hsmall₀ hsmall₁ σ hσ exact ⟨τ, hτ⟩