Braess's Paradox, math that surprises you lesson

Every morning 4000 drivers cross a small road network from the same start to the same finish, and each of them takes whichever route is quickest for them. A new one-way road opens that takes no time at all to drive, and nobody is forced to use it. Yet once the drivers have adjusted, every trip takes 80 minutes instead of 60. How can adding a free shortcut make every driver slower? This page computes the traffic before and after the shortcut, shows why the old pattern cannot last, and compares what each driver chooses with what would be best for all of them together.

Key terms

Braess’s paradox

Definition Braess’s paradox is the fact that in a traffic network where every driver chooses their own route, adding a road can make the travel time of every driver longer once the traffic has settled into equilibrium. It is named after Dietrich Braess, who described it in 1968. The standard example has a start $S$ , a finish $F$ and two junctions $A$ and $B$ , joined by four one-way roads. The roads $S \to A$ and $B \to F$ are narrow, and each takes $x/100$ minutes when $x$ drivers use it. The roads $A \to F$ and $S \to B$ are wide and always take $40$ minutes. Exactly $4000$ drivers go from $S$ to $F$ . Each driver is so small a part of the traffic that one driver changing routes changes no travel time, and each driver takes a route with the shortest travel time, given the routes of everyone else. With only the upper route $S \to A \to F$ and the lower route $S \to B \to F$ , the traffic settles at $2000$ drivers on each, and every trip takes $60$ minutes. Now add a one-way shortcut $A \to B$ that takes $0$ minutes, which creates the central route $S \to A \to B \to F$ . The traffic then settles with all $4000$ drivers on the central route, and every trip takes $80$ minutes. The resolution is that each driver compares routes at the current traffic and ignores the delay that their own choice adds for everyone else on the narrow roads. The old split is still possible after the shortcut opens and would still give everyone $60$ minutes, but it is no longer an equilibrium, because any one driver could then save $20$ minutes by switching. A new road does not always do this harm. In many networks, and in this one with other travel times, it shortens every trip. The example is a model with chosen numbers, and by itself it says nothing about whether a particular real road should be built or closed.

In plain words The shortcut looks like a free gift to whoever takes it, so everyone takes it. But every driver on the central route uses both narrow roads, so the narrow roads fill up until the central route is no faster than the old routes, and by then every driver is slower than before.

Example Before the shortcut, the split of $2000$ and $2000$ gives each narrow road $2000/100 = 20$ minutes, so each route takes $20 + 40 = 60$ minutes. When the shortcut opens and the old split is still in place, the central route would take

20 + 0 + 20 = 40

minutes, which is $20$ minutes faster than either old route, so drivers start to switch. With $2000$ drivers on the central route and $1000$ on each outer route, each narrow road carries $3000$ drivers and takes $30$ minutes. The central route then takes $30 + 0 + 30 = 60$ minutes and each outer route $30 + 40 = 70$ , so switching still pays. Once all $4000$ drivers use the central route, each narrow road takes $40$ minutes and the trip takes $80$ . A driver who tries the upper route instead meets $40 + 40 = 80$ minutes, and the lower route also gives $40 + 40 = 80$ , so no one gains by leaving. Every trip is now $20$ minutes longer than before the shortcut was built.

Traffic network

Definition A traffic network model has points called nodes, one-way roads between them called links, and a demand, a fixed amount of traffic that must travel from a start node to a finish node. A route is a path from the start to the finish that follows links in their allowed direction. The traffic is described by how many drivers take each route, with no negative numbers and with the total equal to the demand. The load on a link is the number of drivers whose route contains it. Each link has a travel time that depends only on its own load and never decreases when the load grows, and the travel time of a route is the sum of the travel times of its links at their loads. In the continuous model used here, the drivers form a flow that can be split in any proportions, so one driver alone changes no travel time.

In plain words The model records who drives where. Each road gets slower, or at least no faster, as it gets busier, and a trip takes as long as the roads it uses, added up.

Example In the network of Braess’s paradox with the shortcut, let $u$ , $l$ and $c$ be the numbers of drivers on the upper, lower and central routes, with $u + l + c = 4000$ . The road $S \to A$ lies on the upper and central routes, so its load is $x = u + c$ , and the road $B \to F$ has load $y = l + c$ . The route times are

