Finding a Nash Equilibrium in Spatial Games is an NP-Complete Problem

Richard Baron, Jaçques Durieu, Hans Haller and Philippe Solal
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

Abstract: 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:

Downloads: (external link)
http://www.econ.ku.dk/english/research/publications/wp/2002/0219.pdf/ (application/pdf)

Related works:
Journal Article: Finding a Nash equilibrium in spatial games is an NP-complete problem (2004)
Working Paper: 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) HTML/Text

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 Oester Farimagsgade 5, Building 26, DK-1353 Copenhagen K., Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Hoffmann ().