additive_sum_le_of_two_bundles_cover
Two-deviation certificate: if two bundles D1, D2, each worth at most v(A) to an agent with nonnegative additive values, together cover (with multiplicity) A plus two distinct goods x, y outside A, then v(x) + v(y) <= v(A).
Statement
theorem additive_sum_le_of_two_bundles_cover {G : Type*} [DecidableEq G] (w : G → ℝ) (hw : ∀ g, 0 ≤ w g) (A D₁ D₂ : Finset G) (x y : G) (hxy : x ≠ y) (hxA : x ∉ A) (hyA : y ∉ A) (h₁ : ∑ g ∈ D₁, w g ≤ ∑ g ∈ A, w g) (h₂ : ∑ g ∈ D₂, w g ≤ ∑ g ∈ A, w g) (hcov : ∀ g, (if g ∈ A then 1 else 0) + (if g = x then 1 else 0) + (if g = y then 1 else 0) ≤ (if g ∈ D₁ then 1 else 0) + (if g ∈ D₂ then 1 else 0 : ℕ)) : w x + w y ≤ ∑ g ∈ A, w g
- Source
- for RT-3 (round_robin_pne_envy_zero_ef1_of_two_mul_add_one): at a Round-Robin equilibrium the bundles D1, D2 of two deviations are worth at most v(A_i)
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
The proof, explained
The proof establishes the bound by scaling the indicator covering inequality by the nonnegative weights and summing over an ambient finite set S containing all relevant elements. Distributing the sums and simplifying indicator terms reduces the left side to v(A) + v(x) + v(y) and the right side to v(D₁) + v(D₂). Since each of D₁ and D₂ has weight at most v(A), the right side is bounded by 2 v(A), from which subtracting v(A) yields v(x) + v(y) ≤ v(A).
Let S = D₁ ∪ D₂ ∪ A ∪ {x} ∪ {y}; then D₁ ⊆ S, D₂ ⊆ S, A ⊆ S, x ∈ S, and y ∈ S.
We define an ambient finite set S containing both bundles D₁, D₂, the bundle A, and the singleton goods {x} and {y}. By rewriting membership using Finset.mem_union and Finset.mem_singleton, each inclusion (D₁ ⊆ S, D₂ ⊆ S, A ⊆ S) and membership (x ∈ S, y ∈ S) reduces to propositional tautologies. Line 7 records the hypotheses hxy, hxA, and hyA.
uses
Finset.mem_union,Finset.mem_singletonhave _ := hxy; have _ := hxA; have _ := hyA let S : Finset G := D₁ ∪ D₂ ∪ A ∪ {x} ∪ {y} have hD₁ : D₁ ⊆ S := by intro g hg; simp only [S, Finset.mem_union, Finset.mem_singleton]; tauto have hD₂ : D₂ ⊆ S := by intro g hg; simp only [S, Finset.mem_union, Finset.mem_singleton]; tauto have hA : A ⊆ S := by intro g hg; simp only [S, Finset.mem_union, Finset.mem_singleton]; tauto have hx : x ∈ S := by simp only [S, Finset.mem_union, Finset.mem_singleton]; tauto have hy : y ∈ S := by simp only [S, Finset.mem_union, Finset.mem_singleton]; tauto
The weighted covering inequality holds when summed over the ambient set S.
By Finset.sum_le_sum, it suffices to show the inequality pointwise for each element g ∈ S. The covering hypothesis hcov guarantees that the sum of indicator functions for A, x, and y is at most that for D₁ and D₂. Since all weights w(g) are nonnegative by hw, multiplying through by w(g) preserves the inequality. Case analysis on all indicators via split_ifs and linear arithmetic closes each branch.
uses
Finset.sum_le_sumhave hsum : ∑ g ∈ S, ((if g ∈ A then w g else 0) + (if g = x then w g else 0) + (if g = y then w g else 0)) ≤ ∑ g ∈ S, ((if g ∈ D₁ then w g else 0) + (if g ∈ D₂ then w g else 0)) := by apply Finset.sum_le_sum intro g _ have h := hcov g have hwg := hw g split_ifs at * <;> linarith
The summed inequality simplifies to ∑ g ∈ A, w g + w x + w y ≤ ∑ g ∈ D₁, w g + ∑ g ∈ D₂, w g.
We distribute the sums over addition with Finset.sum_add_distrib. Using Finset.sum_ite_mem, the sums of set indicators become sums over S ∩ A, S ∩ D₁, and S ∩ D₂, which simplify to A, D₁, and D₂ via Finset.inter_eq_right.mpr using the subset relations proved earlier. Finally, the point indicators for x and y simplify to w x and w y using Finset.sum_ite_eq' and if_pos since x, y ∈ S.
uses
Finset.sum_add_distrib,Finset.sum_ite_mem,Finset.inter_eq_right.mpr,Finset.sum_ite_eq',if_possimp only [Finset.sum_add_distrib] at hsum simp only [Finset.sum_ite_mem, Finset.inter_eq_right.mpr hA, Finset.inter_eq_right.mpr hD₁, Finset.inter_eq_right.mpr hD₂] at hsum rw [Finset.sum_ite_eq', if_pos hx] at hsum rw [Finset.sum_ite_eq', if_pos hy] at hsum
w x + w y ≤ ∑ g ∈ A, w g.
We have ∑ g ∈ A, w g + w x + w y ≤ ∑ g ∈ D₁, w g + ∑ g ∈ D₂, w g. Substituting the bounds ∑ g ∈ D₁, w g ≤ ∑ g ∈ A, w g (from h₁) and ∑ g ∈ D₂, w g ≤ ∑ g ∈ A, w g (from h₂) gives ∑ g ∈ A, w g + w x + w y ≤ 2 ∑ g ∈ A, w g. Subtracting ∑ g ∈ A, w g from both sides leaves w x + w y ≤ ∑ g ∈ A, w g, which linarith deduces directly.
linarith
Finset.mem_union- An element belongs to the union of two finite sets if and only if it belongs to either set.
Finset.mem_singleton- An element belongs to a singleton set {a} if and only if it equals a.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i in a finite set s, then ∑ i ∈ s, f(i) ≤ ∑ i ∈ s, g(i).
Finset.sum_add_distrib- The sum of a pointwise sum of functions over a finite set equals the sum of the individual sums.
Finset.sum_ite_mem- Summing an indicator function of membership in t multiplied by f over a finite set s equals the sum of f over s ∩ t.
Finset.inter_eq_right.mpr- If t ⊆ s for finite sets s and t, then s ∩ t = t.
Finset.sum_ite_eq'- Summing a single-point indicator over a finite set s equals the function value at that point if the point is in s, and 0 otherwise.
if_pos- If the condition c is true, then (if c then t else e) simplifies to t.
- The hypotheses hxy (x ≠ y), hxA (x ∉ A), and hyA (y ∉ A) appear in the theorem statement and are inspected on line 7, but they are not used anywhere in the proof; the covering hypothesis hcov together with nonnegativity of weights is sufficient on its own.
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.
theorem additive_sum_le_of_two_bundles_cover {G : Type*} [DecidableEq G] (w : G → ℝ) (hw : ∀ g, 0 ≤ w g) (A D₁ D₂ : Finset G) (x y : G) (hxy : x ≠ y) (hxA : x ∉ A) (hyA : y ∉ A) (h₁ : ∑ g ∈ D₁, w g ≤ ∑ g ∈ A, w g) (h₂ : ∑ g ∈ D₂, w g ≤ ∑ g ∈ A, w g) (hcov : ∀ g, (if g ∈ A then 1 else 0) + (if g = x then 1 else 0) + (if g = y then 1 else 0) ≤ (if g ∈ D₁ then 1 else 0) + (if g ∈ D₂ then 1 else 0 : ℕ)) : w x + w y ≤ ∑ g ∈ A, w g := by have _ := hxy; have _ := hxA; have _ := hyA let S : Finset G := D₁ ∪ D₂ ∪ A ∪ {x} ∪ {y} have hD₁ : D₁ ⊆ S := by intro g hg; simp only [S, Finset.mem_union, Finset.mem_singleton]; tauto have hD₂ : D₂ ⊆ S := by intro g hg; simp only [S, Finset.mem_union, Finset.mem_singleton]; tauto have hA : A ⊆ S := by intro g hg; simp only [S, Finset.mem_union, Finset.mem_singleton]; tauto have hx : x ∈ S := by simp only [S, Finset.mem_union, Finset.mem_singleton]; tauto have hy : y ∈ S := by simp only [S, Finset.mem_union, Finset.mem_singleton]; tauto have hsum : ∑ g ∈ S, ((if g ∈ A then w g else 0) + (if g = x then w g else 0) + (if g = y then w g else 0)) ≤ ∑ g ∈ S, ((if g ∈ D₁ then w g else 0) + (if g ∈ D₂ then w g else 0)) := by apply Finset.sum_le_sum intro g _ have h := hcov g have hwg := hw g split_ifs at * <;> linarith simp only [Finset.sum_add_distrib] at hsum simp only [Finset.sum_ite_mem, Finset.inter_eq_right.mpr hA, Finset.inter_eq_right.mpr hD₁, Finset.inter_eq_right.mpr hD₂] at hsum rw [Finset.sum_ite_eq', if_pos hx] at hsum rw [Finset.sum_ite_eq', if_pos hy] at hsum linarith