License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.17
URN: urn:nbn:de:0030-drops-57189
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5718/
Go to the corresponding LIPIcs Volume Portal

Bilò, Vittorio ; Mavronicolas, Marios

A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games

pdf-format:
18.pdf (0.7 MB)

Abstract

[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].

BibTeX - Entry

@InProceedings{bil_et_al:LIPIcs:2016:5718,
  author =	{Vittorio Bil{\`o} and Marios Mavronicolas},
  title =	{{A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5718},
  URN =		{urn:nbn:de:0030-drops-57189},
  doi =		{10.4230/LIPIcs.STACS.2016.17},
  annote =	{Keywords: Nash equilibrium, complexity of equilibria, EXISTS-R-completeness}
}

Keywords: Nash equilibrium, complexity of equilibria, EXISTS-R-completeness
Collection: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue Date: 2016
Date of publication: 16.02.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI