efx_exists_of_common_pair_order_even
For any positive number of agents and an even number 2k of goods with nonnegative additive values, suppose every agent weakly prefers every good in an earlier consecutive pair to every good in a later pair, with arbitrary comparisons within each pair. A complete EFX allocation exists.
Statement
theorem efx_exists_of_common_pair_order_even (k n : ℕ) (hn : 0 < n)
(u : Fin n → Fin (2*k) → ℝ) (hu : ∀ i g, 0 ≤ u i g)
(horder : ∀ (i : Fin n) (g h : Fin (2*k)), g.val / 2 < h.val / 2 → u i h ≤ u i g) :
∃ σ : Fin (2*k) → Fin n, is_efx_goods u σ- Source
- Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01. The baseline is universally least-good insertion for a common individual ranking in arXiv:1707.04769v3 Appendix B. Here the two new goods need not have a common order. Web searches on 2026-11-01 for two smallest goods, ordered pairs, common pair order, and EFX completion found no matching result; arXiv:2504.03951 concerns n+2 goods and does not supply this arbitrary-old-allocation preservation statement. This does not settle unrestricted four-agent EFX.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- efx_exists_of_two_universal_small_goodsFor a positive number of agents with nonnegative real additive values, suppose each of the last two goods is weakly less valuable to every…
- is_efx_goods_equiv_goodsRelabeling a finite set of goods through a bijection, both in the valuation profile and allocation, preserves and reflects EFX.
- 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_common_pair_orderFor any finite number m of goods, any positive number n of agents, and nonnegative real additive values, suppose for every agent and goods…
The proof, explained
The proof proceeds by induction on the number of pairs k of goods. The base case k = 0 has no goods and is vacuously EFX. In the induction step, the 2(k + 1) goods are re-indexed as 2k + 2 goods, with the two added goods forming the final pair; by the common pair order hypothesis, both added goods are universally weakly less valuable to every agent than any of the first 2k goods. The induction hypothesis provides an EFX allocation for the first 2k goods, which is then extended to all 2k + 2 goods using efx_exists_of_two_universal_small_goods and pulled back to the original index set.
When k = 0, the empty allocation on Fin 0 is an EFX allocation.
There are 2 · 0 = 0 goods. The unique map from the empty set Fin 0 to Fin n assigns no goods to any agent, so no agent holds any goods. The condition for an allocation to be EFX quantifies over an item g in an agent's bundle; because Fin 0 has no elements, this condition holds vacuously by Fin.elim0.
uses
Fin.elim0induction k with | zero => refine ⟨fun g => Fin.elim0 g, ?_⟩ intro i j hij g hg exact Fin.elim0 g
For the induction step, the 2(k + 1) goods are re-indexed as Fin (2k + 2), preserving nonnegativity of valuations.
Linear arithmetic establishes 2(k + 1) = 2k + 2, inducing a bijection e : Fin (2(k + 1)) ≃ Fin (2k + 2) via finCongr. The valuations are re-indexed as v_i(g) = u_i(e⁻¹(g)), which remain nonnegative since u is nonnegative.
uses
finCongr| succ k ih => have heq : 2 * (k+1) = 2*k+2 := by omega let e : Fin (2*(k+1)) ≃ Fin (2*k+2) := finCongr heq let v (i : Fin n) (g : Fin (2*k+2)) := u i (e.symm g) have hv (i : Fin n) (g : Fin (2*k+2)) : 0 ≤ v i g := hu i _The two goods in the final pair (indices 2k and 2k + 1 in Fin (2k + 2)) are universally weakly less valuable to every agent than any of the first 2k goods.
For every good g < 2k, integer division gives ⌊g / 2⌋ < k, whereas ⌊2k / 2⌋ = k and ⌊(2k + 1) / 2⌋ = k. By the common pair order hypothesis, every agent weakly prefers any good in an earlier pair to any good in a later pair. Thus, both v_i(2k) ≤ v_i(g) and v_i(2k + 1) ≤ v_i(g) hold for all agents i and all goods g < 2k.
have hsmall₀ (i : Fin n) (g : Fin (2*k)) : v i (Fin.last (2*k)).castSucc ≤ v i g.castSucc.castSucc := by apply horder i _ _ change g.val / 2 < (2*k) / 2 omega have hsmall₁ (i : Fin n) (g : Fin (2*k)) : v i (Fin.last (2*k+1)) ≤ v i g.castSucc.castSucc := by apply horder i _ _ change g.val / 2 < (2*k+1) / 2 omega
An EFX allocation exists for the first 2k goods under the restricted valuations.
We apply the induction hypothesis to the subcollection of the first 2k goods, embedded into Fin (2k + 2) by two successive castSucc operations. The restricted valuations remain nonnegative and inherit the common pair ordering condition, satisfying all premises of the induction hypothesis.
have hold : ∃ σ : Fin (2*k) → Fin n, is_efx_goods (fun i g => v i g.castSucc.castSucc) σ := by apply ih · exact fun i g => hv i _ · intro i g h hgh apply horder i _ _ exact hgh
An EFX allocation τ exists for all 2k + 2 goods under valuation v.
By efx_exists_of_two_universal_small_goods, given an EFX allocation for m goods, adding two goods that are universally weakly smaller than all original m goods for every agent allows extending the allocation to an EFX allocation of all m + 2 goods. Applying this with m = 2k and the pair {2k, 2k + 1} yields the desired allocation τ.
uses
efx_exists_of_two_universal_small_goodsobtain ⟨τ, hτ⟩ := efx_exists_of_two_universal_small_goods hn v hv hsmall₀ hsmall₁ holdThe pullback allocation σ = τ ∘ e is an EFX allocation for the original goods Fin (2(k + 1)) under valuation u.
We define σ by assigning good g to agent τ(e(g)). By is_efx_goods_equiv_goods, re-indexing goods along a bijection preserves the EFX property. Since v_i(e(g)) = u_i(e⁻¹(e(g))) = u_i(g), simplifying definitions shows that σ is EFX for u.
uses
is_efx_goods_equiv_goodsrefine ⟨fun g => τ (e g), ?_⟩ have hh := (is_efx_goods_equiv_goods e v τ).mpr hτ simpa only [v, e.symm_apply_apply] using hh
Fin.elim0- The empty type Fin 0 has no elements; an element of Fin 0 can be used to prove any goal or construct any term.
finCongr- An equality of natural numbers n = m induces a canonical equivalence (bijection) between Fin n and Fin m.
efx_exists_of_two_universal_small_goods- If an EFX allocation exists for m goods with nonnegative additive valuations, and two added goods are each weakly less valuable than all original m goods to every agent, then an EFX allocation exists for all m + 2 goods.
is_efx_goods_equiv_goods- An allocation of goods is EFX if and only if the re-indexed allocation obtained via a bijection between sets of goods is EFX for the re-indexed valuation function.
- In Lean, the types Fin (2 * (k + 1)) and Fin (2 * k + 2) are not definitionally identical, so the proof explicitly introduces a bijection (finCongr) between them and uses is_efx_goods_equiv_goods to transfer the EFX property; on paper, 2(k+1) and 2k+2 are the same number and this step is invisible.
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_common_pair_order_even (k n : ℕ) (hn : 0 < n) (u : Fin n → Fin (2*k) → ℝ) (hu : ∀ i g, 0 ≤ u i g) (horder : ∀ (i : Fin n) (g h : Fin (2*k)), g.val / 2 < h.val / 2 → u i h ≤ u i g) : ∃ σ : Fin (2*k) → Fin n, is_efx_goods u σ := by induction k with | zero => refine ⟨fun g => Fin.elim0 g, ?_⟩ intro i j hij g hg exact Fin.elim0 g | succ k ih => have heq : 2 * (k+1) = 2*k+2 := by omega let e : Fin (2*(k+1)) ≃ Fin (2*k+2) := finCongr heq let v (i : Fin n) (g : Fin (2*k+2)) := u i (e.symm g) have hv (i : Fin n) (g : Fin (2*k+2)) : 0 ≤ v i g := hu i _ have hsmall₀ (i : Fin n) (g : Fin (2*k)) : v i (Fin.last (2*k)).castSucc ≤ v i g.castSucc.castSucc := by apply horder i _ _ change g.val / 2 < (2*k) / 2 omega have hsmall₁ (i : Fin n) (g : Fin (2*k)) : v i (Fin.last (2*k+1)) ≤ v i g.castSucc.castSucc := by apply horder i _ _ change g.val / 2 < (2*k+1) / 2 omega have hold : ∃ σ : Fin (2*k) → Fin n, is_efx_goods (fun i g => v i g.castSucc.castSucc) σ := by apply ih · exact fun i g => hv i _ · intro i g h hgh apply horder i _ _ exact hgh obtain ⟨τ, hτ⟩ := efx_exists_of_two_universal_small_goods hn v hv hsmall₀ hsmall₁ hold refine ⟨fun g => τ (e g), ?_⟩ have hh := (is_efx_goods_equiv_goods e v τ).mpr hτ simpa only [v, e.symm_apply_apply] using hh