Braess paradox

The Braess paradox is an illustration of the fact that an additional option for action, assuming rational individual decisions, can lead to a worsening of the situation for all. The paradox was published in 1968 by the German mathematician Dietrich Braess .

Braess' original work shows a paradoxical situation in which the construction of an additional road (i.e. an increase in capacity) leads to the fact that the journey time for all drivers increases (i.e. the capacity of the network is reduced) with the same traffic volume . It is assumed that every road user chooses his route in such a way that he has no other option with a shorter journey time. The situation that arises after the construction of the new road can be interpreted in game theory as a multi-person prisoner's dilemma and thus explain this paradox.

Occasionally, the paradox is discussed with selfish routers as well. In addition, the Braess paradox is an example that the rational optimization of individual interests in connection with a publicly provided good can lead to a deteriorated condition for each individual.

example

A road network is chosen here as an example of the occurrence of the Braess paradox . If this road network is expanded by another road, the travel time for each driver is increased. The example is taken from Braess' original work Über ein Paradoxon from 1968 in traffic planning.

initial situation

Fig. 1: Sketch of the initial situation

Figure 2: Traffic density with 6000 drivers per hour

The four cities A, B, C and D are connected by four roads. A motorway runs both from A to C and from B to D. The motorways are well developed, so that the journey time depends little on the traffic density. However, the highways have to overcome an obstacle and are therefore quite long. With a traffic volume (in thousands of cars per hour) the corresponding travel time per driver is ${\ displaystyle x}$

{\ displaystyle t _ {\ mathrm {AC}} (x) = t _ {\ mathrm {BD}} (x) = (50 + x) \, \ mathrm {min}}

Cities A and B, like cities C and D, are connected by a country road. These streets are shorter than the motorways, but they are much worse developed. The travel time per driver therefore essentially only depends on the volume of traffic:

{\ displaystyle t _ {\ mathrm {AB}} (x) = t _ {\ mathrm {CD}} (x) = (0 + 10 \ cdot x) \, \ mathrm {min}}

All drivers want to drive from A to D, and each driver chooses the fastest route for them. A so-called Nash equilibrium is established , in which half of the drivers use the route via city B and the other half drive via city C. With 6,000 drivers per hour, 3,000 cars are driving each route and all drivers have a journey time of 83 minutes.

Scenario after the construction of the additional road

Figure 3: Sketch of the scenario after the construction of the additional road

Fig. 4: Equilibrium situation with a new line. The flows (in 1000 cars per hour) are indicated on the routes

After a while, the responsible politicians decide to build a tunnel through the mountain between cities B and C as shown in Figure 3. This new line can only be driven in the direction B → C - this simplifies the consideration, but is not relevant for the occurrence of the paradox.

On this additional route applies to the duration of the journey

{\ displaystyle t _ {\ mathrm {BC}} (x) = (10 + x) \, \ mathrm {min}}

.

So this route is short and has a high capacity .

Here, too, there is a balance (Fig. 4), in which the travel times are the same on all routes:

2000 drivers choose the ABD route
2000 drivers choose the ACD route
2000 drivers choose the ABCD route
Thus there is a current of 4,000 vehicles per hour on the country roads, and a current of 2,000 vehicles per hour on the motorways and the new construction line.

In this case, the journey time is 92 minutes for all drivers, 9 minutes longer than without the new route.

illustration

Considered clearly, a rural road section that is necessarily to be used is the bottleneck for the drivers who use one of the freeways. There the speed of the traffic flow depends strongly on the number of road users or is reduced by them. However, the new road construction now means that some drivers use the full length of the country road and thus also clog it - in addition to the new route, they now use both country road sections and not just one like the motorway users. The bottleneck situation has now become clearer, as the motorway users also need significantly longer for their inevitably used rural road section. In the example, the corresponding reduction in traffic on the high-capacity motorways can not bring about a compensatory time advantage.

discussion

