efx_of_bundle_card_le_one
An allocation where each agent receives at most one good is unconditionally EFX for any nonnegative additive valuations.
Statement
theorem efx_of_bundle_card_le_one {m n : ℕ} (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (hinj : Function.Injective σ) : is_efx_goods u σ- Source
- step towards efx_four_agents_additive_exists
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- 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…
The proof, explained
To show the allocation is EFX, consider any two distinct agents i ≠ j and any good g assigned to j. Because the allocation function σ is injective, at most one good is assigned to agent j, so removing g leaves j with an empty bundle. The additive valuation of an empty bundle is 0. Since agent i's valuation is additive and nonnegative for all goods, i's valuation for their own bundle is at least 0, satisfying the EFX requirement.
Fix two distinct agents i and j, and a good g assigned to j.
To prove the allocation is EFX (is_efx_goods), we introduce arbitrary distinct agents i ≠ j and an item g in agent j's bundle. It suffices to show that agent i values j's bundle after removing g at most as much as i values their own bundle.
intro i j hij g hgRemoving good g from agent j's bundle leaves an empty bundle.
By set extensionality, we show no item x can belong to (bundle_of σ j).erase g. Any such x would have to be distinct from g and satisfy σ x = j. However, since g is in j's bundle, σ g = j as well. By the injectivity of σ, σ x = σ g implies x = g, which contradicts x ≠ g. Hence the erased bundle is empty.
uses
Finset.mem_erase,Finset.mem_filter,Finset.mem_univ,true_and,Finset.notMem_empty,iff_falsehave herase : (bundle_of σ j).erase g = ∅ := by ext x simp only [Finset.mem_erase, bundle_of, Finset.mem_filter, Finset.mem_univ, true_and, Finset.notMem_empty, iff_false] rintro ⟨hne, hx⟩ have hg_eq : σ g = j := by simpa [bundle_of] using hg exact hne (hinj (hx.trans hg_eq.symm))
The EFX inequality holds.
Substituting the empty set for the erased bundle, agent i's valuation for j's bundle without g becomes the sum over the empty set, which is 0. By assumption, agent i assigns a nonnegative utility to every good, so the sum over i's own bundle is at least 0. Thus the valuation of the reduced bundle is at most the valuation of i's bundle.
uses
Finset.sum_nonnegrw [herase] dsimp [additive_valuation] exact Finset.sum_nonneg (fun x _ => hu i x)
Finset.mem_erase- An element a belongs to s.erase b if and only if a ≠ b and a ∈ s.
Finset.mem_filter- An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
Finset.mem_univ- Every element of a finite type belongs to the universal set Finset.univ.
true_and- The conjunction True ∧ p is equal to p.
Finset.notMem_empty- No element belongs to the empty finset.
iff_false- The equivalence (p ↔ False) simplifies to ¬p.
Finset.sum_nonneg- If each term in a finite sum is nonnegative, the sum is nonnegative.
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.
/-- An allocation where each agent receives at most one good (e.g. an injective assignment of goods to agents) is unconditionally EFX for any nonnegative additive valuations. -/theorem efx_of_bundle_card_le_one {m n : ℕ} (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (hinj : Function.Injective σ) : is_efx_goods u σ := by intro i j hij g hg have herase : (bundle_of σ j).erase g = ∅ := by ext x simp only [Finset.mem_erase, bundle_of, Finset.mem_filter, Finset.mem_univ, true_and, Finset.notMem_empty, iff_false] rintro ⟨hne, hx⟩ have hg_eq : σ g = j := by simpa [bundle_of] using hg exact hne (hinj (hx.trans hg_eq.symm)) rw [herase] dsimp [additive_valuation] exact Finset.sum_nonneg (fun x _ => hu i x)