On the computational complexity of decision problems about multi-player Nash equilibria
From MaRDI portal
Publication:5918702
DOI10.1007/s00224-022-10080-1zbMath1493.91005OpenAlexW3000000514MaRDI QIDQ5918702
Kristoffer Arnsfelt Hansen, Marie Louisa Tølbøll Berthelsen
Publication date: 21 June 2022
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-022-10080-1
(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
- 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
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- Nash and correlated equilibria: Some complexity considerations
- The computational complexity of some problems of linear algebra
- Complexity of rational and irrational Nash equilibria
- Non-cooperative games
- The complexity of computational problems about Nash equilibria in symmetric win-lose games
- Realizability of Graphs and Linkages
- On the Complexity of Nash Equilibria and Other Fixed Points
- Settling Some Open Problems on 2-Player Symmetric Nash Equilibria
- Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player 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
- Algorithms in real algebraic geometry
- 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
- Defining \(\mathbb Z\) in \(\mathbb Q\)
