Cover Image

Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Anagnostides, Ioannis, Gemp, Ian, Piliouras, Georgios, Spendlove, Kelly
Format:	Preprint
Published:	2026
Subjects:	Computer Science and Game Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Chaos in Autobidding Auctions
by: Anagnostides, Ioannis, et al.
Published: (2026)

Complex Dynamics in Autobidding Systems
by: Leme, Renato Paes, et al.
Published: (2024)

Autobidding Equilibria in Sponsored Shopping
by: Dütting, Paul, et al.
Published: (2026)

Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization
by: Gemp, Ian, et al.
Published: (2023)

On the Interplay between Social Welfare and Tractability of Equilibria
by: Anagnostides, Ioannis, et al.
Published: (2023)

Barriers to Welfare Maximization with No-Regret Learning
by: Anagnostides, Ioannis, et al.
Published: (2024)

Nash Equilibria via Stochastic Eigendecomposition
by: Gemp, Ian
Published: (2024)

Tight Inapproximability of Nash Equilibria in Public Goods Games
by: Dinh, Jérémi Do, et al.
Published: (2024)

NfgTransformer: Equivariant Representation Learning for Normal-form Games
by: Liu, Siqi, et al.
Published: (2024)

On the Complexity of Learning Nash Equilibria
by: Biggar, Oliver, et al.
Published: (2026)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

Visualizing 2x2 Normal-Form Games: twoxtwogame LaTeX Package
by: Marris, Luke, et al.
Published: (2024)

Revenue Guarantees in Autobidding Platforms
by: Caragiannis, Ioannis, et al.
Published: (2026)

Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning
by: Gemp, Ian, et al.
Published: (2024)

Optimal Type-Dependent Liquid Welfare Guarantees for Autobidding Agents with Budgets
by: Colini-Baldeschi, Riccardo, et al.
Published: (2025)

Pure-Circuit: Tight Inapproximability for PPAD
by: Deligkas, Argyrios, et al.
Published: (2022)

Multidimensional Bayesian Utility Maximization: Tight Approximations to Welfare
by: Goldner, Kira, et al.
Published: (2024)

On the Complexity of Correlated Equilibria Beyond Normal-Form Games
by: Anagnostides, Ioannis, et al.
Published: (2026)

Deviation Ratings: A General, Clone-Invariant Rating Method
by: Marris, Luke, et al.
Published: (2025)

Charting the Shapes of Stories with Game Theory
by: Daskalakis, Constantinos, et al.
Published: (2024)

Re-evaluating Open-ended Evaluation of Large Language Models
by: Liu, Siqi, et al.
Published: (2025)

Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
by: Chen, Xi, et al.
Published: (2025)

Convergence of $\text{log}(1/ε)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis
by: Anagnostides, Ioannis, et al.
Published: (2024)

Solving Zero-Sum Convex Markov Games
by: Kalogiannis, Fivos, et al.
Published: (2025)

Platform Competition in the Autobidding World
by: Aggarwal, Gagan, et al.
Published: (2024)

Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games
by: Leonardos, Stefanos, et al.
Published: (2021)

(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games
by: Anagnostides, Ioannis, et al.
Published: (2026)

Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
by: Anagnostides, Ioannis, et al.
Published: (2023)

Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability
by: Zhang, Brian Hu, et al.
Published: (2025)

Multi-Platform Autobidding with and without Predictions
by: Aggarwal, Gagan, et al.
Published: (2025)

Prediction Accuracy of Learning in Games : Follow-the-Regularized-Leader meets Heisenberg
by: Feng, Yi, et al.
Published: (2024)

Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games
by: Gemp, Ian, et al.
Published: (2026)

Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games
by: Zhang, Brian Hu, et al.
Published: (2023)

No-Regret Online Autobidding Algorithms in First-price Auctions
by: Deng, Yuan, et al.
Published: (2025)

Steering Language Models with Game-Theoretic Solvers
by: Gemp, Ian, et al.
Published: (2024)

Nearly Tight Bounds on Approximate Equilibria in Spatial Competition on the Line
by: Bhaskar, Umang, et al.
Published: (2024)

Efficient $Φ$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games
by: Zhang, Brian Hu, et al.
Published: (2024)

Computational Lower Bounds for Regret Minimization in Normal-Form Games
by: Anagnostides, Ioannis, et al.
Published: (2024)

A Note on EFX Inapproximability for Chores
by: Christoforidis, Vasilis
Published: (2026)

Learning Equilibria in Coordination Games via Minorization-Maximization
by: S., Ashok Krishnan K., et al.
Published: (2026)