COMPUTING NASH EQUILIBRIA FOR TWO-PLAYER RESTRICTED NETWORK CONGESTION GAMES IS $\mathcal{PLS}$-COMPLETE
From MaRDI portal
Publication:5408357
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
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