Braess's paradox

Examples

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, South Korea, traffic around the city sped up when the Cheonggye Expressway was removed as part of the Cheonggyecheon restoration project. 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. In 1990 the temporary closing of 42nd Street in Manhattan, New York City, for Earth Day 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 at Times Square and Herald Square, 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, 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, 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.

Mathematical approach

Example

Consider a road network on which 4000 drivers wish to travel from a Start point to an End point. They have two roads available to choose from, one that goes via point A and one that goes via point B.

The travel time in minutes from the Start to point A is the number of travellers (T) divided by 100, and the time to point B is a constant 45 minutes. These times are then reversed for the routes to the End point: from point A to the End point takes 45 minutes, and from B to the End point takes ${\displaystyle \frac{T}{100}}$.

If these are the only routes available, the time needed to drive Start–A–End route with ${\displaystyle a}$ drivers would be ${\displaystyle \frac{a}{100}+45}$. The time needed to drive the Start–B–End route with ${\displaystyle b}$ drivers would be ${\displaystyle \frac{b}{100}+45}$. As there are 4000 drivers, the fact that ${\displaystyle a+b=4000}$ can be used to derive the fact that ${\displaystyle a=b=2000}$ when the system is at equilibrium. Therefore, each route takes ${\displaystyle \frac{2000}{100}+45=65}$ 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 a new road was built connecting points A and B, 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 ${\displaystyle \frac{2000}{100}+\frac{2001}{100}=40.01}$ 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 ${\displaystyle \frac{2500}{100}+\frac{4000}{100}=65}$ minutes, which is no improvement over the original route. Meanwhile, those 1500 drivers have been slowed to ${\displaystyle 45+\frac{4000}{100}=85}$ minutes, a 20-minute increase. They are obliged to switch to the new route via A too, so it now takes ${\displaystyle \frac{4000}{100}+\frac{4000}{100}=80}$ minutes. Nobody has any incentive to travel A-End or Start-B because any driver trying them will take 90 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 ${\displaystyle L_e(x)}$ be the formula for the travel time of each person traveling along edge ${\displaystyle e}$ when ${\displaystyle x}$ people take that edge. Suppose there is a traffic graph with ${\displaystyle x_e}$ people driving along edge ${\displaystyle e}$. Let the energy of ${\displaystyle e}$, ${\displaystyle E(e)}$, be

$${\displaystyle \sum _{i=1}^{x_e}{L}_e(i)=L_e(1)+L_e(2)+\cdots +L_e(x_e)}$$

(If ${\displaystyle x_e=0}$ let ${\displaystyle E(e)=0}$). 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 ${\displaystyle e_0,e_1,\dots ,e_n}$ while the new route is ${\displaystyle e_0^{\prime },e_1^{\prime },\dots ,e_m^{\prime }}$. Let ${\displaystyle E}$ be total energy of the traffic graph, and consider what happens when the route ${\displaystyle e_0,e_1,...e_n}$ is removed. The energy of each edge ${\displaystyle e_i}$ will be reduced by ${\displaystyle L_{e_i}(x_{e_i})}$ and so the ${\displaystyle E}$ will be reduced by $\sum _{i=0}^n{L}_{e_i}(x_{e_i})$. That is simply the total travel time needed to take the original route. If the new route is then added, ${\displaystyle e_0^{\prime },e_1^{\prime },\dots ,e_m^{\prime }}$, the total energy ${\displaystyle 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, ${\displaystyle E}$ 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 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 <i id="mwoQ">P</i> be some traffic pattern. <b id="mwog">while</b> <i id="mwow">P</i> is not at equilibrium: compute the potential energy <i id="mwpA">e</i> of <i id="mwpQ">P</i> <b id="mwpg">for each</b> driver <i id="mwpw">d</i> in <i id="mwqA">P</i>: <b id="mwqQ">for each</b> alternate path <i id="mwqg">p</i> available to <i id="mwqw">d</i>: compute the potential energy <i id="mwrA">n</i> of the pattern when <i id="mwrQ">d</i> takes path <i id="mwrg">p</i> <b id="mwrw">if</b> <i id="mwsA">n</i> < <i id="mwsQ">e</i>: modify <i id="mwsg">P</i> so that <i id="mwsw">d</i> takes path <i id="mwtA">p</i> <b id="mwtQ">continue</b> the topmost <b id="mwtg">while</b>

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 ${\displaystyle L_e(x)=a_{e}x+b_e}$ for some ${\displaystyle a_e,b_e\ge 0}$, then at worst, traffic in the energy-minimizing equilibrium is twice as bad as socially optimal.

Proof: Let ${\displaystyle Z}$ be some traffic configuration, with associated energy ${\displaystyle E(Z)}$ and total travel time ${\displaystyle T(Z)}$. For each edge, the energy is the sum of an arithmetic progression, and using the formula for the sum of an arithmetic progression, one can show that ${\displaystyle E(Z)\le T(Z)\le 2E(Z)}$. If ${\displaystyle Z_o}$ is the socially-optimal traffic flow and ${\displaystyle Z_e}$ is the energy-minimizing traffic flow, the inequality implies that ${\displaystyle T(Z_e)\le 2E(Z_e)\le 2E(Z_o)\le 2T(Z_o)}$.

Thus, the total travel time for the energy-minimizing equilibrium is at most twice as bad as for the optimal flow.

Effect of network topology

Mlichtaich proved that Braess's paradox occurs in a two-terminal network if and only if it is not a series-parallel graph.

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.

Possible non-traffic analogies

Electricity

In 2012, scientists at the Max Planck Institute for Dynamics and Self-Organization demonstrated, through computational modelling, the potential for the phenomenon to occur in power transmission networks where power generation 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 a paper showing that Braess's 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. 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 hung 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 hung. This remains the case as we add two longer ropes in slack to connect the lower end of the upper spring to the hung 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 (in the mechanical sense) to each other. The total spring constant is twice that of each individual spring, and when the length of the long ropes is not too long, the hung weight will actually be higher compared to before the short rope was cut.

The fact that the hung 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 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, 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.

Blockchain networks

Braess's paradox has been shown to appear in blockchain payment channel networks, also known as layer-2 networks. Payment channel networks implement a solution to the scalability problem of blockchain networks, allowing transactions of high rates without recording them on the blockchain. In such a network, users can establish a channel by locking funds on each side of the channel. Transactions are executed either through a channel connecting directly the payer and payee or through a path of channels with intermediate users that ask for some fees.

While intuitively, opening new channels allows higher routing flexibility, adding a new channel might cause higher fees, and similarly closing existing channels might decrease fees. The paper presented a theoretical analysis with conditions for the paradox, methods for mitigating the paradox as well as an empirical analysis, showing the appearance in practice of the paradox and its effects on Bitcoin's Lightning network.