skip to main content
10.1145/1566374.1566382acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
research-article

Computational analysis of perfect-information position auctions

Published: 06 July 2009 Publication History

Abstract

Position auctions were widely used by search engines to sell keyword advertising before being well understood (and, indeed, studied) theoretically. To date, theorists have made significant progress, for example showing that a given auction is efficient or revenue-dominates a benchmark auction such as VCG. This paper augments that line of work, relying on computational equilibrium analysis. By computing Nash equilibria and calculating their expected revenue and social welfare, we can quantitatively answer questions that theoretical methods have not. Broadly, the questions we answer are: (1) How often do the theoretically predicted "good" (i.e., efficient, high-revenue) equilibria of GSP occur? (2) In models where GSP is known to be inefficient, how much welfare does it waste? We also use our data to examine the larger question of whether GSP is a good choice, compared with the alternatives.

References

[1]
Z. Abrams, O. Mendelevitch, and J. Tomlin. Optimal delivery of sponsored search advertisements sub ject to budget constraints. In EC: Proceedings of the ACM Conference on Electronic Commerce, pages 272--278, 2007.
[2]
G. Aggarwal, J. Feldman, S. Muthukrishnan, and M. Pal. Sponsored search auctions with markovian users. ACM EC Workshop on Advertisement Auctions, 2008.
[3]
G. Aggarwal, A. Goel, and R. Motwani. Truthful auctions for pricing search keywords. In EC: Proceedings of the ACM Conference on Electronic Commerce, pages 1--7, New York, NY, USA, 2006. ACM.
[4]
K. Asdemir. Bidding patterns in search engine auctions. In Second Workshop on Sponsored Search Auctions, 2006.
[5]
I. Ashlagi, D. Monderer, and M. Tennenholtz. Mediators in position auctions. In EC: Proceedings of the ACM Conference on Electronic Commerce, pages 279--287, New York, NY, USA, 2007. ACM.
[6]
M. Benisch, N. Sadeh, and T. Sandholm. The cost of inexpressiveness in advertisement auctions. ACM EC Workshop on Advertisement Auctions, 2008.
[7]
N. Bhat and K. Leyton-Brown. Computing Nash equilibria of Action-Graph Games. In UAI: Proceedings of the Conference on Uncertainty in Artificial Intel ligence, pages 35--42, 2004.
[8]
L. Blumrosen, J. Hartline, and S. Nong. Position auctions and non-uniform conversion rates. ACM EC Workshop on Advertisement Auctions, 2008.
[9]
T. Borgers, I.J. Cox, M. Pesendorfer, and V. Petricek. Equilibrium bids in auctions of sponsored links: Theory and evidence, as of November 2006.
[10]
C. Borgs, J. Chayes, N. Immorlica, K. Jain, O. Etesami, and M. Mahdian. Dynamics of bid optimization in online advertisement auctions. In WWW '07: Proceedings of the 16th international conference on World Wide Web, pages 531--540, New York, NY, USA, 2007. ACM.
[11]
N. Buchbinder, K. Jain, and S. Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Proceedings of the 15th Annual European Symposium on Algorithms, 2007.
[12]
M. Cary, A. Das, B. Edelman, I. Giotis, K. Heimerl, A.R. Karlin, C. Mathieu, and M. Schwarz. Greedy bidding strategies for keyword auctions. In EC: Proceedings of the ACM Conference on Electronic Commerce, pages 262--271, New York, NY, USA, 2007. ACM.
[13]
M.R. Chernick. Bootstrap Methods, A practitioner's guide. Wiley, 1999.
[14]
B. Edelman and M. Ostrovsky. Strategic bidder behavior in sponsored search auctions. Decis. Support Syst., 43(1):192--198, 2007.
[15]
B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242--259, March 2007.
[16]
J. Feng, H.K. Bhargava, and D. Pennock. Comparison of allocation rules for paid placement advertising in search engines. In EC: Proceedings of the ACM Conference on Electronic Commerce, pages 294--299, New York, NY, USA, 2003. ACM.
[17]
J. Feng, H.K. Bhargava, and D.M. Pennock. Implementing sponsored search in web search engines: Computational evaluation of alternative mechanisms. INFORMS J. on Computing, 19(1):137--148, 2007.
[18]
A. Ghosh and M. Mahdian. Externalities in online-advertising. In WWW: International World Wide Web Conference, 2008.
[19]
S. Govindan and R. Wilson. Essential equilibria. Proceedings of the National Academy of Sciences USA, 102:15706--15711, 2005.
[20]
A. X. Jiang and K. Leyton-Brown. A polynomial-time algorithm for Action-Graph Games. In Proceedings of the AAAI Conference on Artificial Intel ligence, pages 679--684, 2006.
[21]
M. Kearns, M. Littman, and S. Singh. Graphical models for game theory. In UAI: Proceedings of the Conference on Uncertainty in Artificial Intel ligence, 2001.
[22]
D. Kempe and M. Mahdian. A cascade model for externalities in sponsored search. ACM EC Workshop on Advertisement Auctions, 2008.
[23]
B. Kitts, P. Laxminarayan, B. LeBlanc, and R. Meech. A formal analysis of search auctions including predictions on click fraud and bidding tactics. In Workshop on Sponsored Search Auctions, 2005.
[24]
S. Lahaie and D.M. Pennock. Revenue analysis of a family of ranking rules for keyword auctions. In EC: Proceedings of the ACM Conference on Electronic Commerce, 2007.
[25]
S. Lahaie, D.M. Pennock, A. Saberi, and R. Vohra. Sponsored search auctions. In Nisan et al. {31}, chapter 28, pages 699--719.
[26]
M. Mahdian, H. Nazerzadeh, and A. Saberi. Allocating online advertisement space with unreliable estimates. In EC: Proceedings of the ACM Conference on Electronic Commerce, pages 288--294, New York, NY, USA, 2007. ACM.
[27]
R.D. McKelvey, A.M. McLennan, and T.L. Turocy. Gambit: Software tools for game theory, 2006. http://econweb.tamu.edu/gambit.
[28]
A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani. Adwords and generalized on-line matching. In FOCS '05: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 264---273, Washington, DC, USA, 2005. IEEE Computer Society.
[29]
R.G.J. Miller. Simultaneous Statistical Inference. Springer, 1981.
[30]
N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, Cambridge, UK, 2007.
[31]
R. Porter, E. Nudelman, and Y. Shoham. Simple search methods for finding a Nash equilibrium. In Proceedings of the AAAI Conference
[32]
on Artificial Intel ligence, pages 664--669, 2004.
[33]
H. Scarf. The approximation of fixed points of continuous mappings. SIAM Journal of Applied Mathematics, 15:1328--1343, 1967.
[34]
C. Shannon. A mathematical theory of communication. Bel l System Technical Journal, 27:379--423, 1948.
[35]
D.R.M. Thompson and K. Leyton-Brown. Tractable computational methods for finding Nash equilibria of perfect-information position auctions. ACM EC Workshop on Advertisement Auctions, 2008.
[36]
H. Varian. Position auctions. International Journal of Industrial Organization, 25(6):1163--1178, 2007.

