Bilò, Vittorio ;
Mavronicolas, Marios
A Catalog of EXISTSRComplete Decision Problems About Nash Equilibria in MultiPlayer Games
Abstract
[Schaefer and Stefankovic, Theory of Computing Systems, 2015] provided an explicit formulation of EXISTSR as the class capturing the complexity of deciding the Existential Theory of the Reals, and established that deciding, given a 3player game, whether or not it has a Nash equilibrium with no probability exceeding a given rational is EXISTSRcomplete. Four more decision problems about Nash equilibria for 3player games were very recently shown EXISTSRcomplete via a chain of individual, problemspecific reductions in [Garg et al., Proceedings of ICALP 2015]; determining more such EXISTSRcomplete problems was posed there as an open problem. In this work, we deliver an extensive catalog of EXISTSRcomplete decision problems about Nash equilibria in 3player 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 EXISTSRcomplete decision problem from [Schaefer and Stefankovic, Theory of Computing Systems, 2015] to (almost) all the decision problems about Nash equilibria that were before shown NPcomplete for 2player 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 EXISTSRcomplete in [Garg et al., Proceedings of ICALP 2015].
BibTeX  Entry
@InProceedings{bil_et_al:LIPIcs:2016:5718,
author = {Vittorio Bil{\`o} and Marios Mavronicolas},
title = {{A Catalog of EXISTSRComplete Decision Problems About Nash Equilibria in MultiPlayer Games}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {17:117:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770019},
ISSN = {18688969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5718},
URN = {urn:nbn:de:0030drops57189},
doi = {10.4230/LIPIcs.STACS.2016.17},
annote = {Keywords: Nash equilibrium, complexity of equilibria, EXISTSRcompleteness}
}
16.02.2016
Keywords: 

Nash equilibrium, complexity of equilibria, EXISTSRcompleteness 
Seminar: 

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Issue date: 

2016 
Date of publication: 

16.02.2016 