Braess' paradox
From Wikipedia, the free encyclopedia
Braess' 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."
Contents |
[edit] Example
Consider a road network as shown in the upper diagram. Drivers wish to travel from the start to the finish, either via A or B. If a road is carrying less than its nominal capacity then cars can travel at 100 km/hour; if a road is carrying more than its nominal capacity then speeds are reduced to 100×capacity/users. Drivers will choose the route with the shortest time, with the result that all complete routes actually being used will take the same time.
In the upper diagram, with 2500 cars attempting the journey, 1250 will take the 110 km easterly route and 1250 the 110 km westerly route, each with a time requirement of 75 minutes.
If the road planners then try to add to road capacity by adding a central link between A and B, also providing a shorter distance route, as shown in the lower diagram, then 1500 cars will take the 80 km central route and 500 each of the original routes, each with a time of 84 minutes. This is longer than on the original network.
Whether adding capacity speeds up travel or slows it down depends on particular circumstances. In this example, adding the extra capacity speeds up travel if the number of cars using the network is fewer than 1334 or more than 4000. If instead the extra capacity had been added between the start and A, or between B and the finish, then speeds would have not have got slower for any level of use and in most cases would have improved.
Extending this, if 4000 cars attempt to use either of these networks, then the time will be the same with or without the new 60 km link between A or B. But if that new link was shortened to an instantaneous connection then travel times would increase by 12 minutes. This implies not only that improving part of a network can sometimes increase transit times but also that simply increasing choice (i.e. not restricting drivers to the east or west routes) can sometimes worsen overall results.
[edit] How rare is Braess' Paradox?
In 1983 Steinberg and Zangwill provided, under reasonable assumptions, necessary and sufficient conditions for Braess' paradox to occur in a general transportation network when a new route is added. As a corollary, they obtain that Braess' paradox is about as likely to occur as not occur; their result applies to random rather than planned networks and additions.
[edit] See also
[edit] References
- D. Braess, Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258 - 268 (1969) [1] [2]
- 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. More information
- A. D. Irvine. How Braess' 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' Paradox. Transportation Science, Vol. 17 (1983), no. 3, 301-318.
