The Braess paradox

The Braess paradox, named after the mathematician Dietrich Braess, provides an example of a network that by adding links looses performance. On the example of a road network Braess showed that in some cases the addition of capacity - in this case of an additional road - can reduce the overall running time in the network, that is, the overall time it takes for drivers to get from point A to point D.

Braess, D. (1968). Uber ein Paradoxon der Verkehrsplanung. Unternehmenforschung 12, p. 258-268.

The problem behind this paradox is a suboptimal Nash-equilibrium of drivers selfishly trying to optimize their payoff (i.e. their driving time) but causing the opposite.

The paradox can be illustrated with the following simple road network consisting of four cities A, B, C and D and four roads connecting these cities. Commuters are trying to get from A to D and always chose the route that is most attractive in terms of travel time.

Braess 1

The driving time depends on the density of the traffic, that is, the number \(x\) of commuters currently using the roads. Since the routes ABD and ACD are equally attractive - both taking \(6x + 26\) minutes to get from A to D - the traffic will split half and half. For example, the driving time for each of 6 commuters, that is 3 commuters per route (\(x = 3\)), would be \(6*3 + 26 = 44\) minutes.

Now lets assume a high-speed highway with travel time \(= 1\) is added to the road net in the following form, providing additional possible routes ABCD and ACBD:

Braess 2

Since travel time on this new highway is fast and independent of density, the route ABCD will be highly attractive to drivers. If there is just one driver on this route, the new highway will reduce driving time to just 13 minutes. If there are two drivers, driving time becomes 23 minutes. If there are three, four or five of them it becomes 33, 43 and 53 minutes respectively. But once there are six commuters, like in the highway-less case above, travel time increases to 63 minutes, which raises the attractiveness of the routes ABD and ACD. If each route would be used by just the fifth and the sixth driver, these routes would reduce travel time of these drivers to 57 minutes - which after all is still remarkably more than the original 44 minutes without the additional highway. However, the other commuters would not waive the possibility to decrease their driving time too. They would switch together back and forth between those routes which seem most attractive to them and hence would increase driving time severely. The consequence of the additional highway hence is a dis-balance in Nash-equilibria which lets each of them become suboptimal.

In 1999 one of three main traffic tunnels in Seoul was shut down for maintenance. Despite the fact that the other two routes were heavily used, the result was not the predicted traffic congestion. Instead traffic flows improved in both cases. Inspired by this experience, Seoul’s city planners subsequently demolished a motorway leading into the center of the city. The result was exactly the same strange phenomenon, with the added benefit of creating a long, large park for the city's inhabitants

Baker L. (2009). Removing Roads and Traffic Lights Speeds Urban Travel. Scientific American, Jan 19, 2009.