Lemma 5.1 — additive rounding loses at most the largest coefficient:
OpenSubadditiveMMS580.Amplification.Supplement.lemma_5_1fair-divisionfractional-allocationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1rounding
Let be nonnegative additive valuations on a finite set , given by coefficients , and let be a fractional allocation: numbers with for every good . Then there are pairwise disjoint bundles such that every agent satisfies
where (zero when is empty).
This rounding step converts the fractional auxiliary value in the reservation theorem (Theorem 5.2) into integral bundles.
Differences from the source:
- encoding: agents i (any finite number) → agents Fin r for an arbitrary r ≥ 0; reason: same instances; r = 0 is trivial
Preamble
import Mathlib import Definitions.Def_SubadditiveMMS580_Amplification_Supplement_Reservation import Definitions.Def_MultiAllocToAlloc_Subadditive_Valuation import Definitions.Def_MultiAllocToAlloc_Subadditive_Allocation open MultiAllocToAlloc.Subadditive MeasureTheory
Formal statement
namespace SubadditiveMMS580.Amplification.Supplement
/-- Lemma 5.1 (Li–Sun, STOC 2027 submission #580, p. 31): let `ṽ_i` (`i` among `r` agents) be
nonnegative additive valuations on the finite set `M = Fin m` and `f` a fractional allocation
(`f_ig ≥ 0`, `∑_i f_ig ≤ 1` for every good `g`). There are pairwise disjoint bundles `B_i ⊆ M`
with `ṽ_i(B_i) ≥ ∑_{g ∈ M} ṽ_i(g) f_ig − ‖ṽ_i‖∞` for every agent `i`. -/
theorem lemma_5_1 {r m : ℕ} (vt : Fin r → Fin m → ℝ) (hvt : ∀ i g, 0 ≤ vt i g)
(f : Fin r → Fin m → ℝ) (hf : ∀ i g, 0 ≤ f i g) (hfsum : ∀ g, ∑ i, f i g ≤ 1) :
∃ B : Fin r → Finset (Fin m), IsAllocation B ∧
∀ i : Fin r, ∑ g, vt i g * f i g - supNorm (vt i) ≤ ∑ g ∈ B i, vt i g := 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, Lemma 5.1, p. 31 (PDF p. 31)