Braess's Paradox in large random graphs

DOI10.1002/rsa.20325zbMath1207.05185OpenAlexW4245653884MaRDI QIDQ3061184

Gregory Valiant, Tim Roughgarden

Publication date: 14 December 2010

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20325

zbMATH Keywords

random graphsselfish routingBraess's paradoxtraffic equilibria

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random graphs (graph-theoretic aspects) (05C80)

Related Items (11)

A Selective Tour Through Congestion Games ⋮ Collusion in atomic splittable routing games ⋮ Resolving Braess's paradox in random networks ⋮ On delocalization of eigenvectors of random non-Hermitian matrices ⋮ The Chicken Braess Paradox ⋮ Degrading network capacity may improve performance: private versus public monitoring in the Braess paradox ⋮ Selfish splittable flows and NP-completeness ⋮ Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors ⋮ Topological price of anarchy bounds for clustering games on networks ⋮ Escaping Braess's paradox through approximate Caratheodory's theorem ⋮ Braess's paradox in expanders

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Avoiding paradoxes in multi-agent competitive routing.
• On the severity of Braess's paradox: designing networks for selfish users is hard
• Capacity allocation under noncooperative routing
• How bad is selfish routing?
• The Braess paradox
• BRAESS' PARADOX IN A TWO-TERMINAL TRANSPORTATION NETWORK
• Avoiding the Braess paradox in non-cooperative networks
• Über ein Paradoxon aus der Verkehrsplanung
• Traffic assignment problem for a general network

This page was built for publication: Braess's Paradox in large random graphs