AFTD Auto-Formalizing Theoretical Domains

balanced_high_count_chore_mms_bound

theoremverified

For n at least two, k at least two and n*k bivalued chores, a bundle of size k whose high-cost count times n is at most the total high-cost count plus n minus one costs at most (r+1)/2 times the n-agent chore maximin share, for every ratio r at least one and positive base cost a.

Statement

theorem balanced_high_count_chore_mms_bound (n k : ℕ) (hn : 2 ≤ n) (hk : 2 ≤ k) (r : ℝ) (hr : 1 ≤ r) (a : ℝ) (ha : 0 < a) (u : Fin (n*k) → ℝ) (hu : ∀ g, u g = a ∨ u g = r*a) (S : Finset (Fin (n*k))) (hs : S.card = k) (hh : n * ((S.filter fun g => u g = r*a).card) ≤ ((Finset.univ.filter fun g => u g = r*a).card) + n - 1) : additive_valuation u S ≤ ((r+1)/2) * chore_maximin_share n u
Source
Bivalued specialization of the proportional-share lower bound in arXiv:2609.35280, Lemma 2.4.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • chore_maximin_shareThe maximin share (MMS) of an agent with additive chore costs u among n agents: the infimum over all partitions P : Fin m → Fin n of the…
  • chore_prop_share_le_maximin_shareFor any number of agents n >= 1, items m, and additive chore cost function u, the proportional share (sum of costs divided by n) is at…
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Used by 1

The proof, explained

