Hybrid keyword search auctions

ABSTRACT

Search auctions have become a dominant source of revenue generation on the Internet. Such auctions have typically used per-click bidding and pricing. We propose the use of hybrid auctions where an advertiser can make a per-impression as well as a per-click bid, and the auctioneer then chooses one of the two as the pricing mechanism. We assume that the advertiser and the auctioneer both have separate beliefs (called priors) on the click-probability of an advertisement. We first prove that the hybrid auction is truthful, assuming that the advertisers are risk-neutral. We then show that this auction is superior to the existing per-click auction in multiple ways: We show that risk-seeking advertisers will choose only a per-impression bid whereas risk-averse advertisers will choose only a per-click bid, and argue that both kind of advertisers arise naturally. Hence, the ability to bid in a hybrid fashion is important to account for the risk characteristics of the advertisers. For obscure keywords, the auctioneer is unlikely to have a very sharp prior on the click-probabilities. In such situations, we show that having the extra information from the advertisers in the form of a per-impression bid can result in significantly higher revenue. An advertiser who believes that its click-probability is much higher than the auctioneer's estimate can use per-impression bids to correct the auctioneer's prior without incurring any extra cost. The hybrid auction can allow the advertiser and auctioneer to implement complex dynamic programming strategies to deal with the uncertainty in the click-probability using the same basic auction. The per-click and per-impression bidding schemes can only be used to implement two extreme cases of these strategies. As Internet commerce matures, we need more sophisticated pricing models to exploit all the information held by each of the participants. We believe that hybrid auctions could be an important step in this direction. The hybrid auction easily extends to multiple slots, and is also applicable to scenarios where the hybrid bidding is per-impression and per-action (i.e. CPM and CPA), or per-click and per-action (i.e. CPC and CPA).

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: S. Athey and I. Segal. An efficient dynamic mechanism. 2007. Available at http://kuznets.fas.harvard.edu/athey.
• 3: A. Bapna and T. Weber. Efficient dynamic allocation with uncertain valuation. Working Paper, Department of Management Science and Engineering, Stanford University, 2005.
• 4: 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, 2007.
• 5: J. C. Gittins. Bandit processes and dynamic allocation indices. J Royal Statistical Societe Series B, 14:148--167, 1979.
• 6: S. Lahaie, D. Pennock, A. Saberi, and R. Vohra. Sponsored search auctions. In Algorithmic Game Theory, edited by Nisan, Roughgarden, Tardos, and Vazirani, 2007.
• 7: A.W. Marshall and I. Olkin. Inequalities: theory of majorization and its applications. Academic Press (Volume 143 of Mathematics in Science and Engineering), 1979.
• 8: 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]
• 9: R. B. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58--73, 1981.
• 10: Matthew Richardson , Ewa Dominowska , Robert Ragno, Predicting clicks: estimating the click-through rate for new ads, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242643]
• 11: H. Varian. Position auctions. International Journal of Industrial Organization, October 2006.
• 12: R. Weber. On the gittins index for multiarmed bandits. Annals of applied probability, 2(4):1024--1033, 1992.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Algorithms, Economics, Theory

Keywords:
internet, keyword auctions, mechanism design