Buchumschlag

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Anagnostides, Ioannis, Panageas, Ioannis, Sandholm, Tuomas, Yan, Jingming
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computer Science and Game Theory Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem
von: Kalogiannis, Fivos, et al.
Veröffentlicht: (2024)

Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2023)

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

(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2026)

On the Interplay between Social Welfare and Tractability of Equilibria
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2023)

Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
von: Daskalakis, Constantinos, et al.
Veröffentlicht: (2018)

Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games
von: Zhang, Brian Hu, et al.
Veröffentlicht: (2025)

On the Complexity of Correlated Equilibria Beyond Normal-Form Games
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2026)

Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization
von: Zhang, Brian Hu, et al.
Veröffentlicht: (2022)

Convergence of Regret Matching in Potential Games and Constrained Optimization
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2025)

Computational Lower Bounds for Regret Minimization in Normal-Form Games
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2024)

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

The Complexity of Min-Max Optimization with Product Constraints
von: Bernasconi, Martino, et al.
Veröffentlicht: (2026)

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

The Complexity of Proper Equilibrium in Extensive-Form and Polytope Games
von: Zhang, Brian Hu, et al.
Veröffentlicht: (2026)

Barriers to Welfare Maximization with No-Regret Learning
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2024)

The Complexity of Equilibrium Refinements in Potential Games
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2025)

Improved Hardness Results for Min-Max Optimization with Coupled Constraints
von: Bernasconi, Martino, et al.
Veröffentlicht: (2024)

Exponential Lower Bounds on the Double Oracle Algorithm in Zero-Sum Games
von: Zhang, Brian Hu, et al.
Veröffentlicht: (2024)

On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games
von: Hansen, Kristoffer Arnsfelt, et al.
Veröffentlicht: (2025)

The Complexity of Symmetric Bimatrix Games with Common Payoffs
von: Ghosh, Abheek, et al.
Veröffentlicht: (2024)

Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability
von: Zhang, Brian Hu, et al.
Veröffentlicht: (2025)

Computing Nash Equilibria in Potential Games with Private Uncoupled Constraints
von: Patris, Nikolas, et al.
Veröffentlicht: (2024)

On the Complexity of Learning Nash Equilibria
von: Biggar, Oliver, et al.
Veröffentlicht: (2026)

Position: Machine Learning for Heart Transplant Allocation Policy Optimization Should Account for Incentives
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2026)

Efficiently Computing Equilibria in Budget-Aggregation Games
von: Becker, Patrick, et al.
Veröffentlicht: (2025)

Tight Inapproximability of Nash Equilibria in Public Goods Games
von: Dinh, Jérémi Do, et al.
Veröffentlicht: (2024)

Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2026)

A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2025)

On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games
von: Cheval, Vincent, et al.
Veröffentlicht: (2025)

Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Extensive-Form Games
von: Zhang, Brian Hu, et al.
Veröffentlicht: (2023)

Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria
von: Barakat, Anas, et al.
Veröffentlicht: (2026)

On the Outcome Equivalence of Extensive-Form and Behavioral Correlated Equilibria
von: Zhang, Brian Hu, et al.
Veröffentlicht: (2024)

Multiplicative weights, equalizers, and P=PPAD
von: Avramopoulos, Ioannis
Veröffentlicht: (2016)

Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
von: Li, Tongyang, et al.
Veröffentlicht: (2025)

Hardness of Approximate Hylland-Zeckhauser Equilibria
von: Braverman, Mark, et al.
Veröffentlicht: (2026)

On the Computation of Equilibria in Discrete First-Price Auctions
von: Filos-Ratsikas, Aris, et al.
Veröffentlicht: (2024)

Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
von: Chen, Xi, et al.
Veröffentlicht: (2025)

A Smoothed FPTAS for Equilibria in Congestion Games
von: Giannakopoulos, Yiannis
Veröffentlicht: (2023)

Solving Infinite-Player Games with Player-to-Strategy Networks
von: Martin, Carlos, et al.
Veröffentlicht: (2025)