Theorem 4 — suggested matching achieves a tight factor
ProvedOnlineStochMatching.SuggestedMatching.theorem_4Fix the suggested matching algorithm on any finite integer-frequency online stochastic matching instance. For every , there exist and independent of the instance, of which maximum integral flow is selected, and of its random-choice labelling such that, for ,
The factor is tight: on the complete bipartite family with , every maximum expected-instance matching and every valid labelling have in every scenario and ; the expected ratio tends to as .
Formalization Note The paper states a high-probability approximation factor. Its proof yields the displayed additive error without assuming ; a multiplicative ratio with an arbitrary small error follows when that further growth condition holds. The theorem keeps all integer and represents both arrival and algorithm randomness by independent uniform draws of labelled copies.
import Definitions.Def_OnlineStochMatching_SuggestedMatching_Algorithm
namespace OnlineStochMatching.SuggestedMatching
/-- Theorem 4: additive high-probability guarantee and a complete-graph family
whose exact expected ratio approaches `1 - 1/e`. -/
theorem theorem_4 :
(∀ ε : ℝ, 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)) * (optimum inst ω : ℝ) - ε * (inst.n : ℝ) ≤
(algorithm inst label ω : ℝ)) ≥
1 - Real.exp (-δ * (inst.n : ℝ))) ∧
(∀ (n : ℕ) (hn : 0 < n),
let inst := completeInstance n hn
∀ (M : Finset (Fin n × Fin n)) (hM : IsMaxBMatching inst M)
(label : inst.Copy → Option (Fin n)) (hlabel : IsLabelling inst M label),
(∀ ω : Fin inst.n → inst.Copy, optimum inst ω = n) ∧
expectedAlgorithm inst label =
(n : ℝ) * (1 - (1 - 1 / (n : ℝ)) ^ n)) ∧
Filter.Tendsto (fun n : ℕ => 1 - (1 - 1 / (n : ℝ)) ^ n)
Filter.atTop (nhds (1 - Real.exp (-1))) := by sorry
end OnlineStochMatching.SuggestedMatching
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.