Asymptotically optimal repeated auctions for sponsored search

ABSTRACT

We investigate asymptotically optimal keyword auctions, that is, auctions which maximize revenue as the number of bidders grows. We do so under two alternative behavioral assumptions. The first explicitly models the repeated nature of keyword auctions. It introduces a novel assumption on individual bidding, namely that bidders never overbid their value, and bid their actual value if shut out for long enough. Under these conditions we present a broad class of repeated auctions that are asymptotically optimal among all sequential auctions (a superset of repeated auctions). Those auctions have varying payment schemes but share the ranking method. The Google auction belongs to this class, but not the Yahoo auction, and indeed we show that the latter is not asymptotically optimal. (Nonetheless, with some additional distributional assumptions, the Yahoo auction can be shown to belong to a broad category of auctions that are asymptotically optimal among all auction mechanisms that do not rely on ad relevance.) We then look at the one-shot keyword auction, which can be taken to model repeated auctions in which relatively myopic bidders converge on the equilibrium of the full-information stage game. In this case we show that the Google auction remains asymptotically optimal and the Yahoo auction suboptimal. The distributional assumptions under which our theorems hold are quite general. We do however show that the Google auction is not asymptotically revenue-maximizing for general distributions.

REFERENCES

• 1: Gagan Aggarwal , Ashish Goel , Rajeev Motwani, Truthful auctions for pricing search keywords, Proceedings of the 7th ACM conference on Electronic commerce, p.1-7, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134708]
• 2: B. Edelman and M. Ostrovsky. Strategic bidder behavior in sponsored search auctions. Working paper, 2005.
• 3: 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, 2005.
• 4: Juan Feng , Hemant K. Bhargava , David M. Pennock, Implementing Sponsored Search in Web Search Engines: Computational Evaluation of Alternative Mechanisms, INFORMS Journal on Computing, v.19 n.1, p.137-148, January 2007 [doi>10.1287/ijoc.1050.0135]
• 5: G. Iyengar and A. Kumar. Characterizing optimal keyword auctions. Second Workshop on Sponsored Search Auctions, 2006.
• 6: Sébastien Lahaie, An analysis of alternative slot auction designs for sponsored search, Proceedings of the 7th ACM conference on Electronic commerce, p.218-227, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134731]
• 7: R. Myerson. Optimal Auction Design. Math. Oper. Res., 6(1):58--73, 1981.
• 8: H. Varian. Position auctions. Working Paper, 2006.

INDEX TERMS

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

General Terms:
Economics, Theory

Keywords:
auctions, keyword auctions, sponsored search