Theorem 5.1 — finite-sample gap below the adversarial optimum
OpenSampleCRS.AlmostGreedy.Supplement.theorem_5_1contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Fix any , any finite sample bound and any family of randomized online capacity- policies using at most independent samples per element. They may know the fixed arrival order beforehand, but not . There is a finite instance with and exact mass such that
Here is the operational optimum for schemes that know , rather than the random-order constant . The policy family precedes the choice of the bad instance. Padding unused samples covers every bound of at most , including zero.
Differences from the source:
- encoding: arbitrary randomized nonanticipating policies, even with fixed order known in advance → real behavioral kernels on complete activation/action histories in arrival-position labels; reason: perfect recall on the finite observation tree represents arbitrary independent private randomness; relabelling a known order preserves all information
- encoding: the minimum conditional acceptance is strictly below γ → there exists a positive-bias element with Pr[A_i]<γ p_i; reason: on a finite exact-positive-mass instance these formulations are equivalent and avoid an empty-set minimum
Preamble
import Mathlib import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_sampleModel
Formal statement
namespace SampleCRS.AlmostGreedy.Supplement
/-- Theorem 5.1, p.22. finite-sample gap below the adversarial optimum. -/
theorem theorem_5_1 (k m : ℕ) (hk : 2 ≤ k) (π : ∀ n : ℕ, SamplePolicy n m) :
∃ (n : ℕ) (p : Fin n → ℝ), ValidProb p ∧ (∑ i, p i) = (k : ℝ) ∧
∃ i : Fin n, 0 < p i ∧ sampleAccept k (π n) p i < gammaAdv k * p i := by sorry
end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Theorem 5.1, p. 22