§4.1 Bounding ALG — assignments from the selected flow
ProvedOnlineStochMatching.SuggestedMatching.bounding_algballs-in-binsonline-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-matching
Let be the advertisers covered by any maximum integral expected-instance matching . For every , there are constants and independent of the instance, , and its labelling such that, whenever ,
This is the assignment side of Theorem 4's analysis. The paper writes the failure probability as ; the constants are quantified before the instance to make that uniform claim explicit.
Preamble
import Definitions.Def_OnlineStochMatching_SuggestedMatching_Algorithm
Formal statement
namespace OnlineStochMatching.SuggestedMatching
/-- Section 4.1, "Bounding ALG": the paper's exponential concentration claim. -/
theorem bounding_alg :
∀ ε : ℝ, 0 < ε → ∃ δ : ℝ, 0 < δ ∧ ∃ N : ℕ,
∀ (A I : Type) [Fintype A] [Fintype I]
(inst : Instance A I) (hn : N ≤ inst.n)
(M : Finset (A × I)) (hM : IsMaxBMatching inst M)
(label : inst.Copy → Option A) (hlabel : IsLabelling inst M label),
runProbability inst (fun ω =>
(1 - Real.exp (-1)) * (coveredAds M).card - ε * (inst.n : ℝ) ≤
(algorithm inst label ω : ℝ)) ≥
1 - Real.exp (-δ * (inst.n : ℝ)) := by sorry
end OnlineStochMatching.SuggestedMatching
Source
Feldman, Mehta, Mirrokni, Muthukrishnan, Online Stochastic Matching: Beating 1-1/e, arXiv:0905.4100v1, p. 5, §4.1, Bounding ALG
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.