Braess's paradox

Braess's paradox, credited to the mathematician Dietrich Braess, states that adding extra capacity to a network, when the moving entities selfishly choose their route, can in some cases reduce overall performance. This is because the equilibrium of such a system is not necessarily optimal.

The paradox is stated as follows: "For each point of a road network, let there be given the number of cars starting from it, and the destination of the cars. Under these conditions one wishes to estimate the distribution of traffic flow. Whether one street is preferable to another depends not only on the quality of the road, but also on the density of the flow. If every driver takes the path that looks most favorable to him, the resultant running times need not be minimal. Furthermore, it is indicated by an example that an extension of the road network may cause a redistribution of the traffic that results in longer individual running times."

The reason for this is the Nash equilibrium of drivers will make any individual's attempt to find a better route futile, because other drivers would have to change their routes as well for an improvement to happen.

Example

Consider a road network as shown in the upper diagram, on which 4000 drivers wish to travel from point Start to End. The travel time in minutes on the Start-A road is the number of travelers (T) divided by 100, and on Start-B is a constant 45 minutes (similarly with the other roads). If the dashed road does not exist (so the traffic network has 4 roads in total), drivers will be indifferent between Start-A-End and Start-B-End. Each of these routes has a travel time of 2000/100 + 45 = 65 minutes.

Now suppose the dashed line is a road with a very small travel time of approximately 0 minutes. In this situation, all drivers will choose the Start-A path, as it is 40 minutes at its worst while Start-B is always 45. Upon reaching A, every rational driver will elect to take the "free" road to B and continue to End. Now the driver's travel time is 4000/100 + 4000/100 = 80 minutes, an increase from the 65 minutes required when the fast A-B road did not exist. The two original routes (Start-A-End and Start-B-End) are both now 85 minutes.

How rare is Braess's paradox?

In 1983 Steinberg and Zangwill provided, under reasonable assumptions, necessary and sufficient conditions for Braess's paradox to occur in a general transportation network when a new route is added. (Note that their result applies to the addition of "any" new route--not just to the case of adding a single link.) As a corollary, they obtain that Braess's paradox is about as likely to occur as not occur; their result applies to random rather than planned networks and additions.In Seoul, South Korea, a speeding-up in traffic around the city was seen when a motorway was removed as part of the Cheonggyecheon restoration project. [Easley, D and Kleinberg, J: "Networks", page 71. Cornell Store Press, 2008] In Stuttgart, Germany after investments into the road network in 1969, the traffic situation did not improve until a section of newly-built road was closed for traffic again. [Knödel, Walter: Graphentheoretische Methoden und ihre Anwendungen. Springer-Verlag 1969, p. 57 - 59] In 1990 the closing of 42nd street in New York City reduced the amount of congestion in the area. [G. Kolata: What if they closed 42nd Street and nobody noticed? In: New York Times, December 25, 1990, p. 38]

ee also

*Downs-Thomson paradox
*Induced demand
*Lewis-Mogridge Position
*Traffic wave

References

* D. Braess, Über ein Paradoxon aus der Verkehrsplanung. "Unternehmensforschung" 12, 258 - 268 (1969) [http://homepage.ruhr-uni-bochum.de/Dietrich.Braess/paradox.pdf] [http://homepage.rub.de/Dietrich.Braess/Paradox-BNW.pdf]
*Translation of the Braess 1968 article from German to English appears as the article "On a paradox of traffic planning," by D. Braess, A. Nagurney, and T. Wakolbinger in the journal Transportation Science, volume 39, 2005, pp. 446-450. [http://supernet.som.umass.edu/cfoto/braess-visit/braessvisit.html More information]
* A. D. Irvine. How Braess's Paradox Solves Newcomb's Problem. "International Studies in Philosophy of Science", Vol. 7 (1993), no. 2, 145-164.
* R. Steinberg and W.I. Zangwill. The Prevalence of Braess's Paradox. "Transportation Science", Vol. 17 (1983), no. 3, 301-318.

External links

* [http://msdn.microsoft.com/msdnmag/issues/05/12/TestRun/default.aspx Software Testing Paradoxes]
* [http://homepage.ruhr-uni-bochum.de/Dietrich.Braess/#paradox Braess's homepage]
* [http://tigger.uic.edu/~hagstrom/Research/Braess/ Characterizing Braess's Paradox for Traffic Networks]
* [http://www.davros.org/science/roadparadox.html The Road Network Paradox]