Optimal delivery of sponsored search advertisements subject to budget constraints

ABSTRACT

We discuss an auction framework in which sponsored search advertisements are delivered in response to queries. In practice, the presence of bidder budgets can have a significant impact on the ad delivery process. We propose an approach based on linear programming which takes bidder budgets into account, and uses them in conjunction with forecasting of query frequencies, and pricing and ranking schemes, to optimize ad delivery. Simulations show significant improvements in revenue and efficiency.

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: 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]
• 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: J. J. Carrasco, D. Fain, K. Lang, and L. Zhukov. Clustering of bipartite advertiser-keyword graphs. Workshop on Large Scale Clustering at IEEE International Conference on Data Mining, 2003.
• 5: E. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
• 6: G. B. Dantzig. Linear Programming and Extensions. Princeton University Press, Princeton, NJ, 1963.
• 7: I. de Farias and G. Nemhauser. A polyhedral study of the cardinality constrained knapsack problem. Mathematical Programming (Ser. A), 96:439--467,2003.
• 8: B. Dietrich and J. J. Forrest. A column generation approach for combinatorial auctions. Workshop on Mathematics of the Internet: E-Auction and Markets Institute for Mathematics and its Applications, 2001.
• 9: B. Edelman, M. Ostrovsky, and M. Schwarz. Internet advertising and the generalizaed second price auction: Selling billions of dollars worth of keywords. Second Workshop on Sponsored Search Auctions, Ann Arbor, MI. June, 2006.
• 10: T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
• 11: R. Lougee-Heimer, F. Barahona, B. L. Dietrich, J. Fasano, J. J. Forrest, R. Harder, L. Ladanyi, T. Pfender, T. Ralphs, M. Saltzman, and K. Scheinberg. The COIN-OR initiative: accelerating operations research progress through open-source software. ORMS Today, 28(5), 2001.
• 12: Marco E. Lübbecke , Jacques Desrosiers, Selected Topics in Column Generation, Operations Research, v.53 n.6, p.1007-1023, November-December 2005 [doi>10.1287/opre.1050.0234]
• 13: Mohammad Mahdian , Hamid Nazerzadeh , Amin Saberi, Allocating online advertisement space with unreliable estimates, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250952]
• 14: COIN-OR Foundation: http://www.coin-or.org+.
• 15: S. Sathiya Keerthi and J. A. Tomlin. Constructing an optimal slate of advertisements. Yahoo! Research Report, 2006.
• 16: L. Schrage. Solving multi-object auctions with LP/IP. University of Chicago, Unpublished Manuscript, 2001.
• 17: Craig Silverstein , Hannes Marais , Monika Henzinger , Michael Moricz, Analysis of a very large web search engine query log, ACM SIGIR Forum, v.33 n.1, p.6-12, Fall 1999 [doi>10.1145/331403.331405]
• 18: 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]
• 19: W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Performance

Keywords:
advertising, budgets, column generation, sponsored search