The proof first expresses the total cost of any bundle of bivalued chores as its size times the base cost a plus its count of high-cost items times (r - 1) * a. By chore_prop_share_le_maximin_share, the proportional share P = (1/n) ∑ u(g) is a lower bound for the chore maximin share, so it suffices to show that the bundle S costs at most ((r + 1)/2) * P. Because the bundle S has size k and satisfies the balanced high-cost count condition n * h_S ≤ h_U + n - 1, its cost is bounded above by P + (r - 1) * a. Finally, since each bundle has size k ≥ 2, the proportional share satisfies P ≥ 2 * a, which implies that P + (r - 1) * a ≤ ((r + 1)/2) * P.

  1. The sum of costs over the high-cost items in s equals their count times r * a, and s decomposes into high-cost items and non-high-cost items.

    We enable classical logic and partition s into items with u(g) = r * a and those with u(g) ≠ r * a, splitting both the total sum and the cardinality into these two parts. For the high-cost items, u(g) is identically r * a, so the sum over this subset equals its cardinality times r * a.

    lines 4–9

    uses Finset.sum_filter_add_sum_filter_not, Finset.card_filter_add_card_filter_not, Finset.sum_congr, Finset.mem_filter.mp

      classical
      have hsum := (Finset.sum_filter_add_sum_filter_not s (fun g => u g = r * a) u).symm
      have hcard := (Finset.card_filter_add_card_filter_not (s := s) (fun g => u g = r * a)).symm
      have h1 : ∑ g ∈ s.filter (fun g => u g = r * a), u g = (s.filter (fun g => u g = r * a)).card * (r * a) := by
        rw [Finset.sum_congr rfl (fun x hx => (Finset.mem_filter.mp hx).2)]
        simp
  2. The sum of costs over items in s not having high cost equals their count times a.

    For any item x ∈ s with u(x) ≠ r * a, the bivalued hypothesis u(x) = a ∨ u(x) = r * a implies that u(x) must equal a (since the second branch contradicts the filter condition). Replacing the summand with the constant a gives |{g ∈ s : u(g) ≠ r * a}| * a.

    lines 10–18

    uses Finset.sum_congr, Finset.mem_filter.mp, False.elim

      have h2 : ∑ g ∈ s.filter (fun g => ¬ u g = r * a), u g = (s.filter (fun g => ¬ u g = r * a)).card * a := by
        have : ∑ g ∈ s.filter (fun g => ¬ u g = r * a), u g = ∑ g ∈ s.filter (fun g => ¬ u g = r * a), a := by
          refine Finset.sum_congr rfl (fun x hx => ?_)
          have hx' := Finset.mem_filter.mp hx
          cases hu x hx'.1 with
          | inl h => exact h
          | inr h => exact False.elim (hx'.2 h)
        rw [this]
        simp
  3. For any subset s of bivalued items, the sum of costs is |s| * a + |{g ∈ s : u(g) = r * a}| * ((r - 1) * a).

    Substituting the sums of the two parts into the sum decomposition yields |s_{ra}| * (r * a) + |s_{≠ ra}| * a. Since the total size is |s| = |s_{ra}| + |s_{≠ ra}|, eliminating |s_{≠ ra}| via a linear combination gives the desired formula.

    lines 19–23

      rw [hsum, h1, h2]
      have hcard_cast : (s.card : ℝ) = ((s.filter (fun g => u g = r * a)).card : ℝ) + ((s.filter (fun g => ¬ u g = r * a)).card : ℝ) := by
        exact_mod_cast hcard
      linear_combination
        -a * hcard_cast
  4. The number of agents n is nonzero, and the proportional chore share P = (∑ u g) / n is at most the chore maximin share.

    Since n ≥ 2, n is nonzero. By chore_prop_share_le_maximin_share, the proportional share P = (1/n) ∑ u(g) is at most the chore maximin share MMS_n(u).

    lines 26–28

    uses chore_prop_share_le_maximin_share

      classical
      have : NeZero n := ⟨by omega⟩
      have hprop := chore_prop_share_le_maximin_share n (n * k) u
  5. The valuations of bundle S and of the entire set of chores are given in terms of their counts of high-cost items.

    Applying the bivalued sum lemma to S (using |S| = k) gives ∑_{g ∈ S} u(g) = k * a + h_S * ((r - 1) * a). Applying it to the universe of all n * k chores gives ∑_g u(g) = (n * k) * a + h_U * ((r - 1) * a).

    lines 29–36

    uses balanced_high_count_chore_mms_bound_sum_bivalued, Finset.card_univ, Fintype.card_fin

      have hS_sum : ∑ g ∈ S, u g = (k : ℝ) * a + ((S.filter fun g => u g = r * a).card : ℝ) * ((r - 1) * a) := by
        have := balanced_high_count_chore_mms_bound_sum_bivalued S u a r (fun g _ => hu g)
        rw [hs] at this
        exact this
      have huniv_sum : ∑ g : Fin (n * k), u g = ((n * k : ℕ) : ℝ) * a + ((Finset.univ.filter fun g => u g = r * a).card : ℝ) * ((r - 1) * a) := by
        have := balanced_high_count_chore_mms_bound_sum_bivalued (Finset.univ : Finset (Fin (n * k))) u a r (fun g _ => hu g)
        simp only [Finset.card_univ, Fintype.card_fin] at this
        exact this
  6. The proportional share satisfies P = k * a + (h_U / n) * ((r - 1) * a).

    Rewriting the goal in terms of the bundle sum formula and defining h_S, h_U, and P = (1/n) ∑ u(g), we substitute the formula for the total universe sum into P and simplify algebraically by dividing by n.

    lines 37–47

      change ∑ g ∈ S, u g ≤ ((r + 1) / 2) * chore_maximin_share n u
      rw [hS_sum]
      set hS := ((S.filter fun g => u g = r * a).card : ℝ)
      set hU := ((Finset.univ.filter fun g => u g = r * a).card : ℝ)
      set P := (∑ g : Fin (n * k), u g) / (n : ℝ)
      have hP_eq : P = (k : ℝ) * a + (hU / (n : ℝ)) * ((r - 1) * a) := by
        dsimp [P]
        rw [huniv_sum]
        push_cast
        have : (n : ℝ) ≠ 0 := by positivity
        field_simp
  7. The high-count balance hypothesis holds over the real numbers: n * h_S ≤ h_U + n - 1.

    The integer inequality n * h_S ≤ h_U + n - 1 is rewritten via omega as n * h_S + 1 ≤ h_U + n, cast from ℕ to ℝ, and simplified using linear arithmetic.

    lines 48–52

      have hh_real : (n : ℝ) * hS ≤ hU + (n : ℝ) - 1 := by
        have h2 : n * (S.filter fun g => u g = r * a).card + 1 ≤ (Finset.univ.filter fun g => u g = r * a).card + n := by omega
        have h3 : ((n * (S.filter fun g => u g = r * a).card + 1 : ℕ) : ℝ) ≤ (((Finset.univ.filter fun g => u g = r * a).card + n : ℕ) : ℝ) := by exact_mod_cast h2
        push_cast at h3
        linarith
  8. The parameters satisfy n > 0, r - 1 ≥ 0, a ≥ 0, (r - 1) * a ≥ 0, and k ≥ 2 in ℝ.

    These inequalities follow immediately from the hypotheses n ≥ 2, r ≥ 1, a > 0, and k ≥ 2, with (r - 1) * a ≥ 0 obtained as the product of non-negative reals.

    lines 53–57

    uses mul_nonneg

      have hn_pos : 0 < (n : ℝ) := by positivity
      have hr_sub : 0 ≤ r - 1 := by linarith
      have ha_nonneg : 0 ≤ a := by linarith
      have h_da : 0 ≤ (r - 1) * a := mul_nonneg hr_sub ha_nonneg
      have hk_cast : 2 ≤ (k : ℝ) := by exact_mod_cast hk
  9. The proportional share satisfies P ≥ 2 * a.

    From the formula for P and the non-negativity of (h_U / n) * (r - 1) * a, we have P ≥ k * a. Since k ≥ 2 and a > 0, it follows that P ≥ k * a ≥ 2 * a.

    lines 58–64

      have hP_ge : 2 * a ≤ P := by
        have h1 : (k : ℝ) * a ≤ P := by
          rw [hP_eq]
          have : 0 ≤ (hU / (n : ℝ)) * ((r - 1) * a) := by positivity
          linarith
        have h2 : 2 * a ≤ (k : ℝ) * a := by nlinarith
        linarith
  10. The bundle cost is bounded by P + (r - 1) * a: k * a + h_S * ((r - 1) * a) ≤ P + (r - 1) * a.

    The difference (P + (r - 1) * a) - (k * a + h_S * ((r - 1) * a)) simplifies to ((r - 1) * a) * (h_U + n - n * h_S) / n. Since (r - 1) * a ≥ 0, n > 0, and n * h_S ≤ h_U + n - 1 implies h_U + n - n * h_S ≥ 1 > 0, this difference is non-negative.

    lines 65–75

    uses sub_nonneg.symm, mul_nonneg, div_nonneg

      have h_step1 : (k : ℝ) * a + hS * ((r - 1) * a) ≤ P + (r - 1) * a := by
        have hdiff : (P + (r - 1) * a) - ((k : ℝ) * a + hS * ((r - 1) * a)) =
            ((r - 1) * a) * ((hU + (n : ℝ) - (n : ℝ) * hS) / (n : ℝ)) := by
          rw [hP_eq]
          have : (n : ℝ) ≠ 0 := by positivity
          field_simp
          ring
        rw [sub_nonneg.symm, hdiff]
        apply mul_nonneg h_da
        apply div_nonneg _ (by positivity)
        linarith
  11. P + (r - 1) * a ≤ ((r + 1) / 2) * P.

    The difference ((r + 1) / 2) * P - (P + (r - 1) * a) factors as ((r - 1) / 2) * (P - 2 * a). Since r ≥ 1 gives (r - 1) / 2 ≥ 0 and P ≥ 2 * a gives P - 2 * a ≥ 0, the product is non-negative.

    lines 76–80

    uses sub_nonneg.symm, mul_nonneg

      have h_step2 : P + (r - 1) * a ≤ ((r + 1) / 2) * P := by
        have hdiff : ((r + 1) / 2) * P - (P + (r - 1) * a) = ((r - 1) / 2) * (P - 2 * a) := by
          ring
        rw [sub_nonneg.symm, hdiff]
        exact mul_nonneg (by linarith) (by linarith)
  12. The bundle S costs at most ((r + 1) / 2) times the chore maximin share.

    Combining the two upper bounds by transitivity gives u(S) ≤ ((r + 1) / 2) * P. Since (r + 1) / 2 ≥ 0 and P ≤ MMS_n(u), scaling the proportional share inequality gives ((r + 1) / 2) * P ≤ ((r + 1) / 2) * MMS_n(u), which completes the proof by transitivity.

    lines 81–85

    uses le_trans, mul_le_mul_of_nonneg_left

      have h_le_P : (k : ℝ) * a + hS * ((r - 1) * a) ≤ ((r + 1) / 2) * P := le_trans h_step1 h_step2
      have hr1 : 0 ≤ (r + 1) / 2 := by linarith
      have h_final : ((r + 1) / 2) * P ≤ ((r + 1) / 2) * chore_maximin_share n u :=
        mul_le_mul_of_nonneg_left hprop hr1
      exact le_trans h_le_P h_final
chore_prop_share_le_maximin_share
For any chore valuation, the proportional share (total cost divided by the number of agents n) is at most the n-agent chore maximin share.
balanced_high_count_chore_mms_bound_sum_bivalued
For any finite set of bivalued items each costing a or r * a, the total sum of costs is |s| * a + |{g ∈ s : u(g) = r * a}| * ((r - 1) * a).
Finset.sum_filter_add_sum_filter_not
The sum of a function over a finite set equals the sum over elements satisfying a predicate plus the sum over elements satisfying its negation.
Finset.card_filter_add_card_filter_not
The cardinality of a finite set equals the cardinality of the subset satisfying a predicate plus the cardinality of the subset satisfying its negation.
Finset.sum_congr
If two finite sets are equal and two functions agree on every element, their sums over the set are equal.
Finset.mem_filter.mp
If an element belongs to the filtered subset of elements satisfying a predicate, it belongs to the ambient set and satisfies the predicate.
False.elim
From False, any proposition follows (principle of explosion).
Finset.card_univ
The cardinality of the universal finset of a finite type is the cardinality of the underlying type.
Fintype.card_fin
The finite type Fin n has cardinality n.
mul_nonneg
The product of two non-negative real numbers is non-negative.
div_nonneg
The quotient of a non-negative real number by a non-negative (or positive) real number is non-negative.
sub_nonneg.symm
A real number b is less than or equal to a if and only if 0 ≤ a - b.
le_trans
The less-than-or-equal relation is transitive: if a ≤ b and b ≤ c, then a ≤ c.
mul_le_mul_of_nonneg_left
Multiplying both sides of an inequality b ≤ c by a non-negative number a preserves the inequality: a * b ≤ a * c.

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

lemma balanced_high_count_chore_mms_bound_sum_bivalued {α : Type*} [DecidableEq α] (s : Finset α) (u : α → ℝ) (a r : ℝ)    (hu : ∀ g ∈ s, u g = a ∨ u g = r * a) :    ∑ g ∈ s, u g = (s.card : ℝ) * a + ((s.filter fun g => u g = r * a).card : ℝ) * ((r - 1) * a) := by  classical  have hsum := (Finset.sum_filter_add_sum_filter_not s (fun g => u g = r * a) u).symm  have hcard := (Finset.card_filter_add_card_filter_not (s := s) (fun g => u g = r * a)).symm  have h1 : ∑ g ∈ s.filter (fun g => u g = r * a), u g = (s.filter (fun g => u g = r * a)).card * (r * a) := by    rw [Finset.sum_congr rfl (fun x hx => (Finset.mem_filter.mp hx).2)]    simp  have h2 : ∑ g ∈ s.filter (fun g => ¬ u g = r * a), u g = (s.filter (fun g => ¬ u g = r * a)).card * a := by    have : ∑ g ∈ s.filter (fun g => ¬ u g = r * a), u g = ∑ g ∈ s.filter (fun g => ¬ u g = r * a), a := by      refine Finset.sum_congr rfl (fun x hx => ?_)      have hx' := Finset.mem_filter.mp hx      cases hu x hx'.1 with      | inl h => exact h      | inr h => exact False.elim (hx'.2 h)    rw [this]    simp  rw [hsum, h1, h2]  have hcard_cast : (s.card : ℝ) = ((s.filter (fun g => u g = r * a)).card : ℝ) + ((s.filter (fun g => ¬ u g = r * a)).card : ℝ) := by    exact_mod_cast hcard  linear_combination    -a * hcard_casttheorem balanced_high_count_chore_mms_bound (n k : ℕ) (hn : 2 ≤ n) (hk : 2 ≤ k) (r : ℝ) (hr : 1 ≤ r) (a : ℝ) (ha : 0 < a) (u : Fin (n*k) → ℝ) (hu : ∀ g, u g = a ∨ u g = r*a) (S : Finset (Fin (n*k))) (hs : S.card = k) (hh : n * ((S.filter fun g => u g = r*a).card) ≤ ((Finset.univ.filter fun g => u g = r*a).card) + n - 1) : additive_valuation u S ≤ ((r+1)/2) * chore_maximin_share n u := by  classical  have : NeZero n := ⟨by omega⟩  have hprop := chore_prop_share_le_maximin_share n (n * k) u  have hS_sum : ∑ g ∈ S, u g = (k : ℝ) * a + ((S.filter fun g => u g = r * a).card : ℝ) * ((r - 1) * a) := by    have := balanced_high_count_chore_mms_bound_sum_bivalued S u a r (fun g _ => hu g)    rw [hs] at this    exact this  have huniv_sum : ∑ g : Fin (n * k), u g = ((n * k : ℕ) : ℝ) * a + ((Finset.univ.filter fun g => u g = r * a).card : ℝ) * ((r - 1) * a) := by    have := balanced_high_count_chore_mms_bound_sum_bivalued (Finset.univ : Finset (Fin (n * k))) u a r (fun g _ => hu g)    simp only [Finset.card_univ, Fintype.card_fin] at this    exact this  change ∑ g ∈ S, u g ≤ ((r + 1) / 2) * chore_maximin_share n u  rw [hS_sum]  set hS := ((S.filter fun g => u g = r * a).card : ℝ)  set hU := ((Finset.univ.filter fun g => u g = r * a).card : ℝ)  set P := (∑ g : Fin (n * k), u g) / (n : ℝ)  have hP_eq : P = (k : ℝ) * a + (hU / (n : ℝ)) * ((r - 1) * a) := by    dsimp [P]    rw [huniv_sum]    push_cast    have : (n : ℝ) ≠ 0 := by positivity    field_simp  have hh_real : (n : ℝ) * hS ≤ hU + (n : ℝ) - 1 := by    have h2 : n * (S.filter fun g => u g = r * a).card + 1 ≤ (Finset.univ.filter fun g => u g = r * a).card + n := by omega    have h3 : ((n * (S.filter fun g => u g = r * a).card + 1 : ℕ) : ℝ) ≤ (((Finset.univ.filter fun g => u g = r * a).card + n : ℕ) : ℝ) := by exact_mod_cast h2    push_cast at h3    linarith  have hn_pos : 0 < (n : ℝ) := by positivity  have hr_sub : 0 ≤ r - 1 := by linarith  have ha_nonneg : 0 ≤ a := by linarith  have h_da : 0 ≤ (r - 1) * a := mul_nonneg hr_sub ha_nonneg  have hk_cast : 2 ≤ (k : ℝ) := by exact_mod_cast hk  have hP_ge : 2 * a ≤ P := by    have h1 : (k : ℝ) * a ≤ P := by      rw [hP_eq]      have : 0 ≤ (hU / (n : ℝ)) * ((r - 1) * a) := by positivity      linarith    have h2 : 2 * a ≤ (k : ℝ) * a := by nlinarith    linarith  have h_step1 : (k : ℝ) * a + hS * ((r - 1) * a) ≤ P + (r - 1) * a := by    have hdiff : (P + (r - 1) * a) - ((k : ℝ) * a + hS * ((r - 1) * a)) =        ((r - 1) * a) * ((hU + (n : ℝ) - (n : ℝ) * hS) / (n : ℝ)) := by      rw [hP_eq]      have : (n : ℝ) ≠ 0 := by positivity      field_simp      ring    rw [sub_nonneg.symm, hdiff]    apply mul_nonneg h_da    apply div_nonneg _ (by positivity)    linarith  have h_step2 : P + (r - 1) * a ≤ ((r + 1) / 2) * P := by    have hdiff : ((r + 1) / 2) * P - (P + (r - 1) * a) = ((r - 1) / 2) * (P - 2 * a) := by      ring    rw [sub_nonneg.symm, hdiff]    exact mul_nonneg (by linarith) (by linarith)  have h_le_P : (k : ℝ) * a + hS * ((r - 1) * a) ≤ ((r + 1) / 2) * P := le_trans h_step1 h_step2  have hr1 : 0 ≤ (r + 1) / 2 := by linarith  have h_final : ((r + 1) / 2) * P ≤ ((r + 1) / 2) * chore_maximin_share n u :=    mul_le_mul_of_nonneg_left hprop hr1  exact le_trans h_le_P h_final
See it in the graphDiscuss this resultChallenge it