exists_minimally_envied_source_extension
For 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 a good g outside A(s) has strictly positive value for s. Then A(s) union {g} contains a subset T containing g which some agent j strictly prefers to A(j), and deleting any good of T leaves value at most the own A(i) for every agent i.
Statement
theorem exists_minimally_envied_source_extension {m n : ℕ}
(u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g)
(A : Fin n → Finset (Fin m)) (s : Fin n) (g : Fin m)
(hg : g ∉ A s) (hpos : 0 < u s g)
(hs : ∀ i, additive_valuation (u i) (A s) ≤ additive_valuation (u i) (A i)) :
∃ (j : Fin n) (T : Finset (Fin m)), T ⊆ insert g (A s) ∧ g ∈ T ∧
additive_valuation (u j) (A j) < additive_valuation (u j) T ∧
∀ i, ∀ h ∈ T, additive_valuation (u i) (T.erase h) ≤
additive_valuation (u i) (A 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 3
- exists_minimally_envied_subsetGiven a real additive valuation profile, a real utility threshold for each agent, and a finite bundle envied by some agent relative to…
- envied_subset_contains_added_goodFor nonnegative additive item values, if every agent values a bundle S at most her threshold, any subset of S union a singleton g that…
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
The proof, explained
Adding good g to bundle A(s) strictly increases agent s's valuation beyond their own bundle A(s) because g ∉ A(s) and u(s, g) > 0. Applying exists_minimally_envied_subset extracts a subbundle T ⊆ A(s) ∪ {g} envied by some agent j such that deleting any good from T eliminates envy for all agents. Finally, because A(s) was unenvied and valuations are nonnegative, envied_subset_contains_added_good guarantees that the envied subbundle T must contain g.
The extended bundle A(s) ∪ {g} is strictly envied by agent s relative to their own bundle A(s).
Working classically, we show that agent s serves as a witness to envy for the bundle A(s) ∪ {g}. By definition of additive valuation and because g ∉ A(s), the lemma Finset.sum_insert rewrites the valuation of A(s) ∪ {g} as u(s, g) + ∑_{x ∈ A(s)} u(s, x). Because u(s, g) > 0, linear arithmetic confirms that this sum strictly exceeds the valuation of A(s).
uses
Finset.sum_insertclassical have hex : ∃ i, additive_valuation (u i) (A i) < additive_valuation (u i) (insert g (A s)) := by refine ⟨s, ?_⟩ simp only [additive_valuation, Finset.sum_insert hg] linarith
There exists a subbundle T ⊆ A(s) ∪ {g} that is strictly envied by some agent, but from which removing any good leaves it unenvied by all agents.
Applying exists_minimally_envied_subset to the extended bundle A(s) ∪ {g} with thresholds given by each agent's valuation of their own bundle A(i) produces a subset T ⊆ A(s) ∪ {g} strictly envied by some agent, such that removing any item h ∈ T reduces the valuation to at most A(i)'s value for every agent i.
uses
exists_minimally_envied_subsetobtain ⟨T, hT, henv, htrim⟩ := exists_minimally_envied_subset u (fun i => additive_valuation (u i) (A i)) (insert g (A s)) hex
The minimally envied subbundle T contains the newly added good g.
By assumption, the original bundle A(s) is unenvied by all agents. Since valuations are nonnegative, any subset of A(s) is also unenvied. Because T ⊆ A(s) ∪ {g} is strictly envied, envied_subset_contains_added_good guarantees that T cannot be contained entirely in A(s), so g ∈ T.
uses
envied_subset_contains_added_goodhave hgT := envied_subset_contains_added_good u hu (fun i => additive_valuation (u i) (A i)) (A s) T g hT hs henv
The agent j and subbundle T satisfy all required conditions.
Unpacking the existential envy condition gives an agent j who strictly prefers T to A(j). Combining this with T ⊆ A(s) ∪ {g}, g ∈ T, and the condition that single-good deletions eliminate envy across all agents yields the full existential conclusion.
obtain ⟨j, hj⟩ := henv exact ⟨j, T, hT, hgT, hj, htrim⟩
Finset.sum_insert- For a finite set s and an element a ∉ s, the sum of a function over s ∪ {a} equals the value at a plus the sum over s.
exists_minimally_envied_subset- If a bundle has valuation strictly exceeding given thresholds for some agent, it contains a subbundle that strictly exceeds the threshold for some agent, yet removing any single item reduces its valuation to at most the threshold for all agents.
envied_subset_contains_added_good- Under nonnegative valuations, if a bundle S does not exceed thresholds for any agent, any subbundle of S ∪ {g} that exceeds some agent's threshold must contain g.
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_source_extension {m n : ℕ} (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) (A : Fin n → Finset (Fin m)) (s : Fin n) (g : Fin m) (hg : g ∉ A s) (hpos : 0 < u s g) (hs : ∀ i, additive_valuation (u i) (A s) ≤ additive_valuation (u i) (A i)) : ∃ (j : Fin n) (T : Finset (Fin m)), T ⊆ insert g (A s) ∧ g ∈ T ∧ additive_valuation (u j) (A j) < additive_valuation (u j) T ∧ ∀ i, ∀ h ∈ T, additive_valuation (u i) (T.erase h) ≤ additive_valuation (u i) (A i) := by classical have hex : ∃ i, additive_valuation (u i) (A i) < additive_valuation (u i) (insert g (A s)) := by refine ⟨s, ?_⟩ simp only [additive_valuation, Finset.sum_insert hg] linarith obtain ⟨T, hT, henv, htrim⟩ := exists_minimally_envied_subset u (fun i => additive_valuation (u i) (A i)) (insert g (A s)) hex have hgT := envied_subset_contains_added_good u hu (fun i => additive_valuation (u i) (A i)) (A s) T g hT hs henv obtain ⟨j, hj⟩ := henv exact ⟨j, T, hT, hgT, hj, htrim⟩