Braess's paper
Dietrich Braess published "Über ein Paradoxon aus der Verkehrsplanung" ("On a paradox of traffic planning") in the German journal Unternehmensforschung. An English translation appeared only in 2005, in Transportation Science.
Every morning 4,000 drivers go from Start to Finish along two routes. Each has a narrow street, which gets slower the more cars use it, and a wide highway that always takes 45 minutes. The drivers have split evenly, and the trip takes 65 minutes. Now the city builds an instant shortcut between the two routes. Each driver still picks the fastest way for themselves. How long will the trip take?
It seems a new road cannot hurt: if you don't like it, don't use it. But the shortcut pays off for every single driver, whatever the others do. So everyone takes it, both narrow streets clog up, and the trip takes 80 minutes instead of 65. Close the shortcut, and everyone gains 15 minutes.
In 1968 the German mathematician Dietrich Braess described a road network in which a new road slows everybody down. Here is the best-known version of his example, with concrete numbers.
Every morning 4,000 drivers go from Start to Finish. Each wants to arrive as fast as possible and knows how long every road takes, say from a navigation app.
The streets Start → A and B → Finish are narrow: if T cars use one, it takes T/100 minutes. 1,000 cars mean 10 minutes, 4,000 cars mean 40.
The highways A → Finish and Start → B are wide but long: 45 minutes however many cars use them.
There are two routes: via A and via B. The drivers have split evenly, 2,000 each, and everyone drives 2000/100 + 45 = 65 minutes. Nobody gains by switching to the other route.
The city builds a shortcut A → B that takes no time at all, 0 minutes. Again each driver picks the fastest route for themselves, until nobody wants to change anything. How long will the trip take then?
"A new road can only help. It can't get worse: whoever doesn't want it just won't use it"
In fact all 4,000 drivers take the shortcut, and each spends 80 minutes. None of them makes a mistake: for each one alone the shortcut really is fastest. They lose together.
Without the shortcut the trip takes 65 minutes. The shortcut opens, the drivers get used to it, and nobody wants to change route any more. How long does each of them drive now?
A breakdown of your answer will appear here.
Hard to decide? Open the hints one at a time: the easy one first, then stronger ones.
Look through one driver's eyes right after the opening: while everyone else drives as before, the shortcut route takes 20 + 0 + 20 = 40 minutes. Who would turn that down?
Compare a 45-minute highway with a narrow street. Even if all 4,000 cars use the street, it takes 40 minutes. Is the highway ever the better choice?
If the shortcut is best for every driver whatever the others do, everyone takes it. How many cars are on each narrow street then, and how many minutes does the whole trip take?
Use the sliders to split the drivers between the routes, and the switch to open or close the shortcut. A road's thickness shows how many cars use it. On the right you see each route's time and whether anyone wants to move to a faster one. Try to find a split where, with the shortcut open, nobody wants to change route.
Each of the 4,000 drivers reconsiders on a given morning with some probability: they check the app for how long each route took yesterday and pick the fastest. The app is a little off. The shortcut opens on day 11 and closes on day 61. The chart shows how long a driver spends on the road on average.
Every driver is modelled separately. The app error means that a random error with this standard deviation, in minutes, is added to yesterday's time of each route. When the shortcut closes, those who used it pick one of the two old routes the next morning.
None of the drivers makes a mistake. The trouble is that a driver choosing a road counts only their own time, not the time they take from others.
The street B → Finish, even jammed solid, takes 4000/100 = 40 minutes, while the highway always takes 45. So a driver at A does better via the shortcut to B whatever the others do. Likewise a driver at Start does better on the narrow street to A (≤ 40 min) than on the highway to B (45 min). Together the two choices make the shortcut route.
A new driver on a narrow street adds 1/100 of a minute for each person already on it. They don't notice it, but together it adds up to minutes and later to tens of minutes. While fewer than 500 drivers use the shortcut, switching pays off for everyone together. Beyond that each new driver gains less for themselves than they take from the others.
| Network | Each for themselves | Dispatcher |
|---|---|---|
| No shortcut | 65 min | 65 min |
| With the shortcut | 80 min | 64.69 min |
In 1950 John Nash called an equilibrium a state of a game in which no player gains by changing their choice alone. In our network with the shortcut there is just one equilibrium: all 4,000 take the shortcut. From there it makes no sense to move to the route via A or via B: 85 minutes instead of 80.
A dispatcher who routes the cars would send only 500 drivers via the shortcut and split the rest evenly between the routes via A and via B. That gives an average of 64.69 minutes, 19 seconds better than without the shortcut. But the split is unstable: those on the highways at once want the shortcut.
In 1952 the British transport engineer John Wardrop separated two goals. The first describes how drivers spread out on their own: all routes that anyone uses take the same time, and no unused route is faster. The second describes how a planner would spread them: so that the total time is the least. Without the shortcut both give the same thing, 2,000 and 2,000. The shortcut pulls them apart.
Let a drivers go via A, b via B and z via the shortcut, with a + b + z = 4000. The street Start → A carries a + z cars, the street B → Finish carries b + z.
Without the shortcut z = 0, and equilibrium needs tA = tB, so a = b = 2000.
With the shortcut, route Z is always faster, since b + z ≤ 4000 < 4500. So at equilibrium z = 4000.
The total time for a symmetric split a = b = (4000 − z)/2, and its minimum that a dispatcher would look for.
The price of anarchy, how many times worse the equilibrium is than the optimum, in this network:
The 4/3 bound is no accident: in 2002 Tim Roughgarden and Éva Tardos proved that when each road's time depends linearly on the number of cars, selfish drivers in any network spend at most a third more time than under the best possible routing.
Braess's paradox leads into three worlds. In mathematics it becomes the theory of the price of anarchy: how badly selfish players can spread out. In logic it is the same trap as the prisoner's dilemma. And in practice cities close roads, and traffic does not get worse.
Mathematics
The paradox depends on traffic. With few cars, up to 3,000, the shortcut really helps: the narrow streets are nearly empty, and the route through it is fastest for everyone. From 3,000 to 9,000 the shortcut hurts. Beyond 9,000 cars the narrow streets are so jammed that nobody takes the shortcut any more, and it changes nothing.
The harm peaks at 4,500 drivers: 90 minutes with the shortcut, 67.5 without it. The ratio is exactly 4/3. That's no coincidence: Roughgarden proved that in a network of linear roads a new road cannot make the equilibrium worse by more than a factor of 4/3, and Braess's example reaches that bound.
In 1920 the economist Arthur Pigou looked at two roads between the same towns. The first always takes an hour. The second takes xd hours, where x is the share of drivers on it. The second is never worse than the first, so selfish drivers all take it and spend an hour. A dispatcher would send some drivers by the first road to keep the second one freer.
For d = 1 the price of anarchy is 4/3, as in Braess's network. In 2003 Roughgarden showed that for roads with polynomial times the worst case in any network comes from just such a pair of roads. Traffic engineers often model congestion with the US Bureau of Public Roads formula from 1964, where time grows with the fourth power of the load. For d = 4 the price of anarchy is already about 2.15.
Logic
You are one of the 4,000 drivers, and the other 3,999 have spread out somehow. The slider sets how many of them take the shortcut, with the rest split evenly over the two old routes. Wherever you move it, the shortcut is 5 to 25 minutes faster for you. There are two lines of logic here: "whatever the others do, I'm better off this way" and "if everyone does this, everyone is worse off". Both are right.
This is the structure of the prisoner's dilemma, devised in 1950 by Merrill Flood and Melvin Dresher at the RAND Corporation; Albert Tucker added the name and the story about prisoners. Two suspects stay silent or betray, and betraying pays off for each whatever the other does. But if both betray, both are worse off than if both had stayed silent. Braess showed the same trap for thousands of players, where each one "betrays" just by picking the faster road.
Practice
A toll is handy to measure in minutes: how many minutes a driver would give up to avoid paying it. At a toll of 22.5 minutes exactly 500 drivers use the shortcut, as the dispatcher advised, and the average time falls to 64.69. The toll forces nobody; it only adds to a driver's decision the time they take from others. That is how the congestion charges in central London and Stockholm work.
Simpler still is to close the shortcut. In Stuttgart in 1969 traffic improved only when a newly built section of road was closed again. On Earth Day 1990 New York closed the always jammed 42nd Street, and the predicted gridlock never came. In 2003 Seoul began tearing down the Cheonggye elevated highway, which carried about 170 thousand cars a day, and in 2005 a stream with a park opened in its place. The city planned detours and reformed its buses at the same time, so it was no clean experiment, but the jams did not grow.
In 2008 the physicists Hyejin Youn, Michael Gastner and Hawoong Jeong modelled the streets of Boston, New York and London and found streets whose closure should cut travel times.
Dietrich Braess published "Über ein Paradoxon aus der Verkehrsplanung" ("On a paradox of traffic planning") in the German journal Unternehmensforschung. An English translation appeared only in 2005, in Transportation Science.
A year after Braess's paper Stuttgart invested in its road network, but traffic did not improve until a section of the new road was closed again. Walter Knödel described the case in his 1969 book on graph-theory methods.
On Earth Day New York's transportation commissioner Lucius Riccio closed 42nd Street in Manhattan. Many expected doomsday on the roads, but no jam came. On 25 December The New York Times told the story in an article by Gina Kolata featuring Braess's paradox.
Joel Cohen and Paul Horowitz described in Nature a rig of springs and strings holding a weight. Cut one taut string, and the weight goes up. They showed the same effect in an electric circuit of resistors and diodes.
The 5.6 km Cheonggye overpass stood above a stream buried in concrete. In 2003 mayor Lee Myung-bak began tearing it down, and in 2005 the restored stream with a park opened in its place. The number of cars entering downtown fell by 2.3%.
Roughgarden and Tardos's paper "How Bad Is Selfish Routing?" with its 4/3 bound won the Gödel Prize, one of the top awards in theoretical computer science. It shared the prize with two other papers in algorithmic game theory, including the one where Koutsoupias and Papadimitriou introduced the price of anarchy.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.