\begin{aligned} T_{\text{up}} &= \frac{x}{100} + 40, \\[0.4em] T_{\text{low}} &= 40 + \frac{y}{100}, \\[0.4em] T_{\text{mid}} &= \frac{x}{100} + \frac{y}{100}. \end{aligned}

For $u = l = 1000$ and $c = 2000$ the loads are $x = y = 3000$ , which gives $T_{\text{up}} = T_{\text{low}} = 70$ and $T_{\text{mid}} = 60$ . Before the shortcut is built there is no central route, which is the same as requiring $c = 0$ .

Nash equilibrium

Definition In a game, each player chooses a strategy, and each player’s result depends on the choices of all the players. A Nash equilibrium is a choice of strategy for every player such that no player can get a better result by changing only their own strategy while all the others keep theirs. In a traffic network with continuous flow, where one driver alone changes no travel time, this becomes a condition on the traffic. The traffic is in equilibrium when every route used by a positive number of drivers has the shortest travel time among all the available routes, at the current loads. A route that nobody uses may tie with the used routes or be slower, but it is never faster. This form of the condition is also called a Wardrop equilibrium.

In plain words An equilibrium is a pattern of traffic that no driver wants to leave on their own. It is stable against single drivers changing their minds, which is not a promise that it is good for anyone.

Example Before the shortcut, suppose $u$ drivers take the upper route and $4000 - u$ take the lower one. The route times are

\begin{aligned} T_{\text{up}} &= \frac{u}{100} + 40, \\[0.4em] T_{\text{low}} &= 40 + \frac{4000 - u}{100}. \end{aligned}

They are equal only for $u = 2000$ , when both are $60$ minutes. A split of $2500$ and $1500$ gives $65$ minutes on the upper route and $55$ on the lower one, so a driver on the upper route can save $10$ minutes by switching, and the split is not an equilibrium. In the same way, any split with more than $2000$ drivers on one route makes that route the slower one, so the equal split is the only equilibrium.

Selfish routing

Definition Selfish routing is the model of traffic in which each driver chooses a route that minimizes their own travel time, taking the travel times produced by everyone else as given and ignoring the extra delay that their own choice adds for other drivers. The traffic it predicts is a Nash equilibrium. When the travel time of every link is a continuous function of its load that never decreases, such an equilibrium exists, and at an equilibrium all drivers with the same start and finish have the same travel time.

In plain words Every driver does the best they can for themselves, and the traffic settles where no one can do better alone. Nobody counts the minutes that their choice costs everyone else.

Example In the network with the shortcut, the upper and central routes share the road $S \to A$ , so their difference is

T_{\text{up}} - T_{\text{mid}} = 40 - \frac{y}{100}.

The load $y$ is at most $4000$ , so the difference is never negative, and it is $0$ only when $y = l + c = 4000$ , which forces $u = 0$ . So whenever some drivers take the upper route, the central route is strictly faster for them. The same comparison, with $T_{\text{low}} - T_{\text{mid}} = 40 - x/100$ , applies to the lower route. Selfish routing therefore ends with all $4000$ drivers on the central route, and this is the only equilibrium of the network with the shortcut.

Definition A social optimum of a traffic network is a way of routing the whole demand, with no negative numbers of drivers, that makes the total travel time of all the drivers as small as possible. Dividing the total by the number of drivers gives the average travel time, so a social optimum also has the smallest possible average. A social optimum need not be a Nash equilibrium, because it can ask some drivers to take a route that is slower for them than another available route. The ratio of the total travel time at an equilibrium to the total at a social optimum is called the price of anarchy. A theorem about selfish routing in the continuous model says that when the travel time of every link has the form $ax + b$ for its load $x$ , with constants $a \ge 0$ and $b \ge 0$ , as in Braess’s network, this ratio is never more than $4/3$ .

In plain words The social optimum is the traffic pattern that a planner who could assign every route would choose to make the average trip as short as possible. Drivers who choose for themselves need not end up there.

Example With the shortcut open, the total time of all drivers is the sum over the roads of the load times the road’s travel time. With $x = u + c$ , $y = l + c$ and $u + l = 4000 - c$ this gives

\begin{aligned} \text{total} &= \frac{x^2 + y^2}{100} \\[0.4em] &\quad + 40(4000 - c). \end{aligned}

