braess' paradox

youtube

Chris Bishop explains Braess’s paradox, the very counterintuitive fact that adding extra capacity to a network, in which the moving entities selfishly choose their route, can in some cases reduce overall performance.

A concrete interpretation: removing fast roads can actually reduce the average journey times if all drivers act selfishly. The same phenomenon also occurs in data traffic over the internet and power transmission networks. The example in the video may seem artificial but has been observed in real life as well:

  • In Seoul, a speeding-up in traffic was seen when a motorway was removed as part of a restoration project.
  • In Stuttgart, despite investments into the road network, the traffic situation did not improve until a section of newly built road was closed for traffic again.
  • In New York City, the closing of a street reduced the amount of congestion in the area.
Braess's Paradox

Suppose you live in a small village just outside a city, and every morning you commute to work (along with 9 other residents) by one of two routes linking the village and the city, one via Town A and one via Town B.

On route A, the first portion of the road is relatively short, but narrow, and so takes N minutes to complete, where N is the number of cars taking the road. The second portion of the drive is longer, but with a much better carrying capacity, so takes a flat 12 minutes.

Route B is the opposite, with the longer, wider section first, and the shorter, narrower section second. Assuming that every driver wants to make their drive as short as possible, 5 people will take route A, and 5 will take route B, giving a journey time of N+12 = 5+12 = 17 minutes.

The council thinks this isn’t ideal, too many traffic jams on the narrow portions they say. So they add a road connecting Town A to Town B directly that takes 0 minutes (they’re really very close together). People have the option to change routes halfway through, however something very strange happens.

Now, when leaving the village, people deduce that the first portion of A is going to take 10 minutes tops (with all 10 cars on it) whereas the first portion of B will take 12! Of course they choose route A. Then they see that the second half of route B is again, at least 2 minutes quicker than the second part of A, a no-brainer. So everybody takes the first part of A, followed by the second part of B, however, the average travel time has now gone up to 20 minutes, 3 minutes longer than before.

Increasing the capacity of the road network has made the average commute slower! This is not a purely mathematical issue, and has been observed in cities around the world.

http://en.wikipedia.org/wiki/Braess’s_paradox