Theorem 3.2 — single-sample adversarial impossibility
OpenSampleCRS.AlmostGreedy.Supplement.theorem_3_2contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Consider any family of randomized single-sample online policies for capacity one. Each policy sees its ground-set size, the whole independent Bernoulli sample row and the fixed arrival order in advance; its decisions use only revealed activations, past actions and private randomness, with no access to the hidden vector . There is a finite admissible instance and a positive-bias element for which
Consequently no such family is universally -balanced in adversarial order. The bad instance is chosen after the entire family, so a different probability-tailored policy cannot be selected for each vector.
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: nonexistence of a universally 1/2-balanced scheme → a bad positive-bias element for each policy family; reason: negating the universal balance condition gives exactly this witness; unconditional acceptance < p_i/2 is equivalent when p_i>0
Preamble
import Mathlib import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_sampleModel
Formal statement
namespace SampleCRS.AlmostGreedy.Supplement
/-- Theorem 3.2, p.9. single-sample adversarial impossibility. -/
theorem theorem_3_2 (π : ∀ n : ℕ, SamplePolicy n 1) :
∃ (n : ℕ) (p : Fin n → ℝ), ValidProb p ∧ (∑ i, p i) ≤ 1 ∧
∃ i : Fin n, 0 < p i ∧ sampleAccept 1 (π n) p i < (1 / 2 : ℝ) * p i := by sorry
end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Theorem 3.2, p. 9