Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games

DOI10.4230/LIPIcs.STACS.2017.13zbMath1402.68070OpenAlexW2604467574MaRDI QIDQ4636611

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

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

Related Items (10)

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 \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values ⋮ Unnamed Item ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Approximating the existential theory of the reals ⋮ Approximating the existential theory of the reals ⋮ On the computational complexity of decision problems about multi-player Nash equilibria ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem ⋮ Computational complexity of multi-player evolutionarily stable strategies

This page was built for publication: Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games