# The Complexity of Pacing for Second-Price Auctions

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2021.

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

- [Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics](https://mlsanity.com/paper/2301.13306/) (2023)
- [Optimal Spend Rate Estimation and Pacing for Ad Campaigns with Budgets](https://mlsanity.com/paper/2202.05881/) (2022)
- [Robust Budget Pacing with a Single Sample](https://mlsanity.com/paper/2302.02006/) (2023)
- [Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint](https://mlsanity.com/paper/2502.05599/) (2025)
- [Large-Scale Auto-bidding with Nash Equilibrium Constraints](https://mlsanity.com/paper/2503.10304/) (2025)

## Abstract (arXiv)

Budget constraints are ubiquitous in online advertisement auctions. To manage these constraints and smooth out the expenditure across auctions, the bidders (or the platform on behalf of them) often employ pacing: each bidder is assigned a pacing multiplier between zero and one, and her bid on each item is multiplicatively scaled down by the pacing multiplier. This naturally gives rise to a game in which each bidder strategically selects a multiplier. The appropriate notion of equilibrium in this game is known as a pacing equilibrium. In this work, we show that the problem of finding an approximate pacing equilibrium is PPAD-complete for second-price auctions. This resolves an open question of Conitzer et al. [2021]. As a consequence of our hardness result, we show that the tatonnement-style budget-management dynamics introduced by Borgs et al. [2007] are unlikely to converge efficiently for repeated second-price auctions. This disproves a conjecture by Borgs et al. [2007], under the assumption that the complexity class PPAD is not equal to P. Our hardness result also implies the existence of a refinement of supply-aware market equilibria which is hard to compute with simple linear utilities.