∃ℝ-complete decision problems about symmetric nash equilibria in symmetric multi-player games
Ημερομηνία
2017Συγγραφέας
Bilò, VittorioMavronicolas, Marios
ISBN
978-3-95977-028-6Εκδότης
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl PublishingSource
Leibniz International Proceedings in Informatics, LIPIcs34th Symposium on Theoretical Aspects of Computer Science, STACS 2017
Volume
66Google Scholar check
Keyword(s):
Metadata
Εμφάνιση πλήρους εγγραφήςΕπιτομή
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 ∃ℝ-complete that is, they are exactly as hard as deciding the Existential Theory of the Reals. © Vittorio Bilò and Marios Mavronicolas.