Computational complexity of decision problems about Nash equilibria in win-lose multi-player games

DOI10.1007/978-3-031-43254-5_3zbMATH Open1537.9105MaRDI QIDQ6546277

Marios Mavronicolas, Kristoffer Arnsfelt Hansen, Vittorio Bilò

Publication date: 29 May 2024

Mathematics Subject Classification ID

(n)-person games, (n>2) (91A06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decision theory for games (91A35) Algorithmic game theory and complexity (91A68)

Cites Work

• Unnamed Item
• Fixed points, Nash equilibria, and the existential theory of the reals
• Acceptable points in games of perfect information
• New complexity results about Nash equilibria
• Exotic quantifiers, complexity classes, and complete problems
• Nash and correlated equilibria: Some complexity considerations
• The computational complexity of some problems of linear algebra
• Inapproximability results for constrained approximate Nash equilibria
• Computational complexity of multi-player evolutionarily stable strategies
• Non-cooperative games
• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• On the Complexity of Nash Equilibria and Other Fixed Points
• ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
• Settling the complexity of computing two-player Nash equilibria
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• The Complexity of Computing a Nash Equilibrium
• Game Theory
• Approximating the existential theory of the reals
• On the computational complexity of decision problems about multi-player Nash equilibria
• The real computational complexity of minmax value and equilibrium refinements in multi-player games

This page was built for publication: Computational complexity of decision problems about Nash equilibria in win-lose multi-player games