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

DOI10.1007/S00199-003-0376-1zbMath1065.91010OpenAlexW2011808708MaRDI QIDQ1424226

Hans H. Haller, Jacques Durieu, Richard Baron, Philippe Solal

Publication date: 11 March 2004

Published in: Economic Theory (Search for Journal in Brave)

Full work available at URL: https://curis.ku.dk/ws/files/32250102/0219.pdf

zbMATH Keywords

NP-completenessGraph \(k\)-colorability.Spatial games

Mathematics Subject Classification ID

Noncooperative games (91A10) Games involving graphs (91A43)

Related Items (4)

Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms ⋮ The computational complexity of rationalizing boundedly rational choice behavior ⋮ Weak equilibrium in a spatial model ⋮ Bridging game theory and the knapsack problem: a theoretical formulation

This page was built for publication: Finding a Nash equilibrium in spatial games is an NP-complete problem