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

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

Marios Mavronicolas, Kristoffer Arnsfelt Hansen, Vittorio Bilò

Publication date: 29 May 2024

Mathematics Subject Classification ID

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

Cites Work

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

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

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