One could now assume that some drivers choose different routes to create a better situation. However, this is not the case. A driver who decides otherwise the next day - provided that the described balance exists - has the effect that the journey time on the route he has chosen - and thus for himself - is extended. This state corresponds to a Nash equilibrium . On the previous day's route, however, the journey time is reduced for everyone else. Of course, this is not a criterion that induces a driver to change his route. For the sake of simplicity, in the following numerical example, 1000 drivers each change their route compared to the equilibrium. If the behavior of an individual driver changed, the changes would be smaller, but always go in the same direction because of the monotonous (linear) dependence of the journey time on the river.

Fig. 5: Average travel time if N = 6000 drivers drive p via BD and k via BC. That is, N - p - k drive on AC, N - p CD, p + k AB, k BC, p BD. The minimum is p = 3000, k = 0 (red area).

3000 drivers choose the ABD route and take 93 minutes. 2000 drivers choose the ACD route and take 82 minutes. 1000 drivers choose the ABCD route and take 81 minutes.
3000 drivers choose the ABD route and take 103 minutes. 1000 drivers choose the ACD route and take 81 minutes. 2000 drivers choose the ABCD route and take 92 minutes.
2000 drivers choose the ABD route and take 82 minutes. 3000 drivers choose the ACD route and take 93 minutes. 1000 drivers choose the ABCD route and take 81 minutes.
1000 drivers choose the ABD route and take 81 minutes. 3000 drivers choose the ACD route and take 103 minutes. 2000 drivers choose the ABCD route and take 92 minutes.
1000 drivers choose the ABD route and take 91 minutes. 2000 drivers choose the ACD route and take 102 minutes. 3000 drivers choose the ABCD route and take 103 minutes.
2000 drivers choose the ABD route and take 102 minutes. 1000 drivers choose the ACD route and take 91 minutes. 3000 drivers choose the ABCD route and take 103 minutes.

Please note that on all routes with 3000 drivers per hour, the journey time is longer than 92 minutes.

If all drivers agreed to ignore the new route and to behave as they did when it didn't exist, the journey time for all road users would be 83 minutes again. However, the temptation would be great to be the only one to use the then free new line and thus to reduce your own journey time from 83 minutes to 70 minutes. The usual human behavior then is to imitate the breach of contract. The system thus tends to return to the equilibrium described above. As a solution to this dilemma , there is no other option than to demolish the new line, planned centrally, or to double the capacity of lines AB and CD.

In his original publication, Braess did not classify the situation as a prisoner's dilemma , but it is a variant of a multi-person prisoner's dilemma with three alternative choices.

Occurrence of Braess paradoxes in the real world

There are examples that the Braess paradox is not just a theoretical construct. In 1969, the opening of a new street in Stuttgart meant that the flow of traffic in the vicinity of Schlossplatz deteriorated. In New York in 1990 the opposite phenomenon was observed. Blocking 42nd Street resulted in fewer traffic jams in the area. Likewise, traffic flow and travel times improved in the South Korean capital Seoul in 2005 after a four-lane, cross-free urban highway was demolished. There are other empirical reports of the paradox occurring from the streets of Winnipeg . In Neckarsulm, the flow of traffic improved after an often closed level crossing was shut down completely. The effect was shown when it had to be temporarily closed due to a construction site. Theoretical considerations also suggest that the Braess paradox occurs frequently in random networks. Many networks in the real world are random networks.

Mechanical analogue

Mechanical analogue: a weight hangs on two soft springs (yellow) and three hard springs (blue and red)

There is an analogue - albeit not in the narrow sense of a mathematical representation - to the Braess paradox in mechanics :

