Bid optimization for broad match ad auctions

ABSTRACT

Ad auctions in sponsored search support "broad match" that allows an advertiser to target a large number of queries while bidding only on a limited number. While giving more expressiveness to advertisers, this feature makes it challenging to optimize bids to maximize their returns: choosing to bid on a query as a broad match because it provides high profit results in one bidding for related queries which may yield low or even negative profits.

We abstract and study the complexity of the {\em bid optimization problem} which is to determine an advertiser's bids on a subset of keywords (possibly using broad match) so that her profit is maximized. In the query language model when the advertiser is allowed to bid on all queries as broad match, we present a linear programming (LP)-based polynomial-time algorithm that gets the optimal profit. In the model in which an advertiser can only bid on keywords, ie., a subset of keywords as an exact or broad match, we show that this problem is not approximable within any reasonable approximation factor unless P=NP. To deal with this hardness result, we present a constant-factor approximation when the optimal profit significantly exceeds the cost. This algorithm is based on rounding a natural LP formulation of the problem. Finally, we study a budgeted variant of the problem, and show that in the query language model, one can find two budget constrained ad campaigns in polynomial time that implement the optimal bidding strategy. Our results are the first to address bid optimization under the broad match feature which is common in ad auctions.

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 G. Ellison. Position auctions with consumer search. Working Paper, Sept 2007.
• 3: Christian Borgs , Jennifer Chayes , Nicole Immorlica , Kamal Jain , Omid Etesami , Mohammad Mahdian, Dynamics of bid optimization in online advertisement auctions, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242644]
• 4: 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]
• 5: D. Chakrabarty, Y. Zhou, and R. Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. 3rd Workshop on Sponsored Search Auctions (SSA), 2007.
• 6: B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalized second price auction selling billions of dollars worth of keywords. In Second workshop on sponsored search auctions, 2006.
• 7: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 8: Jon Feldman , S Muthukrishnan , Martin Pal , Cliff Stein, Budget optimization in search-based advertising auctions, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250917]
• 9: D. Martin, J. Gehrke, and J. Halperin. Toward expressive and scalable sponsored search auctions. Proceedings of the 24th International Conference on Data Engineering, ICDE 2008.
• 10: Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and generalized online matching, Journal of the ACM (JACM), v.54 n.5, p.22-es, October 2007 [doi>10.1145/1284320.1284321]
• 11: S. Muthukrishnan, M. Pál, and Z. Svitkina. Stochastic models for budget optimization in search-based advertising. Proc. Workshop on Internet and Network Economics (WINE), 2007.
• 12: C. H. Papadimitriou and K. Steiglitz. Combinatorial optimization. Prentice Hall.
• 13: Paat Rusmevichientong , David P. Williamson, An adaptive algorithm for selecting profitable keywords for search-based advertising services, Proceedings of the 7th ACM conference on Electronic commerce, p.260-269, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134736]
• 14: Mechthild Stoer , Frank Wagner, A simple min-cut algorithm, Journal of the ACM (JACM), v.44 n.4, p.585-591, July 1997 [doi>10.1145/263867.263872]
• 15: M. Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint. Operations Research Letters 32 (2004), 41--43.
• 16: H. Varian. Position auctions. International Journal of Industrial Organization 25(6):1163--1178, December 2007.
• 17: http://adcentercommunity.com/blogs/advertiser/archive/2008/04/07/keyword-match-types.aspx.
• 18: http://adwords.google.com/support/bin/answer.py?answer=25148.
• 19: http://adwords.google.com/support/bin/answer.py?hl=en&answer=6100.
• 20: http://help.yahoo.com/l/us/yahoo/ysm/sps/start/overview_matchtypes.html.
• 21: https://adcenter.microsoft.com/Default.aspx.
• 22: https://clients.mamma.com/faq/bidsystem/faq_broad_matching.html.
• 23: http://sem.smallbusiness.yahoo.com/searchenginemarketing/index.php?&abr=2%022403519.
• 24: Yahoo! search marketing advertiser workbook. http://us.i1.yimg.com/us.yimg.com/i/us/ysm/misc/pdf/eworkbook.pdf.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  H. Information Systems
  H.m MISCELLANEOUS

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

General Terms:
Algorithms, Economics, Theory

Keywords:
ad auctions, bid optimization, optimal bidding, sponsored search