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.date.accessioned2019-11-13T10:38:27Z
dc.date.available2019-11-13T10:38:27Z
dc.date.issued2016
dc.identifier.isbn978-3-95977-001-9
dc.identifier.urihttp://gnosis.library.ucy.ac.cy/handle/7/53638
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.source.urihttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84961665583&doi=10.4230%2fLIPIcs.STACS.2016.17&partnerID=40&md5=9e927903ec0dffbd4450b5d01772c258
dc.subjectNash equilibriumen
dc.subjectGame theoryen
dc.subjectDecision theoryen
dc.subjectTelecommunication networksen
dc.subjectAluminumen
dc.subjectComputation theoryen
dc.subjectNP Completeen
dc.subject∃ℝ-completenessen
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.typeinfo:eu-repo/semantics/conferenceObject
dc.identifier.doi10.4230/LIPIcs.STACS.2016.17
dc.description.volume47
dc.author.faculty002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences
dc.author.departmentΤμήμα Πληροφορικής / Department of Computer Science
dc.type.uhtypeConference Objecten
dc.description.notes<p>Sponsors:en
dc.description.notesConference code: 119274en
dc.description.notesCited By :4</p>en


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record