Though often designed to maximize flow, in some contexts, networks can suffer from Braess' Paradox, where additional links actually reduce network flow. Braess' Paradox occurs in networks subject to congestion and where individuals can make selfish choices. Individuals flowing through a network are encouraged to find the optimum path to reduce travel time, achieving a Nash equilibrium, or a situation where no individual can do better. These selfish optima can reduce overall flow through a network because the individual equilibrium is not always the optimal solution for the population.

Dietrich Braess first discovered this paradox in 1968 while examining traffic congestion on a network of roads. Braess, while modeling traffic in Germany, noticed that closing a road could reduce travel time for everyone. The inverse is also true: adding or improving a road in the network could increase travel time for all individuals.

In this example, drivers on the network are attempting to travel from A to D. Edges A->B and C->D, described by T/100, are subject to congestion; as the number of drivers, T, increases, travel time over that edge also increases. On the other hand, edges B->D and A->C have static costs of 45 minutes. As drivers are added to the network, they choose the optimal path A->D. In this original network, that results in drivers alternating between taking the upper route through B or taking the lower route through C.

Above, we show that with the original network, an equilibrium occurs when traffic is evenly distributed between the upper and lower paths from A to D. Each driver spends 65 minutes to travel from A to D. But, when a shortcut edge is added from B to C, it is in each driver's self-interest to take the shortcut. This shortcut negatively impacts the entire population; once one driver takes the shortcut, it adds a little bit to the travel time for everyone else traveling on C->D.

As drivers advantageously switch from their original paths to take the shortcut, they overload the edges subject to congestion and slow everyone down.

To examine the impact of adding the shortcut, we solve for the Nash equilibrium of the new network. We find that when every driver chooses to take the shortcut, the flow through the network suffers. Instead of each driver traveling through the network in 65 minutes as we had in the original network, the shortcut creates a situation where each individual spends 80 minutes of travel time. In the Nash equilibrium, it is not advantageous for an individual to not take the shortcut; switching back to their original route (A->B->D or A->C->D) would cost 85 minutes instead of their current cost of 80 minutes. As a result, everyone has incentive to take the shortcut.

Glossary

• Nash equilibrium: a game theoretic stable state where no individual can improve their situation. Also called the individual equilibrium or selfish equilibrium.
• Potential energy: a method of tracking the impact individuals have when switching edges
• Social equilibrium: the state where the outcome is best for all participants. Also called the global optimum.
• Traffic network: a directed graph consisting of vertices (intersections of roads) and edges (roads)
• Traffic pattern: a set of network edges and flows.
• Travel cost: how long it takes an individual to travel on an edge or through a network given that edge has flow of x. Travel cost is given by the linear equation T = ax+b where a,b > 0 and x is the current number of drivers.