AFTD Auto-Formalizing Theoretical Domains

efx_exists_of_common_pair_order_even

theoremverified

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.

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

    lines 7–11

    uses Fin.elim0

      induction k with
      | zero =>
        refine ⟨fun g => Fin.elim0 g, ?_⟩
        intro i j hij g hg
        exact Fin.elim0 g
  2. 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.

    lines 12–16

    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 _
  3. 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.

    lines 17–26

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

    lines 27–33

        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
  5. 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 τ.

    line 34

    uses efx_exists_of_two_universal_small_goods

        obtain ⟨τ, hτ⟩ := efx_exists_of_two_universal_small_goods hn v hv hsmall₀ hsmall₁ hold
  6. The 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.

    lines 35–37

    uses is_efx_goods_equiv_goods

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

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