Proposition 4.3 — instances admit -MMS allocations
OpenSubadditiveMMS580.Amplification.Supplement.proposition_4_3fair-divisionmaximin-sharep2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1q-partitioning
Let be integers, and . Every instance with agents and valuations on a finite set of goods admits an -MMS allocation: there are pairwise disjoint bundles with
Here is the maximum, over ordered partitions of into possibly empty bundles, of the minimum bundle value.
It gives the first two branches of in Theorem 1.2 ( for and for ).
Differences from the source:
- reading: 'Algorithm 2 returns an α-MMS allocation on the working instance. Consequently, every instance with valuations in Q_q admits an α-MMS allocation' → the existence of an α-MMS allocation for every instance with valuations in Q_q; reason: the working instance is one such instance, so its claim is a special case of the stated conclusion; Algorithm 2 is the procedure of the proof, not a separate mathematical object
- 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
/-- Proposition 4.3 (Li–Sun, STOC 2027 submission #580, p. 22): for integers `n, q ≥ 2`, with
`x = max {1, n/q}` and `α = 1/(11x − 5)`, every instance with `n` agents and valuations in
`Q_q` on the goods `Fin m` admits an `α`-MMS allocation: pairwise disjoint bundles `A_i` with
`v_i(A_i) ≥ α · MMS_n(v_i; M)`. -/
theorem proposition_4_3 (n q : ℕ) (hn : 2 ≤ n) (hq : 2 ≤ q) {m : ℕ}
(v : Fin n → Finset (Fin m) → ℝ) (hv : ∀ i, IsQPartitioning q (v i)) :
∃ A : Fin n → Finset (Fin m), IsAllocation A ∧
∀ i : Fin n, 1 / (11 * max 1 ((n : ℝ) / q) - 5) * 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, Proposition 4.3, p. 22 (PDF p. 22)