TY - GEN
T1 - Stochastic models for budget optimization in search-based advertising
AU - Muthukrishnan, S.
AU - Pál, Martin
AU - Svitkina, Zoya
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=38449109438&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38449109438&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-77105-0_15
DO - 10.1007/978-3-540-77105-0_15
M3 - Conference contribution
AN - SCOPUS:38449109438
SN - 9783540771043
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 131
EP - 142
BT - Internet and Network Economics - Third International Workshop, WINE 2007, Proceedings
PB - Springer Verlag
T2 - 3rd International Workshop on Internet and Network Economics, WINE 2007
Y2 - 12 December 2007 through 14 December 2007
ER -