GSP: The Cinderella of Mechanism Design

ABSTRACT

Nearly fifteen years ago, Google unveiled the generalized second price (GSP) auction. By all theoretical accounts including their own [Varian 14], this was the wrong auction --- the Vickrey-Clarke-Groves (VCG) auction would have been the proper choice --- yet GSP has succeeded spectacularly.

We give a deep justification for GSP's success: advertisers' preferences map to a model we call value maximization; they do not maximize profit as the standard theory would believe. For value maximizers, GSP is the truthful auction [Aggarwal 09]. Moreover, this implies an axiomatization of GSP --- it is an auction whose prices are truthful for value maximizers --- that can be applied much more broadly than the simple model for which GSP was originally designed. In particular, applying it to arbitrary single-parameter domains recovers the folklore definition of GSP. Through the lens of value maximization, GSP metamorphosizes into a powerful auction, sound in its principles and elegant in its simplicity.

References

1. Zoe Abrams, Arpita Ghosh, and Erik Vee. Cost of conciseness in sponsored search auctions. In Proceedings of the 3rd International Conference on Internet and Network Economics, pages 326--334, 2007.
2. Tsuyoshi Adachi. Equity and the vickrey allocation rule on general preference domains. Social Choice and Welfare, 42(4):813--830, 2013.
3. Gagan Aggarwal, Ashish Goel, and Rajeev Motwani. Truthful auctions for pricing search keywords. In Proceedings of the 7th ACM Conference on Electronic Commerce, pages 1--7, 2006.
4. Gagan Aggarwal, S. Muthukrishnan, Dávid Pál, and Martin Pál. General auction mechanism for search advertising. In Proceedings of the 18th International Conference on World Wide Web, WWW '09, pages 241--250, New York, NY, USA, 2009. ACM.
5. Saeed Alaei, Kamal Jain, and Azarakhsh Malekian. Competitive equilibrium in two sided matching markets with general utility functions. SIGecom Exch., 10(2):34--36, June 2011.
6. A. Archer and É. Tardos. Truthful mechanisms for one-parameter agents. In Proceedings of the 42nd IEEE the on Foundations of Computer Science, FOCS '01, pages 482--, Washington, DC, USA, 2001. IEEE Computer Society.
7. Susan Athey and Denis Nekipelov. Designing large advertising markets where agents have heterogeneous objectives: A structural empirical approach, 2016.
8. Jason Auerbach, Joel Galenson, and Mukund Sundararajan. An empirical analysis of return on investment maximization in sponsored search auctions. In Proceedings of the 2Nd International Workshop on Data Mining and Audience Intelligence for Advertising, ADKDD '08, pages 1--9, New York, NY, USA, 2008. ACM.
9. Yoram Bachrach, Sofia Ceppi, Ian A. Kash, Peter Key, and Mohammad Reza Khani. Mechanism design for mixed bidders. In Proceedings of the 25th International Conference on World Wide Web, WWW '16, pages 215--225, Republic and Canton of Geneva, Switzerland, 2016. International World Wide Web Conferences Steering Committee.
10. Yoram Bachrach, Sofia Ceppi, Ian A. Kash, Peter Key, and David Kurokawa. Optimising trade-offs among stakeholders in ad auctions. In Proceedings of the 15th ACM Conference on Economics and Computation, pages 75--92, 2014.
11. Christian Borgs, Jennifer Chayes, Nicole Immorlica, Kamal Jain, Omid Etesami, and Mohammad Mahdian. Dynamics of bid optimization in online advertisement auctions. In Proceedings of the 16th International Conference on World Wide Web, WWW '07, pages 531--540, New York, NY, USA, 2007. ACM.
12. Ruggiero Cavallo, Prabhakar Krishnamurthy, Maxim Sviridenko, and Christopher A. Wilkens. Sponsored search auctions with rich ads. In Proceedings of the 26th International Conference on World Wide Web, WWW '17, 2017.
13. Ruggiero Cavallo, Prabhakar Krishnamurthy, and Christopher A. Wilkens. On the truthfulness of gsp. In Eleventh Workshop on Sponsored Search Auctions, 2015.
14. Ruggiero Cavallo and Christopher A. Wilkens. Web and Internet Economics: 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings, chapter GSP with General Independent Click-through-Rates, pages 400--416. Springer International Publishing, Cham, 2014.
15. Xiaotie Deng, Yang Sun, Ming Yin, and Yunhong Zhou. Mechanism Design for Multi-slot Ads Auction in Sponsored Search Markets, pages 11--22. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.
16. Paul Dütting, Felix Fischer, and David C. Parkes. Truthful outcomes from non-truthful position auctions. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16, pages 813--813, New York, NY, USA, 2016. ACM.
17. Benjamin Edelman and Michael Ostrovsky. Strategic bidder behavior in sponsored search auctions. Decis. Support Syst., 43(1):192--198, February 2007.
18. Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242--259, 2007.
19. Salman Fadaei and Martin Bichler. Truthfulness and approximation with value-maximizing bidders. In Algorithmic Game Theory - Ninth International Symposium, SAGT, 2016. To appear.
20. Patrick Hummel and Preston McAfee. Position auctions with externalities and brand effects. In Proceedings of the 10th International Workshop on Internet and Network Economics, pages 585--596, 2014.
21. Brendan Kitts and Benjamin Leblanc. Optimal bidding on keyword auctions. Electronic Markets, 14(3):186--201, 2004.
22. A. Mas-Collel, M. D. Winston, and J. R. Green. Microeconomic Theory. 1995.
23. Paul Milgrom. Simplified mechanisms with an application to sponsored-search auctions. Games and Economic Behavior, 70(1):62--70, 2010.
24. Shuhei Morimoto and Shigehiro Serizawa. Strategy-proofness and efficiency with non-quasi-linear preferences: A characterization of minimum price walrasian rule. Theoretical Economics, 10(2):445--487, 2015.
25. Roger B. Myerson. Optimal auction design. Math. Oper. Res., 6(1):58--73, February 1981.
26. Jiang Rong, Tao Qin, and Bo An. Quantal response equilibrium for sponsored search auctions: Computation and inference. In Tenth Workshop on Sponsored Search Auctions, 2014.
27. B. Szymanski and J. Lee. Impact of roi on bidding and revenue in sponsored search advertisement auctions. In Second Workshop on Sponsored Search Auctions, 2006.
28. Hal R. Varian. Position auctions. International Journal of Industrial Organization, 25:1163--1178, 2007.
29. Hal R. Varian and Christopher Harris. The vcg auction in theory and practice. American Economic Review, 104(5):442--45, 2014.
30. Yunhong Zhou, Deeparnab Chakrabarty, and Rajan Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. In Proceedings of the 17th International Conference on World Wide Web, WWW '08, pages 1243--1244, New York, NY, USA, 2008. ACM.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

    • Economics

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Algorithmic mechanism design

      • Computational advertising theory

      • Computational pricing and auctions