COMPUTING NASH EQUILIBRIA FOR TWO-PLAYER RESTRICTED NETWORK CONGESTION GAMES IS $\mathcal{PLS}$-COMPLETE

DOI10.1142/S0129626412500144zbMath1284.91068OpenAlexW2247582943MaRDI QIDQ5408357

Burkhard Monien, Dominic Dumrauf

Publication date: 10 April 2014

Published in: Parallel Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129626412500144

zbMATH Keywords

computational complexityNash equilibriacongestion games\(\mathcal{PLS}\)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Games involving graphs (91A43) Other game-theoretic models (91A40) Distributed systems (68M14)

Cites Work

• How easy is local search?
• Congestion games with player-specific payoff functions
• A class of games possessing pure-strategy Nash equilibria
• Non-cooperative games
• Simple Local Search Problems that are Hard to Solve
• On the impact of combinatorial structure on congestion games
• Settling the complexity of computing two-player Nash equilibria