Complexity of rational and irrational nash equilibria

Abstract

We 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 coincide

we 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 game

we 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, 2003

Games Econ. Behav. 63(2), 621–641, 2008). © Springer Science+Business Media New York 2013