Hacker News new | past | comments | ask | show | jobs | submit login
How Bad Is Selfish Routing? (2001) [pdf] (stanford.edu)
31 points by beefman 7 months ago | hide | past | web | favorite | 5 comments

The paper is pretty coy about what they mean by "network", "congestion" and "latency". It doesn't just apply to computer networking -- the original motivating example for this kind of model was road network traffic, and it also applies to things like choosing which bus to take to work with some "overcrowding discomfort" function.

This research could motivate how self-driving taxis are routed through a city. The Braess network example shows that cooperative routing could decrease everyone's travel times simultaneously compared to the "everyone takes the shortest path given traffic" Nash equilibrium (called "Wardrop equilibrium" in the continuous network flow domain.)

I guess you mean that they're not too specific about concrete situations to which their analysis might apply. But in some sense the network model was already fairly specific, since the analysis would become yet more general in e.g. Perakis 2007.


Aw man I freakin love this paper I did my whole undergrad honors project based on this and this paper by Tim Roughgarden https://theory.stanford.edu/~tim/papers/optima.pdf

I have always found selfish routing to have interesting implications for a world in which traffic is more coordinated and centrally managed -- be it through present-day apps like Google Maps and Waze, or some near-future technology with autonomous cars communicating with one another. The happy Roughgarden/Tardos result that selfish routing is only 4/3 as bad as coordination is great, but it also means there’s not much slack to be picked up: fully coordinated routes would only be 3/4 as long as the status quo.

(Of course that's not the entire story on autonomous cars, for instance, because they will also get into fewer accidents, react to changing traffic conditions faster, can potentially drive more tightly at high speed, etc.)

Anyone interested in selfish routing should check out Braess's paradox, which is wonderfully unintuitive and strange:


I don't completely understand on a skim through. They are imagining a network where nodes are never assessed on their performance by other nodes?

Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact