Lemma 5.1 — uniform acceptance-tail and moving-prefix limits
OpenSampleCRS.AlmostGreedy.Supplement.lemma_5_1contention-resolutionp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probability
Fix and the optimal known-probability adversarial balance . Consider any sequence of instances, with possibly varying sizes and policies, satisfying , and . Each policy is -balanced on its instance and may have full distributional knowledge. Let be its number of acceptances in the first arrivals, and interpolate linearly at the prefix masses .
With defined by (11),
Moreover, for every sequence and every real with ,
This includes every moving-prefix limit, not just the two-block constructions used later. The balance assumption need only hold at each indicated instance, as in the proof in Appendix A.5.
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: positive-bias instances, interpolation and h₂ in (11) → dependent finite sizes, half-open affine segments, the actual terminal node and explicit hSecond; reason: strictly positive p gives distinct interpolation nodes; hSecond is exactly formula (11) with the operational optimum
- generalization: a sequence of γ-balanced OCRSs and instances → arbitrary kernels with γ balance at their indicated instances; reason: Appendix A.5 uses only the acceptance inequalities at each indicated instance; every globally γ-balanced scheme specializes to these kernels
Preamble
import Mathlib import Definitions.Def_SampleCRS_AlmostGreedy_Supplement_prefixLimits
Formal statement
namespace SampleCRS.AlmostGreedy.Supplement
/-- Lemma 5.1, p.24. uniform acceptance-tail and moving-prefix limits. -/
theorem lemma_5_1 (k : ℕ) (hk : 2 ≤ k) (n : ℕ → ℕ)
(p : (r : ℕ) → Fin (n r) → ℝ) (π : (r : ℕ) → OnlineKernel (n r))
(hp : ∀ r, ValidProb (p r)) (hpos : ∀ r i, 0 < p r i)
(hmass : ∀ r, (∑ i, p r i) = (k : ℝ))
(hbal : ∀ r, BalancedInstance k (gammaAdv k) (π r) (p r))
(hsmall : Filter.Tendsto (fun r => maxBias (p r)) Filter.atTop (nhds 0)) :
TendstoUniformlyOn (fun r t => interpolateTail k (π r) (p r) 2 t)
(hSecond k) Filter.atTop (Set.Icc 0 (k : ℝ)) ∧
∀ j : ℕ → ℕ, (∀ r, j r ≤ n r) → ∀ t : ℝ,
Filter.Tendsto (fun r => prefixMass (p r) (j r)) Filter.atTop (nhds t) →
Filter.Tendsto (fun r => tailExpectation k (π r) (p r) 2 (j r))
Filter.atTop (nhds (hSecond k t)) := by sorry
end SampleCRS.AlmostGreedy.Supplement
Source
Shaddin Dughmi, Vasilis Livanos, Pranav Nuti, STOC 2027 submission #686 (October 2026), Lemma 5.1, p. 24