  In this paper, we propose a stochastic model to describe how search service
providers charge client companies based on users' queries for the keywords
related to these companies' ads by using certain advertisement assignment
strategies. We formulate an optimization problem to maximize the long-term
average revenue for the service provider under each client's long-term average
budget constraint, and design an online algorithm which captures the stochastic
properties of users' queries and click-through behaviors. We solve the
optimization problem by making connections to scheduling problems in wireless
networks, queueing theory and stochastic networks. Unlike prior models, we do
not assume that the number of query arrivals is known. Due to the stochastic
nature of the arrival process considered here, either temporary "free" service,
i.e., service above the specified budget or under-utilization of the budget is
unavoidable. We prove that our online algorithm can achieve a revenue that is
within $O(\epsilon)$ of the optimal revenue while ensuring that the overdraft
or underdraft is $O(1/\epsilon)$, where $\epsilon$ can be arbitrarily small.
With a view towards practice, we can show that one can always operate strictly
under the budget. In addition, we extend our results to a click-through rate
maximization model, and also show how our algorithm can be modified to handle
non-stationary query arrival processes and clients with short-term contracts.
  Our algorithm allows us to quantify the effect of errors in click-through
rate estimation on the achieved revenue. We also show that in the long run, an
expected overdraft level of $\Omega(\log(1/\epsilon))$ is unavoidable (a
universal lower bound) under any stationary ad assignment algorithm which
achieves a long-term average revenue within $O(\epsilon)$ of the offline
optimum.
