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

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.

MoreLess

Year of publication:	2002-09
Authors:	Baron, Richard ; Durieu, Jaçques ; Haller, Hans ; Solal, Philippe
Institutions:	Økonomisk Institut, Københavns Universitet
Subject:	spatial games \| NP-completeness \| graph K-colorability

freely available

Full text |

More access options

Check Google Scholar

In German libraries (KVK)

I need help

More details

Extent:	application/pdf
Series:	Discussion Papers.
Type of publication:	Book / Working Paper
Language:	English
Notes:	Number 02-19 9 pages
Classification:	C72 - Noncooperative Games
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005818473