Greedy bidding strategies for keyword auctions

ABSTRACT

How should players bid in keyword auctions such as those used by Google, Yahoo! and MSN?allWe consider greedy bidding strategies for a repeated auction on a single keyword, where in each round, each player chooses some optimal bid for the next round, assuming that the other players merely repeat their previous bid. We study the revenue, convergence and robustness properties of such strategies. Most interesting among these is a strategy we call the balanced bidding strategy (BB): it is known that BB has a unique fixed point with payments identical to those of the VCG mechanism. We show that if all players use the BB strategy and update each round, BB converges when the number of slots is at most 2, but does not always converge for 3 or more slots. On the other hand, we present a simple variant which is guaranteed to converge to the same fixed point for any number of slots. In a model in which only one randomly chosen player updates each round according to the BB strategy, we prove that convergence occurs with probability 1.We complement our theoretical results with empirical studies.

REFERENCES

• 1: Asdemir, K. Bidding patterns in search engine auctions. In Second Workshop on Sponsored Search Auctions (2006), ACM Electronic Commerce.
• 2: 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
• 3: Clarke, E. H. Multipart pricing of public goods. Public Choice 11 (1971), 17--33.
• 4: Edelman, B., and Ostrovsky, M. Strategic bidder behavior in sponsored search auctions. In First Workshop on Sponsored Search Auctions (2005), ACM Electronic Commerce.
• 5: Edelman, B., Ostrovsky, M., and Schwarz, M. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. To appear in American Economic Review, 2006.
• 6: 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]
• 7: Groves, T. Incentives in teams. Econometrica 41 (1973), 617--631.
• 8: Kitts, B., Laxminarayan, P., LeBlanc, B., and Meech, R. A formal analysis of search auctions including predictions on click fraud and bidding tactics. In First Workshop on Sponsored Search Auctions (2005), ACM Electronic Commerce.
• 9: Kitts, B., and Leblanc, B. Optimal bidding on keyword auctions. Electronic Markets (2004), 186--201.
• 10: 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]
• 11: Varian, H. Position auctions. To appear in International Journal of Industrial Organization, 2006.
• 12: Vickery, W. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance (1961), 8--37.
• 13: Web-Cite. Shooting the moon and budget busting with overture's auto-bidding, April 2003.
• 14: Zhang, X. Finding edgeworth cycles in online advertising auctions. MIT Sloan School of Management, Working Paper, 2005.
• 15: Zhou, Y., and Lukose, R. Vindictive bidding in keyword auctions. In Second Workshop on Sponsored Search Auctions (2006), ACM Electronic Commerce.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.0 GENERAL

Additional Classification:
  G. Mathematics of Computing
  G.0 GENERAL

General Terms:
Algorithms, Economics, Theory

Keywords:
bidding strategies, keyword auctions