Theorem 4.4 — PROP, MMS1 and exact 4/3-MMS
OpenSublinearChoresMMS.Disposal.Supplement.theorem_4_4choresfair-divisionmaximin-sharep2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let agents have arbitrary nonnegative real additive costs on a finite set of chores. There is one finite probability law of complete allocations such that
Every positive-weight outcome satisfies, for every agent , both
where is the original full-set -part cost minimax share. All clauses concern the same law. Zero costs, zero MMS, ties, empty chores and empty bundles are included. This companion theorem supplies a uniform worst-case multiplicative bound alongside MMS1 and ex-ante proportionality.
Differences from the source:
- encoding: finite agents, chores, complete partitions and finite lotteries → zero-based Fin labels, owner maps and published finite real-weight laws with positive-weight support; reason: bijections cover exactly the finite source instances, and repeated lottery atoms can be merged
- encoding: cost minimax share over all positive-part-count labelled partitions → the published costShare, the negative of the goods maximin functional on negative additive costs; reason: finite sign duality gives the same attained minimax without imposing any goods nonnegativity predicate
Preamble
import Mathlib import Definitions.Def_SublinearChoresMMS_Disposal_Setting
Formal statement
namespace SublinearChoresMMS.Disposal.Supplement
/-- Theorem 4.4, printed 16 / PDF 17. No ordering, normalization or strict
positivity assumption restricts the original nonnegative real instance. -/
theorem theorem_4_4 (n m : ℕ) (hn : 0 < n) (c : Cost n m) (hc : Nonnegative c) :
∃ P : FiniteLaw (Allocation n m),
(∀ i, P.mean (fun X => cost c i (bundle X i)) ≤ propShare c i) ∧
∀ a, 0 < P.weight a → ∀ i,
MMS1 c i (bundle (P.atom a) i) ∧
cost c i (bundle (P.atom a) i) ≤ (4 / 3 : ℝ) * mu c i := by sorry
end SublinearChoresMMS.Disposal.Supplement
Source
Zehan Lin, Xiaowei Wu, Shengwei Zhou, STOC 2027 submission #845 (October 2026), Theorem 4.4, printed p. 16 / PDF p. 17. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/845.pdf