AFTD Auto-Formalizing Theoretical Domains

is_efx_goods_insert_of_unenvied_of_min

theoremverified

Adding 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 bundle; all item values are nonnegative.

Statement

theorem is_efx_goods_insert_of_unenvied_of_min {m n : ℕ} (u : Fin n → Fin (m+1) → ℝ)
    (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n)
    (hσ : is_efx_goods (fun i g => u i g.castSucc) σ) (s : Fin n)
    (hs : ∀ i, additive_valuation (fun g => u i g.castSucc) (bundle_of σ s) ≤
      additive_valuation (fun g => u i g.castSucc) (bundle_of σ i))
    (hmin : ∀ i, i ≠ s → ∀ g ∈ bundle_of σ s, u i (Fin.last m) ≤ u i g.castSucc) :
    is_efx_goods u (Fin.lastCases s σ)
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
  • additive_valuation_erase_of_memRemoving a good belonging to a finite bundle subtracts exactly its item value from the additive value of that bundle.
  • additive_valuation_bundle_last_casesAssigning the additional last good to agent s adds exactly its value to the old bundle value of s and leaves every other bundle value…
  • 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 1
  • 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…

The proof, explained

To prove that adding a good to an unenvied agent $s$ preserves the EFX property, we consider any two distinct agents $i ≠ j$ and an item $g$ in $j$'s new bundle. When the envied agent is the recipient ($j = s$), removing $g$ leaves an envied valuation bounded by $i$'s original bundle: if $g$ is the new good, it cancels out directly, and if $g$ is an old good, the new good is worth at most $g$ to agent $i$, so unenviedness of $s$ still applies. When the envied agent is someone else ($j ≠ s$), $j$'s bundle is unchanged, so $g$ must be an old good, and the original EFX property combined with nonnegativity of valuations ensures $i$ does not envy $j$.

  1. The EFX condition for agents $i ≠ j$ and good $g$ in $j$'s new bundle reduces to expressing both bundles in terms of the original bundles and the new good.

    We fix distinct agents $i ≠ j$ and a good $g$ in agent $j$'s new bundle, noting that the new allocation assigns $g$ to $j$. By `additive_valuation_erase_of_mem`, the valuation of $j$'s new bundle without $g$ is the valuation of the full bundle minus $u_i(g)$. Using `additive_valuation_bundle_last_cases`, the valuation of any agent's new bundle is their valuation of their original bundle plus the value of the new good if that agent is $s$.

    lines 10–12

    uses additive_valuation_erase_of_mem, additive_valuation_bundle_last_cases

      intro i j hij g hg
      have hg' : Fin.lastCases s σ g = j := by simpa [bundle_of] using hg
      rw [additive_valuation_erase_of_mem _ _ _ hg, additive_valuation_bundle_last_cases, additive_valuation_bundle_last_cases]
  2. When $j = s$, the condition simplifies to $u_i(B_s) + u_i(g_{\text{new}}) - u_i(g) ≤ u_i(B_i)$.

    We split on whether the envied agent $j$ is the recipient $s$. When $j = s$, distinctness of agents gives $i ≠ s$. Thus, the indicator $s = j$ evaluates to true using `if_pos` (adding $u_i(g_{\text{new}})$ to $j$'s bundle), while $s = i$ evaluates to false using `if_neg` (adding $0$ to $i$'s bundle).

    lines 13–15

    uses if_pos, if_neg

      by_cases hjs : j = s
      · have his : i ≠ s := by simpa only [hjs] using hij
        rw [hjs, if_pos rfl, if_neg his.symm]
  3. When $j = s$ and $g$ is an original good, the inequality holds.

    By `Fin.eq_castSucc_or_eq_last`, we check whether $g$ is an original good or the new good. If $g$ is an original good $a$, then $a$ belongs to $s$'s original bundle. By the minimality hypothesis `hmin`, agent $i$ values the new good no more than $a$ ($u_i(g_{\text{new}}) ≤ u_i(a)$). Furthermore, hypothesis `hs` states that agent $s$ was unenvied by $i$ ($u_i(B_s) ≤ u_i(B_i)$). Combining these two inequalities via linear arithmetic establishes that $u_i(B_s) + u_i(g_{\text{new}}) - u_i(a) ≤ u_i(B_i)$.

    lines 16–20

    uses Fin.eq_castSucc_or_eq_last

        rcases Fin.eq_castSucc_or_eq_last g with ⟨a, rfl⟩ | rfl
        · have ha : a ∈ bundle_of σ s := by simpa [bundle_of, hjs] using hg'
          have hm := hmin i his a ha
          have hh := hs i
          linarith
  4. When $j = s$ and $g$ is the new good, the inequality holds, completing the case $j = s$.

    If $g$ is the new good $g_{\text{new}}$, subtracting $u_i(g_{\text{new}})$ cancels the added good from $s$'s bundle, leaving $u_i(B_s) ≤ u_i(B_i)$. This holds directly from the assumption `hs` that $s$ was unenvied, as confirmed by `sub_le_iff_le_add.mpr` and linear arithmetic.

    line 21

    uses sub_le_iff_le_add.mpr

        · exact sub_le_iff_le_add.mpr (by linarith [hs i])
  5. When $j ≠ s$ and $g$ is an original good, the EFX inequality holds.

    When $j ≠ s$, agent $j$ did not receive the new good, so the indicator term for $j$ vanishes by `if_neg` and `Ne.symm`. We split on whether $g$ is an original good or the new good with `Fin.eq_castSucc_or_eq_last`. If $g$ is an original good $a \in B_j$, the original allocation satisfies the EFX property `hσ`, meaning $u_i(B_j) - u_i(a) ≤ u_i(B_i)$ by `additive_valuation_erase_of_mem`. Because all item values are nonnegative (`hu`), adding the new good to agent $i$'s bundle (if $i = s$) only preserves or increases the right-hand side, so linear arithmetic closes the inequality in both cases ($i = s$ and $i ≠ s$).

    lines 22–27

    uses if_neg, Ne.symm, Fin.eq_castSucc_or_eq_last, additive_valuation_erase_of_mem

      · try simp only [if_neg (Ne.symm hjs)]
        rcases Fin.eq_castSucc_or_eq_last g with ⟨a, rfl⟩ | rfl
        · have ha : a ∈ bundle_of σ j := by simpa [bundle_of] using hg'
          have hh := hσ i j hij a ha
          rw [additive_valuation_erase_of_mem _ _ _ ha] at hh
          split_ifs <;> linarith [hu i (Fin.last m)]
  6. The case where $j ≠ s$ and $g$ is the new good is impossible, completing the proof.

    If $g$ were the new good, then because the new good is assigned to $s$ by `Fin.lastCases_last`, $g$ belonging to $j$'s bundle forces $s = j$. This directly contradicts $j ≠ s$, eliminating the branch.

    lines 28–29

    uses Fin.lastCases_last

        · simp only [Fin.lastCases_last] at hg'
          exact (hjs hg'.symm).elim
additive_valuation_erase_of_mem
The additive valuation of a set with an element $g$ removed is the valuation of the set minus the valuation of $g$.
additive_valuation_bundle_last_cases
Under an allocation where an extra good is given to agent $s$, the valuation of agent $j$'s bundle equals the valuation of $j$'s original bundle plus the value of the new good if $s = j$ (and $0$ otherwise).
if_pos
If a condition $c$ holds, then `if c then t else e` reduces to $t$.
if_neg
If a condition $c$ does not hold, then `if c then t else e` reduces to $e$.
Fin.eq_castSucc_or_eq_last
Every element of `Fin (n + 1)` is either the embedding of an element of `Fin n` (an original good) or the last element (the new good).
sub_le_iff_le_add.mpr
If $a ≤ b + c$, then $a - c ≤ b$.
Ne.symm
Inequality is symmetric: if $a ≠ b$, then $b ≠ a$.
Fin.lastCases_last
Evaluating `Fin.lastCases` at the last element returns the value designated for the last element.

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 is_efx_goods_insert_of_unenvied_of_min {m n : ℕ} (u : Fin n → Fin (m+1) → ℝ)    (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n)    (hσ : is_efx_goods (fun i g => u i g.castSucc) σ) (s : Fin n)    (hs : ∀ i, additive_valuation (fun g => u i g.castSucc) (bundle_of σ s) ≤      additive_valuation (fun g => u i g.castSucc) (bundle_of σ i))    (hmin : ∀ i, i ≠ s → ∀ g ∈ bundle_of σ s, u i (Fin.last m) ≤ u i g.castSucc) :    is_efx_goods u (Fin.lastCases s σ) := by  intro i j hij g hg  have hg' : Fin.lastCases s σ g = j := by simpa [bundle_of] using hg  rw [additive_valuation_erase_of_mem _ _ _ hg, additive_valuation_bundle_last_cases, additive_valuation_bundle_last_cases]  by_cases hjs : j = s  · have his : i ≠ s := by simpa only [hjs] using hij    rw [hjs, if_pos rfl, if_neg his.symm]    rcases Fin.eq_castSucc_or_eq_last g with ⟨a, rfl⟩ | rfl    · have ha : a ∈ bundle_of σ s := by simpa [bundle_of, hjs] using hg'      have hm := hmin i his a ha      have hh := hs i      linarith    · exact sub_le_iff_le_add.mpr (by linarith [hs i])  · try simp only [if_neg (Ne.symm hjs)]    rcases Fin.eq_castSucc_or_eq_last g with ⟨a, rfl⟩ | rfl    · have ha : a ∈ bundle_of σ j := by simpa [bundle_of] using hg'      have hh := hσ i j hij a ha      rw [additive_valuation_erase_of_mem _ _ _ ha] at hh      split_ifs <;> linarith [hu i (Fin.last m)]    · simp only [Fin.lastCases_last] at hg'      exact (hjs hg'.symm).elim
See it in the graphDiscuss this resultChallenge it