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. Copyright Springer-Verlag Berlin/Heidelberg 2004

MoreLess

Year of publication:	2004
Authors:	Baron, Richard ; Durieu, Jacques ; Haller, Hans ; Solal, Philippe
Published in:	Economic Theory. - Springer. - Vol. 23.2004, 2, p. 445-454
Publisher:	Springer
Subject:	Spatial games \| NP-completeness \| Graph k-colorability

More details

Extent:	text/html
Type of publication:	Article
Source:	RePEc - Research Papers in Economics

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