Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria
arXiv:2602.09110v1 Announce Type: new 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 […]