CS 700 “Computational Mechanism Design”Notes on “On Best-Response Bidding in GSP Aucitons”∗Fall 2008Prof. David ParkesHarvard University and EPFLOctober 15, 20081 OverviewThe authors study the convergence of a balanced-bidding (BB) strategy in a GSP auction on a single keywordfor bidders without budget constraints and with complete knowledge of the bids of other bidders. The mainresult is that BB is shown to converge under asynchronous updates with probabiliy 1.The model has k slots with CTR θ1, . . . , θk, n players with vivalue per click, and defines γj=θjθj−1andγ∗= maxiγi. As γ∗→ 1, adjacent slots have closer CTR.The purpose of this note is to give a complete proof of Lemma 2, one of the early results for the restrictedbalanced bidding strategy and also to include the remark about where the log k term comes from in theasynchronous analysis.2 An early LemmaOne lemma they establish is for a restricted balanced bidding (RBB) strategy.Lemma 2 At every round t s.t. t > t1= 2 logγ∗((1 − γ∗)(vk− vk+1)/vk+1), where γ∗= maxi>0θi/θi−1, wehavebi> vk+1, if i ≤ kbi= vi, if i ≥ k + 1Proof 1 Let b denote the k + 1st bid and assume that b < vk+1. Consider any player i ∈ {1, 2, . . . , k + 1}(a bidder with one of the top k + 1 values). If this player bids b0iits value then(vk+1− b0i) ≤ γ∗(vk+1− b) (1)Otherwise, if in RBB it targets slot j ∈ {1, . . . , k} then its bid isb0i= (1 − γj)vi+ γjpj= vi− γj(vj− pj)≥ vk+1− γ∗(vk+1− b)since pj≥ b because b is the k + 1st highest bid.∗On Best-Response Bidding in GSP Auctions, by Cary, Das, Edelman, Giotis, Heimerl, Karlin, Mathieu and Schwarz. HBSWorking paper, 2008.1Now, we initially havevk+1− b ≤ vk+1Since b < vk+1. And for all i ∈ {1, . . . , k + 1} we have that Eq. (1) holds irrespective of how such anagent i bids. From this, we see that the (k + 1)st highest bid must satisfy(vk+1− b0) ≤ γ∗(vk+1− b) (2)where b0is this bid in the next round after an update by every agent i in the top k + 1. To reachvk+1− b < (1 − γ∗)(vk− vk+1) (3)we need at most r rounds such that(γ∗)rvk+1≤ (1 − γ∗)(vk− vk+1)and thusr ≥ logγ∗(1 − γ∗)(vk− vk+1)vk+1Now in round r + 1, every agent i ∈ {1, . . . , k} bids vi> vk+1or at leastb0i= (1 − γj)vi+ γjpj≥ (1 − γ∗)vk+ γ∗b= b + (1 − γ∗)(vk− b)≥ b + (1 − γ∗)(vk− vk+1) (4)> vk+1(5)where Eq. (4) follows since b ≤ vk+1and Eq. (5) follows by the property (Eq. 3) established.Thus, in round (r + 2), player k + 1 bids vk+1and players 1 . . . k bid above vk+1. This completes theproof, with bi> vk+1for players i ≤ k and bi= viotherwise.3 The asynchronous analysisI had wondered why it takes O(n log k) random attempts to activate k players from n players. The argumentis that one of k players is picked with probability k/n, then one of the remaining k − 1 players is picked withprobability (k − 1)/n and so on, so that the expected number of activations required to activate each of kplayers isT (n, k) =nk+nk − 1+nk − 2+ . . . +n1(6)= n1k+1k − 1+ . . . +11(7)= O(n log(k))