Imagen de Portada

(Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Anagnostides, Ioannis, Panageas, Ioannis, Patris, Nikolas, Sandholm, Tuomas
Formato:	Preprint
Publicado:	2026
Materias:	Computer Science and Game Theory
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

Convergence of Regret Matching in Potential Games and Constrained Optimization
por: Anagnostides, Ioannis, et al.
Publicado: (2025)

Computing Nash Equilibria in Potential Games with Private Uncoupled Constraints
por: Patris, Nikolas, et al.
Publicado: (2024)

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

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

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

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

The Complexity of Equilibrium Refinements in Potential Games
por: Anagnostides, Ioannis, et al.
Publicado: (2025)

The Complexity of Proper Equilibrium in Extensive-Form and Polytope Games
por: Zhang, Brian Hu, et al.
Publicado: (2026)

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

A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition
por: Anagnostides, Ioannis, et al.
Publicado: (2025)

Position: Machine Learning for Heart Transplant Allocation Policy Optimization Should Account for Incentives
por: Anagnostides, Ioannis, et al.
Publicado: (2026)

A Lower Bound on Swap Regret in Extensive-Form Games
por: Daskalakis, Constantinos, et al.
Publicado: (2024)

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

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

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

Solving Infinite-Player Games with Player-to-Strategy Networks
por: Martin, Carlos, et al.
Publicado: (2025)

Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
por: Daskalakis, Constantinos, et al.
Publicado: (2018)

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

Efficient Kernelized Learning in Polyhedral Games Beyond Full-Information: From Colonel Blotto to Congestion Games
por: Kontogiannis, Andreas, et al.
Publicado: (2025)

Polynomial Convergence of Bandit No-Regret Dynamics in Congestion Games
por: Dadi, Leello, et al.
Publicado: (2024)

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

Equilibrium Refinements Improve Subgame Solving in Imperfect-Information Games
por: Kubicek, Ondrej, et al.
Publicado: (2026)

Domain-Independent Game Abstraction using Word Embedding Techniques
por: Kim, Juho, et al.
Publicado: (2026)

Faster Game Solving via Hyperparameter Schedules
por: Zhang, Naifeng, et al.
Publicado: (2024)

Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games
por: Feng, Yi, et al.
Publicado: (2024)

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

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

Simultaneous incremental support adjustment and metagame solving: An equilibrium-finding framework for continuous-action games
por: Martin, Carlos, et al.
Publicado: (2024)

Learning a Game by Paying the Agents
por: Zhang, Brian Hu, et al.
Publicado: (2025)

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

Expected Variational Inequalities
por: Zhang, Brian Hu, et al.
Publicado: (2025)

Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria
por: Anagnostides, Ioannis, et al.
Publicado: (2026)

Chaos in Autobidding Auctions
por: Anagnostides, Ioannis, et al.
Publicado: (2026)

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

Steering No-Regret Learners to a Desired Equilibrium
por: Zhang, Brian Hu, et al.
Publicado: (2023)

On the Outcome Equivalence of Extensive-Form and Behavioral Correlated Equilibria
por: Zhang, Brian Hu, et al.
Publicado: (2024)