Traffic jams are something nearly everyone can relate to. While driving is ideally a communal activity, where people pay attention to each other and follow the rules of the road, most people seem to follow their whims, only occasionally within the confines of common sense. This urge to do what is best for the individual leads to headaches for the group, increasing the total amount of time everyone has to spend on the road.
In a paper set to be published in an upcoming issue of Physical Review Letters, physicists Hyejin Youn and Hawoong Jeong, along with computer scientist Micheal Gastner, look at the result of self-interested drivers traveling on both hypothetical and real-world networks. The abstract describes what happens very clearly:
Uncoordinated individuals in human society pursuing
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.
To illustrate this principle, the authors discuss a trivial example: two points A and B are connected by both a short bridge and a long freeway. Here, the total number of travelers going from A to B is constant, but the bridge is narrow and prone to congestion, while the freeway is wide and is less susceptible to traffic jams. In this setup, the ideal situation for everyone is for half the traffic to take each path. Even in this trivial example, however, what is best for everyone is not best to each person. Using their example numbers, a driver taking the freeway under ideal conditions would reduce his or her individual delay by 40 percent over taking the bridge.
But as more and more people move away from the global optimum and take the bridge, the total time involved in traveling from A to B increases and a Nash equilibrium is reached. This is the point where "no single user can make any individual gain by changing his own strategy unilaterally." In other words, no matter what route you take, you're going to be stuck in traffic. By looking at the ratio of the cost at Nash equilibrium to the equilibrium representing the global optimum, one can calculate the price of anarchy (POA)—a measure of inefficiency caused by the lack of coordination.
Imaginary bridges and freeways can only take us so far, so the authors decided to apply the analysis to the real world. They calculated the Price of Anarchy for three real-world commutes: from Harvard Square to Boston Common in Boston, from Washington Market Park to the Queens Midtown Tunnel in New York, and the trip from Borough underground station to Farringdon station in London. Using a well-established function to model traffic delays, they find that at an average traffic flow of 10,000 vehicles per hour in Boston—a typical number—the POA peaks at 1.3. This means that drivers waste 30 percent more time because they are driving with their own interests in mind rather than a group concern (not a news flash for anyone who has driven in Boston). New York and London had similar peak POA values of about 1.27 and 1.22, respectively.
To gain a better theoretical understanding of the nature of POA in networks, the team applied their methodology to various types of idealized networks. They came to the conclusion that, to improve the Price of Anarchy, you must close off various roads—something known as Braess's paradox. In the network representing Boston, the researchers find six possible road closures that would reduce the delay in the suboptimal Nash (selfish) equilibrium. A similar analysis of the London and New York networks found that there were seven and twelve roads, respectively, that could be closed to improve the overall travel time.
While still theoretical, the work has the potential to aid future urban planning. Since the obvious solution of adding more roads may actually make the problem worse, an analysis of this sort could prove invaluable in determining real-world driving conditions.
Physical Review Letters, 2008. Upcoming.