balanced_high_count_chore_mms_bound
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
- all_agent_bivalued_equal_marginal_divisible_choresFor every n at least two and k at least two, any common ratio r at least one, and any n-agent scaled bivalued additive cost profile on n*k…
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.
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.
uses
Finset.sum_filter_add_sum_filter_not,Finset.card_filter_add_card_filter_not,Finset.sum_congr,Finset.mem_filter.mpclassical 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
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.
uses
Finset.sum_congr,Finset.mem_filter.mp,False.elimhave 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
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.
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
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).
uses
chore_prop_share_le_maximin_shareclassical have : NeZero n := ⟨by omega⟩ have hprop := chore_prop_share_le_maximin_share n (n * k) u
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).
uses
balanced_high_count_chore_mms_bound_sum_bivalued,Finset.card_univ,Fintype.card_finhave 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
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.
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
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.
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
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.
uses
mul_nonneghave 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
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.
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
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.
uses
sub_nonneg.symm,mul_nonneg,div_nonneghave 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
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.
uses
sub_nonneg.symm,mul_nonneghave 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)
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.
uses
le_trans,mul_le_mul_of_nonneg_lefthave 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.
- Casting the integer inequality n * hS ≤ hU + n - 1 to real numbers uses an intermediate step n * hS + 1 ≤ hU + n to avoid truncation of natural number subtraction.
- Algebraic identities and simplifications (such as rewriting the difference between P + (r - 1) * a and the bundle cost) are checked using field_simp and ring.
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.
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