arXiv preprint ·
The Power of Flexible Budgets in Adwords
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $DB_i$. Given a flexibility parameter $δ$, the platform may spend at most $δB_i$ on advertiser $i$ on any single day, subject to the horizon spending limit of $DB_i$. We quantify the power of $δ$-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 $δ$, we design an algorithm whose competitive ratio converges to $1-e^{-δ}$ 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 $δB_i$ each day and may spend up to $δD B_i$ over the horizon. Along the way, we characterize the exact optimal competitive ratio for every pair $(D,δ)$ on high-traffic instances, where the offline benchmark exhausts every advertiser's budget on every day.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Sparsification Framework for Directed Densest Subgraph
A Shortest Augmenting Path Algorithm for Linear Matroid Parity
Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2
Hamiltonian locality testing and certification do not achieve the Heisenberg limit
A Faster Auction Algorithm for Weighted Matroid Intersection
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.