Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-031 | 1st March 2005 00:00

Pure Nash equilibria in games with a large number of actions

RSS-Feed




TR05-031
Authors: Carme Alvarez, Joaquim Gabarro, Maria Serna
Publication: 9th March 2005 00:00
Downloads: 3025
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint