exists_minimally_envied_subset
Given a real additive valuation profile, a real utility threshold for each agent, and a finite bundle envied by some agent relative to those thresholds, there is a subset still strictly envied by some agent such that deleting any of its goods leaves value at most the threshold for every agent.
Statement
theorem exists_minimally_envied_subset {m n : ℕ} (u : Fin n → Fin m → ℝ)
(b : Fin n → ℝ) (S : Finset (Fin m))
(h : ∃ i, b i < additive_valuation (u i) S) :
∃ T ⊆ S, (∃ j, b j < additive_valuation (u j) T) ∧
∀ i, ∀ g ∈ T, additive_valuation (u i) (T.erase g) ≤ b i- Source
- Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01. Standard minimal-envied-subset mechanism, arXiv:2002.05119v3 Observation 6 and Corollary 7; no novelty claim.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- Used by 1
- exists_minimally_envied_source_extensionFor nonnegative additive values and any family of finite bundles A, suppose A(s) is unenvied by every agent relative to her own A(i), and…
The proof, explained
The theorem is proved by strong induction on the bundle S ordered by proper inclusion. If deleting any good from S drops every agent's valuation to at most their threshold, then S itself is the desired subset. Otherwise, some deletion S \ {g} remains strictly envied, and since it is a proper subset of S, the induction hypothesis provides a minimally envied subset T ⊆ S \ {g} ⊆ S.
The problem reduces to proving the claim by strong induction on the bundle S ordered by proper inclusion.
Working classically, we revert the hypothesis that S is envied so that the induction hypothesis applies to any envied sub-bundle. We then set up strong induction on S using Finset.strongInductionOn, assuming that the claim holds for every proper subset t ⊂ S that is strictly envied by some agent.
uses
Finset.strongInductionOnclassical revert h refine Finset.strongInductionOn S ?_ intro S ih h
If deleting any single good from S leaves all agents at or below their thresholds, then S itself satisfies the theorem.
We perform a case split on whether deleting any element g ∈ S ensures that every agent's valuation is at most their threshold b i. If this condition holds, we can choose T = S: S ⊆ S by Finset.Subset.refl, S is strictly envied by assumption, and every deletion of a single good stays within the thresholds.
uses
Finset.Subset.reflby_cases hmin : ∀ i, ∀ g ∈ S, additive_valuation (u i) (S.erase g) ≤ b i · exact ⟨S, Finset.Subset.refl _, h, hmin⟩
If some single-good deletion is still strictly envied, the induction hypothesis on that strict subset provides the required subset T ⊆ S.
Otherwise, negating the minimality condition yields an agent i and a good g ∈ S such that deleting g leaves a bundle S \ {g} strictly envied by agent i. Since g ∈ S, the deletion S \ {g} is a proper subset of S by Finset.erase_ssubset. Applying the induction hypothesis to S \ {g} produces a subset T ⊆ S \ {g} that is strictly envied and satisfies the single-deletion threshold bounds. Since S \ {g} ⊆ S by Finset.erase_subset, transitivity of inclusion guarantees T ⊆ S.
uses
Finset.erase_ssubset,Finset.erase_subset· push Not at hmin obtain ⟨i, g, hg, hgt⟩ := hmin obtain ⟨T, hT, henv, htrim⟩ := ih (S.erase g) (Finset.erase_ssubset hg) ⟨i, hgt⟩ exact ⟨T, hT.trans (Finset.erase_subset g S), henv, htrim⟩
Finset.strongInductionOn- strong induction on finite sets: to show a property holds for a finite set s, it suffices to show it holds for any set assuming it holds for all its proper subsets
Finset.Subset.refl- every finite set is a subset of itself
Finset.erase_ssubset- removing an element from a finite set in which it belongs yields a proper subset
Finset.erase_subset- removing an element from a finite set yields a subset of the original set
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 exists_minimally_envied_subset {m n : ℕ} (u : Fin n → Fin m → ℝ) (b : Fin n → ℝ) (S : Finset (Fin m)) (h : ∃ i, b i < additive_valuation (u i) S) : ∃ T ⊆ S, (∃ j, b j < additive_valuation (u j) T) ∧ ∀ i, ∀ g ∈ T, additive_valuation (u i) (T.erase g) ≤ b i := by classical revert h refine Finset.strongInductionOn S ?_ intro S ih h by_cases hmin : ∀ i, ∀ g ∈ S, additive_valuation (u i) (S.erase g) ≤ b i · exact ⟨S, Finset.Subset.refl _, h, hmin⟩ · push Not at hmin obtain ⟨i, g, hg, hgt⟩ := hmin obtain ⟨T, hT, henv, htrim⟩ := ih (S.erase g) (Finset.erase_ssubset hg) ⟨i, hgt⟩ exact ⟨T, hT.trans (Finset.erase_subset g S), henv, htrim⟩