dc.contributor.author | Bilò, Vittorio | en |
dc.contributor.author | Mavronicolas, Marios | en |
dc.contributor.editor | Vollmer H. | en |
dc.contributor.editor | Ollinger N. | en |
dc.creator | Bilò, Vittorio | en |
dc.creator | Mavronicolas, Marios | en |
dc.date.accessioned | 2019-11-13T10:38:27Z | |
dc.date.available | 2019-11-13T10:38:27Z | |
dc.date.issued | 2016 | |
dc.identifier.isbn | 978-3-95977-001-9 | |
dc.identifier.uri | http://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.abstract | determining 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 2012 | en |
dc.description.abstract | Conitzer and Sandholm, Games and Economic Behavior, 2008 | en |
dc.description.abstract | Gilboa 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 Mavronicolas | en |
dc.description.abstract | licensed under Creative Commons License CC-BY. | en |
dc.publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing | en |
dc.source | Leibniz International Proceedings in Informatics, LIPIcs | en |
dc.source | 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-84961665583&doi=10.4230%2fLIPIcs.STACS.2016.17&partnerID=40&md5=9e927903ec0dffbd4450b5d01772c258 | |
dc.subject | Nash equilibrium | en |
dc.subject | Game theory | en |
dc.subject | Decision theory | en |
dc.subject | Telecommunication networks | en |
dc.subject | Aluminum | en |
dc.subject | Computation theory | en |
dc.subject | NP Complete | en |
dc.subject | ∃ℝ-completeness | en |
dc.subject | Complexity of equilibria | en |
dc.subject | Decision problems | en |
dc.subject | Multiplayer games | en |
dc.subject | Nash equilibria | en |
dc.subject | Complete problems | en |
dc.subject | Computer games | en |
dc.subject | Computing system | en |
dc.subject | Explicit formulation | en |
dc.title | A catalog of ∃ℝ-complete decision problems about Nash equilibria in multi-player games | en |
dc.type | info:eu-repo/semantics/conferenceObject | |
dc.identifier.doi | 10.4230/LIPIcs.STACS.2016.17 | |
dc.description.volume | 47 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Conference Object | en |
dc.description.notes | <p>Sponsors: | en |
dc.description.notes | Conference code: 119274 | en |
dc.description.notes | Cited By :4</p> | en |