The Power of Flexible Budgets in Adwords

Abstract

Search advertising platforms routinely spend beyond an advertiser's average daily budget on high-traffic days, so long as total spending over the month stays within the monthly budget. Motivated by this practice, we study a $D$-day generalization of the Adwords problem (Mehta et al. 2007), where each advertiser $i$ has a nominal (average) daily budget $B_i$ and a total horizon (monthly) budget $D{B}_i$. Given a flexibility parameter $\delta$, the platform may spend at most $\delta B_i$ on advertiser $i$ on any single day, subject to the horizon spending limit of $D{B}_i$. We quantify the power of $\delta$-flexible budgets by benchmarking against the inflexible offline optimum, which may spend at most $B_i$ on advertiser $i$ on each day. We show that no amount of flexibility helps direct generalizations of the classical algorithm of Mehta et al. (2007). By contrast, for every fixed $\delta$, we design an algorithm whose competitive ratio converges to $1-e^{-\delta }$ as $D\to \infty$, and we show that this is asymptotically optimal. Perhaps surprisingly, this matches the optimal competitive ratio in a more permissive setting where the algorithm receives a fresh spending limit of $\delta B_i$ each day and may spend up to $\delta D{B}_i$ over the horizon. Along the way, we characterize the exact optimal competitive ratio for every pair $(D,\delta )$ on high-traffic instances, where the offline benchmark exhausts every advertiser's budget on every day.