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

DOI10.1007/978-3-031-43254-5_3MaRDI QIDQ6546277zbMATHFDO

Authors Vittorio Bilò, Kristoffer Arnsfelt Hansen, Marios Mavronicolas

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)

Recommendations

• The complexity of decision problems about Nash equilibria in win-lose games
• On the computational complexity of decision problems about multi-player Nash equilibria
• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• On the computational complexity of decision problems about multi-player Nash equilibria
• \(\exists\mathbb{R}\)-complete decision problems about symmetric Nash equilibria in symmetric multi-player games

Cites work

• Acceptable points in games of perfect information
• Approximating the existential theory of the reals
• Computational complexity of multi-player evolutionarily stable strategies
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• Exotic quantifiers, complexity classes, and complete problems
• Fixed points, Nash equilibria, and the existential theory of the reals
• Game theory. Translated from the Hebrew by Ziv Hellman and edited by Mike Borns
• Inapproximability of NP-complete variants of Nash equilibrium
• Inapproximability results for constrained approximate Nash equilibria
• Nash and correlated equilibria: Some complexity considerations
• New complexity results about Nash equilibria
• Non-cooperative games
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the computational complexity of decision problems about multi-player Nash equilibria
• Settling the complexity of computing two-player Nash equilibria
• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• The complexity of computing a Nash equilibrium
• The computational complexity of some problems of linear algebra
• 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

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