Braess's paradox is the observation that adding one or more roads to a road network can slow down overall
traffic
Traffic comprises pedestrians, vehicles, ridden or herded animals, trains, and other conveyances that use public ways (roads) for travel and transportation.
Traffic laws govern and regulate traffic, while rules of the road include traffic ...
flow through it. The paradox was discovered by the German mathematician
Dietrich Braess in 1968.
The paradox may have analogies 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. The paradox has been used to explain instances of improved
traffic flow
In mathematics and transportation engineering, traffic flow is the study of interactions between travellers (including pedestrians, cyclists, drivers, and their vehicles) and infrastructure (including highways, signage, and traffic control devi ...
when existing major roads are closed.
Discovery and definition
Dietrich Braess, a mathematician at
Ruhr University
The Ruhr University Bochum (, ) is a public research university located in the southern hills of the central Ruhr area, Bochum, Germany. It was founded in 1962 as the first new public university in Germany after World War II. Instruction began in ...
,
Germany
Germany,, officially the Federal Republic of Germany, is a country in Central Europe. It is the second most populous country in Europe after Russia, and the most populous member state of the European Union. Germany is situated betwe ...
, noticed the flow in a road network could be impeded by adding a new road, when he was working on
traffic modelling. His idea was that if each driver is making the
optimal
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
self-interested decision as to which route is quickest, a shortcut could be chosen too often for drivers to have the shortest travel times possible. More formally, the idea behind Braess's discovery is that the
Nash equilibrium
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
may not equate with the best overall flow through a network.
[New Scientist]
42nd St Paradox: Cull the best to make things better
16 January 2014 by Justin Mullins
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 favourable to them, 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
Network, networking and networked may refer to:
Science and technology
* Network theory, the study of graphs as a representation of relations between discrete objects
* Network science, an academic field that studies complex networks
Mathematics
...
when the moving entities selfishly choose their route can in some cases reduce overall performance. That is because the
Nash equilibrium
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
of such a system is not necessarily optimal. The network change induces a new game structure which leads to a (multiplayer)
prisoner's dilemma
The Prisoner's Dilemma is an example of a game analyzed in game theory. It is also a thought experiment that challenges two completely rational agents to a dilemma: cooperate with their partner for mutual reward, or betray their partner ("defe ...
. 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's paradox, drivers will continue to switch until they reach Nash equilibrium despite the reduction in overall performance.
If the latency functions are linear, adding an edge can never make total travel time at equilibrium worse by a factor of more than 4/3.
[
]
Possible instances of the paradox in action
Prevalence
In 1983, Steinberg and Zangwill provided, under reasonable assumptions, the 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 when a random new route is added.
Traffic
Braess's paradox has a counterpart in case of a reduction of the road network (which may cause a reduction of individual commuting time).
[
In ]Seoul
Seoul (; ; ), officially known as the Seoul Special City, is the capital and largest metropolis of South Korea.Before 1972, Seoul was the ''de jure'' capital of the Democratic People's Republic of Korea (North Korea) as stated iArticle 103 ...
, South Korea
South Korea, officially the Republic of Korea (ROK), is a country in East Asia, constituting the southern part of the Korea, Korean Peninsula and sharing a Korean Demilitarized Zone, land border with North Korea. Its western border is formed ...
, traffic around the city sped up when a motorway was removed as part of the Cheonggyecheon
Cheonggyecheon (Hangul: 청계천, ) is a modern public recreation space in downtown Seoul, South Korea. The massive urban renewal project is on the site of a stream that flowed before the rapid post-war economic development caused it to be co ...
restoration project. In Stuttgart
Stuttgart (; Swabian: ; ) is the capital and largest city of the German state of Baden-Württemberg. It is located on the Neckar river in a fertile valley known as the ''Stuttgarter Kessel'' (Stuttgart Cauldron) and lies an hour from the ...
, Germany
Germany,, officially the Federal Republic of Germany, is a country in Central Europe. It is the second most populous country in Europe after Russia, and the most populous member state of the European Union. Germany is situated betwe ...
, 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. In 1990 the temporary closing of 42nd Street in New York City
New York, often called New York City or NYC, is the List of United States cities by population, most populous city in the United States. With a 2020 population of 8,804,190 distributed over , New York City is also the L ...
for Earth Day
Earth Day is an annual event on April 22 to demonstrate support for environmental protection. First held on April 22, 1970, it now includes a wide range of events coordinated globally by EarthDay.org (formerly Earth Day Network) including 1 b ...
reduced the amount of congestion in the area. In 2008 Youn, Gastner and Jeong demonstrated specific routes in Boston, New York City and London where that might actually occur and pointed out roads that could be closed to reduce predicted travel times. In 2009, New York experimented with closures of Broadway
Broadway may refer to:
Theatre
* Broadway Theatre (disambiguation)
* Broadway theatre, theatrical productions in professional theatres near Broadway, Manhattan, New York City, U.S.
** Broadway (Manhattan), the street
**Broadway Theatre (53rd Stree ...
at Times Square
Times Square is a major commercial intersection, tourist destination, entertainment hub, and neighborhood in Midtown Manhattan, New York City. It is formed by the junction of Broadway, Seventh Avenue, and 42nd Street. Together with adjacent ...
and Herald Square
Herald Square is a major commercial intersection in the Midtown Manhattan neighborhood of New York City, formed by the intersection of Broadway, Sixth Avenue (officially Avenue of the Americas), and 34th Street. Named for the now-defunct ''New ...
, which resulted in improved traffic flow and permanent pedestrian plazas.
In 2012, Paul Lecroart, of the institute of planning and development of the Île-de-France
, timezone1 = CET
, utc_offset1 = +01:00
, timezone1_DST = CEST
, utc_offset1_DST = +02:00
, blank_name_sec1 = Gross regional product
, blank_info_sec1 = Ranked 1st
, bla ...
, wrote that "Despite initial fears, the removal of main roads does not cause deterioration of traffic conditions beyond the starting adjustments. The traffic transfer are limited and below expectations".[ He also notes that some private vehicle trips (and related economic activity) are not transferred to public transport and simply disappear ("evaporate").][
The same phenomenon was also observed when road closing was not part of an urban project but the consequence of an accident. In 2012 in ]Rouen
Rouen (, ; or ) is a city on the River Seine in northern France. It is the prefecture of the Regions of France, region of Normandy (administrative region), Normandy and the Departments of France, department of Seine-Maritime. Formerly one of ...
, a bridge was destroyed by fire. Over the next two years, other bridges were used more, but the total number of cars crossing bridges was reduced.[ Olivier Razemon, "Le paradoxde de l'« évaporation » du trafic automobile", '']Le Monde
''Le Monde'' (; ) is a French daily afternoon newspaper. It is the main publication of Le Monde Group and reported an average circulation of 323,039 copies per issue in 2009, about 40,000 of which were sold abroad. It has had its own website si ...
'', Thursday 25 August 2016, page 5. Published on-line a
"Et si le trafic s’évaporait ?"
on 24 August 2016 and updated on 25 August 2016 (page visited on 19 September 2016).
Electricity
In 2012, scientists at the Max Planck Institute for Dynamics and Self-Organization
The Max Planck Institute for Dynamics and Self-Organization in Göttingen, Germany, is a research institute for investigations of complex non-equilibrium systems, particularly in physics and biology.
Its founding history goes back to Ludwig Pran ...
demonstrated, through computational modelling
Computer simulation is the process of mathematical modelling, performed on a computer, which is designed to predict the behaviour of, or the outcome of, a real-world or physical system. The reliability of some mathematical models can be deter ...
, the potential for the phenomenon to occur in power transmission networks where power generation
Electricity generation is the process of generating electric power from sources of primary energy. For utilities in the electric power industry, it is the stage prior to its delivery ( transmission, distribution, etc.) to end users or its stor ...
is decentralized.
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
''Physical Review Letters'' (''PRL''), established in 1958, is a peer-reviewed, scientific journal that is published 52 times per year by the American Physical Society. As also confirmed by various measurement standards, which include the ''Journa ...
'' a paper showing that Braess's paradox may occur in mesoscopic
Mesoscopic physics is a subdiscipline of condensed matter physics that deals with materials of an intermediate size. These materials range in size between the nanoscale for a quantity of atoms (such as a molecule) and of materials measuring micr ...
electron systems. In particular, they showed that adding a path for electrons in a nanoscopic network paradoxically reduced its conductance. That was shown both by simulations as well as experiments at low temperature using scanning gate microscopy.
Springs
A model with springs and ropes can show that a hanged weight can rise in height despite a taut rope in the hanging system being cut, and follows from the same mathematical structure as the original Braess's paradox.
For two identical springs joined in series by a short rope, their total spring constant is half of each individual spring, resulting in a long stretch when a certain weight is hanged; This remains the case as we add two longer ropes in slack to connect the lower end of the upper spring to the hanged weight (lower end of the lower spring), and the upper end of the lower spring to the hanging point (upper end of the upper spring). However, when the short rope is cut, the longer ropes become taut, and the two springs become parallel to each other; The total spring constant is twice of each individual spring, and when the length of the long ropes are not too long, the hanged weight will actually rise in height compared to before the short rope is cut.
The fact that the hanged weight rises despite cutting a taut rope (the short rope) in the hanging system is counter-intuitive, but it does follow from Hooke's law and the way springs work in series and in parallel.
Biology
Adilson E. Motter
Adilson E. Motter (born January 1, 1974, in Brazil), is the Charles E. and Emma H. Morrison Professor of Physics at Northwestern University, where he has helped develop the concept of synthetic rescue in network biology as well as methods to con ...
and collaborators demonstrated that Braess's paradox outcomes may often occur in biological and ecological systems. Motter suggests removing part of a perturbed network could rescue it. For resource management of endangered species food webs
A food web is the natural interconnection of food chains and a graphical representation of what-eats-what in an ecological community. Another name for food web is consumer-resource system. Ecologists can broadly lump all life forms into one ...
, in which extinction of many species might follow sequentially, selective removal of a doomed species from the network could in principle bring about the positive outcome of preventing a series of further extinctions.
Team sports strategy
It has been suggested that in basketball, a team can be seen as a network of possibilities for a route to scoring a basket, with a different efficiency for each pathway, and a star player could reduce the overall efficiency of the team, analogous to a shortcut that is 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. However, this approach is not supported by hard statistical evidence, as noted in the original paper.
Mathematical approach
Example
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 travellers (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 drivers would be . The time needed to drive the Start–B–End route with drivers would be . As there are 4000 drivers, the fact that can be used to derive the fact that when the system is at equilibrium. Therefore, each route takes minutes. If either route took less time, it would not be a Nash equilibrium: a rational driver would switch from the longer route to the shorter route.
Now suppose the dashed line A–B is a road with an extremely short travel time of approximately 0 minutes. Suppose that the road is opened and one driver tries Start–A–B–End. To his surprise he finds that his time is minutes, a saving of almost 25 minutes. Soon, more of the 4000 drivers are trying this new route. The time taken rises from 40.01 and keeps climbing. When the number of drivers trying the new route reaches 2500, with 1500 still in the Start–B–End route, their time will be minutes, which is no improvement over the original route. Meanwhile, those 1500 drivers have been slowed to minutes, a 20-minute increase. They are obliged to switch to the new route via A too, so it now takes minutes. Nobody has any incentive to travel A-End or Start-B because any driver trying them will take 85 minutes. Thus, the opening of the cross route triggers an irreversible change to it by everyone, costing everyone 80 minutes instead of the original 65. If every driver were to agree not to use the A–B path, or if that route were closed, every driver would benefit by a 15-minute reduction in travel time.
Existence of an equilibrium
If one assumes the travel time for each person driving on an edge to be equal, an equilibrium will always exist.
Let be the formula for the travel time of each person traveling along edge when people take that edge. Suppose there is a traffic graph with people driving along edge . Let the energy of , , be
:
(If let ). Let the total energy of the traffic graph be the sum of the energies of every edge in the graph.
Take a choice of routes that minimizes the total energy. Such a choice must exist because there are finitely many choices of routes. That will be an equilibrium.
Assume, for contradiction, this is not the case. Then, there is at least one driver who can switch the route and improve the travel time. Suppose the original route is while the new route is . Let be total energy of the traffic graph, and consider what happens when the route is removed. The energy of each edge will be reduced by and so the will be reduced by . That is simply the total travel time needed to take the original route. If the new route is then added, , the total energy will be increased by the total travel time needed to take the new route. Because the new route is shorter than the original route, must decrease relative to the original configuration, contradicting the assumption that the original set of routes minimized the total energy.
Therefore, the choice of routes minimizing total energy is an equilibrium.
Finding an equilibrium
The above proof outlines a procedure known as best response
In game theory, the best response is the strategy (or strategies) which produces the most favorable outcome for a player, taking other players' strategies as given (; ). The concept of a best response is central to John Nash's best-known contribu ...
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?
If the travel time functions are linear, that is for some , then at worst, traffic in the energy-minimizing equilibrium is twice as bad as socially optimal.[
– This is the preprint of ]
Proof: Let be some traffic configuration, with associated energy and total travel time . For each edge, the energy is the sum of an arithmetic progression
An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
, and using the formula for the sum of an arithmetic progression, one can show that . If is the socially-optimal traffic flow and is the energy-minimizing traffic flow, the inequality implies that .
Thus, the total travel time for the energy-minimizing equilibrium is at most twice as bad as for the optimal flow.
Dynamics analysis of Braess's paradox
In 2013, Dal Forno and Merlone interpret Braess's 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, there can even be coexistence of cycles, and the implication of the paradox on the dynamics can be seen from both a geometrical and an analytical perspective.
See also
*
*
*
*
References
Further reading
(translation by Nagurney & Wakolbinger)
*Katharina Belaga-Werbitzky: „Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienern“
* 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
*
*
*
* T. Roughgarden. "The Price of Anarchy." MIT Press, Cambridge, MA, 2005.
External links
Software Testing Paradoxes (Dec. 2005)Direct Link
Dietrich Braess's homepage
Short video illustrating the Braess Paradox with Lego minifigures
The Spring Paradox
YouTube
YouTube is a global online video platform, online video sharing and social media, social media platform headquartered in San Bruno, California. It was launched on February 14, 2005, by Steve Chen, Chad Hurley, and Jawed Karim. It is owned by ...
video by Steve Mould explaining Braess's Paradox as well as a closely related spring
Spring(s) may refer to:
Common uses
* Spring (season)
Spring, also known as springtime, is one of the four temperate seasons, succeeding winter and preceding summer. There are various technical definitions of spring, but local usage of ...
paradox
{{Portal bar, Mathematics, Roads, Transport, Economy
Mathematical paradoxes
Game theory
Network flow problem
1968 introductions
Articles with example pseudocode