efx_exists_of_common_pair_order
For any finite number m of goods, any positive number n of agents, and nonnegative real additive values, suppose for every agent and goods g,h, floor(g.index/2) < floor(h.index/2) implies that the value of h is at most the value of g. A complete EFX allocation exists. Thus all agents agree on the order of consecutive blocks of at most two goods, but can disagree on comparisons within each pair.
Statement
theorem efx_exists_of_common_pair_order (m n : ℕ) (hn : 0 < n)
(u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g)
(horder : ∀ (i : Fin n) (g h : Fin m), g.val / 2 < h.val / 2 → u i h ≤ u i g) :
∃ σ : Fin m → 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 3
- 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…
- 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…
- 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 proceeds by parity case analysis on the number of goods m. Using integer division by 2, m is classified as either even (m = 2k) or odd (m = 2k + 1). The existence of an EFX allocation then follows in each case by invoking the specialized theorems `efx_exists_of_common_pair_order_even` and `efx_exists_of_common_pair_order_odd`.
The number of goods m is either even (m = 2k) or odd (m = 2k + 1) for some natural number k.
We perform a case split on whether m % 2 = 0. If m is divisible by 2, setting k = m / 2 gives m = 2k, yielding the left disjunct via `Or.inl`. Otherwise, m % 2 ≠ 0, so setting k = m / 2 gives m = 2k + 1, yielding the right disjunct via `Or.inr`. Both division identities are verified by linear integer arithmetic (`omega`).
uses
Or.inl,Or.inrhave hex : (∃ k, m = 2*k) ∨ (∃ k, m = 2*k+1) := by by_cases hm : m % 2 = 0 · exact Or.inl ⟨m / 2, by omega⟩ · exact Or.inr ⟨m / 2, by omega⟩
An EFX allocation exists in both parity cases, completing the proof.
We destruct the parity disjunction on m. In the even branch where m = 2k, the existence of an EFX allocation follows directly from `efx_exists_of_common_pair_order_even`. In the odd branch where m = 2k + 1, the result follows directly from `efx_exists_of_common_pair_order_odd`.
uses
efx_exists_of_common_pair_order_even,efx_exists_of_common_pair_order_oddrcases hex with ⟨k, rfl⟩ | ⟨k, rfl⟩ · exact efx_exists_of_common_pair_order_even k n hn u hu horder · exact efx_exists_of_common_pair_order_odd k n hn u hu horder
Or.inl- Given a proof of the left disjunct, produces a proof of the disjunction `a ∨ b`.
Or.inr- Given a proof of the right disjunct, produces a proof of the disjunction `a ∨ b`.
efx_exists_of_common_pair_order_even- For any positive number of agents and any even number of goods 2k, if agents have non-negative additive valuations and agree on the ordering of consecutive pairs of goods, then an EFX allocation exists.
efx_exists_of_common_pair_order_odd- For any positive number of agents and any odd number of goods 2k + 1, if agents have non-negative additive valuations and agree on the ordering of consecutive pairs of goods, then an EFX allocation exists.
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 (m n : ℕ) (hn : 0 < n) (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) (horder : ∀ (i : Fin n) (g h : Fin m), g.val / 2 < h.val / 2 → u i h ≤ u i g) : ∃ σ : Fin m → Fin n, is_efx_goods u σ := by have hex : (∃ k, m = 2*k) ∨ (∃ k, m = 2*k+1) := by by_cases hm : m % 2 = 0 · exact Or.inl ⟨m / 2, by omega⟩ · exact Or.inr ⟨m / 2, by omega⟩ rcases hex with ⟨k, rfl⟩ | ⟨k, rfl⟩ · exact efx_exists_of_common_pair_order_even k n hn u hu horder · exact efx_exists_of_common_pair_order_odd k n hn u hu horder