2026-07-23T15:11:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5718 2024-03-06T10:36:55Z ddc:004 open_access

A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games Bilò, Vittorio Mavronicolas, Marios Nash equilibrium complexity of equilibria EXISTS-R-completeness [Schaefer and Stefankovic, Theory of Computing Systems, 2015] provided an explicit formulation of EXISTS-R 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 EXISTS-R-complete. Four more decision problems about Nash equilibria for 3-player games were very recently shown EXISTS-R-complete via a chain of individual, problem-specific reductions in [Garg et al., Proceedings of ICALP 2015]; determining more such EXISTS-R-complete problems was posed there as an open problem. In this work, we deliver an extensive catalog of EXISTS-R-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 EXISTS-R-complete decision problem from [Schaefer and Stefankovic, 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 [Bilo 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 EXISTS-R-complete in [Garg et al., Proceedings of ICALP 2015]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vittorio Bilò and Marios Mavronicolas 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.17 urn:nbn:de:0030-drops-57189 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.17 eng https://creativecommons.org/licenses/by/3.0/legalcode