envied_subset_contains_added_good
For nonnegative additive item values, if every agent values a bundle S at most her threshold, any subset of S union a singleton g that some agent values strictly above her threshold must contain g.
Statement
theorem envied_subset_contains_added_good {m n : ℕ}
(u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g)
(b : Fin n → ℝ) (S T : Finset (Fin m)) (g : Fin m)
(hT : T ⊆ insert g S) (hS : ∀ i, additive_valuation (u i) S ≤ b i)
(henv : ∃ j, b j < additive_valuation (u j) T) : g ∈ T- 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
We argue by contradiction, assuming that the added item g is not in T. Because T ⊆ {g} ∪ S and g ∉ T, every element of T belongs to S, so T ⊆ S. Since all item valuations are nonnegative, each agent's additive valuation of T is at most their valuation of S. This contradicts the assumption that some agent values T strictly above their threshold while valuing S at or below it.
Assume for contradiction that g ∉ T.
We set up a proof by contradiction, assuming that the added item g is not in T (labeled hg).
classical by_contra hgT is a subset of S (T ⊆ S).
Let x ∈ T. Since T ⊆ insert g S, Finset.mem_insert.mp implies that either x = g or x ∈ S. If x = g, then g ∈ T, directly contradicting the assumption hg (g ∉ T). Thus x must be in S, which establishes T ⊆ S.
uses
Finset.mem_insert.mphave hsub : T ⊆ S := by intro x hx rcases Finset.mem_insert.mp (hT hx) with h | h · exact (hg (h ▸ hx)).elim · exact h
For an agent j who envies bundle T, their valuation of T is at most their valuation of S.
From the hypothesis that some agent values T strictly above their threshold, let j be such an agent (so b(j) < additive_valuation(u j) T). Because T ⊆ S and all item values are nonnegative (hu), the sum of values over T is bounded above by the sum over S via Finset.sum_le_sum_of_subset_of_nonneg.
uses
Finset.sum_le_sum_of_subset_of_nonnegobtain ⟨j, hj⟩ := henv have hle : additive_valuation (u j) T ≤ additive_valuation (u j) S := Finset.sum_le_sum_of_subset_of_nonneg hsub (fun x _ _ => hu j x)
A contradiction is reached, completing the proof that g ∈ T.
Chaining the inequality additive_valuation(u j) T ≤ additive_valuation(u j) S with the threshold bound additive_valuation(u j) S ≤ b(j) (from hS) shows that additive_valuation(u j) T ≤ b(j). By not_lt_of_ge, this directly contradicts b(j) < additive_valuation(u j) T.
uses
not_lt_of_geexact (not_lt_of_ge (hle.trans (hS j))) hj
Finset.mem_insert.mp- If an element belongs to the insertion of an item into a finite set, then it is either equal to that item or belongs to the set.
Finset.sum_le_sum_of_subset_of_nonneg- If one finite set is a subset of another and the terms are nonnegative on the elements outside the subset, the sum over the subset is at most the sum over the superset.
not_lt_of_ge- If a ≤ b, then it is false that b < a.
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 envied_subset_contains_added_good {m n : ℕ} (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) (b : Fin n → ℝ) (S T : Finset (Fin m)) (g : Fin m) (hT : T ⊆ insert g S) (hS : ∀ i, additive_valuation (u i) S ≤ b i) (henv : ∃ j, b j < additive_valuation (u j) T) : g ∈ T := by classical by_contra hg have hsub : T ⊆ S := by intro x hx rcases Finset.mem_insert.mp (hT hx) with h | h · exact (hg (h ▸ hx)).elim · exact h obtain ⟨j, hj⟩ := henv have hle : additive_valuation (u j) T ≤ additive_valuation (u j) S := Finset.sum_le_sum_of_subset_of_nonneg hsub (fun x _ _ => hu j x) exact (not_lt_of_ge (hle.trans (hS j))) hj