Braess' paradox

From Wikipedia, the free encyclopedia
  (Redirected from Braess's paradox)
Jump to: navigation, search

Braess' paradox or Braess's paradox is a proposed explanation for why a seeming improvement to a road network can impede traffic through it. It was exposed in 1968 by mathematician Dietrich Braess who noticed that adding a road to a congested road traffic network could increase overall journey time, and has been used to explain incidences of improved traffic flow when existing major roads are closed. The paradox may have analogues in electrical power grids and biological systems. It has been suggested that, in theory, the improvement of a malfunctioning network could be accomplished by removing certain parts of it.

Discovery and definition[edit]

Dietrich Braess, a mathematician at Ruhr University, Germany, was working on traffic modelling, when he noticed the flow in a road network could be impeded by adding a new road. Braess' idea was that if that each driver is making the optimal self-interested decision as to which route is quickest, then a short cut could be chosen too often for drivers to have the shortest travel times possible. More formally, the idea behind Braess' discovery is that the Nash equilibrium may not equate with the best overall flow through a network.[1]

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."

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 Nash equilibrium of such a system is not necessarily optimal. The network change induces a new game structure which leads to a (multiplayer) prisoner's dilemma. In a Nash equilibrium, drivers have no incentive to change their routes. While the system is not in a Nash equilibrium, individual drivers are able to improve their respective travel times by changing the routes they take. In the case of Braess' paradox, drivers will continue to switch until they reach Nash equilibrium, despite the reduction in overall performance.

If the latency functions are linear then adding an edge can never make total travel time at equilibrium worse by a factor of more than 4/3.[2]

Possible instances of the paradox in action[edit]

Prevalence[edit]

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. (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' paradox is about as likely to occur as not occur; their result applies to random rather than planned networks and additions.[3]

Traffic[edit]

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.[4] 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.[5] In 1990 the closing of 42nd street in New York City reduced the amount of congestion in the area.[6] In 2008 Youn, Gastner and Jeong demonstrated specific routes in Boston, New York City and London where this might actually occur and pointed out roads that could be closed to reduce predicted travel times.[7]

Electricity[edit]

In 2012, scientists at the Max Planck Institute for Dynamics and Self-Organization demonstrated through computational modeling the potential for this phenomenon to occur in power transmission networks where power generation is decentralized.[8] In 2012, an international team of researchers from Institut Néel (CNRS, France), INP (France), IEMN (CNRS, France) and UCL (Belgium) published in Physical Review Letters[9] a paper showing that Braess' paradox may occur in mesoscopic electron systems. In particular, they showed that adding a path for electrons in a nanoscopic network paradoxically reduced its conductance. This was shown both by theoretical simulations and experiments at low temperature using as scanning gate microscopy.

Biology[edit]

According to Adilson E. Motter possible Braess' paradox outcomes may exist in many biological systems. Motter suggests cutting out part of a damaged network could rescue it. For resource management of endangered species food webs, whereby extinction of many species might follow sequentially, a deliberate elimination of a doomed species from the network could be used to bring about the positive outcome of preventing a series of further extinctions.[10]

Team sports strategy[edit]

It has been suggested that in the sport of basketball a team can be seen as a network of possibilities for a route to scoring a goal, with a different efficiency for each pathway, and a star player could reduce the overall efficiency of the team, analogous to a short-cut that will be overused increasing the overall times for a journey through a road network. A proposed solution for maximum efficiency in scoring is for a star player to shoot about the same number of shots as teammates.[11]

Example[edit]

Braess paradox road example.svg

Consider a road network as shown in the adjacent 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 (likewise with the roads across from them). If the dashed road does not exist (so the traffic network has 4 roads in total), the time needed to drive Start-A-End route with A drivers would be \tfrac{A}{100} + 45. And the time needed to drive the Start-B-End route with B drivers would be \tfrac{B}{100} + 45. If either route were shorter, it would not be a Nash equilibrium: a rational driver would switch routes from the longer route to the shorter route. As there are 4000 drivers, the fact that A + B = 4000 can be used to derive the fact that A = B = 2000 when the system is at equilibrium. Therefore, each route takes \tfrac{2000}{100} + 45 = 65 minutes.

Now suppose the dashed line is a road with an extremely short travel time of approximately 0 minutes. In this situation, all drivers will choose the Start-A route rather than the Start-B route, because Start-A will only take \tfrac{T}{100} = \tfrac{4000}{100} = 40 minutes at its worst, whereas Start-B is guaranteed to take 45 minutes. Once at point A, every rational driver will elect to take the "free" road to B and from there continue to End, because once again A-End is guaranteed to take 45 minutes while A-B-End will take at most  0 + \tfrac{4000}{100} =  40 minutes. Each driver's travel time is \tfrac{4000}{100} + \tfrac{4000}{100} = 80 minutes, an increase from the 65 minutes required when the fast A-B road did not exist. No driver has an incentive to switch, as the two original routes (Start-A-End and Start-B-End) are both now 85 minutes. If every driver were to agree not to use the A-B path, every driver would benefit by reducing their travel time by 15 minutes. However, because any single driver will always benefit by taking the A-B path, the socially optimal distribution is not stable and so Braess' paradox occurs.

Existence of an equilibrium[edit]

Let L_e(x) be the formula for the cost of x people driving along edge e. If a traffic graph has linear edges (those of the form L_e(x) = a_ex + b_e > 0 where a_e and b_e are constants) then an equilibrium will always exist.

Suppose we have a linear traffic graph with e_x people driving along edge e. Let the energy of e, E(e) be

\sum_{i=1}^{e_x} L_e(i) = L_e(1) + L_e(2) + \cdots + L_e(e_x)

(If x_e = 0 let E(e) = 0). Let the total energy of the traffic graph be the sum of the energies of every edge in the graph.

Suppose that the distribution for the traffic graph is not an equilibrium. There must be at least one driver who can switch their route and improve total travel time. Suppose their original route is x_0, x_1, \ldots, x_n while their new route is y_0, y_1, \ldots, y_m. Let E be total energy of the traffic graph, and consider what happens when the route x_0, x_1, ... x_n is removed. The energy of each edge e will be reduced by L_e(e_x) and so the E will be reduced by \sum_{i=0}^n L_e(e_x). Note that this is simply the total travel time needed to take the original route. If we then add the new route, y_0, y_1, \ldots, y_m, E will be increased by the total travel time needed to take the new route. Because the new route is shorter than the original route, E must decrease. If we repeat this process, E will continue to decrease. As E must remain positive, eventually an equilibrium must occur.

Finding an equilibrium[edit]

The above proof outlines a procedure known as Best Response Dynamics, which finds an equilibrium for a linear traffic graph and terminates in a finite number of steps. The algorithm is termed "best response" because at each step of the algorithm, if the graph is not at equilibrium then some driver has a best response to the strategies of all other drivers, and switches to that response.

Pseudocode for Best Response Dynamics:

 Let P be some traffic pattern.
 while P is not at equilibrium:
   compute the potential energy e of P
   for each driver d in P:
     for each alternate path p available to d:
        compute the potential energy n of the pattern when d takes path p
        if n < e:
          modify P so that d takes path p
 continue the topmost while

At each step, if some particular driver could do better by taking an alternate path (a "best response"), doing so strictly decreases the energy of the graph. If no driver has a best response, the graph is at equilibrium. Since the energy of the graph strictly decreases with each step, the Best Response Dynamics algorithm must eventually halt.

How far from optimal is traffic at equilibrium[edit]

At worst, traffic in equilibrium is twice as bad as socially optimal[2]

Proof

S_j = \text{starting point for car } j \,
T_j = \text{target for car } j \,

Strategies for car j are possible paths from S_j to T_j

Each edge e has a travel function L_e(x) = a_e x + b_e for some a_e, b_e \geq 0

Energy on edge e with x drivers:

E(e) = L_e(1) + L_e(2) + \cdots + L_e(x)

Total time spent by all drivers on that edge:

T(e) = x L_e(x) ((where there are x terms))

E(e) is less than or equal to T(e) and

\begin{align}
L_e(1) + \cdots + L_e(x) &= a_e(1+2+\cdots+x) + b_e x \\
& = a_e \tfrac{x (x+1)}{2} + b_e x \\
& = x ( a_e \tfrac{x+1}{2} + b_e ) \\
& \geq \tfrac{1}{2} x ( a_e x + b_e ) \\
& = \tfrac{1}{2} T(e)
\end{align}

Resulting Inequality

\tfrac{1}{2}T(e) \leq E(e) \leq T(e)

If Z is a traffic pattern:

\tfrac{1}{2}\text{social cost}(Z) \leq E(Z) \leq \text{social cost}(Z)

If we start from a socially optimal traffic pattern Z and end in an equilibrium pattern Z':

\begin{align}
\text{social cost}(Z') & \leq 2 E(Z') \\
& \leq 2 E(Z) \\
& \leq 2 \text{social cost}(Z)
\end{align}

Thus we can see that worst is twice as bad as optimal.

Dynamics analysis of Braess' paradox[edit]

In 2013, Dal Forno and Merlone [12] interpret Braess' paradox as a dynamical ternary choice problem. The analysis shows how the new path changes the problem. Before the new path is available the dynamics is the same as in binary choices with externalities, but the new path transforms it into a ternary choice problem. The addition of an extra resource enriches the complexity of the dynamics. In fact, in this case, there can even be coexistence of cycles. This way, the implication of the paradox on the dynamics can be seen from both a geometrical and analytical perspective.

See also[edit]

References[edit]

  1. ^ New Scientist, 42nd St Paradox: Cull the best to make things better, 16 January 2014 by Justin Mullins
  2. ^ a b Easley, David; Kleinberg, Jon. "Networks, Crowds, and Markets: Reasoning about a Highly Connected World (8.3 Advanced Material: The Social Cost of Traffic at Equilibrium)" (PDF). Jon Kleinberg's Homepage. Jon Kleinberg. Archived (PDF) from the original on 2015-03-16. Retrieved 2015-05-30.  - This is the preprint of ISBN 9780521195331
  3. ^ Steinberg, R.; Zangwill, W. I. (1983). "The Prevalence of Braess' Paradox". Transportation Science 17 (3): 301. doi:10.1287/trsc.17.3.301.  edit
  4. ^ Easley, D.; Kleinberg, J. (2008). Networks. Cornell Store Press. p. 71. 
  5. ^ Knödel, W. (31 January 1969). Graphentheoretische Methoden Und Ihre Anwendungen. Springer-Verlag. pp. 57–59. ISBN 978-3-540-04668-4. 
  6. ^ Kolata, Gina (1990-12-25). "What if They Closed 42d Street and Nobody Noticed?". New York Times. Retrieved 2008-11-16. 
  7. ^ Youn, Hyejin; Gastner, Michael; Jeong, Hawoong (2008). "Price of Anarchy in Transportation Networks: Efficiency and Optimality Control". Physical Review Letters 101 (12): 128701. arXiv:0712.1598. Bibcode:2008PhRvL.101l8701Y. doi:10.1103/PhysRevLett.101.128701. ISSN 0031-9007. PMID 18851419. 
  8. ^ Staff (Max Planck Institute) (September 14, 2012), "Study: Solar and wind energy may stabilize the power grid", R&D Magazine, rdmag.com, retrieved September 14, 2012 
  9. ^ Pala, M. G.; Baltazar, S.; Liu, P.; Sellier, H.; Hackens, B.; Martins, F.; Bayot, V.; Wallart, X.; Desplanque, L.; Huant, S. (2012) [6 Dec 2011 (v1)]. "Transport Inefficiency in Branched-Out Mesoscopic Networks: An Analog of the Braess Paradox". Physical Review Letters 108 (7). arXiv:1112.1170. Bibcode:2012PhRvL.108g6802P. doi:10.1103/PhysRevLett.108.076802. ISSN 0031-9007. 
  10. ^ New Scientist, 42nd St Paradox: Cull the best to make things better, 16 January 2014 by Justin Mullins
  11. ^ The price of Anarchy in Basketball, Brian Skinner
  12. ^ Dal Forno, Arianna; Merlone, Ugo (2013). "Border-collision bifurcations in a model of Braess paradox". Mathematics and Computers in Simulation 87: 1–18. doi:10.1016/j.matcom.2012.12.001. ISSN 0378-4754. 

Further reading[edit]

  • D. Braess, Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258–268 (1969) [1] [2]
  • Katharina Belaga-Werbitzky: „Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienern“ ISBN 3-89959-123-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
  • Irvine, A. D. (1993). "How Braess' paradox solves Newcomb's problem". International Studies in the Philosophy of Science 7 (2): 141. doi:10.1080/02698599308573460.  edit
  • Steinberg, R.; Zangwill, W. I. (1983). "The Prevalence of Braess' Paradox". Transportation Science 17 (3): 301. doi:10.1287/trsc.17.3.301.  edit
  • A. Rapoport, T. Kugler, S. Dugar, and E. J. Gisches, Choice of routes in congested traffic networks: Experimental tests of the Braess Paradox. Games and Economic Behavior 65 (2009) [3]
  • T. Roughgarden. "The Price of Anarchy." MIT Press, Cambridge, MA, 2005.

External links[edit]