Theorem 3.1 — single-item Conservative Scaling
OpenSampleCRS.AlmostGreedy.Supplement.theorem_3_1contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be any finite ground-set size, and let the unknown activation probabilities satisfy and . Algorithm 1 scans an independent uniform random order and accepts the first active element passing its sample-dependent coin: it always passes a sample-inactive element and passes a sample-active one with probability .
For every realization the output is an active subset of cardinality at most one, and for every with ,
The probability averages the online activations, samples, independent coins and uniform order. This is the specified single-item run, separate from Algorithm 4.
Differences from the source:
- encoding: elements 1,…,n and independent Bernoulli trials → Fin n and finite product-weight expectations; reason: the label shift is a bijection and the weights are exactly the independent Bernoulli law
Preamble
import Mathlib import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_scaling
Formal statement
namespace SampleCRS.AlmostGreedy.Supplement
/-- Theorem 3.1, p.6. single-item Conservative Scaling. -/
theorem theorem_3_1 {n : ℕ} (p : Fin n → ℝ) (hp : ValidProb p) (hmass : (∑ i, p i) = 1) :
ScalingFeasible n 1 ∧
∀ i, 0 < p i → 1 - 1 / Real.exp 1 ≤ scalingC 1 (1 - 1 / Real.exp 1) p i := by sorry
end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Theorem 3.1, p. 6