AFTD Auto-Formalizing Theoretical Domains

efx_exists_of_common_pair_order_odd

theoremverified

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`.

  1. 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.

    line 7

    uses efx_exists_of_universal_least_good

      apply efx_exists_of_universal_least_good hn u hu
  2. The 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.

    lines 8–11

      · intro i g
        apply horder i _ _
        change g.val / 2 < (2*k) / 2
        omega
  3. 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`.

    lines 12–16

    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

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
See it in the graphDiscuss this resultChallenge it