Chapter 4

BRAESS’S PARADOX

People take different roads seeking fulfillment and happiness. Just because they’re not on your road doesn’t mean they’ve gotten lost.

H. Jackson Browne

A Road to Nowhere

In the 1969 publication ‘Graphentheoretische Methoden und ihre Anwendungen’, W. Knödel remarked that

. . . major road investment in Stuttgart’s city centre, in the vicinity of the Schlossplatz, failed to yield the benefits expected. They were only obtained when a cross street, the lower part of Königstrasse, was subsequently withdrawn from traffic use. . . .

Eliminating a road, rather than building a road, improved traffic flow.

Figure 4.1.

Figure 4.1 shows a map of the relevant part of the city, with part of Königstrasse now a pedestrian precinct.

When 42nd Street in New York City was temporarily closed to traffic, rather than the expected gridlock resulting, traffic flowed more easily; in fact, it was reported in the 2 September 2002 edition of The New Yorker that in the twenty-three American cities that added the most new roads per person during the 1990s, traffic congestion rose by more than 70%.

These observed phenomena would have been no surprise to the German mathematician Dietrich Braess, who had published the article ‘Über ein Paradoxon aus der Verkehrsplanung’ in Unternehmenstorchung (12:258–68) in 1968, in which he made exactly that point: under the appropriate conditions, building new roads to ease congestion actually makes the problem worse. He made the point by use of a simple, hypothetical road network which deteriorated when a bypass link was added to it.

The Grip of an Invisible Hand

Figure 4.2 shows Braess’s hypothetical system of one-way roads from A to B, via alternatives X and Y. The arrows indicate the direction in which travel is possible and the expressions labelling the four routes are the ‘cost functions’ for that route. Here we can think of the ‘cost’ of following a particular route as the time taken for it to be traversed, given that a certain number of vehicles are using it; the driver will, we assume, wish to minimize this and the assumption is that he or she will be completely aware of the traffic situation at all times, selfishly choosing the route that is most beneficial to that individual. The determination of such cost functions is a complicated example of mathematical modelling but Braess suggested the simplest model of all: a linear function of the number of vehicles x_r using a particular route, which might be thought of as a loading influenced by the nature of the road in question and which uses up time, fuel, etc.

Figure 4.2.

If we take the traffic load from A to B to be n vehicles (perhaps an hour), the costs of using route X and route Y are clearly 10x₁ + x₄ + 50 and 10x₅ + x₂ + 50, respectively, and since any vehicle which committed to using the first part of a route must use the second part, x₁ = x₄ and x₂ = x₅. This means that the cost functions simplify to 11x₁ + 50 and 11x₂ + 50, respectively. The knowledgeable drivers will decide to use a particular route depending on the relative sizes of x₁ and x₂. The first driver in the system will have a choice of either route, the second will switch to the other route, the third is in the same position as the first, etc.: equilibrium is reached with the n drivers split into two sets of n, with equal cost functions of C = 11 × n + 50 = (11n + 100).

With this entirely selfish model in place, the natural equilibrium position is reached with the load equally shared between the two alternatives.

Now let us suppose that the authorities intervene by introducing a mechanism which routes traffic so that the average cost function is minimized, thereby bringing about a collective rather than individual benefit.

With the distribution shown in figure 4.2, the average cost function is given by

since x₁ + x₂ = n.

A little extra algebra allows us to rewrite the expression as

and this is clearly minimized when x₁ = n and so, once again, we have the result that an equally shared load provides the solution to the problem. The selfish approach has done as much as one which possesses corporate responsibility, with individual optimization aggregating to collective optimization: Adam Smith’s invisible hand has taken its grip.¹ Yet, Smith’s invisible hand sometimes loses its grip—and we are about to approach one such example.

Figure 4.3.

Figure 4.4.

The Grip Loosens

Suppose that, with a view to easing congestion, a one-way relief road is built joining X and Y, with a cost function of x₃ + 10, as shown in figure 4.3.

We can no longer conclude that x₁ = x₄ and x₂ = x₅ and we will study the behaviour of the network by adopting the notation that, of the n vehicles entering A, x of them choose path AX and y of those subsequently choose path XY. This means that x₁ = x, x₂ = n − x, x₃ = y, x₄ = x − y and x₅ = n − x + y, as in figure 4.4.

Now we can compute the cost functions for each of the three routes from A to B via X or via Y or via X and Y:

Equilibrium will be reached when all three cost functions are equal, with no route being better than any other. Setting C_X= C_Y and C_X = C_XY results in the two equations 2x − y = n and 11x − 12y = 10n − 40, which have solutions

It must be that for the solutions to make sense, and these inequalities reduce to respectively.

So, provided that we have meaningful solutions for the equilibrium position. Finally, substituting these values of x and y back into the original cost functions results in the equilibrium position of

Recall that, with no relief road, the cost equilibrium function C = (11n + 100). Braess’s Paradox emerges when C_X > C, which is when and this means that again we need

Braess’s Paradox will appear for any n which allows the equilibrium to be realized: n = 4, 5, 6, 7, 8.

In fact, Braess took n = 6 to demonstrate the point, which caused the traffic flow to be as in figure 4.5 and the equilibrium cost of travel before the relief road was built to be

Figure 4.5.

and the cost afterwards to be

The building of the extra road has made things worse!

We can also see that the invisible hand has indeed lost its grip. Now the average cost is the more formidable expression

which simplifies to

and which we will consider as a function of y for any given x, again completing the square to get

Now we have isolated y we can see that A will achieve its minimum value when for any given x. In the selfish case, we saw that equilibrium is achieved when which would now make which we can compare with the original The invisible hand has indeed disappeared.

There now exist any number of formulations of the phenomenon, using networks which are ever more complicated, with cost functions linear or otherwise. As a first step, in the original Braess form that we have looked at we might imagine that making XY two-way would make a difference but, although the numbers change, the paradox stubbornly reemerges.

We have framed the paradox, as Braess originally framed it, in terms of traffic flow and we have mentioned two cases where it might have a real impact on a road system. The article ‘The prevalence of Braess’s Paradox’ by R. Steinberg and W. I. Zangwill in the journal Transportation Science (17:301–18, 1983) provides more examples. That said, the paradox is essentially about flow in a network in which there are varied cost functions associated with its arcs, and as such it is not restricted to traffic flow: examples of it appear in cases of water flow, computer data transfer, mechanical and electrical networks and telephone exchanges. In 1990 the British Telecom network suffered in such a way when its ‘intelligent’ exchanges reacted to blocked routes by rerouting calls along ‘better’ paths. This in turn caused later calls to be rerouted with the cascade effect leading to a catastrophic change in the network’s behaviour.

Braess’s Paradox is a manifestation of small local changes unpredictably resulting in large global effects and has become a force to be reckoned with.

¹In his 1776 book, The Wealth of Nations, the economist Adam Smith wrote:

Every individual necessarily labours to render the annual revenue of the society as great as he can. He generally indeed neither intends to promote the public interest, nor knows how much he is promoting it. He intends only his own gain, and he is in this, as in many other cases, led by an invisible hand to promote an end which was no part of his intention. By pursuing his own interest he frequently promotes that of the society more effectually than when he really intends to promote it. I have never known much good done by those who affected to trade for the public good.