On the hardness of network design for bottleneck routing games

DOI10.1016/J.TCS.2013.11.035MaRDI QIDQ389953zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Dimitris Fotakis, A. C. Kaporis, Thanasis Lianeas, P. G. Spirakis

Publication date 22 January 2014

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

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

zbMATH Keywords

Braess's paradoxbottleneck routing gamesselfish network design

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) Games involving graphs (91A43)

Recommendations

• On the hardness of network design for bottleneck routing games
• On the severity of Braess's paradox: designing networks for selfish users is hard
• Efficient Methods for Selfish Network Design
• Efficient methods for selfish network design
• The Hardness of Selective Network Design for Bottleneck Routing Games

Cites work

• scientific article; zbMATH DE number 6469163 (Why is no real title available?)
• Algorithms and Computation
• Approximation and Online Algorithms
• Atomic routing games on maximum congestion
• Automata, Languages and Programming
• Bottleneck links, variable demand, and the tragedy of the commons
• Efficient Methods for Selfish Network Design
• Efficient graph topologies in network routing games
• Network topology and the efficiency of equilibrium
• On sparse approximations to randomized strategies and convex combinations
• On the severity of Braess's paradox: designing networks for selfish users is hard
• Resolving Braess's paradox in random networks
• Simple strategies for large zero-sum games with applications to complexity theory
• The Hardness of Selective Network Design for Bottleneck Routing Games
• The directed subgraph homeomorphism problem
• Worst-case equilibria
• Über ein Paradoxon aus der Verkehrsplanung

Cited in

(12)

• On the core of routing games
• \(\mathcal{NP}\)-hardness of pure Nash equilibrium in scheduling and network design games
• Automata, Languages and Programming
• Stronger bounds on Braess's paradox and the maximum latency of selfish routing
• The Hardness of Selective Network Design for Bottleneck Routing Games
• Efficient methods for selfish network design
• Efficient Methods for Selfish Network Design
• On the severity of Braess's paradox: designing networks for selfish users is hard
• Excluding Braess's paradox in nonatomic selfish routing
• Approximation and Online Algorithms
• On the hardness of network design for bottleneck routing games
• Network characterizations for excluding Braess's paradox

This page was built for publication: On the hardness of network design for bottleneck routing games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q389953)