AFTD Auto-Formalizing Theoretical Domains

efx_exists_of_universal_least_good

theoremverified

For a positive number of agents and nonnegative additive values, if the last good is weakly least valuable for every agent, existence of EFX without it implies existence of EFX with it.

Statement

theorem efx_exists_of_universal_least_good {m n : ℕ} (hn : 0 < n)
    (u : Fin n → Fin (m+1) → ℝ) (hu : ∀ i g, 0 ≤ u i g)
    (hmin : ∀ (i : Fin n) (g : Fin m), u i (Fin.last m) ≤ u i g.castSucc)
    (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 5
  • is_efx_goods_insert_of_unenvied_of_minAdding a good to an unenvied agent preserves EFX if every other agent values the new good no more than every old good in that recipient's…
  • is_efx_goods_exists_unenviedFor a positive number of agents, any EFX allocation of nonnegative additive goods can be changed to another EFX allocation that weakly…
  • 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_null_last_goodFor a positive number of agents and nonnegative additive values, a good worth zero to every agent can be added while retaining existence…

The proof, explained

To extend an EFX allocation of $m$ goods to an additional good that is universally least valuable, we first obtain an EFX allocation of the first $m$ goods under which some agent $s$ is unenvied by all agents. We then assign the new good to agent $s$. Because $s$ was previously unenvied and the new good is weakly least valuable among all goods for every agent, the resulting allocation of all $m+1$ goods remains EFX.

  1. There exists an EFX allocation $\tau$ of the first $m$ goods under which some agent $s$ is unenvied by everyone.

    From the assumption that an EFX allocation of the first $m$ goods exists ($h$), let $\sigma$ be such an allocation. By `is_efx_goods_exists_unenvied`, there exists an EFX allocation $\tau$ of the first $m$ goods and an agent $s$ such that every agent $i$ weakly prefers their own bundle to $s$'s bundle.

    lines 8–10

    uses is_efx_goods_exists_unenvied

      obtain ⟨σ, hσ⟩ := h
      obtain ⟨τ, hτ, _, s, hs⟩ := is_efx_goods_exists_unenvied hn
        (fun i g => u i g.castSucc) (fun i g => hu i g.castSucc) σ hσ
  2. The allocation extending $\tau$ by assigning the last good to agent $s$ is an EFX allocation of all $m+1$ goods.

    We extend $\tau$ to all $m+1$ goods via `Fin.lastCases s τ`, assigning the last good to the unenvied agent $s$ and all other goods according to $\tau$. By `is_efx_goods_insert_of_unenvied_of_min`, adding a good to an unenvied agent preserves the EFX condition whenever every other agent values the new good weakly less than each item in $s$'s bundle. This condition is satisfied because the last good is assumed to be weakly least valuable among all goods for every agent ($hmin$).

    line 11

    uses Fin.lastCases, is_efx_goods_insert_of_unenvied_of_min

      exact ⟨Fin.lastCases s τ, is_efx_goods_insert_of_unenvied_of_min u hu τ hτ s hs (fun i _ g _ => hmin i g)⟩
is_efx_goods_exists_unenvied
For any positive number of agents and nonnegative additive valuations, given an EFX allocation of goods, there exists an EFX allocation under which some agent $s$ is unenvied by all agents.
is_efx_goods_insert_of_unenvied_of_min
Given an EFX allocation of $m$ goods with an unenvied agent $s$, assigning an additional good to $s$ produces an EFX allocation of all $m+1$ goods, provided every other agent values the new good weakly less than every good in $s$'s bundle.
Fin.lastCases
Constructs a function on `Fin (m + 1)` by specifying its value at the last element `Fin.last m` and its values on the initial $m$ elements.

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_universal_least_good {m n : ℕ} (hn : 0 < n)    (u : Fin n → Fin (m+1) → ℝ) (hu : ∀ i g, 0 ≤ u i g)    (hmin : ∀ (i : Fin n) (g : Fin m), u i (Fin.last m) ≤ u i g.castSucc)    (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  obtain ⟨σ, hσ⟩ := h  obtain ⟨τ, hτ, _, s, hs⟩ := is_efx_goods_exists_unenvied hn    (fun i g => u i g.castSucc) (fun i g => hu i g.castSucc) σ hσ  exact ⟨Fin.lastCases s τ, is_efx_goods_insert_of_unenvied_of_min u hu τ hτ s hs (fun i _ g _ => hmin i g)⟩
See it in the graphDiscuss this resultChallenge it