Network characterizations for excluding Braess's paradox

DOI10.1007/s00224-016-9710-4zbMath1356.91030OpenAlexW2530722280MaRDI QIDQ506543

Zhuo Diao, Xu-jin Chen, Xiao-Dong Hu

Publication date: 1 February 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-016-9710-4

zbMATH Keywords

series-parallel graphBraess's paradoxmulti-commodity networknonatomic selfish routingsingle-commodity network

Mathematics Subject Classification ID

Games involving graphs (91A43) Traffic problems in operations research (90B20)

Related Items (12)

Inefficiencies in network models: a graph-theoretic perspective ⋮ Depletable channels: dynamics, behaviour, and efficiency in network design ⋮ A note on social learning in non-atomic routing games ⋮ Unnamed Item ⋮ A polynomial-time algorithm for detecting the possibility of Braess paradox in directed graphs ⋮ Informational Braess’ Paradox: The Effect of Information on Traffic Congestion ⋮ A Characterization of Undirected Graphs Admitting Optimal Cost Shares ⋮ Efficient Black-Box Reductions for Separable Cost Sharing ⋮ Social learning in nonatomic routing games ⋮ On weak Pareto optimality of nonatomic routing networks ⋮ Polynomial recognition of vulnerable multi-commodities ⋮ Escaping Braess's paradox through approximate Caratheodory's theorem

Cites Work

• Unnamed Item
• On the hardness of network design for bottleneck routing games
• Worst-case equilibria
• Strong equilibrium in network congestion games: increasing versus decreasing costs
• Network topology and the efficiency of equilibrium
• Efficient graph topologies in network routing games
• The directed subgraph homeomorphism problem
• Network structure and strong equilibrium in route selection games.
• Inefficiencies in network models: a graph-theoretic perspective
• On the severity of Braess's paradox: designing networks for selfish users is hard
• How bad is selfish routing?
• Stronger Bounds on Braess's Paradox and the Maximum Latency of Selfish Routing
• The Recognition of Series Parallel Digraphs
• Finding k Disjoint Paths in a Directed Planar Graph
• Matroids Are Immune to Braess’ Paradox
• Über ein Paradoxon aus der Verkehrsplanung
• Topological Conditions for Uniqueness of Equilibrium in Networks
• Approximation and Online Algorithms

This page was built for publication: Network characterizations for excluding Braess's paradox