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

DOI10.4230/LIPICS.STACS.2017.13zbMATH Open1402.68070OpenAlexW2604467574MaRDI QIDQ4636611FDOQ4636611

Vittorio Bilò, Marios Mavronicolas

Publication date: 19 April 2018

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

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

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)

Cited In (13)

• 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
• 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
• Title not available (Why is that?)
• Inapproximability results for constrained approximate Nash equilibria
• On the computational complexity of decision problems about multi-player Nash equilibria
• Approximating the existential theory of the reals
• Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
• Approximating the existential theory of the reals
• Computational complexity of multi-player evolutionarily stable strategies
• The complexity of computational problems about Nash equilibria in symmetric win-lose games

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)