Proof of Theorem 9, p. 15 — Σ_{j=1}^{N} min{1, Σ_{i=1}^{j} 1/(N−i+1)} ≤ (1 − 1/e + δ)N for all large N
ProvedAdWordsMSVV.LowerBound.harmonic_sum_boundadwordsasymptoticsharmonic-numbersp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For every there is such that for every ,
This is the analytic step of the proof of Theorem 9: summing the per-bidder bounds over the positions gives at most a fraction of the optimum , up to a lower-order error.
Formalization Note The paper writes "at most ". Taken literally this is false for every (at the sum is ; the excess over tends to about ), so the bound is stated asymptotically with a slack ; no explicit error term is asserted, since the paper gives none.
Preamble
import Mathlib import Definitions.Def_AdWordsMSVV_LowerBound_Setting
Formal statement
namespace AdWordsMSVV.LowerBound
open Finset
theorem harmonic_sum_bound :
∀ δ : ℝ, 0 < δ → ∃ N₀ : ℕ, ∀ N : ℕ, N₀ ≤ N →
∑ j ∈ Icc 1 N, min 1 (∑ i ∈ Icc 1 j, 1 / ((N : ℝ) - i + 1))
≤ (1 - Real.exp (-1) + δ) * N := by sorry
end AdWordsMSVV.LowerBound
Source
Mehta, Saberi, Vazirani, Vazirani, AdWords and generalized on-line matching, J. ACM (2007), DOI 10.1145/1284320.1284321, p. 15, proof of Theorem 9, last paragraph, second sentence
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.