Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2 — single-sample adversarial impossibility

Open
SampleCRS.AlmostGreedy.Supplement.theorem_3_2

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

contention-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 ppp. There is a finite admissible instance and a positive-bias element for which

∑ipi≤1,Ci,π(p)<1/2.\sum_i p_i\le1,\qquad C_{i,\pi}(p)<1/2.i∑​pi​≤1,Ci,π​(p)<1/2.

Consequently no such family is universally 1/21/21/2-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

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me