Lemma 3, p. 8 — the value of the LPs L and D tends to N/e as k → ∞
ProvedAdWordsMSVV.Tradeoff.lemma_3adwordsfactor-revealing-lplimitsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix the number of bidders . For each number of slabs , let be the supremum of the objective of the factor-revealing LP over its feasible set and the infimum of the objective of its dual . Then
For BALANCE this gives the competitive ratio ; for the tradeoff algorithm it supplies the term in the proof of Theorem 8.
Formalization Note The values are a real sSup and sInf. For the feasible sets are nonempty (, ) and the objectives are bounded on them, so both are attained values; for the index range is empty and both values are , which does not affect the limit.
Preamble
import Mathlib import Definitions.Def_AdWordsMSVV_Tradeoff_LP
Formal statement
namespace AdWordsMSVV.Tradeoff
theorem lemma_3 (N : ℕ) :
Filter.Tendsto (fun k : ℕ => LValue k N) Filter.atTop (nhds ((N : ℝ) / Real.exp 1)) ∧
Filter.Tendsto (fun k : ℕ => DValue k N) Filter.atTop (nhds ((N : ℝ) / Real.exp 1)) := by sorry
end AdWordsMSVV.Tradeoff
Source
Mehta, Saberi, Vazirani, Vazirani, AdWords and generalized on-line matching, J. ACM (2007), DOI 10.1145/1284320.1284321, p. 8, Lemma 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.