Algorithms and complexity for computing Nash equilibria in adversarial team games

DOI10.1016/J.GEB.2026.01.006MaRDI QIDQ6839162zbMATH OpenFDO

Authors Ioannis Anagnostides, Fivos Kalogiannis, Ioannis Panageas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Stephen Mcaleer

Publication date 24 March 2026

Published in Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.GEB.2026.01.006

zbMATH Keywords

adversarial potential gameadversarial team gamesCLScomplexityNash equilibriumpotential games

Mathematics Subject Classification ID

Game theory, economics, finance, and other social and behavioral sciences (91-XX)

Cites work

• 10.1162/1532443041424328
• A class of games possessing pure-strategy Nash equilibria
• A converse to Banach's fixed point theorem and its CLS-completeness
• A faster cutting plane method and its implications for combinatorial and convex optimization
• Adventures in monotone complexity and TFNP
• Algorithms, games, and evolution
• Behavior strategies, mixed strategies and perfect recall
• Computing correlated equilibria in multi-player games
• Congestion games with malicious players
• Distinguishability of Sets of Distributions
• Elements for a theory of teams
• Further collapses in TFNP
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• How easy is local search?
• scientific article; zbMATH DE number 5145289 (Why is no real title available?)
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• Non-cooperative games
• On the complexity of approximating a Nash equilibrium
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of the parity argument and other inefficient proofs of existence
• On the interpretation of decision problems with imperfect recall
• On the NP-completeness of finding an optimal strategy in games with common payoffs
• Sampling equilibria: fast no-regret learning in structured games
• Settling the complexity of computing approximate two-player Nash equilibria
• Settling the complexity of computing two-player Nash equilibria
• Settling the complexity of Nash equilibrium in congestion games
• Team-maxmin equilibria
• The complexity of computing a Nash equilibrium
• The complexity of constrained min-max optimization
• The complexity of gradient descent: CLS = PPAD ∩ PLS
• The duality gap for two-team zero-sum games
• The equivalence of linear programs and zero-sum games
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• The myth of the folk theorem
• Unique end of potential line

This page was built for publication: Algorithms and complexity for computing Nash equilibria in adversarial team games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6839162)