AFTD Auto-Formalizing Theoretical Domains

efx_exists_of_two_universal_small_goods

theoremverified

For a positive number of agents with nonnegative real additive values, suppose each of the last two goods is weakly less valuable to every agent than each old good, and a complete EFX allocation of the old goods exists. Then a complete EFX allocation including both new goods exists.

Statement

theorem efx_exists_of_two_universal_small_goods {m n : ℕ} (hn : 0 < n)
    (u : Fin n → Fin (m+2) → ℝ) (hu : ∀ i g, 0 ≤ u i g)
    (hsmall₀ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last m).castSucc ≤ u i g.castSucc.castSucc)
    (hsmall₁ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last (m+1)) ≤ u i g.castSucc.castSucc)
    (h : ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g.castSucc.castSucc) σ) :
    ∃ τ : Fin (m+2) → Fin n, is_efx_goods u τ
Source
Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • efx_exists_of_two_universal_small_goods_irLet m and n be natural numbers with n positive. There are m+2 goods with nonnegative real additive values for n agents. Each agent values…
  • 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…
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • 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.
Used by 1

The proof, explained

The theorem reduces directly to a companion result, efx_exists_of_two_universal_small_goods_ir. From the existential hypothesis, we extract an initial EFX allocation σ of the first m goods. Applying the companion theorem to σ produces an extended allocation τ for all m+2 goods that is EFX, which immediately witnesses the existential claim.

  1. We fix a complete EFX allocation σ for the initial m goods.

    By the hypothesis h, there exists an allocation of the initial m goods that is EFX under the agents' valuations restricted to those goods. We choose such an allocation σ along with the certificate hσ that it is EFX.

    line 9

      obtain ⟨σ, hσ⟩ := h
  2. An allocation τ for all m+2 goods is constructed and certified to be EFX, witnessing the goal.

    We apply the companion theorem efx_exists_of_two_universal_small_goods_ir to σ and hσ. This theorem extends σ to an allocation τ of all m+2 goods that remains EFX (and also preserves bundles and guarantees weak utility improvements). Providing τ and its EFX certificate completes the existential proof.

    lines 10–11

    uses efx_exists_of_two_universal_small_goods_ir

      obtain ⟨τ, hτ, _, _⟩ := efx_exists_of_two_universal_small_goods_ir hn u hu hsmall₀ hsmall₁ σ hσ
      exact ⟨τ, hτ⟩
efx_exists_of_two_universal_small_goods_ir
If n > 0 agents have nonnegative additive valuations and two additional goods are each universally weakly less valuable than any of the first m goods, then any complete EFX allocation of the first m goods can be extended to a complete EFX allocation of all m+2 goods that weakly increases each agent's valuation and keeps together goods previously allocated to the same agent.

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_two_universal_small_goods {m n : ℕ} (hn : 0 < n)    (u : Fin n → Fin (m+2) → ℝ) (hu : ∀ i g, 0 ≤ u i g)    (hsmall₀ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last m).castSucc ≤ u i g.castSucc.castSucc)    (hsmall₁ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last (m+1)) ≤ u i g.castSucc.castSucc)    (h : ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g.castSucc.castSucc) σ) :    ∃ τ : Fin (m+2) → Fin n, is_efx_goods u τ := by  obtain ⟨σ, hσ⟩ := h  obtain ⟨τ, hτ, _, _⟩ := efx_exists_of_two_universal_small_goods_ir hn u hu hsmall₀ hsmall₁ σ hσ  exact ⟨τ, hτ⟩
See it in the graphDiscuss this resultChallenge it