Eq. (7), p. 10 — a(e)·Pr[e is free] ≥ ã(p_e y_e)·Pr[e is safe]
ProvedOfflineStochMatch.Attenuation.eq_7attenuationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-orderstochastic-matching
Let Algorithm 1 run on a finite graph with activeness probabilities , patience values , probing probabilities , and an attenuation function mapping into , so that edge has attenuation . Then for every edge ,
The inequality holds because a safe edge is free. It reduces the goal theorem to a lower bound on the probability of the event safe, which depends only on the edges incident to the endpoints of .
Formalization Note Since , both sides carry the same factor. LP feasibility is not needed for this step and is not assumed; only (3c) is.
Preamble
import Mathlib import Definitions.Def_OfflineStochMatch_Attenuation_Setting
Formal statement
namespace OfflineStochMatch.Attenuation
theorem eq_7 {V E : Type} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
(G : EdmondsMatching65.Polyhedron.Graph V E) (p y : E → ℝ) (t : V → ℕ∞) (aT : ℝ → ℝ)
(hp : ∀ f, 0 ≤ p f ∧ p f ≤ 1) (hy : ∀ f, 0 ≤ y f ∧ y f ≤ 1)
(haT : ∀ z ∈ Set.Icc (0 : ℝ) 1, aT z ∈ Set.Icc (0 : ℝ) 1) (e : E) :
aT (p e * y e) * probSafe G p t y aT e ≤ aT (p e * y e) * probFree G p t y aT e := by sorry
end OfflineStochMatch.Attenuation
Source
Brubach, Grammel, Ma, MacRury, Srinivasan, Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes, arXiv:2106.06892v3, p. 10, Eq. (7) (safe event defined on p. 9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.