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

DOI10.1007/S00199-003-0376-1MaRDI QIDQ1424226zbMATH OpenOpenAlexFDO

Authors Richard Baron, Jacques Durieu, Hans Haller, 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)

Recommendations

• The complexity of finding Nash equilibria
• Finding all pure strategy Nash equilibria in a planar location game
• Finding a Nash equilibrium in noncooperativeN-person games by solving a sequence of linear stationary point problems
• Nash equilibrium in a spatial model of coalition bargaining
• On the Complexity of Nash Equilibria and Other Fixed Points
• Finding Pure Nash Equilibrium of Graphical Game Via Constraints Satisfaction Approach
• Reachability of locational Nash equilibria
• Nash Equilibria in Voronoi Games on Graphs
• Inapproximability of NP-complete variants of Nash equilibrium

Cited in

(5)

• Bridging game theory and the knapsack problem: a theoretical formulation
• Weak equilibrium in a spatial model
• On the complexity of deciding degeneracy in a bimatrix game with sparse payoff matrix
• The computational complexity of rationalizing boundedly rational choice behavior
• Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1424226)