Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sample policies and the full-information adversarial optimum

Definition
SampleCRS_AlmostGreedy_Supplement_sampleModel

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

contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability

A sample policy sees all mmm Bernoulli sample rows before it begins and returns an online kernel. The same policy is used for every hidden vector ppp. The sample array, online activations and subsequent kernel random choices are independent in the experiment. Each sample row has the published activation law, and the sample-array weight is

w(Y)=∏s=1mwp(Y(s)).w(Y)=\prod_{s=1}^m w_p(Y^{(s)}).w(Y)=s=1∏m​wp​(Y(s)).

Sample acceptance averages the actual kernel law over this array. With m=0m=0m=0, the empty product is one.

For capacity kkk, let γadv(k)\gamma_{\rm adv}(k)γadv​(k) be the supremum of c∈[0,1]c\in[0,1]c∈[0,1] attainable by full-information online schemes uniformly over every finite nnn and every admissible vector of mass kkk:

γadv(k)=sup⁡{c∈[0,1]: ∀n,p, ∑ipi=k⇒∃πp, Pr⁡[Ai]≥cpi}.\gamma_{\rm adv}(k)=\sup\{c\in[0,1]:\ \forall n,p,\ \sum_i p_i=k\Rightarrow\exists\pi_p,\ \Pr[A_i]\ge cp_i\}.γadv​(k)=sup{c∈[0,1]: ∀n,p, i∑​pi​=k⇒∃πp​, Pr[Ai​]≥cpi​}.

Here full-information policies may depend on ppp; sample policies cannot. This bounded, nonempty supremum defines the adversarial optimum independently of any impossibility conclusion or ODE characterization.

Definition code
import Mathlib
import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_onlineKernel

namespace SampleCRS.AlmostGreedy.Supplement

/-- All samples are visible before the run. There is no hidden `p` argument. -/
abbrev SamplePolicy (n m : ℕ) := (Fin m → Fin n → Bool) → OnlineKernel n

noncomputable def sampleWeight {n m : ℕ} (p : Fin n → ℝ)
    (Y : Fin m → Fin n → Bool) : ℝ :=
  ∏ s, activationWeight p (Y s)

noncomputable def sampleAccept {n m : ℕ} (k : ℕ) (π : SamplePolicy n m)
    (p : Fin n → ℝ) (i : Fin n) : ℝ :=
  ∑ Y, sampleWeight p Y * policyAccept k (π Y) p i

/-- Full-information adversarial balance: the policy may be chosen after seeing p.
Relabelling a fixed, even advance-known, order to `0,…,n-1` loses no information. -/
def AdvAttainable (k : ℕ) (c : ℝ) : Prop :=
  c ∈ Set.Icc (0 : ℝ) 1 ∧
  ∀ (n : ℕ) (p : Fin n → ℝ), ValidProb p → (∑ i, p i) = (k : ℝ) →
    ∃ π : OnlineKernel n, BalancedInstance k c π p

/-- The operational known-p adversarial optimum, not the random-order constant.
The defining set is bounded by 1; 0 is attainable by rejecting every arrival. -/
noncomputable def gammaAdv (k : ℕ) : ℝ := sSup {c : ℝ | AdvAttainable k c}

end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), §2, pp.5–6; §5.2, p.22

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