Price of Anarchy in Transportation Networks: Efficiency and Optimality Control

Uncoordinated individuals in human society pursuing their personally optimal strategies do not always achieve the social optimum, the most beneficial state to the society as a whole. Instead, strategies form Nash equilibria which are often socially suboptimal. Society, therefore, has to pay a price of anarchy for the lack of coordination among its members. Here we assess this price of anarchy by analyzing the travel times in road networks of several major cities. Our simulation shows that uncoordinated drivers possibly waste a considerable amount of their travel time. Counterintuitively, simply blocking certain streets can partially improve the traffic conditions. We analyze various complex networks and discuss the possibility of similar paradoxes in physics.

Figure 1

Illustration of the price of anarchy. (a) Suppose $F=10$ users travel per unit time from $s$ to $t$. (b) The socially optimal flow sends five users along each link, thus the total cost is $\mathcal{C}=75$. (c) In the Nash equilibrium with $f_A=10$ and $f_B=0$, $\mathcal{C}=100$ is higher than in (b).

Figure 2

Networks of principal roads (both solid and dotted lines; the thickness represents the number of lanes). (a) Boston-Cambridge area, (b) London, UK, and (c) New York City. The color of each link indicates the additional travel time needed in the Nash equilibrium if that link is cut [blue (dark gray): no change, red (medium gray): more than 60 seconds additional delay]. Black dotted lines denote links whose removal reduces the travel time, i.e., allowing drivers to use these streets in fact creates additional congestion. This counter-intuitive phenomenon is called “Braess’s paradox.”

Figure 3

The price of anarchy (POA), as a function of the traffic volume $F$. (a) In Boston’s road network for journeys from Harvard Square to Boston Common with BPR delays with $\alpha =0.2$, $\beta =10$. Inset: The POA in London from Borough to Farringdon, and in New York from Washington Market Park to Queens Midtown Tunnel. (b) The POA in ensembles of model networks with affine delays. The error bars represent 1 standard deviation in the POA distribution. Inset: The POA in regular lattices with multiple random sources and sinks (“multicommodity flows”) averaged over 100 to 400 networks. Each pair contributes equally to $F$.