-complete decision problems about symmetric Nash equilibria in symmetric multi-player games

DOI10.4230/LIPICS.STACS.2017.13MaRDI QIDQ4636611zbMATH OpenOpenAlexFDO

Authors Vittorio Bilò, Marios Mavronicolas

Publication date 19 April 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.STACS.2017.13

zbMATH Keywords

Nash equilibriumcomplexity of equilibria\(\exists\mathbb{R}\)-completeness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) (n)-person games, (n>2) (91A06)

Recommendations

• On the computational complexity of decision problems about multi-player Nash equilibria
• On the computational complexity of decision problems about multi-player Nash equilibria
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• The complexity of computational problems about Nash equilibria in symmetric win-lose games

Cited in

(18)

• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• The complexity of recognizing geometric hypergraphs
• The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Settling some open problems on 2-player symmetric Nash equilibria
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• scientific article; zbMATH DE number 7559416 (Why is no real title available?)
• Inapproximability results for constrained approximate Nash equilibria
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• On the computational complexity of decision problems about multi-player Nash equilibria
• On the computational complexity of decision problems about multi-player Nash equilibria
• Approximating the existential theory of the reals
• Fixed points, Nash equilibria, and the existential theory of the reals
• Computational complexity of multi-player evolutionarily stable strategies
• Computational complexity of decision problems about Nash equilibria in win-lose multi-player games
• Approximating the existential theory of the reals

This page was built for publication: \(\exists\mathbb{R}\)-complete decision problems about symmetric Nash equilibria in symmetric multi-player games

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