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.InfinitePatience.lemma_3attenuationconvexityinequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a graph with and for all edges, and let be an effective attenuation function (Definition 3), with . Fix an edge , an endpoint of , and . With ,
In the paper is the arrival time on which the analysis conditions, and the product is the conditional probability that no edge of blocks by being matched before it. The lemma turns that product into an exponential in the LP mass at .
Formalization Note. The convexity in Definition 3 is assumed for ; the statement covers the closed interval over which the paper integrates.
Preamble
import Mathlib import Definitions.Def_OfflineStochMatch_InfinitePatience_Setting
Formal statement
namespace OfflineStochMatch.InfinitePatience
/-- Lemma 3, p. 11: for an effective attenuation function, an endpoint `r` of `e` and `x ∈ [0,1]`,
`∏_{f ∈ E_1(r)} (1 - x a(f) y_f) ≥ e^{-x ∑_{f ∈ E_1(r)} y_f}`, where `a(f) = ã(p_f y_f)`. -/
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 ∈ E1 G p e r, y f))
≤ ∏ f ∈ E1 G p e r, (1 - x * aT (p f * y f) * y f) := 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. 11, Lemma 3 (E(r), E_b(r) defined just before)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.