Lemma 8, p. 17 — Σ w_i z_i ∏_{j<i}(1 − z_j) ≥ (1 − 1/e) Σ w_i z_i for Σ z_i ≤ 1 and w decreasing, ≥ 0
ProvedOfflineStochMatch.UnitPatience.lemma_8greedyinequalityone-minus-one-over-ep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For let with , and let . Then
This deterministic inequality says that greedy-by-weight on independent edges with total activation probability at most one collects a fraction of the fractional value; combined with Lemma 7 it yields Lemma 9.
Formalization Note The page's is read as (the proof uses only ). The sequences are indexed by and only the indices are constrained. is written .
Preamble
import Mathlib import Definitions.Def_OfflineStochMatch_UnitPatience_Setting
Formal statement
namespace OfflineStochMatch.UnitPatience
open Finset
theorem lemma_8 (k : ℕ) (z w : ℕ → ℝ) (hz : ∀ i ∈ Icc 1 k, 0 ≤ z i ∧ z i ≤ 1)
(hsum : ∑ i ∈ Icc 1 k, z i ≤ 1) (hw : ∀ i ∈ Icc 1 k, 0 ≤ w i)
(hmono : ∀ i ∈ Icc 1 k, ∀ j ∈ Icc 1 k, i ≤ j → w j ≤ w i) :
(1 - Real.exp (-1)) * ∑ i ∈ Icc 1 k, w i * z i
≤ ∑ i ∈ Icc 1 k, w i * z i * ∏ j ∈ Ico 1 i, (1 - z j) := by sorry
end OfflineStochMatch.UnitPatience
Source
Brubach, Grammel, Ma, MacRury, Srinivasan, Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes, arXiv:2106.06892v3, p. 17, Lemma 8, Eq. (26)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.