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

DOI10.1016/J.TCS.2009.07.046zbMath1175.91044OpenAlexW2046097055MaRDI QIDQ1034618

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

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

complexitynon-cooperative gamesunsplittable flowmakespan objectiveextreme equilibrianetwork congestion game

Mathematics Subject Classification ID

Noncooperative games (91A10) Network design and communication in computer systems (68M10) Games involving graphs (91A43) Applications of game theory (91A80)

Related Items (5)

Selfish bin coloring ⋮ A logarithmic approximation for polymatroid congestion games ⋮ Single Parameter FPT-Algorithms for Non-trivial Games ⋮ 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?

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

This page was built for publication: How hard is it to find extreme Nash equilibria in network congestion games?