Lemma 5.5 — exponential comparison bounds (25) and (26) on
OpenSubadditiveMMS580.Amplification.Supplement.lemma_5_5exponential-distributionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityreservation-theorem
Let and be independent mean-one exponential random variables, and for coefficients let (empty maximum zero) and .
- For every finite family of nonnegative coefficients and every ,
- Let finitely many competitors have nonnegative coefficients on the goods , put and , and let be auxiliary coefficients with . If , then
These estimates verify the hypothesis (18) of the reservation theorem for the choices of §5.4 in the proof of Theorem 1.3.
Differences from the source:
- encoding: a finite family (b_j)_j; the other agents j ≠ i in (26) → families indexed by an arbitrary finite type ι; reason: the other agents form a finite index set; the bounds do not depend on the indexing
- encoding: supp(ṽ) → the goods g with ṽ(g) ≠ 0; reason: definition of the support
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.5 (Li–Sun, STOC 2027 submission #580, p. 35): (25) for every finite family of
nonnegative coefficients `(b_j)_j`, `V = max_j b_j Z_j` and `x ≥ 0`,
`R_V(x) ≥ (3/4) x − (1/4) ∑_j b_j` and `R_V(x) ≥ (73/80) x − (1/2) ∑_j b_j`; (26) for competitors `j`
with nonnegative coefficients `c_j(g)`, `b_g = ∑_j c_j(g)`, `V_g = max_j c_j(g) Z_j`, and a
nonnegative `ṽ` with `ṽ(M) = 1`: if `L = ∑_{g ∈ supp ṽ} b_g ≤ 1` then
`∑_{g ∈ M} R_{V_g}(ṽ(g)) ≥ 1/(1 + L)`. -/
theorem lemma_5_5 :
(∀ {ι : Type} [Fintype ι] (b : ι → ℝ), (∀ j, 0 ≤ b j) → ∀ x : ℝ, 0 ≤ x →
3 / 4 * x - 1 / 4 * ∑ j, b j ≤ expComparison b x ∧
73 / 80 * x - 1 / 2 * ∑ j, b j ≤ expComparison b x) ∧
(∀ {m : ℕ} {ι : Type} [Fintype ι] (c : ι → Fin m → ℝ), (∀ j g, 0 ≤ c j g) →
∀ vt : Fin m → ℝ, (∀ g, 0 ≤ vt g) → ∑ g, vt g = 1 →
∑ g ∈ Finset.univ.filter (fun g => vt g ≠ 0), ∑ j, c j g ≤ 1 →
1 / (1 + ∑ g ∈ Finset.univ.filter (fun g => vt g ≠ 0), ∑ j, c j g) ≤
∑ g, expComparison (fun j => c j g) (vt 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.5, p. 35 (PDF p. 35)