A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.

DOI10.4230/LIPIcs.STACS.2016.17zbMath1388.68100OpenAlexW2296078827MaRDI QIDQ4601869

Marios Mavronicolas, Vittorio Bilò

Publication date: 24 January 2018

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5718/pdf/18.pdf/

zbMATH Keywords

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) (n)-person games, (n>2) (91A06) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

The complexity of computational problems about Nash equilibria in symmetric win-lose games ⋮ The complexity of the Hausdorff distance ⋮ Inapproximability Results for Approximate Nash Equilibria ⋮ Unnamed Item ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ The real computational complexity of minmax value and equilibrium refinements in multi-player games ⋮ Unnamed Item ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Approximating the existential theory of the reals ⋮ Approximating the existential theory of the reals ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem ⋮ Computational complexity of multi-player evolutionarily stable strategies