efx_exists_of_two_universal_small_goods_ir
Let 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 each of the last two goods no more than every one of the first m goods, with no required order between the last two. Given any complete EFX allocation of the first m goods, there exists a complete EFX allocation of all m+2 goods in which every agent has at least her original utility and any two old goods originally allocated together are still allocated together, possibly to a different agent. EFX tests deletion of every good, including a zero-valued one.
Statement
theorem efx_exists_of_two_universal_small_goods_ir {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) (σ : Fin m → Fin n) (hσ : is_efx_goods (fun i g => u i g.castSucc.castSucc) σ) : ∃ τ : Fin (m+2) → Fin n, is_efx_goods u τ ∧ (∀ i, additive_valuation (fun g : Fin m => u i g.castSucc.castSucc) (bundle_of σ i) ≤ additive_valuation (u i) (bundle_of τ i)) ∧ (∀ g h : Fin m, σ g = σ h → τ g.castSucc.castSucc = τ h.castSucc.castSucc)
- Related work
- Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01. The baseline is universally least-good insertion for a common individual ranking in arXiv:1707.04769v3 Appendix B. Here the two new goods need not have a common order. Web searches on 2026-11-01 for two smallest goods, ordered pairs, common pair order, and EFX completion found no matching result; arXiv:2504.03951 concerns n+2 goods and does not supply this arbitrary-old-allocation preservation statement. This does not settle unrestricted four-agent EFX.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- additive_valuation_erase_of_memRemoving a good belonging to a finite bundle subtracts exactly its item value from the additive value of that bundle.
- bundle_of_permute_agentsReassigning every good by the inverse of an agent permutation makes the bundle of agent i equal to the old bundle of the permuted agent.
- is_efx_goods_all_pairsFor nonnegative additive values, the EFX inequalities also hold when the observer and the target agent coincide.
- 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…
- finite_two_bonus_ordered_assignmentFor any finite nonempty real matrix w and two nonnegative agent-dependent bonuses a and b, there is a permutation of the old columns, a…
- 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_two_universal_small_goodsFor a positive number of agents with nonnegative real additive values, suppose each of the last two goods is weakly less valuable to every…
Read back from the Lean
For any natural numbers $m$ and $n$ with $0 < n$, any valuation profile $u : \text{Fin } n \to \text{Fin } (m+2) \to \mathbb{R}$ such that:
1. $u$ is non-negative everywhere ($0 \le u(i, g)$ for all $i, g$);
2. the item at index $m$ (represented by (Fin.last m).castSucc) is weakly less valued by every agent $i$ than any of the first $m$ items (represented by g.castSucc.castSucc for $g : \text{Fin } m$);
3. the item at index $m+1$ (represented by Fin.last (m+1)) is weakly less valued by every agent $i$ than any of the first $m$ items;
and for any allocation $\sigma : \text{Fin } m \to \text{Fin } n$ of the first $m$ items that is EFX for goods under the valuations restricted to the first $m$ items:
there exists an allocation $\tau : \text{Fin } (m+2) \to \text{Fin } n$ of all $m+2$ items such that:
1. $\tau$ is EFX for goods under $u$;
2. every agent $i$ values their bundle under $\tau$ (under $u(i)$) at least as much as they valued their bundle under $\sigma$ (under the restricted valuation);
3. any two items $g, h \in \text{Fin } m$ that were assigned to the same agent under $\sigma$ remain assigned to the same agent under $\tau$ (i.e., $\sigma(g) = \sigma(h) \implies \tau(g) = \tau(h)$ after embedding into $\text{Fin } (m+2)$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof extends an existing EFX allocation σ of m goods to all m + 2 goods by reducing the extension to an assignment problem with two bonus goods. Applying the lemma finite_two_bonus_ordered_assignment yields a permutation p of the original bundles and two designated bonus recipients r and s such that each agent weakly improves their utility and non-envy holds whenever a bonus good is trimmed. In the resulting allocation τ, any removed item g is either one of the bonus goods (satisfying EFX by the assignment lemma) or an original good, in which case removing g reduces envy at least as much as trimming a bonus good (by universal smallness) or reduces to the original EFX allocation (if the bundle contains no bonus goods). Bundles from σ are preserved intact because the permutation reassigns each original bundle as an indivisible unit.
There exist a permutation p of the agents and recipients r, s for the two bonus goods satisfying individual rationality and non-envy upon removing each bonus good.
We define w(i, j) as agent i's valuation of bundle j under the initial allocation σ, and a(i), b(i) as agent i's valuations of the two additional goods (at indices m and m + 1). Since n > 0, the agent type is nonempty. Applying finite_two_bonus_ordered_assignment to w, a, and b yields a permutation p of the agents and two recipients r and s such that each agent weakly prefers their assigned package to their initial bundle (hI), and removing bonus good a from agent r or bonus good b from agent s guarantees no other agent envies them (hA, hB).
uses
Nat.ne_of_gt,finite_two_bonus_ordered_assignmentclassical letI : NeZero n := ⟨Nat.ne_of_gt hn⟩ let w (i j : Fin n) := additive_valuation (fun g : Fin m => u i g.castSucc.castSucc) (bundle_of σ j) let a (i : Fin n) := u i (Fin.last m).castSucc let b (i : Fin n) := u i (Fin.last (m+1)) obtain ⟨p, r, s, hI, hA, hB⟩ := finite_two_bonus_ordered_assignment w a b (fun i => hu i _) (fun i => hu i _)
Define the new allocation τ of all m + 2 goods.
We define τ₀ on the original m goods by giving agent j the original bundle σ(p(j)), so that τ₀(g) = p⁻¹(σ(g)). We then extend τ₀ to τ₁ on m + 1 goods by assigning the first bonus good (at index m) to recipient r, and finally extend τ₁ to τ on all m + 2 goods by assigning the second bonus good (at index m + 1) to recipient s.
let τ₀ : Fin m → Fin n := fun g => p.symm (σ g) let τ₁ : Fin (m+1) → Fin n := Fin.lastCases r τ₀ let τ : Fin (m+2) → Fin n := Fin.lastCases s τ₁
Under τ, agent i's valuation of agent j's bundle is w(i, p(j)) + (if j = r then a(i) else 0) + (if j = s then b(i) else 0).
By unfolding the recursive definition of τ and applying additive_valuation_bundle_last_cases twice for the two extra goods, followed by bundle_of_permute_agents for the permuted original allocation, agent j's bundle decomposes into the original bundle p(j) plus bonus good a if j = r and bonus good b if j = s.
uses
additive_valuation_bundle_last_cases,bundle_of_permute_agents,eq_commhave hval (i j : Fin n) : additive_valuation (u i) (bundle_of τ j) = w i (p j) + (if j = r then a i else 0) + (if j = s then b i else 0) := by dsimp [τ, τ₁, τ₀] rw [additive_valuation_bundle_last_cases, additive_valuation_bundle_last_cases, bundle_of_permute_agents] simp only [w, a, b, eq_comm]
Each agent i achieves at least their initial utility under σ: w(i, i) ≤ u_i(bundle_of τ i).
Rewriting the assignment guarantee hI with the valuation formula hval shows that agent i's utility under τ is at least their utility under σ.
have hown (i : Fin n) : w i i ≤ additive_valuation (u i) (bundle_of τ i) := by simpa only [hval] using hI i
Removing the first bonus good from agent r's bundle prevents any agent i ≠ r from envying r.
Rewriting the condition hA using the bundle valuation formula hval and simplifying the conditionals when j = r, linear arithmetic establishes that agent i's valuation of bundle r minus a(i) is at most their valuation of their own bundle.
uses
ite_truehave htrim₀ (i : Fin n) (hi : i ≠ r) : additive_valuation (u i) (bundle_of τ r) - a i ≤ additive_valuation (u i) (bundle_of τ i) := by have hh := hA i hi rw [hval, hval] simp only [ite_true] linarith
Removing the second bonus good from agent s's bundle prevents any agent i ≠ s from envying s.
Similarly, rewriting the condition hB using hval and simplifying the conditionals when j = s shows by linear arithmetic that agent i's valuation of bundle s minus b(i) is at most their valuation of their own bundle.
uses
ite_truehave htrim₁ (i : Fin n) (hi : i ≠ s) : additive_valuation (u i) (bundle_of τ s) - b i ≤ additive_valuation (u i) (bundle_of τ i) := by have hh := hB i hi rw [hval, hval] simp only [ite_true] linarith
It suffices to show that τ is EFX, satisfies individual rationality, and preserves original bundles.
We provide τ as the witness for the existential quantifier, splitting the theorem into three subgoals: the EFX property of τ, the preservation of each agent's utility, and the bundle integrity condition.
refine ⟨τ, ?_, ?_, ?_⟩To verify EFX, for any distinct agents i ≠ j and any good g in bundle j, it suffices to show u_i(bundle_of τ j) - u_i(g) ≤ u_i(bundle_of τ i).
Assuming i ≠ j and g is allocated to j under τ, additive_valuation_erase_of_mem rewrites the valuation of bundle j with g removed as the total valuation of bundle j minus u_i(g).
uses
additive_valuation_erase_of_mem· intro i j hij g hg have hg' : τ g = j := by simpa [bundle_of] using hg rw [additive_valuation_erase_of_mem _ _ _ hg]
The EFX condition holds when g is an original good and j = r.
Using Fin.eq_castSucc_or_eq_last twice, we split on whether g is an original good or one of the two bonus goods. If g is an original good and j = r, agent i ≠ r does not envy r upon removing a(i) by htrim₀. Since g is an original good, the universal smallness hypothesis hsmall₀ gives a(i) ≤ u_i(g), so removing g reduces the bundle value by at least a(i), which leaves no envy by linear arithmetic.
uses
Fin.eq_castSucc_or_eq_lastrcases Fin.eq_castSucc_or_eq_last g with ⟨g₁, rfl⟩ | rfl · rcases Fin.eq_castSucc_or_eq_last g₁ with ⟨g₀, rfl⟩ | rfl · by_cases hjr : j = r · have hi : i ≠ r := by simpa only [hjr] using hij rw [hjr] have hh := htrim₀ i hi have hl := hsmall₀ i g₀ change a i ≤ u i g₀.castSucc.castSucc at hl linarith
The EFX condition holds when g is an original good and j = s (with j ≠ r).
If j = s, agent i ≠ s does not envy s upon removing b(i) by htrim₁. By the universal smallness hypothesis hsmall₁, b(i) ≤ u_i(g), so removing g removes at least b(i), eliminating envy by linear arithmetic.
· by_cases hjs : j = s · have hi : i ≠ s := by simpa only [hjs] using hij rw [hjs] have hh := htrim₁ i hi have hl := hsmall₁ i g₀ change b i ≤ u i g₀.castSucc.castSucc at hl linarith
The EFX condition holds when g is an original good and j receives no bonus goods (j ≠ r and j ≠ s).
When j ≠ r and j ≠ s, bundle j under τ contains only original goods from bundle p(j), so g belongs to bundle σ(p(j)) via Equiv.symm_apply_eq. Since the original allocation σ was EFX, is_efx_goods_all_pairs and additive_valuation_erase_of_mem imply that removing g leaves at most w(i, i). Since bundle j has no bonus goods, its value is exactly w(i, p(j)), and by individual rationality (hown), w(i, i) ≤ u_i(bundle_of τ i), completing the inequality.
uses
Equiv.symm_apply_eq,is_efx_goods_all_pairs,additive_valuation_erase_of_mem,if_neg,add_zero· have hold : g₀ ∈ bundle_of σ (p j) := by simpa [τ, τ₁, τ₀, bundle_of, Equiv.symm_apply_eq] using hg' have hh := is_efx_goods_all_pairs (fun i (g : Fin m) => u i g.castSucc.castSucc) (fun i g => hu i _) σ hσ i (p j) g₀ hold rw [additive_valuation_erase_of_mem _ _ _ hold] at hh change w i (p j) - u i g₀.castSucc.castSucc ≤ w i i at hh rw [hval] simp only [if_neg hjr, if_neg hjs, add_zero] exact hh.trans (hown i)
The EFX condition holds when g is the first bonus good.
Because the first bonus good was given to r, its owner j must be r, so i ≠ r. Removing this good leaves bundle r trimmed by a(i), which is bounded by agent i's bundle value by htrim₀.
· have howner : r = j := by simpa [τ, τ₁, τ₀] using hg' have hi : i ≠ r := by simpa only [← howner] using hij rw [← howner] exact htrim₀ i hi
The EFX condition holds when g is the second bonus good.
Because the second bonus good was given to s, its owner j must be s, so i ≠ s. Removing this good leaves bundle s trimmed by b(i), which is bounded by agent i's bundle value by htrim₁.
· have howner : s = j := by simpa [τ] using hg' have hi : i ≠ s := by simpa only [← howner] using hij rw [← howner] exact htrim₁ i hi
Each agent i has utility under τ at least their utility under σ.
This is the individual rationality guarantee hown proved earlier from hI.
· intro i exact hown i
Any two original goods allocated together under σ remain allocated together under τ.
Original goods are assigned by τ according to τ₀ = p⁻¹ ∘ σ. If σ(g) = σ(h), then τ(g) = p⁻¹(σ(g)) = p⁻¹(σ(h)) = τ(h), which simp verifies by unfolding definitions.
· intro g h hgh simp [τ, τ₁, τ₀, hgh]
Nat.ne_of_gt- If b < a for natural numbers, then a ≠ b.
finite_two_bonus_ordered_assignment- Given an n × n matrix of valuations and nonnegative valuations for two bonus goods, there exists a permutation of the n agents and two bonus recipients such that each agent weakly prefers their assigned bundle to their initial bundle, and no agent envies either recipient once that recipient's bonus good is removed.
additive_valuation_bundle_last_cases- The additive valuation of a bundle extended by a new item assigned to agent s is the valuation of the unextended bundle plus the value of the new item if s is the owner.
bundle_of_permute_agents- Permuting agents by p assigns to agent i the bundle that was originally allocated to agent p(i).
eq_comm- Equality is symmetric: a = b is equivalent to b = a.
ite_true- An if-then-else expression with a true condition evaluates to the 'then' branch.
Fin.eq_castSucc_or_eq_last- Every element of Fin (n + 1) is either the canonical embedding of an element of Fin n or the last element Fin.last n.
Equiv.symm_apply_eq- For an equivalence e, applying the inverse e.symm to x equals y if and only if x equals e(y).
is_efx_goods_all_pairs- In an EFX allocation with nonnegative valuations, removing any good from agent j's bundle leaves agent i valuing it no more than i's own bundle, even when i = j.
additive_valuation_erase_of_mem- For an additive valuation, removing an item g from a finite set S subtracts the value of g from the total valuation of S.
if_neg- An if-then-else expression with a false condition evaluates to the 'else' branch.
add_zero- Adding zero to an element leaves it unchanged.
- The formalization represents allocations as functions from Fin (m + 2) to Fin n, using Fin.castSucc and Fin.last to distinguish original goods from the two newly appended bonus goods.
- In steps 5, 6, 9, and 10, the linarith tactic verifies linear inequalities over ℝ by combining the bonus-trimming bounds with the assumption that bonus goods are universally smaller than original goods.
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 efx_exists_of_two_universal_small_goods_ir {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) (σ : Fin m → Fin n) (hσ : is_efx_goods (fun i g => u i g.castSucc.castSucc) σ) : ∃ τ : Fin (m+2) → Fin n, is_efx_goods u τ ∧ (∀ i, additive_valuation (fun g : Fin m => u i g.castSucc.castSucc) (bundle_of σ i) ≤ additive_valuation (u i) (bundle_of τ i)) ∧ (∀ g h : Fin m, σ g = σ h → τ g.castSucc.castSucc = τ h.castSucc.castSucc) := by classical letI : NeZero n := ⟨Nat.ne_of_gt hn⟩ let w (i j : Fin n) := additive_valuation (fun g : Fin m => u i g.castSucc.castSucc) (bundle_of σ j) let a (i : Fin n) := u i (Fin.last m).castSucc let b (i : Fin n) := u i (Fin.last (m+1)) obtain ⟨p, r, s, hI, hA, hB⟩ := finite_two_bonus_ordered_assignment w a b (fun i => hu i _) (fun i => hu i _) let τ₀ : Fin m → Fin n := fun g => p.symm (σ g) let τ₁ : Fin (m+1) → Fin n := Fin.lastCases r τ₀ let τ : Fin (m+2) → Fin n := Fin.lastCases s τ₁ have hval (i j : Fin n) : additive_valuation (u i) (bundle_of τ j) = w i (p j) + (if j = r then a i else 0) + (if j = s then b i else 0) := by dsimp [τ, τ₁, τ₀] rw [additive_valuation_bundle_last_cases, additive_valuation_bundle_last_cases, bundle_of_permute_agents] simp only [w, a, b, eq_comm] have hown (i : Fin n) : w i i ≤ additive_valuation (u i) (bundle_of τ i) := by simpa only [hval] using hI i have htrim₀ (i : Fin n) (hi : i ≠ r) : additive_valuation (u i) (bundle_of τ r) - a i ≤ additive_valuation (u i) (bundle_of τ i) := by have hh := hA i hi rw [hval, hval] simp only [ite_true] linarith have htrim₁ (i : Fin n) (hi : i ≠ s) : additive_valuation (u i) (bundle_of τ s) - b i ≤ additive_valuation (u i) (bundle_of τ i) := by have hh := hB i hi rw [hval, hval] simp only [ite_true] linarith refine ⟨τ, ?_, ?_, ?_⟩ · intro i j hij g hg have hg' : τ g = j := by simpa [bundle_of] using hg rw [additive_valuation_erase_of_mem _ _ _ hg] rcases Fin.eq_castSucc_or_eq_last g with ⟨g₁, rfl⟩ | rfl · rcases Fin.eq_castSucc_or_eq_last g₁ with ⟨g₀, rfl⟩ | rfl · by_cases hjr : j = r · have hi : i ≠ r := by simpa only [hjr] using hij rw [hjr] have hh := htrim₀ i hi have hl := hsmall₀ i g₀ change a i ≤ u i g₀.castSucc.castSucc at hl linarith · by_cases hjs : j = s · have hi : i ≠ s := by simpa only [hjs] using hij rw [hjs] have hh := htrim₁ i hi have hl := hsmall₁ i g₀ change b i ≤ u i g₀.castSucc.castSucc at hl linarith · have hold : g₀ ∈ bundle_of σ (p j) := by simpa [τ, τ₁, τ₀, bundle_of, Equiv.symm_apply_eq] using hg' have hh := is_efx_goods_all_pairs (fun i (g : Fin m) => u i g.castSucc.castSucc) (fun i g => hu i _) σ hσ i (p j) g₀ hold rw [additive_valuation_erase_of_mem _ _ _ hold] at hh change w i (p j) - u i g₀.castSucc.castSucc ≤ w i i at hh rw [hval] simp only [if_neg hjr, if_neg hjs, add_zero] exact hh.trans (hown i) · have howner : r = j := by simpa [τ, τ₁, τ₀] using hg' have hi : i ≠ r := by simpa only [← howner] using hij rw [← howner] exact htrim₀ i hi · have howner : s = j := by simpa [τ] using hg' have hi : i ≠ s := by simpa only [← howner] using hij rw [← howner] exact htrim₁ i hi · intro i exact hown i · intro g h hgh simp [τ, τ₁, τ₀, hgh]