Proof of Theorem 9, p. 15 — the optimal allocation of every permuted instance is N (N·B after scaling), attained by Q_i ↦ π(i)
ProvedAdWordsMSVV.LowerBound.opt_round_instanceadwordsb-matchingoffline-optimump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be natural numbers and a permutation of the bidders. On the permuted round instance (budget , rounds of queries, round bid on by ), the allocation that sends every query of to bidder has offline revenue , and no allocation earns more:
In the paper's units (budget , bids ) the optimum is . This fixes the denominator of the competitive ratio in Theorem 9.
Preamble
import Mathlib import Definitions.Def_AdWordsMSVV_LowerBound_Setting
Formal statement
namespace AdWordsMSVV.LowerBound
theorem opt_round_instance (N B : ℕ) (π : Equiv.Perm (Fin N)) :
offlineRevenue B (roundInstance N B π) (roundAllocation N B π) = N * B ∧
∀ τ : Fin (N * B) → Option (Fin N), offlineRevenue B (roundInstance N B π) τ ≤ N * B := 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, second paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.