TR05-031 Authors: Carme Alvarez, Joaquim Gabarro, Maria Serna

Publication: 9th March 2005 00:00

Downloads: 1805

Keywords:

We 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).