How hard is it to find extreme Nash equilibria in network congestion games?

DOI10.1016/j.tcs.2009.07.046zbMath1175.91044MaRDI QIDQ1034618

Gerhard J. Woeginger, Sven O. Krumke, Heike Sperber, Elisabeth Gassner, Johannes Hatzl

Publication date: 6 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.046

zbMATH Keywords

complexity; non-cooperative games; unsplittable flow; makespan objective; extreme equilibria; network congestion game

Mathematics Subject Classification ID

91A10: Noncooperative games

68M10: Network design and communication in computer systems

91A43: Games involving graphs

91A80: Applications of game theory

Related Items

How to find Nash equilibria with extreme total latency in network congestion games?, How hard is it to find extreme Nash equilibria in network congestion games?, Single Parameter FPT-Algorithms for Non-trivial Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Worst-case equilibria
• On the structure and complexity of worst-case equilibria
• How hard is it to find extreme Nash equilibria in network congestion games?
• Minimum cost flow algorithms for series-parallel networks
• A class of games possessing pure-strategy Nash equilibria
• Structure and complexity of extreme Nash equilibria
• Selfish unsplittable flows
• The complexity of pure Nash equilibria
• The price of anarchy of finite congestion games
• `` Strong NP-Completeness Results
• The price of selfish routing
• Algorithms, games, and the internet
• Approximation and Online Algorithms
• The Price of Routing Unsplittable Flow