Lemma B.1 — for the first admissible dyadic ,
ProvedSubadditiveMMS580.Amplification.Supplement.lemma_B_1fair-divisionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1real-inequality
For and a dyadic integer (a power of two), let
If is the first dyadic integer at least two with (so for every dyadic ), then
This turns the family of grouping guarantees into the smooth bound of Proposition 4.3.
Differences from the source:
- encoding: d dyadic, d ≥ 2, the first one with x ≤ x_d → d = 2^k with k ≥ 1, x ≤ x_{2^k}, and x_{2^{k'}} < x for every 1 ≤ k' < k; reason: the dyadic integers at least two are exactly 2^k with k ≥ 1, and 'first' means every smaller one fails x ≤ x_{d'}
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
/-- Lemma B.1 (Li–Sun, STOC 2027 submission #580, p. 42): for `x ≥ 1` and dyadic `d ≥ 2`, with
`F_d(x) = (1 − x/d)^+/(2d − 1)` and `x_d = 4d²/(6d − 1)`: if `d = 2^k` (`k ≥ 1`) is the first
dyadic integer at least two with `x ≤ x_d`, then `F_d(x) ≥ 1/(11x − 5)`. -/
theorem lemma_B_1 (x : ℝ) (hx : 1 ≤ x) (k : ℕ) (hk : 1 ≤ k)
(hle : x ≤ xd ((2 : ℝ) ^ k))
(hfirst : ∀ k' : ℕ, 1 ≤ k' → k' < k → xd ((2 : ℝ) ^ k') < x) :
1 / (11 * x - 5) ≤ Fd ((2 : ℝ) ^ k) x := 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 B.1, p. 42 (PDF p. 42)