Finding a Nash equilibrium in spatial games is an NP-complete problem

B-Tier
Journal: Economic Theory
Year: 2004
Volume: 23
Issue: 2
Pages: 445-454

Authors (4)

Richard Baron (Université de Lyon) Jacques Durieu (not in RePEc) Hans Haller (not in RePEc) Philippe Solal (Université de Lyon)

Score contribution per author:

0.503 = (α=2.01 / 4 authors) × 1.0x B-tier

α: calibrated so average coauthorship-adjusted count equals average raw count

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

Technical Details

RePEc Handle
repec:spr:joecth:v:23:y:2004:i:2:p:445-454
Journal Field
Theory
Author Count
4
Added to Database
2026-01-24