Braess' Paradox : A fascinating, yet counter-intuitive result
Postulated in 1968 by German mathematician Dietrich Braess, Braess’ paradox is one of the most counter-intuitive results in network games. Loosely, it postulates that adding a highway to a network might not ease traffic at all, rather it might lead to higher congestion. Mind = blown, right? Let’s check out the math. But first, let’s get a few definitions out of the way.
Let S be the source node and D be the destination node. Suppose there are k different paths connecting S and D through which traffic can flow.
Flow vector : A flow vector f denotes the fraction of total traffic passing through each of the k different roads connecting source with destination.
Equilibrium flow : A flow vector f is called a flow in equilibrium if the cost of traversal along all k paths is the same, so there is no incentive for traffic to jump from one path to another.
Optimal flow : A flow vector f is called an optimal flow if it minimizes the average cost of traversal from source S to destination D.
Fig.1 shows the network of roads connecting source and destination. There are 2 paths from S to D, namely S-U-D and S-V-D. The cost along paths S-U and V-D are proportional to the traffic along those paths while cost along other paths are fixed. In a network, cost can mean time required for transit. Let’s try to find the equilibrium and optimal flows for above network.
In an equilibrium flow, cost along both paths must be the same. Let the fraction of traffic along paths S-U-D and S-V-D be a and (1-a) respectively. Therefore, a + 1 = 1 + (1-a) which implies that a* = 0.5. Which means an equilibrium flow for the above network is (0.5, 0.5).
The average cost of traversal through this network is as follows:
C_avg = a(1+a) + (1-a)(2-a)
The value of a which minimizes C_avg comes out to be 0.5 again. So for this network, the equilibrium and optimal flows are the same. The minimum average cost comes out to be 3/2 units. Let’s kick things up a notch now. Consider the following network where an extra link exists between nodes U and V. Let this new link be a zero-cost path.
There are now 3 possible paths of traversal from S to D.
- Path S-U-D ( traffic contribution- a)
- Path S-V-D (traffic contribution- b)
- Path S-U-V-D (traffic contribution- (1-a-b))
We recompute the equilibrium and optimal flows in the same way as above. The equilibrium flow comes out to be (0, 0, 1). All traffic jumps to the path S-U-V-D. This was expected, right? But what is the cost for traversing this path ? Turns out, 2 units. The optimal flow still remains the same (0.5, 0.5, 0) which means that the minimum average cost of traversal is 3/2 units.
Thus we have arrived at a scenario where the equilibrium and optimal flows are different. All traffic would choose to flow through the new link, without realizing that it is sub-optimal.
Braess’ paradox captures a very intriguing aspect of human behavior. A key takeaway from here is that a system in which each individual is only looking out for himself, might go towards anarchy making everybody worse off in the end. We say that the Price-of-Anarchy of such a system is very high. But that is a discussion for another day.
Cheers!