Finding a Nash Equilibrium in Spatial Games is an NP-Complete Problem
Hans Haller and
Additional contact information
Jaçques Durieu: CREUSET, University of Saint-Etienne
Hans Haller: Virginia Polytechnic Institute and State University
No 02-19, Discussion Papers from University of Copenhagen. Department of Economics
We consider the class of (finite) spatial games. We show that the problem of determining whether there exists a Nash equilibrium in which each player has a payoff of at least k is NP-complete as a function of the number of players. When each player has two strategies and the base game is an anti-coordination game, the problem is decidable in polynomial time.
Keywords: spatial games; NP-completeness; graph K-colorability (search for similar items in EconPapers)
JEL-codes: C72 (search for similar items in EconPapers)
Pages: 9 pages
Date: 2002-09, Revised 2002-11
New Economics Papers: this item is included in nep-gth
References: Add references at CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
Journal Article: Finding a Nash equilibrium in spatial games is an NP-complete problem (2004)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:kud:kuiedp:0219
Access Statistics for this paper
More papers in Discussion Papers from University of Copenhagen. Department of Economics Øster Farimagsgade 5, Building 26, DK-1353 Copenhagen K., Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Hoffmann ().