Abstract: We examine the complexity of computing welfare- and revenue-maximizing equilibria in autobidding second-price auctions subject to return-on-spend (RoS) constraints. We show that computing an autobidding equilibrium that approximates the welfare-optimal one within a factor of $2 - \epsilon$ is NP-hard for any constant $\epsilon > 0$. Moreover, deciding whether there exists an autobidding equilibrium that attains a $1/2 + \epsilon$ fraction of the optimal welfare -- unfettered by equilibrium constraints -- is NP-hard for any constant $\epsilon > 0$. This hardness result is tight in view of the fact that the price of anarchy (PoA) is at most 2, and shows that deciding whether a non-trivial autobidding equilibrium exists -- one that is even marginally better than the worst-case guarantee -- is intractable. For revenue, we establish a stronger logarithmic inapproximability, while under the projection games conjecture, our reduction rules out even a polynomial approximation factor. These results significantly strengthen the APX-hardness of Li and Tang (AAAI '24). Furthermore, we refine our reduction in the presence of ML advice concerning the buyers' valuations, revealing again a close connection between the inapproximability threshold and PoA bounds. Finally, we examine relaxed notions of equilibrium attained by simple learning algorithms, establishing constant inapproximability for both revenue and welfare.
Introduction
In the high-stakes world of online advertising—a market that recently topped $1 trillion—the mechanism of bidding has undergone a fundamental shift. Advertisers have largely moved away from manual bid adjustments toward autobidding systems. In these systems, advertisers specify high-level objectives, such as maximizing conversions while maintaining a specific Return on Spend (RoS) constraint.
While this automation simplifies the advertiser's experience, it introduces significant complexity for platform designers. When multiple automated agents interact, they reach an equilibrium. Previous research established that the worst-case equilibrium in these auctions captures at least 50% of the theoretical maximum welfare (a Price of Anarchy of 2). However, a critical question remained: can a platform designer efficiently find or "steer" the system toward a better equilibrium? This research demonstrates that doing so is computationally intractable.
The Equilibrium Selection Problem
The central challenge addressed is equilibrium selection. In many auction settings, multiple equilibria exist. A system designer (e.g., Google or Meta) would ideally nudge the system toward the equilibrium that maximizes total "liquid welfare" (the value generated for advertisers) or platform revenue.
Earlier work indicated that this problem was APX-hard, meaning it is difficult to find an equilibrium very close to the optimum. This paper provides a tight bound, proving that it is NP-hard to approximate the welfare-optimal equilibrium within a factor of $2 - \epsilon$. Essentially, because the Price of Anarchy is 2, we are mathematically stuck with the worst-case guarantee; we cannot efficiently find an equilibrium that is even marginally better than the baseline.
Methodology: The Label Cover Reduction
To establish these hardness results, the authors employ a reduction from the Label Cover problem, a standard tool in computational complexity. The proof involves constructing a hypothetical auction "gadget" that encodes a hard logic problem into the auction's structure.
As shown in the reduction flowchart, the authors developed several novel components:
- Label Assignment Gadget: A configuration of bidders and items where, in equilibrium, only one bidder can "activate," representing a logic variable.
- AND/NAND/NOT Gadgets: These scenarios ensure the equilibrium behavior of a "result" bidder depends on the logical combination of "input" bidders.
- Edge Constraint Encoding: By stringing these gadgets together, the authors demonstrate that finding a high-welfare equilibrium is equivalent to solving a Label Cover instance, which is known to be NP-hard.
Key Results
Welfare and Revenue Hardness
The most striking insight is the PoA-Hardness Connection: the threshold for hardness ($2 - \epsilon$) exactly matches the Price of Anarchy (2). This suggests that the structural reasons allowing for "bad" equilibria also make it impossible to find "good" ones. For revenue, the results are even more severe, establishing logarithmic inapproximability, which may jump to polynomial inapproximability under the Projection Games Conjecture.
The Role of ML Advice
Even when the auctioneer has access to Machine Learning (ML) advice—a signal approximating the bidders' true values—the complexity remains. The authors show that the hardness threshold shifts in lockstep with the improved PoA bounds provided by that advice, maintaining the tight link between the two.
Learning Dynamics
The study extends to "responsive learning sequences," which model the actual step-by-step algorithms bidders use to update their bids in real-time. The research finds that even these dynamic processes are subject to constant-factor inapproximability for both revenue and welfare.
Conclusion and Future Work
These results provide a sobering reality check for auction design in the era of autobidding. The "marginal improvement paradox" shows that even seeking an equilibrium slightly better than the worst-case is NP-hard.
Future research may look toward other auction formats. While this study focuses on second-price auctions, the industry is increasingly adopting first-price or hybrid mechanisms. Extending this computational lens to those formats, and closing the remaining gaps in learning dynamics, will be essential for a complete understanding of automated auction efficiency.
Summary updated