AFTD Auto-Formalizing Theoretical Domains

additive_sum_le_of_two_bundles_cover

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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).

  1. 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.

    lines 7–13

    uses Finset.mem_union, Finset.mem_singleton

      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
  2. 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.

    lines 14–20

    uses Finset.sum_le_sum

      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
  3. 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.

    lines 21–25

    uses Finset.sum_add_distrib, Finset.sum_ite_mem, Finset.inter_eq_right.mpr, Finset.sum_ite_eq', if_pos

      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
  4. 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.

    line 26

      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.

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

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
See it in the graphDiscuss this resultChallenge it