A weight (weight force 6 N) is suspended from two spring strands. The first consists of a weak yellow feather at the top (between points A and B) and a strong blue feather at the bottom (between B and D), the second strand at the top of a strong blue feather (between A and C) and one at the bottom weak yellow feather (between C and D). The yellow feathers have the length , depending on the force acting on them , the blue feathers the length . The weight is divided equally between the suspensions ABD and ACD, so that a force of 3 N acts on both suspensions. The length of the springs is then ${\ displaystyle F}$ ${\ displaystyle l _ {\ mathrm {g}} (F) = 10 \, \ mathrm {\ tfrac {cm} {N}} \ cdot F}$ ${\ displaystyle l _ {\ mathrm {b}} (F) = 50 \, \ mathrm {cm} +1 \, \ mathrm {\ tfrac {cm} {N}} \ cdot F}$

{\ displaystyle {\ begin {matrix} l _ {\ mathrm {AB}} (3 \, \ mathrm {N}) = 30 \, \ mathrm {cm} \\ l _ {\ mathrm {BD}} (3 \, \ mathrm {N}) = 53 \, \ mathrm {cm} \\ l _ {\ mathrm {AC}} (3 \, \ mathrm {N}) = 53 \, \ mathrm {cm} \\ l _ {\ mathrm {CD}} (3 \, \ mathrm {N}) = 30 \, \ mathrm {cm} \ end {matrix}}}

The entire suspension is 83 cm long.

If the points B and C are now connected with another spring (red in the sketch), the length of which is, one could assume that this spring absorbs part of the force and thereby relieves the other springs, so that the weight is lifted. In fact, only the blue springs are relieved and the yellow springs are more heavily loaded. Because the yellow feathers are weaker, they expand more than the blue ones shorten. This leads to the fact that the weight goes down. In the state of equilibrium, forces of 2 N each act on the blue springs and the red spring, and forces of 4 N each on the yellow springs, resulting in the following lengths: ${\ displaystyle l _ {\ mathrm {r}} (F) = 10 \, \ mathrm {cm} +1 \, \ mathrm {\ tfrac {cm} {N}} \ cdot F}$

{\ displaystyle {\ begin {matrix} l _ {\ mathrm {AB}} (4 \, \ mathrm {N}) = 40 \, \ mathrm {cm} \\ l _ {\ mathrm {BD}} (2 \, \ mathrm {N}) = 52 \, \ mathrm {cm} \\ l _ {\ mathrm {AC}} (2 \, \ mathrm {N}) = 52 \, \ mathrm {cm} \\ l _ {\ mathrm {CD}} (4 \, \ mathrm {N}) = 40 \, \ mathrm {cm} \\ l _ {\ mathrm {BC}} (2 \, \ mathrm {N}) = 12 \, \ mathrm { cm} \ end {matrix}}}

The length of the entire suspension increases to 92 cm.

Note: To find the equilibrium, the following system of equations must be solved for the forces:

{\ displaystyle {\ begin {matrix} F _ {\ mathrm {AB}} = F _ {\ mathrm {BD}} + F _ {\ mathrm {BC}} \\ F _ {\ mathrm {CD}} = F _ {\ mathrm {BC}} + F _ {\ mathrm {AC}} \\ F _ {\ mathrm {AB}} + F _ {\ mathrm {AC}} = 6 \, \ mathrm {N} \\ F _ {\ mathrm {AB} } = F _ {\ mathrm {CD}} \\ l _ {\ mathrm {AB}} (F _ {\ mathrm {AB}}) + l _ {\ mathrm {BC}} (F _ {\ mathrm {BC}}) = l _ {\ mathrm {AC}} (F _ {\ mathrm {AC}}) \ end {matrix}}}

Relationship to other problems

A variant of Newcomb's problem can be solved with the help of the Braess paradox .
The Braess paradox is a variant of the minority game , when minority is understood to mean that a driver “drives well” if he chooses a road that is less traveled than the equilibrium solution provides. If one generalizes to cost functions that are no longer monotonic , this statement no longer applies.
The Braess paradox is somewhat similar to the ice-cream-seller-on-the-beach problem . There a situation is also described how it is theoretically possible that a system optimum can be missed if the actors neither coordinate nor organize centrally.

