Braess' Paradox
Add a road, slow everyone down — selfish routing degrades with more options.
The idea
Proposition (Braess' paradox).
Model traffic as a game in which each driver chooses the route that minimizes their own travel time, given the routes the others have chosen. Adding a road to such a network can slow every driver down: there are networks in which, at equilibrium, every driver's travel time is strictly longer with the new road than without it.
In this game a route's time depends on how many drivers use it. Traffic settles at a Nash equilibrium of this routing game: an assignment of drivers to routes in which no single driver can arrive earlier by switching routes while everyone else stays put. At equilibrium, any two routes in use must take equal time — if one were faster, drivers on the slower one would switch to it.
The social cost is the total travel time summed over all drivers. The equilibrium need not minimize it: each driver counts only their own delay and ignores the delay they impose on everyone sharing their roads.
The paradox shows how large that gap can be. Add a new road — extra capacity, free to use, nothing removed — and the new equilibrium can leave every driver strictly worse off. No driver errs: the new road is faster for each driver who takes it, and once all have taken it, none gains by switching back. The equilibrium itself has moved to a worse outcome.
The figure shows the classic network: from $S$ to $T$, the road into $A$ and the road out of $B$ cost $x/100$ and $y/100$ minutes when $x$ and $y$ drivers use them, the other two roads a constant $c$ — and the added shortcut from $A$ to $B$ costs $0$, after which every driver funnels onto the single route through it.
Ways to work on it
- Walkthrough. Two parallel routes, symmetric split — find the travel time.
- Practice. Everyone uses the shortcut — and everyone is worse off.
- Hardest. Compare selfish and optimal routing, and bound how far apart they can be.
Not sure where to start? Take the ten-question placement test.