Show simple item record

dc.contributor.authorBilò, Vittorioen
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.editorVollmer H.en
dc.contributor.editorOllinger N.en
dc.creatorBilò, Vittorioen
dc.creatorMavronicolas, Mariosen
dc.description.abstract[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]en
dc.description.abstractdetermining 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 2012en
dc.description.abstractConitzer and Sandholm, Games and Economic Behavior, 2008en
dc.description.abstractGilboa 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 Mavronicolasen
dc.description.abstractlicensed under Creative Commons License CC-BY.en
dc.publisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishingen
dc.sourceLeibniz International Proceedings in Informatics, LIPIcsen
dc.source33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016en
dc.subjectNash equilibriumen
dc.subjectGame theoryen
dc.subjectDecision theoryen
dc.subjectTelecommunication networksen
dc.subjectComputation theoryen
dc.subjectNP Completeen
dc.subjectComplexity of equilibriaen
dc.subjectDecision problemsen
dc.subjectMultiplayer gamesen
dc.subjectNash equilibriaen
dc.subjectComplete problemsen
dc.subjectComputer gamesen
dc.subjectComputing systemen
dc.subjectExplicit formulationen
dc.titleA catalog of ∃ℝ-complete decision problems about Nash equilibria in multi-player gamesen
dc.description.volume47 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.type.uhtypeConference Objecten
dc.description.notesConference code: 119274en
dc.description.notesCited By :4</p>en

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record