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.2.6.2 The Basic Model of Sponsored Search Auctions \\Ve discuss next a simplistic but useful and inuential model of spon sored search auctions. The items for sale are k \"slots\" for sponsored links on a search results page. The bidders are the advertisers who have a standing bid on the keyword that was searched on. For ex ample, Volvo and Subaru might be bidders on the keyword \"station wagon,\" while Nikon and Canon might be bidders on the keyword \"camera.\" Such auctions are more complex than singloitem auctions in two ways. First, there are generally multiple items for sale (i.e., k > 1). Second, these items are not identical. For example, if ads are displayed as an ordered list, then higher slots in the list are more valuable than lower ones, since people generally scan the list from top to bottom. We quantify the difference between dierent slots using click threugh rates (CTRS). The CTR o-j of a slot 3' represents the probabil ity that the end user clicks on this slot. Ordering the slots from top to bottom, we make the reasonable assumption that 0:1 2 0:2 2 - - - 2 Oak. For simplicity, we also make the unreasonable assumption that the CTR of a slot is independent of its occupant. Everything we'll say about sponsored search auctions extends to the more general and realistic model in which each advertiser 1' has a \"quality score\" ,5, (the higher the better) and the CTR of advertiser i". in slot 3' is the product (Baj (e.g., Exercise 34) We assume that an advertiser is not interested in an impression (i.e., being displayed on a page) per se, but rather has a private valuation c, for each click on her link. Hence, the expected value derived by advertiser 1'. from slot 3' is \"Urog- anloaded from l\"ttpsawm-.cambr'iclgeergx'cere. AMSIKaist Digital Sci Lib. on 'Iajul 2018 at 12:1?:20. subjectte the Cambridge Ce use, available at l\"tips:mwm-.cambriclgecr'gfcorefterms. l'ttpss'deic-rgx'i 0.1 0' i'x'CBOQF813' EFFQBDEDDB