Definition 4, p. 9 — the exponential and linear attenuation functions with α = 1/2 are effective
ProvedOfflineStochMatch.Attenuation.effective_exp_linattenuationconvexityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be the exponential and linear attenuation functions of Definition 4 with . Both are effective in the sense of Definition 3: each maps into , takes the value at , and for every the function
is convex on .
Effectiveness is the hypothesis of Lemma 3, and it is what lets the analysis of Theorem 1 apply to these two functions.
Formalization Note The paper claims effectiveness for all and for the third function of Definition 4. The statement is made for , the value Theorem 1 uses. The third function is left out because the claim is false for it: with one finds for close to . For the linear function and the range condition fails, which is another reason to fix .
Preamble
import Mathlib import Definitions.Def_OfflineStochMatch_Attenuation_Setting
Formal statement
namespace OfflineStochMatch.Attenuation
theorem effective_exp_lin :
IsEffective (expAtt (1 / 2)) ∧ IsEffective (linAtt (1 / 2)) := 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. 9, Definition 4 and the sentence after it (with Definition 3, p. 8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.