# Dynamic Budget Throttling in Repeated Second-Price Auctions

arXiv: https://arxiv.org/abs/2207.04690 · HTML: https://mlsanity.com/paper/2207.04690/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 66 references that are in the map.
- First posted on arXiv 11 Jul 2022.

## Builds on (most cited first, 25 of 25)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Resourceful Contextual Bandits](https://mlsanity.com/paper/1402.6779/) (2014)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits](https://mlsanity.com/paper/1504.06937/) (2015)
- [Simple and Fast Algorithm for Binary Integer and Online Linear Programming](https://mlsanity.com/paper/2003.02513/) (2020)
- [Uniformly bounded regret in the multi-secretary problem](https://mlsanity.com/paper/1710.07719/) (2017)
- [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018)
- [Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence](https://mlsanity.com/paper/2205.08674/) (2022)
- [Multiplicative Pacing Equilibria in Auction Markets](https://mlsanity.com/paper/1706.07151/) (2017)
- [Smart Pacing for Effective Online Ad Campaign Optimization](https://mlsanity.com/paper/1506.05851/) (2015)
- [Pacing Equilibrium in First-Price Auction Markets](https://mlsanity.com/paper/1811.07166/) (2018)
- [Real Time Bid Optimization with Smooth Budget Delivery in Online Advertising](https://mlsanity.com/paper/1305.3011/) (2013)
- [The Bayesian Prophet: A Low-Regret Framework for Online Decision Making](https://mlsanity.com/paper/1901.05028/) (2019)
- [Online Contextual Decision-Making with a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2206.07316/) (2022)
- [How the Experts Algorithm Can Help Solve LPs Online](https://mlsanity.com/paper/1407.5298/) (2014)
- [Near-Optimal Primal-Dual Algorithms for Quantity-Based Network Revenue Management](https://mlsanity.com/paper/2011.06327/) (2020)
- [Optimal Real-Time Bidding Strategies](https://mlsanity.com/paper/1511.08409/) (2015)
- [The Parity Ray Regularizer for Pacing in Auction Markets](https://mlsanity.com/paper/2106.09503/) (2021)
- [Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards](https://mlsanity.com/paper/1809.02016/) (2018)
- [Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees](https://mlsanity.com/paper/2102.10476/) (2021)
- [Analysis of a Learning Based Algorithm for Budget Pacing](https://mlsanity.com/paper/2205.13330/) (2022)
- [Throttling Equilibria in Auction Markets](https://mlsanity.com/paper/2107.10923/) (2021)

## Built on by (most cited first, 2 of 2)

- [Coordinated Dynamic Bidding in Repeated Second-Price Auctions with Budgets](https://mlsanity.com/paper/2306.07709/) (2023)
- [Multi-Platform Budget Management in Ad Markets with Non-IC Auctions](https://mlsanity.com/paper/2306.07352/) (2023)

## Abstract (arXiv)

In today's online advertising markets, a crucial requirement for an advertiser is to control her total expenditure within a time horizon under some budget. Among various budget control methods, throttling has emerged as a popular choice, managing an advertiser's total expenditure by selecting only a subset of auctions to participate in. This paper provides a theoretical panorama of a single advertiser's dynamic budget throttling process in repeated second-price auctions. We first establish a lower bound on the regret and an upper bound on the asymptotic competitive ratio for any throttling algorithm, respectively, when the advertiser's values are stochastic and adversarial. Regarding the algorithmic side, we propose the OGD-CB algorithm, which guarantees a near-optimal expected regret with stochastic values. On the other hand, when values are adversarial, we prove that this algorithm also reaches the upper bound on the asymptotic competitive ratio. We further compare throttling with pacing, another widely adopted budget control method, in repeated second-price auctions. In the stochastic case, we demonstrate that pacing is generally superior to throttling for the advertiser, supporting the well-known result that pacing is asymptotically optimal in this scenario. However, in the adversarial case, we give an exciting result indicating that throttling is also an asymptotically optimal dynamic bidding strategy. Our results bridge the gaps in theoretical research of throttling in repeated auctions and comprehensively reveal the ability of this popular budget-smoothing strategy.