Budget smoothing for internet ad auctions: a game theoretic approach

In Internet ad auctions, search engines often throttle budget constrained advertisers so as to spread their spends across the specified time period. Such policies are known as budget smoothing policies. In this paper, we perform a principled, game-theoretic study of what the outcome of an ideal budget smoothing algorithm should be. In particular, we propose the notion of regret-free budget smoothing policies whose outcomes throttle each advertiser optimally, given the participation of the other advertisers. We show that regret-free budget smoothing policies always exist, and in the case of single slot auctions we can give a polynomial time smoothing algorithm. Inspired by the existence proof, we design a heuristic for budget smoothing which performs considerably better than existing benchmark heuristics.