The Price of Anarchy in Transportation Networks: E?ciency and Optimality Control
Hyejin Youn and Hawoong Jeong?
Department of Physics, Korea Advanced Institute of Science and Technology, Daejeon 305-701, Korea
Michael T. Gastner
Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, USA and Department of Computer Science, University of New Mexico, Albuquerque, NM 87131, USA Uncoordinated individuals in human society pursuing their personally optimal strategies do not always achieve the social optimum, the most bene?cial 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 tra?c conditions. We analyze various complex networks and discuss the possibility of similar paradoxes in physics.
PACS numbers: 89.75.Hc, 87.23.Ge, 89.75.Fb, 89.65.-s, 89.65.Gh, 02.50.Le
arXiv:0712.1598v4 [physics.soc-ph] 7 Aug 2008
Many real-world transportation systems in human societies are characterized by networked structures and complex agents interacting on these networks . Understanding the agents’ behaviors has important consequences for the optimal design and control of, for example, the Internet, peer-to-peer, or vehicle networks . In fact, optimality has long been a key principle in science. In particular, many branches of physics are governed by principles of least action or minimum energy in the same way that maximizing utility functions is crucial in economics. For example, the ?ow of currents in a resistor network can be derived by minimizing the energy dissipation. One might expect that tra?c ?ows in transportation networks follow a similar optimization principle. It is indeed reasonable to assume that humans opt for the strategies that maximize their personal utility. However, this does not mean that ?ows in transportation networks minimize the cost for all users as is sometimes assumed . On the contrary, we will demonstrate that the ?ows can in reality still be far from optimal even if all individuals search for the quickest paths and if complete information about the network and other users’ behaviors is available. Thus, tra?c networks can be inherently ine?cient – a fact rarely investigated in previous work on tra?c ?ows . In this paper, we investigate decentralized transportation networks where each directed link from node i to j is associated with a delay lij , the time needed to travel along the link. In most real networks, delays depend noticeably on the ?ow , i.e., the number of downloads, vehicles, etc. per unit time. For example, a single vehicle easily moves at the permitted speed limit on an empty road, yet slows down if too many vehicles share the same road. Thus, the choices of some users can cause delays for others and possibly con?ict with everyone’s goal to reduce the overall delay in the network. As a game-theoretic consequence, the best options for indi-
vidual users form a Nash equilibrium, not necessarily a social optimum. Consider, for instance, the simple network depicted in Fig. 1(a) . Suppose that there is a constant ?ow of travellers F between the nodes s and t which are connected by two di?erent types of links: a short but narrow bridge A where the e?ective speed becomes slower as more cars travel on it, and a long but broad multilane freeway B where congestion e?ects are negligible. Suppose the delay on link A is proportional to the ?ow, lA (fA ) = fA , while the delay on B is ?ow-independent, lB (fB ) = 10, where fA(B) is the ?ow on link A(B). The total time spent by all users is given by the “cost function” C(fA ) = lA (fA ) · fA + lB (fB ) · fB where the ?ow on B is equal to fB = F ? fA . It is easily veri?ed that C attains its minimum for fA = 5 if the total ?ow satis?es F ≥ 5. If F = 10, for example, each link should be taken by exactly half of the users, resulting in C = 75 (Fig. 1b). In this social optimum, every user on link B could reduce his delay from 10 to 6 by switching paths, which poses a social dilemma: as individuals, users would like to reduce their own delays, but this reduction comes at an additional cost to the entire group. In our example, as long as lA = lB , there will be an incentive for the users experiencing longer delays to shift to another link. If all users decide to put their own interests ?rst, the ?ow will be in a Nash equilibrium where no single user can make any individual gain by changing his own strategy unilaterally. All users take the link A, as shown in Fig. 1(c), at the total cost of C = 100. Experimental tests indicate that human subjects approach the problem of ?nding paths in a network from this latter self-interested perspective, rather than from the former altruistic point of view . This behavior, known as Wardrop’s principle, is observed even if, as in our example, not a single user experiences a shorter travel time in this Nash equilibrium than in the social optimum. Furthermore, if all functions
2 of anarchy (PoA) is de?ned as the ratio of the total cost of the Nash equilibrium to the total cost of the social optimum  indicating the ine?ciency of decentralization; for example in Fig. 1, PoA = 100/75 = 4/3, or in general PoA =
N N lij (fij E ) · fij E . SO SO lij (fij ) · fij
FIG. 1: (color) Illustration of the price of anarchy. (a) Suppose F = 10 users travel per unit time from s to t. (b) The socially optimal ?ow sends ?ve users along each link, thus the total cost is C = 75. (c) In the Nash equilibrium with fA = 10 and fB = 0, C = 100 is higher than in (b).
lij (fij ) are strictly increasing (as in most realistic cases) and the ?ows fij are continuous, one can prove that there is always exactly one Nash equilibrium . Although di?erences between Nash equilibria and social optima occur frequently in social science, only few papers have studied the di?erence between optimal and actual system performance in real transportation networks . To shed light on this issue, we have analyzed Boston’s road network shown in Fig. 2(a). The 246 directed links in our network are segments of principal roads, and their intersections form 88 nodes. Delays are assumed to follow the Bureau of Public Roads (BPR) function widely used in civil engineering, lij =
. Here dij is the distance of the link
between i and j, vij the speed limit (35 mph on all links, for simplicity), fij the ?ow, and pij the capacity of the road segment. The parameters α and β have been ?tted to empirical data  as α = 0.2 and β = 10, i.e., the delays increase very steeply for large tra?c volumes. Capacity is de?ned as the tra?c volume at “level of service E” which is approximately 2000 vehicles per hour multiplied by the number of lanes . We used Google Maps to identify the principal roads, measure the distances dij , and count the number of lanes for each direction. Next we have calculated the ?ows fij for various total tra?c volumes F from Harvard Square to Boston SO Common. The socially optimal ?ows fij are determined by minimizing the cost to society per unit time C = link(i,j) lij (fij )fij . This optimization problem, satisfying ?ow conservation at each intersection, can be solved with standard convex minimum cost ?ow algorithms . For the Nash equilibrium, we can use the N fact that the equilibrium ?ows fij E minimize the objective function  C =
link(i,j) fij ′ ′ 0 lij (f )df .
4/3 is in fact the upper bound for the PoA in networks with a?ne delays, i.e., β = 1 [6, 12]. For larger β, the theoretical maximum is higher, but here we are more interested in typical than in worst-case network topologies. For β = 10, Fig. 3(a) shows the PoA versus the total traf?c volume F for Boston’s roads. Except for very small F , the Nash equilibrium cost is higher than the social optimum so that PoA > 1. The worst ratio occurs for a tra?c volume of 10, 000 vehicles per hour – a quite realistic ?ow, see  – where PoA ≈ 1.30, i.e., individuals waste 30% of their travel time for not being coordinated. To what extent are properties of the PoA observed in Boston’s road network characteristic of networks with ?ow-dependent costs? Among road networks, the results appear to be typical as suggested by an analysis of the road networks of London and New York in Fig. 2. London’s network consists of 82 intersections and 217 links marked as principal roads by Google Maps. We ?nd that the PoA can increase up to 24% for trips between the Borough and the Farringdon underground stations (Fig. 3(a) inset). Similar results also hold for New York, consisting of 125 intersections and 319 streets. The inset of Fig. 3(a) shows that the PoA can be as high as 28% when 12,000 vehicles per hour travel from Washington Market Park to Queens Midtown Tunnel. The results remain qualitatively similar for di?erent sets of sources and destinations suggesting that a high PoA can generally become a serious problem. To gain further theoretical insight, we also constructed four ensembles of bidirectional model networks with distinct underlying structures : a simple onedimensional lattice with connections up to the thirdnearest neighbors and periodic boundary conditions, Erd?s-R?nyi random graphs with links between rano e domly drawn pairs of nodes, small-world networks with a rewiring probability 0.1, and Barab?si-Albert networks a with broad degree distributions. All the networks contain 100 nodes and have an average degree of 6. Every link between nodes i and j has a delay of the form lij = aij fij + bij , where aij = aji is a random integer equal to 1, 2, or 3, and bij = bji between 1 and 100. This a?ne cost function captures essential properties of links in important physical networks. In electric circuits, for example, the ?ow fij is an electric current and the delay lij can be interpreted as the voltage di?erence between i and j. An a?ne current-voltage characteristic occurs in circuits with a combination of Ohmic resistors (resistances aij ) and Zener diodes (breakdown voltages
FIG. 2: (color) 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: no change, red: 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.”
bij ). Further examples with a?ne cost functions include mechanical, hydraulic, and thermal networks . For each model network, we go through every pair of nodes to calculate the PoA for various total ?ows F . Then the results are averaged over 50 networks to ?nd the mean PoA(F ) for each ensemble as plotted in Fig. 3(b). After averaging over many pairs, there are no longer multiple local maxima as in Fig. 3(a). Instead, we ?nd unimodal functions for all ensembles with a steep increase for small F and a long tail for large ?ows. The qualitative behavior can be understood as follows. The social optimum minimizes C = (aij fij 2 + bij fij ) whereas the ?ow in the Nash equilibrium minimizes C = ( 1 aij fij 2 + bij fij ). In the limit F → 0, both ob2 jective functions become identical and, therefore, PoA → 1. For F → ∞, the quadratic terms in the sums dominate, hence C/C → 2, i.e., both objective functions are minimized by the same asymptotic ?ow pattern fij /F and PoA again approaches 1. The maximum PoA occurs roughly where the quadratic and linear terms in the objective functions are comparable, i.e., aij fij ≈ bij for paths with positive ?ow. Ignoring correlations between aij and fij , we have fij ≈ bij / aij . Since F = c fij where c is a factor bigger than but of the order of 1, we estimate the maximum PoA to be at Fmax ≈ c bij / aij . In our example, aij = 2 and bij = 50.5, so we predict Fmax to be bigger than but of the order of 25. Numerically, we ?nd the maxima for our four ensembles to be between 30 and 60 in good agreement with our estimate. Barab?si-Albert networks tend to have the lowest a PoA(F ) and small-world networks the highest, but the statistical dependence between PoA and F is strikingly similar among all ensembles. Knowing the PoA is important, but it is even more valuable to discover a proper method to reduce it. In a road network, one could charge drivers toll fees to stim-
1.3 1.2 1.1 1.0
1.3 1.2 1.1 1 0
London New York
Vehicles per hour
< PoA >
Number of source-sink pairs 1 5 10 2 400 200
Regular lattice Erdos-Renyi Small world Barabasi-Albert
Traffic volume F
FIG. 3: (color) The price of anarchy (PoA), as a function of the tra?c volume F . (a) In Boston’s road network for journeys from Harvard Square to Boston Common with BPR delays with α = 0.2, β = 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 a?ne delays. All networks have 100 nodes and 300 undirected links. The error bars represent one standard deviation in the PoA-distribution. Inset: the PoA in regular lattices with multiple random sources and sinks (“multi-commodity ?ows”) averaged over 100 to 400 networks. Each pair contributes equally to F .
ulate a more cooperative behavior, but that strategy has problems of its own. For example, one could charge a fee for using each link equal to the “marginal cost” fij · lij ′ (fij ) so that the new Nash ?ow becomes equal to the social optimum. Unfortunately, if collected taxes are not returned to the users, such marginal cost taxes do not improve the cost of the Nash equilibrium in the
4 case of BPR delays . However, as we have learned from Fig. 3(b), we can change the PoA by modifying the underlying network structure. For instance, closing roads to car tra?c is relatively easy to implement and is, moreover, equally e?ective for everybody. One might expect that closing roads only leads to increased congestion. However, contrary to common intuition, Braess’s paradox suggests that road closures can sometimes reduce travel delays . We investigated whether this apparent contradiction occurs in the road networks of Fig. 2. In the case of Boston’s roads, we set F =10,000 between Harvard Square and Boston Common which is the ?ow where the PoA reaches its maximum, i.e., where reducing the travel time is most desirable. We then compare the costs of the Nash ?ow on the original network with those on networks where one of the 246 streets is closed to tra?c. In most cases, the cost increases when one street is blocked, as intuitively expected. Nonetheless, there are six connections which, if one is removed, decrease the delay in the Nash equilibrium, shown as dotted lines in Fig. 2. If all drivers ideally cooperated to reach the social optimum, these roads could be helpful; otherwise it is better to close these streets. Similar results are also found in the other two networks: there are seven links causing Braess’s paradox in London (F =10,000) and twelve in New York (F =18,000), see Fig. 2(b) and (c). Of course, the identi?ed roads may not always be bad because a different set of start and end nodes can change the number and location of links triggering Braess’s paradox. However, their existence under the investigated conditions suggests that Braess’s paradox is more than an academic curiosity [17, 18] or an anecdote with only sketchy empirical evidence . Nevertheless, more work is needed to generalize the presented results, for example for multiple sources and destinations. As a ?rst step, we have calculated the PoA for such multi-commodity ?ows (Fig. 3(b) inset). Braess’s paradox exists because the social optimum and the Nash equilibrium react in di?erent ways to changes in the network. After a link is closed, the socially optimal travel time must be at least as long as before. However, there is no a priori reason why severing a link could not improve the Nash travel time. By the same argument, adding new links can potentially create more delay in the Nash equilibrium. Hence, a target for future policies in transportation networks is to prevent unintended delays caused by, ironically, well-intentioned new constructions that form a disadvantageous Nash ?ow. Because convex costs such as the BPR function are common in economics, Braess’s paradox is presumably also frequent outside vehicle transportation networks. In fact, we do not need game theory to ?nd this paradox. It also occurs in physical networks where equilibrium principles can drive the network away from optimality. For example, currents in electric circuits do not always minimize the dissipated energy, but instead satisfy Kirchho?’s laws. As a consequence, removing wires can sometimes counter-intuitively increase the conductance . Although electrons in a circuit, unlike drivers in a road network, do not act sel?shly, the equilibrium conditions (Kirchho?’s laws and Wardrop’s principle) are in fact closely related. Further studies of the price of anarchy and Braess’s paradox might therefore lead to signi?cantly improved ?ows in a number of important applications. We thank Eric Smith, Yueyue Fan, D.-H. Kim, and H.-K. Lee for helpful discussion. H. Y. acknowledges the motivation from the study group at the NECSI summer school. This work was supported by KOSEF through the grant No. R17-2007-073-01001-0 and is dedicated to the memory of Charles VanBoven.
? Electronic address: firstname.lastname@example.org  G. Kossinets and D. J. Watts, Science 311, 88 (2006).  M. Buchanan, Nature 447, 39 (2007).  M. T. Gastner and M. E. J. Newman, Phys. Rev. E 74, 016117 (2006).  L. Qiu et al., Proc. of ACM SIGCOMM, 151 (2003); O. Jahn et. al., Oper. Res. 53, 600-616 (2005)  D. M. Levinson et. al., Transport Reviews 18, 215 (1998).  T. Roughgarden, Sel?sh Routing and the Price of Anarchy (MIT Press, Cambridge, 2005).  R. Selten et al., Games and Econ. Behav. 58, 394 (2007); A. Rapoport et al., Games and Econ. Behav., in press.  R. Singh, 7th TRB Conference on the Application of Transportation Planning Methods, 340 (1999).  R. F. Roess and W. R. McShane, ITE Journal 57, 27 (1987).  R. K. Ahuja et. al., Network Flows: Theory, Algorithms and Applications (Prentice-Hall, Englewood Cli?s)  C. Papadimitriou, 33rd Annual ACM Symposium on Theory of Computing 749 (2001).  E. J. Friedman, 43rd IEEE Conference on Decision and Control, 4667 (2004); J. R. Correa et. al., Games and Econ. Behav., Forthcoming (2008).  Data from Massachusetts Highway Department, URL: http://www.mhd.state.ma.us/  P. Erd?s, A. R?nyi, Publ. Math. Debrecen 6, 290 (1959); o e D. J. Watts, S. H. Strogatz, Nature 393, 440 (1998); A.-L. Barab?si, R. Albert, Science 286, 509 (1999). a  J. E. Cohen, P. Horowitz, Nature 352, 699 (1991); C. M. Penchina, L. J. Penchina, Am. J. Phys. 71, 479 (2003).  R. Cole et. al., J. Comp. Sys. Sc. 72, 444 (2006); P. Maille, N. E. Stier-Moses, Columbia Working Paper DRO-2007-04 (2007)  D. Braess, Unternehmensforschung 12, 258 (1968).  R. Steinberg, W. I. Zangwill, Transportation Science 17, 301 (1983); G. Valiant, T. Roughgarden, 7th ACM conference on Electronic commerce, 296 (2006).  W. Kn¨del, Graphentheoretische Methoden und ihre Ano wendungen (Springer, Heidelberg) 1969; C. Fisk and S. Pallottino, Transportation Research A 15, 245 (1981); G. Kolata, What if they closed 42nd street and nobody noticed? New York Times, 38 (December 25, 1990).