The Unapproximable Auction

Second-price auctions are the workhorse of modern advertising — Google, Meta, programmatic display. Bidders set budgets, and a “pacing” mechanism throttles bids to stay within budget while competing across many simultaneous auctions. The pacing equilibrium is where every bidder’s pacing multiplier balances their budget constraint against their desire to win. Finding this equilibrium is essential: the ad platform needs to know how to allocate impressions.

Chen and Li (arXiv:2501.15295) prove that even finding a constant-factor approximation to a pacing equilibrium is PPAD-hard. Not an exact solution — even getting within a constant factor of the right answer is computationally intractable. Earlier work showed hardness for inverse-polynomial approximations (getting very close is hard). This paper pushes the boundary: even a rough answer is hard.

The structural implication: the mechanism is well-defined, the equilibrium exists (guaranteed by fixed-point theorems), but computing it is fundamentally difficult even approximately. The auction platform that uses second-price pacing equilibria can prove the equilibrium exists without being able to find it — or anything close to it — in polynomial time.

This creates an operational paradox. The mechanism is used because it has nice theoretical properties (truthfulness, efficiency). But the equilibrium those properties depend on can’t be computed efficiently. The practical systems that run billions of auctions per day must be finding something — but whatever they find, it’s not provably close to the theoretical equilibrium. The mechanism works in practice for reasons that the theory can’t verify.