  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 multiplier between 0 and 1, and her bid on each item is
multiplicatively scaled down by the 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 the 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 [CKSSM17]. As a consequence of our hardness result, we show that
the tatonnement-style budget-management dynamics introduced by [BCI+07] is
unlikely to converge efficiently for repeated second-price auctions. Our
hardness result also implies the existence of a refinement of supply-aware
market equilibria which is hard to compute with simple linear utilities.
