The complexity of pure Nash equilibria
2004pp. 604–612
Citations Over TimeTop 1% of 2004 papers
Abstract
We investigate from the computational viewpoint multi-player games that are guaranteed to have pure Nash equilibria. We focus on congestion games, and show that a pure Nash equilibrium can be computed in polynomial time in the symmetric network case, while the problem is PLS-complete in general. We discuss implications to non-atomic congestion games, and we explore the scope of the potential function method for proving existence of pure Nash equilibria.
Related Papers
- → Nash Equilibrium (Pure and Mixed)(2011)2 cited
- The Robust Nash equilibrium and equilibrium selection in 2x2 coordination games(2012)
- → Computation of Efficient Nash Equilibria for Experimental Economic Games(2015)
- → The Analysis of the Structure Nash Equilibrium Solution of Two-person Two-strategy Game(2014)