Lemma 6, p. 11 — OPT(q) ψ(type(q)) ≤ ALG(q) ψ(slab(q)) for every query with 1 ≤ type(q) ≤ k − 1
ProvedAdWordsMSVV.Tradeoff.lemma_6Fix slabs, a tradeoff function that is monotonically decreasing on , an adwords instance with unit budgets and nonnegative bids , and a run of the discrete algorithm with tradeoff function . Let be any allocation (the "OPT" of the paper), and let be the query at position , which assigns to bidder . If the type of at the end of the run satisfies , then
where is the bid of the bidder to whom the run assigns and is that bidder's active slab when arrives.
The left side is in the paper's notation. The inequality is the per-query comparison summed in Lemma 7.
Formalization Note The lemma uses no optimality of , so it is stated for every allocation. Monotonicity of is assumed on the slab range only.
import Mathlib import Definitions.Def_AdWordsMSVV_Tradeoff_Setting
namespace AdWordsMSVV.Tradeoff
theorem lemma_6 {N M : ℕ} (k : ℕ) (hk : 1 ≤ k) (ψ : ℕ → ℝ)
(hψ : AntitoneOn ψ (Set.Icc 1 k))
(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)) (t : Fin M) (b : Fin N) (hτ : τ t = some b)
(htype : 1 ≤ typeOf k bid σ b ∧ typeOf k bid σ b ≤ k - 1) :
bid b t * ψ (typeOf k bid σ b) ≤ algRev bid σ t * ψ (slabQ k bid σ t) := by sorry
end AdWordsMSVV.Tradeoff
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.