efx_exists_of_common_pair_order_odd
For any positive number of agents and 2k+1 nonnegative additive goods, suppose every agent weakly prefers goods with smaller floor(index/2) to those with larger floor(index/2), with no required order within a pair. A complete EFX allocation exists; the last block is a singleton.
Statement
theorem efx_exists_of_common_pair_order_odd (k n : ℕ) (hn : 0 < n)
(u : Fin n → Fin (2*k+1) → ℝ) (hu : ∀ i g, 0 ≤ u i g)
(horder : ∀ (i : Fin n) (g h : Fin (2*k+1)), g.val / 2 < h.val / 2 → u i h ≤ u i g) :
∃ σ : Fin (2*k+1) → 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_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…
- 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…
- 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…
- Used by 1
- 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 reduces the case of 2k+1 goods to 2k goods by showing that the final good (index 2k) is universally least-preferred. Because every earlier good g < 2k satisfies ⌊g/2⌋ < k = ⌊2k/2⌋, the common pair-order assumption ensures every agent weakly prefers any earlier good to the last good. By `efx_exists_of_universal_least_good`, it suffices to find an EFX allocation for the first 2k goods, which is supplied directly by `efx_exists_of_common_pair_order_even`.
It suffices to show that the last good is universally weakly least-preferred and that an EFX allocation exists for the first 2k goods.
Applying `efx_exists_of_universal_least_good` reduces finding an EFX allocation for 2k+1 goods to finding one for the first 2k goods, provided that the last good (index 2k, represented by `Fin.last (2*k)`) is weakly least-preferred by every agent compared to any of the first 2k goods.
uses
efx_exists_of_universal_least_goodapply efx_exists_of_universal_least_good hn u huThe last good is universally weakly least-preferred by every agent compared to all preceding goods.
Fixing an agent i and any good g < 2k, the pair index satisfies g / 2 < (2k) / 2 = k by integer division, closed by `omega`. The pair-order hypothesis `horder` then guarantees that agent i values good g at least as much as good 2k.
· intro i g apply horder i _ _ change g.val / 2 < (2*k) / 2 omega
An EFX allocation exists for the first 2k goods.
We apply `efx_exists_of_common_pair_order_even` to the restriction of the utilities to the first 2k goods. Nonnegativity holds immediately from the original nonnegativity assumption `hu`, and the pair-order condition on the first 2k goods is inherited directly from `horder`.
uses
efx_exists_of_common_pair_order_even· apply efx_exists_of_common_pair_order_even k n hn · exact fun i g => hu i _ · intro i g h hgh apply horder i _ _ exact hgh
efx_exists_of_universal_least_good- If utilities are nonnegative and the last good is weakly least-preferred by every agent compared to every other good, then the existence of an EFX allocation for the first m goods implies the existence of an EFX allocation for all m+1 goods.
efx_exists_of_common_pair_order_even- An EFX allocation exists for any positive number of agents and 2k nonnegative additive goods whenever all agents weakly prefer goods with smaller ⌊index/2⌋ to those with larger ⌊index/2⌋.
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_odd (k n : ℕ) (hn : 0 < n) (u : Fin n → Fin (2*k+1) → ℝ) (hu : ∀ i g, 0 ≤ u i g) (horder : ∀ (i : Fin n) (g h : Fin (2*k+1)), g.val / 2 < h.val / 2 → u i h ≤ u i g) : ∃ σ : Fin (2*k+1) → Fin n, is_efx_goods u σ := by apply efx_exists_of_universal_least_good hn u hu · intro i g apply horder i _ _ change g.val / 2 < (2*k) / 2 omega · apply efx_exists_of_common_pair_order_even k n hn · exact fun i g => hu i _ · intro i g h hgh apply horder i _ _ exact hgh