Lemma 3, p. 11 — ∏_{f∈E₁(r)}(1 − x a(f) y_f) ≥ e^{−x Σ_{f∈E₁(r)} y_f} for an effective attenuation
ProvedOfflineStochMatch.Attenuation.lemma_3attenuationconvexityinequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite graph with activeness probabilities and values , and let be an effective attenuation function (Definition 3), with . Fix an edge , one of its endpoints , and . Let
Then
In the proof of Theorem 1, is the arrival time of , and the left side is the conditional probability that no edge of arriving before is probed; the lemma bounds it by the value obtained in the limit of many small edges.
Formalization Note The arrival time ranges over the closed interval , as in the integral (8) that the lemma feeds.
Preamble
import Mathlib import Definitions.Def_OfflineStochMatch_Attenuation_Setting
Formal statement
namespace OfflineStochMatch.Attenuation
theorem lemma_3 {V E : Type} [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E]
(G : EdmondsMatching65.Polyhedron.Graph V E) (p y : E → ℝ) (aT : ℝ → ℝ)
(haT : IsEffective aT) (hp : ∀ f, 0 ≤ p f ∧ p f ≤ 1) (hy : ∀ f, 0 ≤ y f ∧ y f ≤ 1)
(e : E) (r : V) (hr : r ∈ G.ends e) (x : ℝ) (hx : x ∈ Set.Icc (0 : ℝ) 1) :
Real.exp (-(x * ∑ f ∈ (incident G r).filter (fun f => f ≠ e ∧ p f = 1), y f))
≤ ∏ f ∈ (incident G r).filter (fun f => f ≠ e ∧ p f = 1),
(1 - x * attProb aT p y f * y f) := 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. 11, Lemma 3 (with the definition of E(r), E_b(r) on p. 11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.