Abstract
Internet search companies sell advertisement slots based on users’ search queries via an auction. Advertisers have to determine how to place bids on the keywords of their interest in order to maximize their return for a given budget: this is the budget optimization problem. The solution depends on the distribution of future queries. In this paper, we formulate stochastic versions of the budget optimization problem based on natural probabilistic models of distribution over future queries, and address two questions that arise.
Evaluation. Given a solution, can we evaluate the expected value of the objective function?
Optimization. Can we find a solution that maximizes the objective function in expectation?
Our main results are approximation and complexity results for these two problems in our three stochastic models. In particular, our algorithmic results show that simple prefix strategies that bid on all cheap keywords up to some level are either optimal or good approximations for many cases; we show other cases to be NP-hard.
A preliminary announcement of these results appears in the WWW Workshop on Sponsored Search, 2007.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, G., Goel, A., Motwani, R.: Truthful auctions for pricing search keywords. In: Proc. 8th ACM Conf. on Electronic Commerce, pp. 1–7 (2006)
Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: Proc. 10th APPROX (2007)
Borgs, C., Chayes, J., Etesami, O., Immorlica, N., Jain, K., Mahdian, M.: Bid optimization in online advertisement auctions. In: 16th International World Wide Web Conference (2007)
Borgs, C., Chayes, J., Immorlica, N., Mahdian, M., Saberi, A.: Multi-unit auctions with budget-constrained bidders. In: Proc. 7th ACM Conf. on Electronic Commerce, pp. 44–51 (2005)
Carraway, R.L., Schmidt, R.L., Weatherford, L.R.: An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns. Naval Research Logistics 40, 161–173 (1993)
Chakrabarty, D., Zhou, Y., Lukose, R.: Budget constrained bidding in keyword auctions and online knapsack problems. In: WWW 2007 Workshop on Sponsored Search Auctions (2007)
Charikar, M., Chekuri, C., Pal, M.: Sampling bounds for stochastic optimization. In: Proc. 9th International Workshop on Randomization and Computation (2005)
Dean, B.C., Goemans, M.X., Vondrak, J.: Approximating the stochastic knapsack problem: The benefit of adaptivity. In: Proc. 45th IEEE Symp. on Foundations of Computer Science, pp. 208–217 (2004)
Feldman, J., Muthukrishnan, S., Pal, M., Stein, C.: Budget optimization in search-based advertising auctions. In: Proc. 9th ACM Conf. on Electronic Commerce (2007)
Goel, A., Indyk, P.: Stochastic load balancing and related problems. In: Proc. 40th IEEE Symp. on Foundations of Computer Science (1999)
Henig, M.I.: Risk criteria in a stochastic knapsack problem. Oper. Res. 38(5), 820–825 (1990)
Kleinberg, J., Rabani, Y., Tardos, E.: Allocating bandwidth for bursty connections. SIAM Journal on Computing 30(1), 191–217 (2000)
Kleywegt, A.J., Shapiro, A., Homem-de-Mello, T.: The sample average approximation method for stochastic discrete optimization. SIAM J. on Optimization 12, 479–502 (2002)
Mahdian, M., Nazerzadeh, H., Saberi, A.: Allocating online advertisement space with unreliable estimates. In: Proc. 9th ACM Conf. on Electronic Commerce (2007)
Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized on-line matching. In: Proc. 46th IEEE Symp. on Foundations of Computer Science, pp. 264–273 (2005)
Ostrovsky, M., Edelman, B., Schwarz, M.: Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords (forthcoming). American Economic Review (2006)
Rusmevichientong, P., Williamson, D.P.: An adaptive algorithm for selecting profitable keywords for search-based advertising services. In: Proc. 8th ACM Conf. on Electronic Commerce, pp. 260–269 (2006)
Sniedovich, M.: Preference order stochastic knapsack problems: Methodological issues. The Journal of the Operational Research Society 31, 1025–1032 (1980)
Steinberg, E., Parks, M.: A preference order dynamic program for a knapsack problem with stochastic rewards. The Journal of the Operational Research Society 30(2), 141–147 (1979)
Swamy, C., Shmoys, D.B.: Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News 37(1), 33–46 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Muthukrishnan, S., Pál, M., Svitkina, Z. (2007). Stochastic Models for Budget Optimization in Search-Based Advertising. In: Deng, X., Graham, F.C. (eds) Internet and Network Economics. WINE 2007. Lecture Notes in Computer Science, vol 4858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77105-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-77105-0_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77104-3
Online ISBN: 978-3-540-77105-0
eBook Packages: Computer ScienceComputer Science (R0)