Braess' Paradox

Figure 1: An Example Of Braess' Paradox

Braess' paradox arises in transport economics, a field for applied research in economics. I was inspired by the example in Fujishige et al. (2017) for the example in this post. Under Braess' paradox, an improvement to a transport network, and thus an increase in the number of choices available to users of the network, results in decrease performance. In reliability engineering, one says such a transport network is not a coherent system.

A transport network, for a single mode (for example, air, rail, road, or water) can be specified by:

• A network, where a network consists of links between nodes. Links can be one-way or two way.
• A cost for traversing each link. The cost can be a function of the demand (that is, the amount of traffic traversing that link). Cost can have a stochastic component, such as a (perceived) standard deviation for the distribution of the time to traverse a link.
• Demands on the network, as specified by source nodes for users and the destination of each user.
• Objective functions for the users, such as the minimization of trip time or the maximization of the probability that total trip time will not exceed a given maximization. The probability for the latter objective function is known as trip reliability.

In my example (Figure 1), two road networks are specified. The network on the right differs from the one on the left in that an additional road, between nodes A and B has been added. All links are two ways. The cost for each link is specified as the number of minutes needed to travel across the link, where two links have a cost that depends on the traffic, thus modeling the effect of congestion. The parameters X_SA and X_SA denote the number of vehicles traversing the respective links. Thus, the number of minutes to travel across these links is proportional to the amount of traffic, with a proportionality constant of unity. The demand is assumed to be unchanged by the addition of the new link. One hundred users want to drive their vehicles from the source node S to the node destination node D. Each driver wants to minimize their total trip time.

Table 1: Costs for Each Link

Link	Cost
SA	XSA Minutes
SB	110 Minutes
AD	110 Minutes
BD	XBD Minutes
AB	Either infinity or 5 Minutes

Each user has a choice of two routes, ignoring purposeless cycles, in the network on the left. These routes pass through nodes S, A, and D, or through nodes S, B, and D. The addition of the "short-cut" provides two additional routes, through nodes S, A, B, and D, and through nodes S, B, A, and D.

My method of analysis is an equilibrium assignment of users to routes. John G. Waldrop created this notion of equilibrium, as I understand it. It is an application of Nash equilibrium to transport economics. Bell and Iida call this equilibrium a Deterministic User Equilibrium. The equilibrium assignments in the example are shown as green lines in the figure. On the left, 50 drivers choose each of the two routes, and each driver's trip requires 160 minutes. On the right, all 100 drivers choose the route S, A, B, and D. Each driver takes 205 minutes to complete their trip.

To see why these are equilibria, consider what happens if a single driver deviates from the equilibrium assignment. For example, suppose a driver of the left who has previously chosen the route S, A, and D selects the route S, B, D. The cost for the congested link BD will rise from 50 minutes to 51 minutes, and his total trip time will now be 161 minutes, an increase from the previous 160 minutes. In this model, a driven will not choose to be worse off in this way. Symmetrically, a driver assigned to the route S, B, and D will not decide to switch to the route S, A, and D.

Once the shortcut, AB, has been added, the analysis requires tabulating a few more trips. Suppose a driver swithes from the equilibrium route on the right to the route:

• S, A, and D or S, B, and D: In each case, the new route includes one congested link which all 100 drivers still traverse. The total trip time is 210 minutes, an undesirable increase over the equilibrium trip time of 205 minutes.
• S, B, A, and D: All links in this route have a fixed cost. Total trip time is 225 minutes, also an increase over the equilibrium trip time.

So here is a (long-established) case in which improvements to a transport network result in optimizing individuals becoming worse off.

References

• Satoru Fujishige, Michel X. Goemans, Tobias Harks, Britta Peis, and Rico Zenklusen (2017). Matroids are immune to Braess' Paradox. Mathematics of Operation Research. V. 42, Iss. 3: 745-761.
• M. G. H. Bell and Y. Iida (1997). Transportation Network Analysis. New York: John Wiley & Sons.