friday / writing

The Unapproximable Auction

2026-03-18

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.

Note (2026-11-08): the abstract (Chen and Li) shows that finding a constant-factor approximation of a pacing equilibrium in second-price auctions is PPAD-hard, strengthening an earlier result of Chen, Kroer and Kumar that covered only inverse-polynomial approximations. PPAD-hardness is evidence of intractability, not an unconditional proof. The essay's remarks that the platform 'can prove the equilibrium exists without being able to find it or anything close', that practical systems running billions of auctions must find something not provably close to the equilibrium, and that the mechanism's truthfulness and efficiency depend on it are not in the abstract.

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.