Chinmay Karande
Ramakrishnan Srikant
ABSTRACT
Search engine ad auctions typically have a significant fraction of advertisers who are budget constrained, i.e., if allowed to participate in every auction that they bid on, they would spend more than their budget. This yields an important problem: selecting the ad auctions which these advertisers participate, in order to optimize different system objectives such as the return on investment for advertisers, and the quality of ads shown to users. We present a system and algorithms for optimizing budget constrained spend. The system is designed be deployed in a large search engine, with hundreds of thousands of advertisers, millions of searches per hour, and with the query stream being only partially predictable. We have validated the system design by implementing it in the Google ads serving system and running experiments on live traffic. We have also compared our algorithm to previous work that casts this problem as a large linear programming problem limited to popular queries, and show that our algorithms yield substantially better results.
- Google automatic bidding product. http://adwords.google.com/support/aw/bin/answer.py?hl=en&answer=113234.Google Scholar
- Google conversion optimizer product. http://www.google.com/adwords/conversionoptimizer/.Google Scholar
- Protocol buffers. Website, 2008. http://code.google.com/p/protobuf.Google Scholar
- Z. Abrams. Revenue maximization when bidders have budgets. In SODA, 2006. Google ScholarDigital Library
- Z. Abrams, S. Keerthi, O. Mendelevitch, and J. Tomlin. Ad delivery with budgeted advertisers: a comprehensive lp approach. J. Electronic Commerce Research, 9(1), 2008.Google Scholar
- G. Aggarwal, A. Goel, and R. Motwani. Truthful auctions for pricing search keywords. In EC, 2006. Google ScholarDigital Library
- C. Borgs, J. Chayes, N. Immorlica, K. Jain, O. Etesami, and M. Mahdian. Dynamics of bid optimization in online advertisement auctions. In Proc. of the 16th international conference on World Wide Web, pages 531--540. ACM, 2007. Google ScholarDigital Library
- C. Borgs, J. Chayes, N. Immorlica, M. Mahdian, and A. Saberi. Multi-unit auctions with budget-constrained bidders. In EC, pages 44--51, 2005. Google ScholarDigital Library
- N. Buchbinder, K. Jain, and J. Naor. Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue. In ESA, 2007. Google ScholarDigital Library
- M. Cary, A. Das, B. Edelman, I. Giotis, K. Heimerl, A. Karlin, C. Mathieu, and M. Schwarz. Greedy bidding strategies for keyword auctions. In Proc. of the 8th ACM conference on Electronic commerce, pages 262--271. ACM New York, NY, USA, 2007. Google ScholarDigital Library
- D. X. Charles, M. Chickering, N. R. Devanur, K. Jain, and M. Sanghi. Fast algorithms for finding matchings in lopsided bipartite graphs with applications to display ads. In ACM Conference on Electronic Commerce, pages 121--128, 2010. Google ScholarDigital Library
- Y. Chen, P. Berkhin, B. Anderson, and N. Devanur. Real-time bidding algorithms for performance-based display ad allocation. In KDD, pages 1307--1315. ACM, 2011. Google ScholarDigital Library
- N. R. Devanur and T. P. Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In ACM Conference on Electronic Commerce, pages 71--78, 2009. Google ScholarDigital Library
- B. Edelman, M. Ostrovsky, and M. Schwarz. Internet Advertising and the Generalized Second-Price Auction. American Economic Review, 97(1):242--259, 2007.Google ScholarCross Ref
- J. Feldman, M. Henzinger, N. Korula, V. S. Mirrokni, and C. Stein. Online stochastic packing applied to display ad allocation. In ESA (1), pages 182--194, 2010. Google ScholarDigital Library
- J. Feldman, N. Korula, V. S. Mirrokni, S. Muthukrishnan, and M. Pál. Online ad assignment with free disposal. In WINE, pages 374--385, 2009. Google ScholarDigital Library
- J. Feldman, S. Muthukrishnan, M. Pal, and C. Stein. Budget optimization in search-based advertising auctions. In EC, 2007. Google ScholarDigital Library
- S. Ghemawat, H. Gobioff, and S.-T. Leung. The Google File System. In 19th ACM Symposium on Operating Systems Principles, 2003. Google ScholarDigital Library
- G. Goel and A. Mehta. Online budgeted matching in random input models with applications to Adwords. In SODA, 2008. Google ScholarDigital Library
- K. Hosanagar and V. Cherepanov. Optimal bidding in stochastic budget constrained slot auctions. In EC, 2008. Google ScholarDigital Library
- M. Mahdian, H. Nazerzadeh, and A. Saberi. Allocating online advertisement space with unreliable estimates. In EC, 2007. Google ScholarDigital Library
- A. Mehta, A. Saberi, U. V. Vazirani, and V. V. Vazirani. Adwords and generalized online matching. J. ACM, 54(5), 2007. Google ScholarDigital Library
- R. Pike, S. Dorward, R. Griesemer, and S. Quinlan. Interpreting the data: Parallel analysis with sawzall. Scientific Programming Journal, 13:277--298, 2005. Google ScholarDigital Library
- P. Rusmevichientong and D. Williamson. An adaptive algorithm for selecting profitable keywords for search-based advertising services. In EC, 2006. Google ScholarDigital Library
- H. Varian. Position auctions. International Journal of Industrial Organization, 25(6):1163--1178, 2007.Google ScholarCross Ref
- E. Vee, S. Vassilvitskii, and J. Shanmugasundaram. Optimal online assignment with forecasts. In ACM Conference on Electronic Commerce, pages 109--118, 2010. Google ScholarDigital Library
Index Terms
- Optimizing budget constrained spend in search advertising
Recommendations
Real time bid optimization with smooth budget delivery in online advertising
ADKDD '13: Proceedings of the Seventh International Workshop on Data Mining for Online AdvertisingToday, billions of display ad impressions are purchased on a daily basis through a public auction hosted by real time bidding (RTB) exchanges. A decision has to be made for advertisers to submit a bid for each selected RTB ad request in milliseconds. ...
An empirical analysis of sponsored search performance in search engine advertising
WSDM '08: Proceedings of the 2008 International Conference on Web Search and Data MiningThe phenomenon of sponsored search advertising - where advertisers pay a fee to Internet search engines to be displayed alongside organic (non-sponsored) web search results - is gaining ground as the largest source of revenues for search engines. ...
An Empirical Analysis of Search Engine Advertising: Sponsored Search in Electronic Markets
The phenomenon of sponsored search advertising---where advertisers pay a fee to Internet search engines to be displayed alongside organic (nonsponsored) Web search results---is gaining ground as the largest source of revenues for search engines. Using a ...
Reviews
Amos O Olagunju
Business organizations have limited advertising budgets. Consequently, Internet ad search engines should be designed to bid on advertisement auctions within budget constraints. The selection of ad auctions for competing advertisers is a two-sided problem. How does an auction search engine provide worthwhile ads to users, while simultaneously ensuring fail-safe investment profits for advertisers__?__ The authors of this paper investigate the issues of optimizing advertising budgets for auctions based on desired investment profits and ad quality. Typically, advertisers determine their participation in auctions within their budget constraints. However, the authors propose that a search engine could limit the participation of advertisers in auctions based on their budgets and ad objectives, such as increasing investment profits, decreasing cost-per-click, maximizing the quality of ads to display, and optimizing the ad quality relative to clicks. To that end, the authors design and implement a system equipped with optimization algorithms for fair allocations of budgets based on ad objectives. In the algorithms, the historical ad traffic data and existing budgets are used to (a) compute the impression probabilities for allowing advertisers to participate in auctions; (b) rank the impressions of each advertiser based on the ad objectives, for use in selecting the best impressions until the budget is expended; and (c) compress the impression ranks into a histogram to decide if an advertiser with a budget constraint should participate in a given auction. The accuracy and relevance of the bid optimized budget allocation algorithms for ad auctions are evaluated in offline and live simulation experiments. Contrary to the ad-auctioning algorithms proposed in this paper, at the exorbitant cost of processing times, the well-known linear programming algorithms [1,2] support the investigation of the effects of all budget constraints of advertisers. Unlike traditional bid algorithms [3], the authors offer an alternative bid-scaling algorithm to all advertisers. This paper proposes a family of throttling algorithms for optimizing the limited ad search budget advertisements that promise future ad opportunities for businesses. Ideally, businesses would be able to make decisions by weighing clicks-per-dollar, profit-per-dollar, and multiple advertisement objectives using reliable optimization algorithms. The authors present reliable algorithms and results for accomplishing these goals. Theoretical scientists should weigh in on the tradeoffs between processing times and memory used by complex optimization algorithms that promote more accurate ad auctions within budget constraints. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments