Show simple item record

dc.contributor.authorBilò, Vittorioen
dc.contributor.authorMavronicolas, Mariosen
dc.creatorBilò, Vittorioen
dc.creatorMavronicolas, Mariosen
dc.description.abstractWe introduce two new natural 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 NASHEQUIVALENCE 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. The problem NASH-EQUIVALENCE asks whether or not the two sets of Nash equilibria coincideen
dc.description.abstractwe identify a restriction of its complementary problem that witnesses ∃ RATIONAL NASH. The problem 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 gameen
dc.description.abstractwe identify a restriction of NASH-REDUCTION 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 both NP-hard, respectively. The reductions significantly extend techniques previously employed by Conitzer and Sandholm (Proceedings of the 18th Joint Conference on Artificial Intelligence, pp. 765–771, 2003en
dc.description.abstractGames Econ. Behav. 63(2), 621–641, 2008). © Springer Science+Business Media New York 2013en
dc.sourceTheory of Computing Systemsen
dc.subjectGame theoryen
dc.subjectDecision theoryen
dc.subjectArtificial intelligenceen
dc.subjectTelecommunication networksen
dc.subjectComputation theoryen
dc.subjectComplexity theoryen
dc.subjectDecision problemsen
dc.subjectNash equilibriaen
dc.subjectComplementary problemsen
dc.subjectRational numbersen
dc.subjectStrategic gameen
dc.subjectStrategic gamesen
dc.titleComplexity of rational and irrational nash equilibriaen
dc.description.endingpage527 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notes<p>Cited By :2</p>en
dc.source.abbreviationTheory Comput.Syst.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