AFTD Auto-Formalizing Theoretical Domains

efx_exists_of_null_last_good

theoremverified

For a positive number of agents and nonnegative additive values, a good worth zero to every agent can be added while retaining existence of a complete EFX allocation, with rearrangement allowed.

Statement

theorem efx_exists_of_null_last_good {m n : ℕ} (hn : 0 < n)
    (u : Fin n → Fin (m+1) → ℝ) (hu : ∀ i g, 0 ≤ u i g)
    (hzero : ∀ i, u i (Fin.last m) = 0)
    (h : ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g.castSucc) σ) :
    ∃ τ : Fin (m+1) → Fin n, is_efx_goods u τ
Source
Helper for efx_four_agents_additive_exists (OP-7), campaign session IN-404, 2026-11-01. Standard cycle elimination and ordered insertion, arXiv:1707.04769v3 Lemma 6.1 and Appendix B; no novelty claim.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • 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 reduces the goal to `efx_exists_of_universal_least_good`, which ensures that an EFX allocation on $m$ goods extends to $m+1$ goods whenever the additional good is valued weakly less than every existing good by all agents. Because valuations are nonnegative and the added good is valued at zero by all agents, it trivially satisfies this minimum-value condition.

  1. It suffices to show that the additional good is valued weakly less than each of the first $m$ goods by every agent.

    By `efx_exists_of_universal_least_good`, an EFX allocation on $m$ goods can be extended to an allocation on $m + 1$ goods provided the new good is weakly dominated in value by all existing goods for all agents.

    line 8

    uses efx_exists_of_universal_least_good

      apply efx_exists_of_universal_least_good hn u hu _ h
  2. The additional good is valued at most as much as any of the first $m$ goods for every agent.

    Fix an agent $i$ and any of the first $m$ goods $g$. By assumption (`hzero`), the value of the $(m+1)$-th good to agent $i$ is $0$. Since valuations are nonnegative by hypothesis (`hu`), agent $i$'s valuation for good $g$ is at least $0$, satisfying the condition $0 \le u(i, g)$.

    lines 9–11

      intro i g
      rw [hzero i]
      exact hu i g.castSucc
efx_exists_of_universal_least_good
An EFX allocation can be extended to an additional good if that good is valued weakly less than every existing good by all agents.

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_null_last_good {m n : ℕ} (hn : 0 < n)    (u : Fin n → Fin (m+1) → ℝ) (hu : ∀ i g, 0 ≤ u i g)    (hzero : ∀ i, u i (Fin.last m) = 0)    (h : ∃ σ : Fin m → Fin n, is_efx_goods (fun i g => u i g.castSucc) σ) :    ∃ τ : Fin (m+1) → Fin n, is_efx_goods u τ := by  apply efx_exists_of_universal_least_good hn u hu _ h  intro i g  rw [hzero i]  exact hu i g.castSucc
See it in the graphDiscuss this resultChallenge it