Theorem 1.2 — every -agent instance with -partitioning valuations admits a -MMS allocation
OpenSubadditiveMMS580.Amplification.Supplement.theorem_1_2fair-divisionmaximin-sharep2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1q-partitioning
Let be an integer and let be the function of equation (1):
Every instance with agents whose valuations on a finite set of goods belong to admits a -MMS allocation: there are pairwise disjoint bundles with
In particular this gives a -MMS allocation when and a -MMS allocation when .
This companion theorem gives constant MMS guarantees whenever is bounded below, for valuation classes strictly between XOS and subadditive; it is not used in the proof of the mission's goal (Theorem 1.1).
Differences from the source:
- encoding: an n-agent instance → n : ℕ with 1 ≤ n; reason: an instance has at least one agent; c = q/n is then positive
- encoding: ρ on the closed pieces of (1), which agree at c = 1, 6/5, 2 → ρ on the half-open pieces (−∞,1], (1,6/5], (6/5,2], (2,∞); reason: adjacent formulas agree at the break points, so the value at every c > 0 is the same
- encoding: partitions into nonempty groups (Definition 2.1) → 1 ≤ t ≤ q and C : Fin t → Finset (Fin m) with nonempty, pairwise disjoint members whose union is S; reason: the same ordered partitions
- encoding: valuations , normalized and monotone → real set functions on Finset (Fin m) with the published IsNormalized and IsMonotone predicates; reason: normalization and monotonicity give nonnegativity, so the instances are the same
- encoding: an allocation (pairwise disjoint bundles, goods may stay unassigned) → IsAllocation A (pairwise disjoint Finset bundles indexed by Fin n); reason: the source allows partial allocations (§2.1, p. 8); completing one cannot lower a monotone value
- encoding: , the maximum over ordered partitions of into possibly empty bundles of the minimum bundle value → LittleCharity.MMS.mms (v i) n univ, a supremum over labelings Fin m → Fin n of the minimum labelled bundle value; reason: a labeling is exactly an ordered partition into n possibly empty bundles; the index set is finite and nonempty for n ≥ 1, so the supremum is the maximum
Preamble
import Mathlib import Definitions.Def_SubadditiveMMS580_Amplification_Supplement_Partitioning import Definitions.Def_MultiAllocToAlloc_Subadditive_Valuation import Definitions.Def_MultiAllocToAlloc_Subadditive_Allocation import Definitions.Def_LittleCharity_MMS_Setting open MultiAllocToAlloc.Subadditive
Formal statement
namespace SubadditiveMMS580.Amplification.Supplement
/-- Theorem 1.2 (Partitioning valuations; Li–Sun, STOC 2027 submission #580, p. 3): for every
integer `q ≥ 2`, every `n`-agent instance (`n ≥ 1`) with valuations in `Q_q` on the goods
`Fin m` admits a `ρ(q/n)`-MMS allocation, with `ρ` the four-branch function of eq. (1). -/
theorem theorem_1_2 (q : ℕ) (hq : 2 ≤ q) (n : ℕ) (hn : 1 ≤ n) {m : ℕ}
(v : Fin n → Finset (Fin m) → ℝ) (hv : ∀ i, IsQPartitioning q (v i)) :
∃ A : Fin n → Finset (Fin m), IsAllocation A ∧
∀ i : Fin n, rho ((q : ℝ) / n) * LittleCharity.MMS.mms (v i) n Finset.univ
≤ v i (A i) := by sorry
end SubadditiveMMS580.Amplification.Supplement
Source
Bo Li, Ankang Sun, Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations, STOC 2027 submission #580 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/580.pdf, sha256 7de124b5706e9e49301a281a1eb418a8ae32d04bf4cf0941b969cc3cde85e485, Theorem 1.2, p. 3 (PDF p. 3)