CS364A: Algorithmic Game Theory Lecture #3: Myerson's Lemma
Last time, we introduced the Vickrey auction and proved that it enjoys three desirable and different guarantees: (1) [strong incentive guarantees] DSIC. That is, truthful bidding should be a dominant strategy (and never leads to negative utility). Don't forget the two reasons we're after the DSIC guarantee. First, such an auction is easy to play for bidders — just play the obvious dominant strategy. Second, assuming only that bidders will play a dominant strategy when they have one, we can confidently predict the outcome of the auction. (2) [strong performance guarantees] Social surplus maximization. That is, assuming truthful bids (which is justified by (1)), the allocation of goods to bidders should maximize n i=1 v i x i , where x i the amount of stuff allocated to bidder i. (3) [computational efficiency] The auction can be implemented in polynomial (indeed, linear) time. To extend these guarantees beyond single-item auctions to more complex problems, like the sponsored search auctions introduced last lecture, we advocated a two-step design approach. Step 1: Assume, without justification, that bidders bid truthfully. Then, how should we assign bidders to slots so that the above properties (2) and (3) hold? Step 2: Given our answer to Step 1, how should we set selling prices so that the above property (1) holds? * c 2013, Tim Roughgarden. These lecture notes are provided for personal use only. See my book Twenty Lectures on Algorithmic Game Theory, published by Cambridge University Press, for the latest version.