The loads satisfy $x + y = 4000 + c$ . Since $2(x^2 + y^2) - (x + y)^2 = (x - y)^2$ is never negative, the first part is at least $(4000 + c)^2/200$ , with equality when $x = y$ , and expanding gives

\text{total} \ge 240000 + \frac{c^2}{200}

minutes. The smallest total, $240000$ minutes, comes from $c = 0$ and $u = l = 2000$ , an average of $60$ minutes. So the old split, with nobody on the shortcut, is the social optimum even after the shortcut is built, while selfish routing gives $80$ minutes. The ratio $80/60 = 4/3$ is the largest that the theorem allows. A planner who sent $1000$ drivers along the shortcut and $1500$ along each outer route would give the shortcut drivers $50$ minutes and the others $65$ , an average of $61.25$ minutes, which is worse than leaving the shortcut empty.

Check yourself

Keep the same roads, but let $3000$ drivers make the trip instead of $4000$ . Find the travel time before the shortcut and after it.

Show the answer

Before the shortcut, the route times are equal only when $1500$ drivers take each route. Then each narrow road takes $15$ minutes and each trip $15 + 40 = 55$ minutes, and as before this is the only equilibrium.

After the shortcut opens, the comparison from selfish routing becomes

T_{\text{up}} - T_{\text{mid}} = 40 - \frac{y}{100}

with $y$ at most $3000$ , so the difference is at least $10$ minutes and the upper route is always slower than the central one. The same holds for the lower route, so all $3000$ drivers take the central route. Each narrow road then takes $30$ minutes and every trip takes $30 + 0 + 30 = 60$ minutes, while either outer route would take $30 + 40 = 70$ . The shortcut again makes every trip longer, here by $5$ minutes.

Change the wide roads so that each takes $70$ minutes instead of $40$ , with $4000$ drivers and the same narrow roads. Does the shortcut still slow everyone down?

Show the answer

No. Before the shortcut, the equal split gives every trip $20 + 70 = 90$ minutes. After it opens, the difference between the upper and central routes is

T_{\text{up}} - T_{\text{mid}} = 70 - \frac{y}{100},

which is at least $70 - 40 = 30$ minutes, and the same holds for the lower route. So the outer routes are always slower and every driver takes the central route, which takes $40 + 0 + 40 = 80$ minutes, while an outer route would take $40 + 70 = 110$ . The shortcut now saves every driver $10$ minutes.

The paradox depends on the numbers. With these narrow roads and $4000$ drivers, the same kind of calculation shows that the shortcut makes the trips longer exactly when each wide road takes more than $20$ and less than $60$ minutes.

Let each wide road take $25$ minutes, with $4000$ drivers and the same narrow roads. Before the shortcut every trip takes $20 + 25 = 45$ minutes. Find the equilibrium after the shortcut opens.

Show the answer

Leaving the shortcut empty is not an equilibrium, because with $2000$ drivers on each narrow road the central route would take $20 + 0 + 20 = 40$ minutes, less than $45$ . Sending everyone along the shortcut is not one either, because then the central route takes $40 + 40 = 80$ minutes, while the upper route would take $40 + 25 = 65$ . So some drivers use the central route and some use an outer one.

A used outer route must tie with the central route. The upper and central routes tie when $25 = y/100$ , so $y = 2500$ , and the lower and central routes tie when $x = 2500$ . Both outer routes must be used. If, say, nobody took the lower route, the upper route would be used, so $y = 2500$ , while $x = u + c = 4000$ . The central route would then take $40 + 25 = 65$ minutes and the unused lower route $25 + 25 = 50$ , which is faster. The same argument with the two outer routes swapped rules out leaving the upper route empty. So $x = y = 2500$ , and from

\begin{aligned} x + y &= u + l + 2c \\[0.4em] &= 4000 + c \end{aligned}

the shortcut carries $c = 1000$ drivers and each outer route $1500$ . Every route then takes $25 + 25 = 50$ minutes. Some drivers use the shortcut and some do not, and all of them are $5$ minutes slower than before it opened.

Braess's Paradox

Video 1, chapter 16

Key terms

Braess’s paradox

Traffic network

Nash equilibrium

Selfish routing

Social optimum

Check yourself