An analysis of alternative slot auction designs for sponsored search

ABSTRACT

Billions of dollars are spent each year on sponsored search, a form of advertising where merchants pay for placement alongside web search results. Slots for ad listings are allocated via an auction-style mechanism where the higher a merchant bids, the more likely his ad is to appear above other ads on the page. In this paper we analyze the incentive, efficiency, and revenue properties of two slot auction designs: "rank by bid" (RBB) and "rank by revenue" (RBR), which correspond to stylized versions of the mechanisms currently used by Yahoo! and Google, respectively. We also consider first- and second-price payment rules together with each of these allocation rules, as both have been used historically. We consider both the "short-run" incomplete information setting and the "long-run" complete information setting. With incomplete information, neither RBB nor RBR are truthful with either first or second pricing. We find that the informational requirements of RBB are much weaker than those of RBR, but that RBR is efficient whereas RBB is not. We also show that no revenue ranking of RBB and RBR is possible given an arbitrary distribution over bidder values and relevance. With complete information, we find that no equilibrium exists with first pricing using either RBB or RBR. We show that there typically exists a multitude of equilibria with second pricing, and we bound the divergence of (economic) value in such equilibria from the value obtained assuming all merchants bid truthfully.

REFERENCES

• 1: Zoë Abrams, Revenue maximization when bidders have budgets, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1074-1082, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109676]
• 2: T. Börgers, I. Cox, and M. Pesendorfer. Personal Communication.
• 3: Christian Borgs , Jennifer Chayes , Nicole Immorlica , Mohammad Mahdian , Amin Saberi, Multi-unit auctions with budget-constrained bidders, Proceedings of the 6th ACM conference on Electronic commerce, p.44-51, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064014]
• 4: Felix Brandt , Gerhard Weiß, Antisocial Agents and Vickrey Auctions, Revised Papers from the 8th International Workshop on Intelligent Agents VIII, p.335-347, August 01-03, 2001
• 5: B. Edelman and M. Ostrovsky. Strategic bidder behavior in sponsored search auctions. In Workshop on Sponsored Search Auctions, ACM Electronic Commerce, 2005.
• 6: B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. NBER working paper 11765, November 2005.
• 7: J. Feng, H. K. Bhargava, and D. M. Pennock. Implementing sponsored search in web search engines: Computational evaluation of alternative mechanisms. INFORMS Journal on Computing, 2005. Forthcoming.
• 8: J. Green and J.-J. Laffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica, 45:427--438, 1977.
• 9: B. Holmstrom. Groves schemes on restricted domains. Econometrica, 47(5):1137--1144, 1979.
• 10: 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, ACM Electronic Commerce, 2005.
• 11: V. Krishna. Auction Theory. Academic Press, 2002.
• 12: D. Liu and J. Chen. Designing online auctions with past performance information. Decision Support Systems, 2005. Forthcoming.
• 13: C. Meek, D. M. Chickering, and D. B. Wilson. Stochastic and contingent payment auctions. In Workshop on Sponsored Search Auctions, ACM Electronic Commerce, 2005.
• 14: Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and Generalized On-line Matching, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.264-273, October 23-25, 2005 [doi>10.1109/SFCS.2005.12]
• 15: P. Milgrom. Putting Auction Theory to Work. Cambridge University Press, 2004.
• 16: P. Milgrom and C. Shannon. Monotone comparative statics. Econometrica, 62(1):157--180, 1994.
• 17: P. J. Reny. On the existence of pure and mixed strategy Nash equilibria in discontinuous games. Econometrica, 67(5):1029--1056, 1999.
• 18: H. R. Varian. Position auctions. Working Paper, February 2006.
• 19: W. Vickrey. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Economics, Theory

Keywords:
auction theory, rank by bid, rank by revenue, search engines, slot allocation, sponsored search