is_efx_goods_insert_of_unenvied_of_min
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$.
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$.
uses
additive_valuation_erase_of_mem,additive_valuation_bundle_last_casesintro 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]
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).
uses
if_pos,if_negby_cases hjs : j = s · have his : i ≠ s := by simpa only [hjs] using hij rw [hjs, if_pos rfl, if_neg his.symm]
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)$.
uses
Fin.eq_castSucc_or_eq_lastrcases 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
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.
uses
sub_le_iff_le_add.mpr· exact sub_le_iff_le_add.mpr (by linarith [hs i])
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$).
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)]
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.
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.
- In the formalization, goods are indexed by `Fin (m+1)`. The original goods correspond to `g.castSucc` (for `g : Fin m`), and the newly added good is `Fin.last m`. The allocation after insertion is defined using `Fin.lastCases s σ`, which assigns `Fin.last m` to agent `s` and delegates all other goods to `σ`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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