Braess's paradox

The paradox was first discovered by Arthur Pigou in 1920,[1] and later named after the German mathematician Dietrich Braess in 1968.

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 when existing major roads are closed.

More formally, the idea behind Braess's discovery is that the Nash equilibrium may not equate with the best overall flow through a network.

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 when the moving entities selfishly choose their route can in some cases reduce overall performance.

The network change induces a new game structure which leads to a (multiplayer) prisoner's dilemma.

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.

[4] In 1983, Steinberg and Zangwill provided, under reasonable[independent source needed] 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.)

[6] In Seoul, South Korea, traffic around the city sped up when the Cheonggye Expressway was removed as part of the Cheonggyecheon restoration project.

[8] In 1990 the temporary closing of 42nd Street in Manhattan, New York City, for Earth Day reduced the amount of congestion in the area.

[9] 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.

[11] 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.

[6] He also notes that some private vehicle trips (and related economic activity) are not transferred to public transport and simply disappear ("evaporate").

[6] The same phenomenon was also observed when road closing was not part of an urban project but the consequence of an accident.

In particular, they showed that adding a path for electrons in a nanoscopic network paradoxically reduced its conductance.

Adilson E. Motter and collaborators demonstrated that Braess's paradox outcomes may often occur in biological and ecological systems.

[16] 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.

Consider a road network as shown in the adjacent diagram on which 4000 drivers wish to travel from point Start to End.

Now suppose the dashed line A–B is a road with an extremely short travel time of approximately 0 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 one assumes the travel time for each person driving on an edge to be equal, an equilibrium will always exist.

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.

Since the energy of the graph strictly decreases with each step, the best response dynamics algorithm must eventually halt.

Mlichtaich[20] proved that Braess's paradox may occur if and only if the network is not a series-parallel graph.