AFTD Auto-Formalizing Theoretical Domains

chore_prop_share_le_maximin_share

theoremverified

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

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.

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

    lines 4–6

    uses le_ciInf

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

    lines 7–10

    uses additive_valuation_bundle_sum_ite, Finset.sum_comm

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

    lines 11–21

    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_irrefl

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

    lines 22–25

    uses Set.finite_range, le_ciSup, le_trans

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

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

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