Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria

Ioannis Anagnostides, Ian Gemp, Georgios Piliouras, Kelly Spendlove

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 - ε$ is NP-hard for any constant $ε> 0$. Moreover, deciding whether there exists an autobidding equilibrium that attains a $1/2 + ε$ fraction of the optimal welfare -- unfettered by equilibrium constraints -- is NP-hard for any constant $ε> 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.
BibTeX
@misc{anagnostides2026tight,
  author = {Ioannis Anagnostides and Ian Gemp and Georgios Piliouras and Kelly Spendlove},
  title = {{Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria}},
  year = {2026},
  eprint = {2602.09110},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.09110},
}

Loading related content...

Figure