ECCC-Report TR05-031https://eccc.weizmann.ac.il/report/2005/031Comments and Revisions published for TR05-031en-usWed, 09 Mar 2005 00:00:18 +0200
Paper TR05-031
| Pure Nash equilibria in games with a large number of actions |
Carme Alvarez,
Joaquim Gabarro,
Maria Serna
https://eccc.weizmann.ac.il/report/2005/031We study the computational complexity of deciding the existence of a
Pure Nash Equilibrium in multi-player strategic games.
We address two fundamental questions: how can we represent a game?, and
how can we represent a game with polynomial pay-off functions?
Our results show that the computational complexity of
deciding the existence of a pure Nash equilibrium in an strategic game
depends on two parameters: the number of players and the size of the
sets of strategies. In particular we show that deciding the existence
of a Nash equilibrium in an strategic game is NP-complete when the
number of players is large and the number of strategies for each
player is constant, while the problem is $\Sigma_2^p$-complete when the number
of players is a constant and the size of the sets of strategies is
exponential (with respect to the length of the strategies).
Wed, 09 Mar 2005 00:00:18 +0200https://eccc.weizmann.ac.il/report/2005/031