Theorem B.3 — PROP and ordinal MMS with sublinear deficit
OpenSublinearChoresMMS.Disposal.Supplement.theorem_B_3choresfair-divisionmaximin-sharep2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Put . There exist an absolute and an integer function , both chosen before all cost profiles, such that for every ,
Every finite nonnegative real additive-chores instance then has one finite law of complete allocations satisfying
for every agent in every positive-weight outcome. The second benchmark is the cost minimax over all -partitions of the original full chore set. Proportionality continues to use denominator . Zero costs, zero benchmarks, ties, empty chores and are included; bounded may use . This is an ordinal guarantee for every agent, rather than a bound on the number of exceptions.
Differences from the source:
- reading: the tilde-O n^(2/3) bound in the short Appendix B theorem → one absolute C multiplying n^(2/3)(log(2n))^(2/3), before all instance data; reason: equation (3), printed 31 / PDF 32, supplies this logarithmic power with a constant independent of k; log(2n) and enlarging C include bounded positive n
- encoding: d=n minus tilde-O n^(2/3) → one integer function d(n) chosen before all cost profiles, with 1≤d(n)≤n and n-d(n)≤C*f(n); reason: the proof chooses k from the instance-independent residual bound (3); bounded n may use d=1 and the PROP denominator remains n
- 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_Supplement_AppendixPacking
Formal statement
namespace SublinearChoresMMS.Disposal.Supplement
/-- Theorem B.3, printed 32 / PDF 33; (3) fixes the rate independently of k.
d is chosen before every cost profile, and PROP still uses n. -/
theorem theorem_B_3 :
∃ C : ℝ, 0 < C ∧ ∃ d : ℕ → ℕ,
∀ n : ℕ, 0 < n →
(1 ≤ d n ∧ d n ≤ n ∧ ((n - d n : ℕ) : ℝ) ≤ C * appendixRate n) ∧
∀ (m : ℕ) (c : Cost n m), 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,
cost c i (bundle (P.atom a) i) ≤ costShare (c i) (d n) := by sorry
end SublinearChoresMMS.Disposal.Supplement
Source
Zehan Lin, Xiaowei Wu, Shengwei Zhou, STOC 2027 submission #845 (October 2026), Theorem B.3, printed p. 32 / PDF p. 33. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/845.pdf Rate evidence: equation (3), printed p. 31 / PDF p. 32.