dc.contributor.author | Bilò, Vittorio | en |
dc.contributor.author | Mavronicolas, Marios | en |
dc.creator | Bilò, Vittorio | en |
dc.creator | Mavronicolas, Marios | en |
dc.date.accessioned | 2019-11-13T10:38:28Z | |
dc.date.available | 2019-11-13T10:38:28Z | |
dc.date.issued | 2011 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53641 | |
dc.description.abstract | We introduce two new decision problems, denoted as ∃ RATIONAL NASH and ∃ IRRATIONAL NASH, pertinent to the rationality and irrationality, respectively, of Nash equilibria for (finite) strategic games. These problems ask, given a strategic game, whether or not it admits (i) a rational Nash equilibrium where all probabilities are rational numbers, and (ii) an irrational Nash equilibrium where at least one probability is irrational, respectively. We are interested here in the complexities of ∃ RATIONAL NASH and ∃ IRRATIONAL NASH. Towards this end, we study two other decision problems, denoted as NASH-EQUIVALENCE and NASH-REDUCTION, pertinent to some mutual properties of the sets of Nash equilibria of two given strategic games with the same number of players. NASH-EQUIVALENCE asks whether the two sets of Nash equilibria coincide | en |
dc.description.abstract | we identify a restriction of its complementary problem that witnesses ∃ RATIONAL NASH. NASH-REDUCTION asks whether or not there is a so called Nash reduction (a suitable map between corresponding strategy sets of players) that yields a Nash equilibrium of the former game from a Nash equilibrium of the latter game | en |
dc.description.abstract | we identify a restriction of it that witnesses ∃ IRRATIONAL NASH. As our main result, we provide two distinct reductions to simultaneously show that (i) NASH-EQUIVALENCE is co-NP-hard and ∃ RATIONAL NASH is NP-hard, and (ii) NASH-REDUCTION and ∃ IRRATIONAL NASH are NP-hard, respectively. The reductions significantly extend techniques previously employed by Conitzer and Sandholm [6, 7]. © 2011 Springer-Verlag. | en |
dc.source | 4th International Symposium on Algorithmic Game Theory, SAGT 2011 | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-80054010186&doi=10.1007%2f978-3-642-24829-0_19&partnerID=40&md5=8e1e6a5971686ee61f0ff3a979bdab5a | |
dc.subject | Game theory | en |
dc.subject | Decision theory | en |
dc.subject | Algorithms | en |
dc.subject | Telecommunication networks | en |
dc.subject | Computational complexity | en |
dc.subject | Parallel processing systems | en |
dc.subject | NP-hard | en |
dc.subject | Decision problems | en |
dc.subject | Nash equilibria | en |
dc.subject | Complementary problems | en |
dc.subject | Rational numbers | en |
dc.subject | Strategic game | en |
dc.subject | Nash Equilibrium | en |
dc.title | Complexity of rational and irrational Nash equilibria | en |
dc.type | info:eu-repo/semantics/article | |
dc.identifier.doi | 10.1007/978-3-642-24829-0_19 | |
dc.description.volume | 6982 LNCS | en |
dc.description.startingpage | 200 | |
dc.description.endingpage | 211 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Article | en |
dc.description.notes | <p>Sponsors: Univ. Studi Salerno, Dip. Inform. "Renato M. Capocelli" | en |
dc.description.notes | Conference code: 86918 | en |
dc.description.notes | Cited By :1</p> | en |
dc.source.abbreviation | Lect. Notes Comput. Sci. | en |