is_efx_goods_exists_unenvied
For a positive number of agents, any EFX allocation of nonnegative additive goods can be changed to another EFX allocation that weakly improves every own utility and has an unenvied agent.
Statement
theorem is_efx_goods_exists_unenvied {m n : ℕ} (hn : 0 < n) (u : Fin n → Fin m → ℝ)
(hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (hσ : is_efx_goods u σ) :
∃ τ : Fin m → Fin n, is_efx_goods u τ ∧
(∀ i, additive_valuation (u i) (bundle_of σ i) ≤
additive_valuation (u i) (bundle_of τ i)) ∧
∃ s : Fin n, ∀ i, additive_valuation (u i) (bundle_of τ s) ≤
additive_valuation (u i) (bundle_of τ i)- 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 6
- finite_unenvied_permutationEvery finite nonempty matrix of real bundle values admits a permutation that weakly improves each diagonal value and has an unenvied…
- 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_permute_of_utility_leA bundle permutation that weakly improves every agent's own additive value preserves EFX for nonnegative item values.
- 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
The proof uses envy-cycle elimination on the agents' bundles. Given an initial EFX allocation σ, we consider the matrix of utilities each agent assigns to every other agent's bundle and invoke finite_unenvied_permutation to find a permutation p and an agent s such that trading bundles along p weakly improves every agent's utility, while bundle p(s) is weakly dispreferred by everyone to their own new bundle. Defining the new allocation by assigning good g to p⁻¹(σ(g)) preserves the EFX property by is_efx_goods_permute_of_utility_le, and leaves agent s unenvied.
The agent population Fin n is nonempty.
Using classical reasoning and the assumption that n > 0, we deduce n ≠ 0 via Nat.ne_of_gt, establishing that Fin n is a nonempty type.
uses
Nat.ne_of_gtclassical letI : NeZero n := ⟨Nat.ne_of_gt hn⟩
There exist an agent permutation p and a candidate agent s such that reassigning bundle p(i) to agent i weakly improves every agent's utility, and no agent prefers bundle p(s) to their own bundle p(i).
Consider the matrix w(i, j) = additive_valuation (u i) (bundle_of σ j) representing agent i's valuation of agent j's bundle under σ. Applying finite_unenvied_permutation to w yields a permutation p of agents and an agent s such that for all i, w(i, i) ≤ w(i, p(i)) (each agent weakly prefers bundle p(i) to their own) and w(i, p(s)) ≤ w(i, p(i)) (each agent weakly prefers bundle p(i) to bundle p(s)).
uses
finite_unenvied_permutationobtain ⟨p, hp, s, hs⟩ := finite_unenvied_permutation (fun i j => additive_valuation (u i) (bundle_of σ j))
The reallocated assignment τ(g) = p⁻¹(σ(g)) is EFX, and agent s will serve as the unenvied agent.
We choose τ to be the allocation where good g is assigned to p⁻¹(σ(g)), which gives agent i the bundle originally held by p(i). By is_efx_goods_permute_of_utility_le, because σ is EFX, goods have non-negative utilities, and p weakly improves every agent's valuation of their own bundle, τ is also EFX. We also provide s as the unenvied agent, leaving two goals: that utilities weakly increase and that s is unenvied under τ.
uses
is_efx_goods_permute_of_utility_lerefine ⟨fun g => p.symm (σ g), is_efx_goods_permute_of_utility_le u hu σ hσ p hp, ?_, s, ?_⟩
Every agent weakly prefers their bundle under τ to their initial bundle under σ.
By bundle_of_permute_agents, agent i's bundle under τ = p⁻¹ ∘ σ is precisely bundle_of σ (p i). Rewriting with this lemma transforms the goal into the hypothesis hp from the permutation construction, which states that each agent weakly prefers bundle p(i) to bundle i.
uses
bundle_of_permute_agents· simpa only [bundle_of_permute_agents] using hpAgent s is unenvied under τ: every agent weakly prefers their own bundle to the bundle of s.
Using bundle_of_permute_agents, the bundles of s and i under τ simplify to bundle_of σ (p s) and bundle_of σ (p i). The condition then reduces exactly to hypothesis hs from the permutation construction, which guarantees that no agent values bundle p(s) more than bundle p(i).
uses
bundle_of_permute_agents· simpa only [bundle_of_permute_agents] using hs
Nat.ne_of_gt- If a natural number is strictly greater than another, they are not equal; in particular, a positive natural number is nonzero.
finite_unenvied_permutation- For any finite nonempty set of agents and any utility matrix w, there exists a permutation p such that every agent weakly prefers their assigned element p(i) to i, and some agent s is unenvied (every agent weakly prefers p(i) to p(s)).
is_efx_goods_permute_of_utility_le- For non-negative additive valuations, permuting the bundles of an EFX allocation according to a permutation that weakly increases each agent's utility yields another EFX allocation.
bundle_of_permute_agents- Under the permuted allocation g ↦ p⁻¹(σ(g)), the bundle assigned to agent i is the bundle that originally belonged to agent p(i).
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_exists_unenvied {m n : ℕ} (hn : 0 < n) (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (hσ : is_efx_goods u σ) : ∃ τ : Fin m → Fin n, is_efx_goods u τ ∧ (∀ i, additive_valuation (u i) (bundle_of σ i) ≤ additive_valuation (u i) (bundle_of τ i)) ∧ ∃ s : Fin n, ∀ i, additive_valuation (u i) (bundle_of τ s) ≤ additive_valuation (u i) (bundle_of τ i) := by classical letI : NeZero n := ⟨Nat.ne_of_gt hn⟩ obtain ⟨p, hp, s, hs⟩ := finite_unenvied_permutation (fun i j => additive_valuation (u i) (bundle_of σ j)) refine ⟨fun g => p.symm (σ g), is_efx_goods_permute_of_utility_le u hu σ hσ p hp, ?_, s, ?_⟩ · simpa only [bundle_of_permute_agents] using hp · simpa only [bundle_of_permute_agents] using hs