literature

Dietrich Braess: About a paradox from traffic planning . (PDF; 841 kB) In: Unternehmensforschung . 12, pp. 258-268.
Katharina Belaga-Werbitzky: The Braess Paradox in Extended Wheatstone Networks with M / M / 1 Operators . ISBN 3-89959-123-2 (dissertation).
Jörg Esser: Simulation of city traffic on the basis of cellular automata . Duisburg 1997, DNB 953736350 , Chapter 8 (dissertation, University of Duisburg).

Web links

Dietrich Braess' working page with bibliography on the subject
Jane Hagstrom: Braess's Paradox Examples - Single Origin-Destination Pair
Jane Hagstrom: Braess's Paradox Examples - Multiple Origin-Destination Pairs

Individual evidence

^ Andreas Diekmann: Game theory. Rowohlt Taschenbuch Verlag, Reinbek bei Hamburg 2009, ISBN 978-3-499-55701-9 , pp. 113-122
↑ Wolfgang Blum: The expressway beckons forever. In: Süddeutsche Zeitung . January 24, 2006.
^ G. Kolata: What if they closed 42nd Street and nobody noticed? In: New York Times . December 25, 1990, p. 38.
^ J. Vidal: Heart and soul of the city In: The Guardian . November 1, 2006.
↑ K. Schön: Traffic jam? Demolish the city highway! In: urbanist magazine . February 7, 2014.
↑ C. Fisk, S. Pallotion: Empirical Evidence for Equilibrium Paradoxes With Implications for Optimal Planning Strategies. In: Transportation Research. Vol. 15A, 1981, no. 3, pp. 245-248.
^ Greg Valiant, Tim Roughgarden: Braess's paradox in large random graphs. In: Proceedings of the 7th ACM conference on Electronic commerce. Ann Arbor MI 2006.
^ Joel E. Cohen, Paul Horowitz: Paradoxical behavior of mechanical and electrical networks . In: Nature . 352, August 22, 1991, pp. 699-701, doi: 10.1038 / 352699a0 .
^ AD Irvine: How Braess' Paradox Solves Newcomb's Problem. In: International Studies in Philosophy of Science . Vol. 7, 1993, no. 2, pp. 145-164.

This version was added to the list of articles worth reading on March 9, 2006 .

[Diekmann2009-1] Andreas Diekmann: Game theory. Rowohlt Taschenbuch Verlag, Reinbek bei Hamburg 2009, ISBN 978-3-499-55701-9 , pp. 113-122

[BLUM-2] Wolfgang Blum: The expressway beckons forever. In: Süddeutsche Zeitung . January 24, 2006.

[NYT-3] G. Kolata: What if they closed 42nd Street and nobody noticed? In: New York Times . December 25, 1990, p. 38.

[Guardian-4] J. Vidal: Heart and soul of the city In: The Guardian . November 1, 2006.

[urbanist-5] K. Schön: Traffic jam? Demolish the city highway! In: urbanist magazine . February 7, 2014.

[Fisk-6] C. Fisk, S. Pallotion: Empirical Evidence for Equilibrium Paradoxes With Implications for Optimal Planning Strategies. In: Transportation Research. Vol. 15A, 1981, no. 3, pp. 245-248.

[Valiant-7] Greg Valiant, Tim Roughgarden: Braess's paradox in large random graphs. In: Proceedings of the 7th ACM conference on Electronic commerce. Ann Arbor MI 2006.

[8] Joel E. Cohen, Paul Horowitz: Paradoxical behavior of mechanical and electrical networks . In: Nature . 352, August 22, 1991, pp. 699-701, doi: 10.1038 / 352699a0 .

[Irvine-9] AD Irvine: How Braess' Paradox Solves Newcomb's Problem. In: International Studies in Philosophy of Science . Vol. 7, 1993, no. 2, pp. 145-164.