∃ℝ-complete decision problems about symmetric nash equilibria in symmetric multi-player games
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
SourceLeibniz International Proceedings in Informatics, LIPIcs
34th Symposium on Theoretical Aspects of Computer Science, STACS 2017
Google Scholar check
MetadataShow full item record
We study the complexity of decision problems about symmetric Nash equilibria for symmetric multi-player games. These decision problems concern the existence of a symmetric Nash equilibrium with certain natural properties. We show that a handful of such decision problems are ∃ℝ-completethat is, they are exactly as hard as deciding the Existential Theory of the Reals. © Vittorio Bilò and Marios Mavronicolas.