Cited By

View all
  • (2023)Auctions for resource allocation and decentralized restoration of interdependent networksReliability Engineering & System Safety10.1016/j.ress.2023.109301237(109301)Online publication date: Sep-2023
  • (2019)Let’s play the search game: Strategic and behavioral properties of sponsored search auction mechanismsElectronic Commerce Research and Applications10.1016/j.elerap.2018.10.00133(100809)Online publication date: Jan-2019
  • (2018)Computational pricing in Internet eraFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-017-6005-012:1(40-54)Online publication date: 1-Feb-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
EC '09: Proceedings of the 10th ACM conference on Electronic commerce
July 2009
376 pages
ISBN:9781605584584
DOI:10.1145/1566374
  • General Chair:
  • John Chuang,
  • Program Chairs:
  • Lance Fortnow,
  • Pearl Pu
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. compact games
  2. empirical analysis
  3. game theory
  4. nash equilibrium
  5. sponsored search

Qualifiers

  • Research-article

Conference

EC '09
Sponsor:
EC '09: ACM Conference on Electronic Commerce
July 6 - 10, 2009
California, Stanford, USA

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25
The 25th ACM Conference on Economics and Computation
July 7 - 11, 2025
Stanford , CA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 09 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Auctions for resource allocation and decentralized restoration of interdependent networksReliability Engineering & System Safety10.1016/j.ress.2023.109301237(109301)Online publication date: Sep-2023
  • (2019)Let’s play the search game: Strategic and behavioral properties of sponsored search auction mechanismsElectronic Commerce Research and Applications10.1016/j.elerap.2018.10.00133(100809)Online publication date: Jan-2019
  • (2018)Computational pricing in Internet eraFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-017-6005-012:1(40-54)Online publication date: 1-Feb-2018
  • (2017)The positronic economistProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298239.3298345(720-727)Online publication date: 4-Feb-2017
  • (2017)Resource graph gamesProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298239.3298324(572-578)Online publication date: 4-Feb-2017
  • (2016)Modeling bounded rationality for sponsored search auctionsProceedings of the Twenty-second European Conference on Artificial Intelligence10.3233/978-1-61499-672-9-515(515-523)Online publication date: 29-Aug-2016
  • (2015)Computing Quantal Response Equilibrium for Sponsored Search AuctionsProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2773445(1803-1804)Online publication date: 4-May-2015
  • (2014)Bayes–Nash equilibria of the generalized second-price auctionGames and Economic Behavior10.1016/j.geb.2012.09.00186(421-437)Online publication date: Jul-2014
  • (2014)Optimal reserve prices in weighted GSP auctionsElectronic Commerce Research and Applications10.1016/j.elerap.2014.02.00313:3(178-187)Online publication date: May-2014
  • (2013)Revenue optimization in the generalized second-price auctionProceedings of the fourteenth ACM conference on Electronic commerce10.1145/2492002.2482612(837-852)Online publication date: 16-Jun-2013
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media