Rush hour traffic and the price of anarchy
The interests of the individual do not always coincide with the interests of the group. This statement is obvious to anyone who has ever stood in line or filled out a tax return. Sure, it would be nice if you could skip to the front of the line at the DMV, but if the DMV didn’t require you to stand in line then it would take even longer for you to receive service. There would be a chaotic jumble of people pushing toward the front counter, and as a result service would move more slowly. Requiring customers to form a queue provides better service to the group at the immediate expense of the individual, who would rather cut to the front.
This kind of reasoning lies at the heart of quantitative social science. How much should the government regulate the free markets? How strict should social laws be? In general, how different is the result of the “globally optimized” strategy from the “everyone for themselves” situation?
Answering these sorts of questions have generally been the territory of economics and game theory. But in recent years, some of the techniques and terminology usually reserved for economists has spilled over into physics. In particular, the idea of the “price of anarchy”, is beginning to be discussed in physics circles. It’s an interesting and surprising idea, and in this post I want to illustrate the meaning of the price of anarchy by discussing a simple scenario of rush hour traffic.
Going from point A to point B
Imagine a small town, where “rush hour” consists of ten cars needing to get from point A to point B. There are two ways to get from A to B: a wide, indirect highway, and a narrow, direct alley. Something like this:
The highway takes 10 minutes, but travel time on the narrow alley depends on how many cars decide to take it. If only one car travels through the alley, then travel time is 1 minute. If two cars go through they alley, then it takes 2 minutes for each of them. Three cars results in a travel time of 3 minutes, and so on.
So which road will the cars travel on? Well, none of the drivers has any reason to take the highway, knowing that it will always take at least as long as the alley. So all ten of them will drive on the alley. As a result, each of them will have a 10 minute commute.
If the local town council wanted to combat this problem, it could mandate that five of the cars must take the highway. That way, those five cars would each have a 10 minute commute, but the remaining five could take the alley and have only a 5 minute commute. The average commute time would then be 7.5 minutes — a clear improvement over the “everyone for themselves” situation. However, as soon as the town council repealed its rule, the five cars on the highway would go back to taking the alley, knowing that their commute time will go down. Without government intervention, we go back to everyone having a 10 minute commute.
So in this example, the “price of anarchy” is 2.5 minutes, or 33% (of the global optimum 7.5 minutes).
Point A to point B, by way of point C
In the previous example, we saw how the local government could improve the average transit time, but something about it still seemed unfair. Some of the drivers (the ones forced to use the highway) were forcibly put at a disadvantage. It seems like they should have the right to a commute as short as that of their fellow drivers. Sure, forcing them to take the highway may have improved the global optimum, but it came at their expense.
But it doesn’t always work that way. Sometimes the global optimum can involve an improvement for every individual, without anyone losing out.
Consider a different town, where now ten drivers need to go from point A to point B by way of wide highways and narrow alleys. Now, however, there is a midpoint, which we’ll call point C. Points A and C are connected by one highway and one alley, and similarly C is connected to B by one highway and one alley. Like this:Just like in the last case, there is no reason for anyone to take the highways: they are always as long or longer than the alleys. So all ten cars will drive on the alley from A to C and from C to B. And because of the resulting congestion, everyone will have a twenty minute commute.
So what should the government do to improve traffic? Easy: close down the exit at point C. Force everyone to choose between two options: the highway from A to C and the alley from C to B (top roads) or the alley from A to C and the highway from C to B (bottom roads). Then, drivers will have the choice of two completely identical roads to travel on from A to B, and they will split equally between the two. As a result, everyone will have a 15 minute commute (10 minutes on a highway and 5 minutes on an alley).
So in this example, the price of anarchy is 5 minutes, or 33%. What’s more, there are no losers: everyone has an equally short drive. And all the government had to do was close a highway exit.
Lest you think this was a purely academic exercise
Over the last few years New York City has closed down large portions of 42nd Street. Rather than causing terrible gridlock, the change has actually improved traffic.
The opening of a new road in Stuttgart, Germany caused traffic to get significantly worse. Eventually the road was torn up, and traffic returned to its normal state.
There are more examples ; they are apparently not uncommon. I attended a talk at the American Physical Society meeting in 2007 that suggested traffic in the Boston area would improve if they closed down Beacon Street. This phenomenon (closing roads leads to improved traffic) is usually called Braess’s Paradox, and it is starting to be tested more and more as large cities shut down roads in the hope of improving gridlock issues.
In the next post I’ll explore the implications of a price of anarchy analysis for basketball strategy. In particular, I think it’s possible to explain one of the most infamous observations in professional sports: the Ewing Theory.