TY - JOUR

T1 - On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria

AU - Berthelsen, Marie Louisa Tølbøll

AU - Hansen, Kristoffer Arnsfelt

N1 - Funding Information:
This paper forms an extension of parts of the master’s thesis of the first author and has appeared previously in a preliminary form []. The second author is supported by the Independent Research Fund Denmark under grant no. 9040-00433B.
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2022/6

Y1 - 2022/6

N2 - We study the computational complexity of decision problems about Nash equilibria in m-player games. Several such problems have recently been shown to be computationally equivalent to the decision problem for the existential theory of the reals, or stated in terms of complexity classes,.R-complete, when m >= 3. We show that, unless they turn into trivial problems, they are there exists R-hard even for 3-player zero-sum games. We also obtain new results about several other decision problems. We show that when m >= 3 the problems of deciding if a game has a Pareto optimal Nash equilibrium or deciding if a game has a strong Nash equilibrium are there exists R-complete. The latter result rectifies a previous claim of NP-completeness in the literature. We show that deciding if a game has an irrational valued Nash equilibrium is there exists R-hard, answering a question of Bilo and Mavronicolas, and address also the computational complexity of deciding if a game has a rational valued Nash equilibrium. These results also hold for 3-player zero-sum games. Our proof methodology applies to corresponding decision problems about symmetric Nash equilibria in symmetric games as well, and in particular our new results carry over to the symmetric setting. Finally we show that deciding whether a symmetric m-player game has a non-symmetric Nash equilibrium is there exists R-complete when m >= 3, answering a question of Garg, Mehta, Vazirani, and Yazdanbod.

AB - We study the computational complexity of decision problems about Nash equilibria in m-player games. Several such problems have recently been shown to be computationally equivalent to the decision problem for the existential theory of the reals, or stated in terms of complexity classes,.R-complete, when m >= 3. We show that, unless they turn into trivial problems, they are there exists R-hard even for 3-player zero-sum games. We also obtain new results about several other decision problems. We show that when m >= 3 the problems of deciding if a game has a Pareto optimal Nash equilibrium or deciding if a game has a strong Nash equilibrium are there exists R-complete. The latter result rectifies a previous claim of NP-completeness in the literature. We show that deciding if a game has an irrational valued Nash equilibrium is there exists R-hard, answering a question of Bilo and Mavronicolas, and address also the computational complexity of deciding if a game has a rational valued Nash equilibrium. These results also hold for 3-player zero-sum games. Our proof methodology applies to corresponding decision problems about symmetric Nash equilibria in symmetric games as well, and in particular our new results carry over to the symmetric setting. Finally we show that deciding whether a symmetric m-player game has a non-symmetric Nash equilibrium is there exists R-complete when m >= 3, answering a question of Garg, Mehta, Vazirani, and Yazdanbod.

KW - Computational complexity

KW - Existential theory of the reals

KW - Nash equilibrium

UR - http://www.scopus.com/inward/record.url?scp=85129825322&partnerID=8YFLogxK

U2 - 10.1007/s00224-022-10080-1

DO - 10.1007/s00224-022-10080-1

M3 - Journal article

AN - SCOPUS:85129825322

SN - 1432-4350

VL - 66

SP - 519

EP - 545

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 3

ER -