A catalog of ∃ℝ-complete decision problems about Nash equilibria in multi-player games
Date
2016Author
Bilò, VittorioMavronicolas, Marios
ISBN
978-3-95977-001-9Publisher
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl PublishingSource
Leibniz International Proceedings in Informatics, LIPIcs33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016
Volume
47Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
[Schaefer and Štefankovic, Theory of Computing Systems, 2015] provided an explicit formulation of ∃ℝ as the class capturing the complexity of deciding the Existential Theory of the Reals, and established that deciding, given a 3-player game, whether or not it has a Nash equilibrium with no probability exceeding a given rational is ∃ℝ-complete. Four more decision problems about Nash equilibria for 3-player games were very recently shown ∃ℝ-complete via a chain of individual, problem-specific reductions in [Garg et al., Proceedings of ICALP 2015] determining more such ∃ℝ-complete problems was posed there as an open problem. In this work, we deliver an extensive catalog of ∃ℝ-complete decision problems about Nash equilibria in 3-player games, thus resolving completely the open problem from [Garg et al., Proceedings of ICALP 2015]. Towards this end, we present a single and very simple, unifying reduction from the ∃ℝ-complete decision problem from [Schaefer and Štefankovic, Theory of Computing Systems, 2015] to (almost) all the decision problems about Nash equilibria that were before shown NP-complete for 2-player games in [Bilò and Mavronicolas, Proceedings of SAGT 2012 Conitzer and Sandholm, Games and Economic Behavior, 2008 Gilboa and Zemel, Games and Economic Behavior, 1989]. Encompassed in the catalog are the four decision problems shown ∃ℝ-complete in [Garg et al., Proceedings of ICALP 2015]. © Vittorio Bilò and Marios Mavronicolas licensed under Creative Commons License CC-BY.