chore_prop_share_le_maximin_share
For 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 most the chore maximin share.
Statement
theorem chore_prop_share_le_maximin_share (n m : ℕ) [NeZero n] (u : Fin m → ℝ) :
(∑ e : Fin m, u e) / (n : ℝ) ≤ chore_maximin_share n u- Source
- step towards ex_post_mms_chore_lottery_below_four_thirds
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
- 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…
- additive_valuation_bundle_sum_iteAn additive value of an allocated bundle equals the sum over all goods of the item value when that good has the specified owner, and zero…
- Used by 2
- balanced_high_count_chore_mms_boundFor 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…
- op913_randomized_mms_barrier_under_upgrade_recourseOpen problem OP-913 (arXiv:2611.00432, after Thm 4.1): for every number of agents n ≥ 2, has_randomized_online_mms_barrier_breaker n…
The proof, explained
The chore maximin share is defined as the infimum over all partitions of the maximum chore cost assigned to any agent. For any partition, the sum of all bundle costs equals the total cost of all items. By an averaging argument, at least one bundle must have cost at least the proportional share (the total cost divided by n), meaning the maximum bundle cost in any partition is at least the proportional share. Taking the infimum over all partitions preserves this inequality, establishing the bound.
To bound the chore maximin share from below by the proportional share, it suffices to show that for any partition P, the proportional share is at most the maximum bundle cost in P.
By definition, the chore maximin share is the infimum over all partitions P of the supremum of bundle costs under P. By le_ciInf, a lower bound on an infimum follows from showing that the lower bound holds for every partition P. We fix an arbitrary partition P of items to agents.
uses
le_ciInfchange (∑ e : Fin m, u e) / (n : ℝ) ≤ ⨅ P : Fin m → Fin n, ⨆ k : Fin n, additive_valuation u (bundle_of P k) apply le_ciInf intro P
The sum of the costs of all bundles in the partition P equals the total cost of all m items.
We rewrite the valuation of each bundle as a sum over items using an indicator for whether the item is assigned to that bundle (via additive_valuation_bundle_sum_ite). Interchanging the order of summation with Finset.sum_comm, each item belongs to exactly one bundle in the partition P, so summing over the agents reduces to the cost of that item, leaving the total cost of all items.
uses
additive_valuation_bundle_sum_ite,Finset.sum_commhave hsum : ∑ k : Fin n, additive_valuation u (bundle_of P k) = ∑ e : Fin m, u e := by simp_rw [additive_valuation_bundle_sum_ite] rw [Finset.sum_comm] simp
There exists at least one bundle k in the partition P whose cost is at least the proportional share.
Suppose, for contradiction, that every bundle has cost strictly less than the proportional share (the total cost divided by n). Since n ≥ 1, the set of agents is nonempty (Finset.univ_nonempty), so summing these strict inequalities over all n agents (Finset.sum_lt_sum_of_nonempty) implies that the total cost across all bundles is strictly less than the sum of n copies of the proportional share. The left-hand sum equals the total item cost by our previous identity, while the right-hand sum simplifies to n times the average, which cancels to the total item cost since n ≠ 0 (Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul, Nat.cast_ne_zero.mpr, NeZero.ne, mul_div_cancel₀). This yields that the total cost is strictly less than itself, contradicting the irreflexivity of strict inequality (lt_irrefl).
uses
Finset.sum_lt_sum_of_nonempty,Finset.univ_nonempty,Finset.sum_const,Finset.card_univ,Fintype.card_fin,nsmul_eq_mul,Nat.cast_ne_zero.mpr,NeZero.ne,mul_div_cancel₀,lt_irreflhave h_ex : ∃ k : Fin n, (∑ e : Fin m, u e) / (n : ℝ) ≤ additive_valuation u (bundle_of P k) := by by_contra! h have hlt : ∑ k : Fin n, additive_valuation u (bundle_of P k) < ∑ k : Fin n, (∑ e : Fin m, u e) / (n : ℝ) := by apply Finset.sum_lt_sum_of_nonempty Finset.univ_nonempty intro i _ exact h i rw [hsum, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] at hlt have hn : (n : ℝ) ≠ 0 := Nat.cast_ne_zero.mpr (NeZero.ne n) rw [mul_div_cancel₀ _ hn] at hlt exact lt_irrefl _ hlt
The proportional share is at most the supremum of bundle costs under partition P.
Let k be a bundle whose cost is at least the proportional share. The set of bundle costs is the image of a finite domain, hence finite (Set.finite_range) and bounded above. Therefore, the cost of bundle k is at most the supremum over all bundles in P (le_ciSup). By transitivity (le_trans), the proportional share is at most this supremum.
uses
Set.finite_range,le_ciSup,le_transrcases h_ex with ⟨k, hk⟩ have hbdd : BddAbove (Set.range (fun k : Fin n => additive_valuation u (bundle_of P k))) := (Set.finite_range _).bddAbove exact le_trans hk (le_ciSup hbdd k)
le_ciInf- A lower bound for every element of a family is also a lower bound for the infimum of that family.
additive_valuation_bundle_sum_ite- The additive valuation of a bundle assigned to an agent equals the sum over all items of the item's cost if assigned to that agent, and 0 otherwise.
Finset.sum_comm- The order of summation in a double sum over finite sets can be exchanged.
Finset.sum_lt_sum_of_nonempty- If a finite set is nonempty and f(i) < g(i) for all elements i in the set, then the sum of f over the set is strictly less than the sum of g.
Finset.univ_nonempty- The universe of a nonempty finite type is a nonempty finite set.
Finset.sum_const- Summing a constant value over a finite set equals the cardinality of the set multiplied by the constant.
Finset.card_univ- The cardinality of the universe of a finite type equals the cardinality of the type.
Fintype.card_fin- The finite set Fin n has cardinality n.
nsmul_eq_mul- Scalar multiplication by a natural number n equals algebraic multiplication by n cast to the ring.
Nat.cast_ne_zero.mpr- If a natural number is nonzero, its cast to the real numbers is nonzero.
NeZero.ne- An element with a NeZero typeclass instance is not equal to zero.
mul_div_cancel₀- For any nonzero b, multiplying b by a / b yields a.
lt_irrefl- Strict inequality is irreflexive; no value is strictly less than itself.
Set.finite_range- The range of a function with a finite domain is a finite set.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
le_ciSup- Any value in the range of a function bounded above is at most the supremum of that function.
- At line 10, the simplifier evaluates the double sum of indicator functions by recognizing that each item is assigned to exactly one bundle in the partition.
- At line 24, the expression `(Set.finite_range _).bddAbove` uses Lean dot notation to invoke `Set.Finite.bddAbove`, deducing that any finite set of real numbers is bounded above.
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.
/-- For 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 most the chore maximin share. -/theorem chore_prop_share_le_maximin_share (n m : ℕ) [NeZero n] (u : Fin m → ℝ) : (∑ e : Fin m, u e) / (n : ℝ) ≤ chore_maximin_share n u := by change (∑ e : Fin m, u e) / (n : ℝ) ≤ ⨅ P : Fin m → Fin n, ⨆ k : Fin n, additive_valuation u (bundle_of P k) apply le_ciInf intro P have hsum : ∑ k : Fin n, additive_valuation u (bundle_of P k) = ∑ e : Fin m, u e := by simp_rw [additive_valuation_bundle_sum_ite] rw [Finset.sum_comm] simp have h_ex : ∃ k : Fin n, (∑ e : Fin m, u e) / (n : ℝ) ≤ additive_valuation u (bundle_of P k) := by by_contra! h have hlt : ∑ k : Fin n, additive_valuation u (bundle_of P k) < ∑ k : Fin n, (∑ e : Fin m, u e) / (n : ℝ) := by apply Finset.sum_lt_sum_of_nonempty Finset.univ_nonempty intro i _ exact h i rw [hsum, Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] at hlt have hn : (n : ℝ) ≠ 0 := Nat.cast_ne_zero.mpr (NeZero.ne n) rw [mul_div_cancel₀ _ hn] at hlt exact lt_irrefl _ hlt rcases h_ex with ⟨k, hk⟩ have hbdd : BddAbove (Set.range (fun k : Fin n => additive_valuation u (bundle_of P k))) := (Set.finite_range _).bddAbove exact le_trans hk (le_ciSup hbdd k)