Braess's paradox

The Braess paradox is an illustration of the fact that an additional policy option under the assumption of rational individual decisions can lead to a deterioration of the situation for all. The paradox was published by the German mathematician Dietrich Braess 1968.

Braess ' original work shows a paradoxical situation in which the construction of an additional road (ie an increase in capacity ) leads to the fact that with constant traffic, the travel time for all motorists is increased ( that is, the capacity of the network is reduced). This is based on the assumption that any road user selects his route so that there is no other option with a shorter travel time for him.

Occasionally, the paradox is discussed at Selfish routers. In addition, the Braess paradox is a proof that the rational optimization of individual interests in the context of a publicly provided good can lead to a suboptimal for each individual state.

Example

As an example of the occurrence of Braess paradox here a road network is selected. Extending this road network to another road, it will be extended for each driver, the driving time. The example is Braess ' original work taken from "On a paradox of traffic planning " from the year 1968.

Initial situation

The four cities A, B, C and D are connected by four lines. Both from A to C and B to D in each case runs a highway. The highways are well developed, so that the travel time depends only slightly on the traffic density. However, the highways have to wind around an obstacle and are therefore quite long. In a traffic density ( in thousand cars per hour ), the corresponding driving time per driver is

The cities A and B are the same as the cities C and D connected by a highway. These roads are indeed shorter than the freeways, but expanded much worse. Therefore, the driving time per driver depends essentially only on the traffic volume from:

All motorists want to drive from A to D, each driver chooses the fastest path for themselves. It turns a so-called Nash equilibrium, in which half of the driver used the route through city B and the other half goes over town C. In 6000 hourly drivers thus on every trip 3000 cars and all drivers have a journey time of 83 minutes.

Scenario after the construction of additional road

The responsible politicians decide as shown in Figure 3, after some time to build a tunnel through the mountain between cities B and C. This new line can only be in the direction B → C be driven - the easy viewing for the occurrence of the paradox but not relevant.

On this additional route applies to the travel time

This distance is so short and has a high capacity.

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

• Select 2000 driver the route ABD
• Select 2000 driver the route ACD
• Select 2000 driver the route ABCD
• Thus is located on the country roads, a current of 4,000 vehicles per hour on the highways and the new line, a current of 2,000 vehicles per hour.

The journey is in this case for all drivers equal to 92 minutes and thus nine minutes longer than without the new line.

Illustration

Clearly seen is in each case for the drivers which use one of motorways, represents a necessarily to be used as a road section where the speed bottleneck of traffic flow depends strongly on the number of road users, or is reduced by this. The new road now causes but that some drivers use the road at full length and thus block them separately - they use in addition to the new line now both road sections and not just one, as the motorway users. Now the bottleneck situation has become clearer, as well as the motorway users need significantly longer for their inevitably used road section. In the example can not cause compensatory time advantage so that the corresponding traffic congestion on the high-capacity highways.

Discussion

One might suspect that some of the drivers by another route elections would create a better situation. However, this is not the way. A driver who - unless the described equilibrium exists - the next day decides otherwise caused by its decision that the journey time on the route for which he chooses - and for himself - extended. This state corresponds to a Nash equilibrium. At its previous day's route, however, the journey time will be reduced for all others. This of course is not a criterion that moves a driver to change its route. For simplicity, 1,000 drivers change their route following numerical example compared with the balance. If you change the behavior of an individual driver, the changes would be small, however, went - because of the monotonic (linear) function of the travel time from the river - always in the same direction.

• Select 3000 driver the route ABD and need 93 minutes.
• Select 2000 driver the route ACD and need 82 minutes.
• Select 1000 driver the route ABCD and need 81 minutes.

• Select 3000 driver the route ABD and need 103 minutes.
• Select 1000 driver the route ACD and need 81 minutes.
• Select 2000 driver the route ABCD and need 92 minutes.

• Select 2000 driver the route ABD and need 82 minutes.
• Select 3000 driver the route ACD and need 93 minutes.
• Select 1000 driver the route ABCD and need 81 minutes.

• Select 2000 driver the route ABD and need 102 minutes.
• Select 1000 driver the route ACD and need 91 minutes.
• Select 3000 driver the route ABCD and need 103 minutes.

Note that the travel time is on all routes with 3000 riders per hour for longer than 92 minutes.

Would arrange to meet all the drivers to ignore the new line and to behave as they did when it did not exist this, the travel time for all road users would be 83 minutes again. However, the temptation would be great, then use it free but the only new line and so to reduce their own journey time of 83 minutes to 70 minutes. The usual human behavior, then, is to emulate the violator. The system thus tends again to the above described equilibrium. As a solution to this dilemma has no other option than the new line centrally planned to tear down again, or the segments AB and CD to double their capacity.

Occurrence of Braess paradox in the real world

There are examples that the Braess paradox is not just a theoretical construct. In 1969 in Stuttgart, the opening of a new road to a worsening in the vicinity of the castle square of the flow of traffic. Also in New York, the opposite phenomenon was observed in 1990. Blocking 42nd Street helped to reduce congestion in the area. Further empirical reports on the occurrence of the paradox are from the streets of Winnipeg. In Neckarsulm, improved traffic flow, often after a closed railroad crossing was completely abolished. The usefulness was demonstrated when he had to be temporarily closed due to a construction site. Theoretical considerations can also expect that the Braess paradox occurs frequently in random networks. Many real-world networks are random networks.

Mechanical analogue

There is an analogy - if not in the narrow sense of a mathematical mappability - to the Braess paradox in mechanics:

A weight ( weight of 6 N) is suspended by two resilient strands. The first is the top of a weak yellow spring ( between points A and B) and down from a strong blue spring ( between B and D), the second string up from a strong blue spring ( between A and C) and down from a faint yellow spring ( between C and D). The Yellow Springs have a function of the force acting on it, the length, the length of springs blue. The weight is divided between the suspensions ABD and ACD, so that both suspensions, a force of 3 N. The length of the springs is then

The entire suspension is 83 cm long.

Now, if the points B and C with an additional spring connected ( in the sketch red), is the length, one could assume that this spring absorbs some of the energy, thereby relieving the other springs so that lifts the weight. In fact, however, only the blue springs are relieved and it pollutes the yellow feathers stronger. Since the yellow feathers are weaker, they are more extended than the blue shorten. This means that the weight is lowered. In equilibrium, act on the blue feathers and the red spring forces of each 2 N, the yellow feathers forces of each 4 N, so that there are the following lengths:

The total length of the suspension thus enlarged to 92 cm.

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

Relationship with other problems

• With the help of the Braess paradox can be a variant of Newcomb's problem to solve.
• The Braess paradox is a variation of the minority game when minority is understood that a driver is "good moves " when choosing a road that is less traveled, as provided for in the equilibrium solution. To generalize on cost functions that are not monotone, this statement is no longer true.
• The Braess paradox has a certain resemblance to the ice cream man - on - beach - problem. There is also a situation is described, as it is theoretically possible that a system optimum can be missed if not deny doer or centrally organized.
• The Prisoner's Dilemma is another illustration of a Nash equilibrium.

Swell