18 Mechanism Design Basics 2.6.3 What We Want ls there an ideal sponsored search auction? Our desiderata are: (l) (2) DSIC. That is, truthful bidding should be a dominant strategy, and never leads to negative utility. Social welfare maximization. rI'hat is, the assignment of bidders to slots should maximize 2:121 1.153,, where 33, now denotes the CTR of the slot to which i. is assigned (or 0 if I". is not assigned to a slot). Each slot can only be assigned to one bidder, and each bidder gets only one slot. Computational efciency. The running time should be polyno~ mial (or even nearlinear) in the size of the input 1:1,... ,1)\". Remember that zillions of these auctions need to be run every davl Problems Problem 3.1 Recall our model of sponsored search auctions (Sec- tion 2.6): there are k slots, the jth slot has a click-through rate Downloaded from https://www.cambridge.org/core. AMS/Kaist Digital Sci Lib, on 16 Jul 2018 at 12:17:21, subject to the Cambridge Core terms of use, available at https://www.cambridge.org/core/terms. https://doi.org/10.1017/CB09781316779309.004 36 Myerson's Lemma (CTR) of a; (nonincreasing in j), and the utility of bidder i in slot j is aj(vi - Pj), where vi is the (private) value-per-click of the bid- der and p; is the price charged per-click in slot j. The Generalized Second-Price (GSP) auction is defined as follows: The Generalized Second Price (GSP) Auction 1. Rank advertisers from highest to lowest bid; assume without loss of generality that b1 2 b2 2 . . . > bn. 2. For i = 1, 2, ..., k, assign the ith bidder to the i slot. 3. For i = 1, 2, ..., k, charge the ith bidder a price of bi+1 per click. The following subproblems show that the GSP auction always has a canonical equilibrium that is equivalent to the truthful outcome in the corresponding DSIC sponsored search auction. (a) Prove that for every k 2 2 and sequence a1 2 . . . 2 0k > 0 of CTRs, the GSP auction is not DSIC. (b) (H) Fix CTRs for slots and values-per-click for bidders. We can assume that k = n by adding dummy slots with zero CTR (if k n). A bid profile b is an equilibrium of GSP if no bidder can increase her utility by unilaterally changing her bid. Verify that this condition translates to the following inequalities, under our standing assumption that b1 2 b2 2 . .. 2 bn: for every i and higher slot j aj (vi - bj); and for every lower slot j > i, ai(vi - bit1) > a; (vi - bj+1). (c) A bid profile b with b1 2 ... 2 bn is envy-free if for every bidder i and slot j # i, ai(vi - bit1) Zaj (vi - bj+1). (3.9) d from https://www.cambridge.org/core. AMS/Kaist Digital Sci Lib, on 16 Jul 2018 at 12:17:21, subject to the Cambridge Core terms ilable at https://www.cambridge.org/core/terms. https://doi.org/10.1017/CB09781316779309.004 Notes, Problems, and Exercises 37 Verify that every envy-free bid profile is an equilibrium.4 (d) (H) A bid profile is locally envy-free if the inequality (3.9) holds for every pair of adjacent slots-for every i and je {i-1, i+1}. By definition, an envy-free bid profile is also locally envy-free. Prove that, for every set of strictly decreasing CTRs, every locally envy-free bid profile is also envy-free. (e) (H) Prove that, for every set of values-per-click and strictly decreasing CTRs, there is an equilibrium of the GSP auction in which the assignments of bidders to slots and all payments-per- click equal those in the truthful outcome of the corresponding DSIC sponsored search auction. (f) Prove that the equilibrium in (e) is the lowest-revenue envy-free bid profile