Eq. (7), p. 10 — a safe edge is free, so a(e)·Pr[e is free] ≥ ã(p_e y_e)·Pr[e is safe]
ProvedOfflineStochMatch.InfinitePatience.eq_7p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-orderstochastic-matching
Let be a graph with activeness probabilities , patiences , a feasible solution of LP (3), and an attenuation function mapping into . For every edge , under Algorithm 1,
Here is safe when, before is processed, at most probes were made at each endpoint , and no edge sharing an endpoint with and processed earlier has . Being safe implies being free, which gives the inequality. The safe event depends only on the edges at the endpoints of , which is what makes its probability computable.
Formalization Note. The page's is (no is defined in the paper).
Preamble
import Mathlib import Definitions.Def_OfflineStochMatch_InfinitePatience_Setting
Formal statement
namespace OfflineStochMatch.InfinitePatience
/-- (7), p. 10: a safe edge is free, so `a(e) · Pr[e is free] ≥ ã(p_e y_e) Pr[e is safe]`. -/
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 : LPFeasible G p t y)
(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.InfinitePatience
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.