§3.3, p. 16 — for ã_exp, ã_lin with α = 1/2, ã(y_e)∫₀¹ e^{−2x(1−y_e)}dx is minimized over y_e ∈ [0,1] at y_e = 0
ProvedOfflineStochMatch.InfinitePatience.min_at_zeroattenuationcalculusinequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the exponential attenuation function or the linear one (Definition 4 with ). Then the function
attains its minimum over at , where its value is .
When every patience is , is the paper's lower bound on ; this minimization turns it into the constant of Corollary 5.
Preamble
import Mathlib import Definitions.Def_OfflineStochMatch_InfinitePatience_Setting
Formal statement
namespace OfflineStochMatch.InfinitePatience
/-- §3.3, p. 16: for the exponential and the linear attenuation functions with `α = 1/2`, the lower
bound `ã(y_e) ∫_0^1 e^{-2x(1-y_e)} dx` on `a(e) Pr[e is safe]` is minimized over `y_e ∈ [0,1]` at
`y_e = 0`. -/
theorem min_at_zero (aT : ℝ → ℝ) (haT : aT = expAtt (1 / 2) ∨ aT = linAtt (1 / 2)) :
IsMinOn (fun z => aT z * ∫ x in (0 : ℝ)..1, Real.exp (-2 * x * (1 - z))) (Set.Icc (0 : ℝ) 1) 0 := 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. 16, §3.3, first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.