Lemma 7, p. 11 — Σ_{i=1}^{k−1} ψ(i)(α_i − β_i) ≤ N/k
ProvedAdWordsMSVV.Tradeoff.lemma_7Fix , an adwords instance with bidders, unit budgets and nonnegative bids , a monotonically decreasing tradeoff function with , a run of the discrete algorithm with tradeoff function , and any allocation . For let
where is the bid of the bidder assigns to, is that bidder's type at the end of the run, and , are as in Lemma 6. Then
Applied to Theorem 8's (which satisfies these hypotheses), through this is the bound on the error term in the proof of Theorem 8.
Formalization Note The two sums are the paper's opening observations in the proof of Lemma 7, taken here as the definitions of and . The paper states the lemma for a generic monotonically decreasing ; the added hypothesis (true for Theorem 8's and for §3's ) replaces the paper's bound on the slab- term, which rests on its simplifying assumption that bidders of type spend exactly : for a tradeoff function positive at slab the slab- money can exceed by one bid per bidder, which the paper absorbs into its small-bid assumption.
import Mathlib import Definitions.Def_AdWordsMSVV_Tradeoff_Setting
namespace AdWordsMSVV.Tradeoff
theorem lemma_7 {N M : ℕ} (k : ℕ) (hk : 1 ≤ k) (ψ : ℕ → ℝ)
(hψ : AntitoneOn ψ (Set.Icc 1 k)) (hψ0 : ∀ i ∈ Set.Icc 1 k, 0 ≤ ψ i) (hψk : ψ k = 0)
(bid : Fin N → Fin M → ℝ) (hbid : ∀ b t, 0 ≤ bid b t)
(σ : Fin M → Option (Fin N)) (hσ : IsRun ψ k bid σ)
(τ : Fin M → Option (Fin N)) :
let α : ℕ → ℝ := fun i =>
∑ t : Fin M, match τ t with
| none => 0
| some b => if typeOf k bid σ b = i then bid b t else 0
let β : ℕ → ℝ := fun i =>
∑ t ∈ Finset.univ.filter (fun t : Fin M => slabQ k bid σ t = i), algRev bid σ t
∑ i ∈ Finset.Icc 1 (k - 1), ψ i * (α i - β i) ≤ (N : ℝ) / k := by sorry
end AdWordsMSVV.Tradeoff
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.