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:
car not drawn to scale
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.
Trackbacks
- The dish » Blog Archive » New quiz, chat, etc.
- How We Drive, the Blog of Tom Vanderbilt’s Traffic » Blog Archive » The Price of Anarchy
- Braess’s Paradox and “The Ewing Theory” « Gravity and Levity
- EcoStreets » Blog Archive » Three reasons we don’t understand traffic
- Three reasons we don’t understand traffic « Gravity and Levity
- Does your culture really affect the gender distribution? « Gravity and Levity
- O preço da anarquia | Calebe Lee
- Opportunity Costs « justPatrickBlog
- The price of anarchy / The magic of roundabouts « Thomas the Think Engine
Gravity and Levity 
Two comments:
1. ” There would be a chaotic jumble of people pushing toward the front counter, and as a result service would move more slowly.”
Maybe; it’s not really a network problem. I do wonder whether, in Latin countries, their jumbles move as quickly as our queues. I suspect they do, at least for everyone except the untutored tourists, all things being equal of course.
B. The classic example for real life thinking on Braess’ Paradox is, at least in America I think, the Embarcadero in San Francisco. It makes me wonder whether Boston would have been better off simply abandoning its own urban freeway.
Having lived in Latin America, I suspect that the jumbles really do move more slowly than North American queues. But you’re right, it wasn’t the clearest example.
Thanks for the link about San Francisco! Quite interesting.
Hi there –
Quantitative social scientist here. Have you ever read George Akerlof’s Rat Race paper?
I’m not a great theorist, but I feel like it’s describing a somewhat similar phenomena in that the government increases utility by forcing participants to work at a lower “speed of work.”
It’s a simplistic mathematical example, but I found it to be very powerful
Thanks, Ben. I’ll check it out.
For anyone else who wants to, here it is on google books: http://books.google.com/books?id=qlwRG3WP4dsC&pg=PA39
Interesting.
So, is Anarchy ever better than regulation?
So what’s the conclusion for public transit? Is there someway the government could step in and better regulate commutes in a Western Democracy? Traffic reports go a long way to mitigating this sort of problem, I think. Apart from better informing commuters, I don’t see any practical solution to streamlining transportation.
Hi Mark,
You’ll notice that in the problem above, there was no mention of how “well informed” the drivers were. All of them were perfectly well informed, and acted exactly in their own best interest. There were no “driving mistakes”. Nonetheless, the average transit time was significantly worse than it could have been. This is the basic content of Braess’s Paradox: in order to improve travel times for all, the government must enforce longer commutes on some.
The question is, how, specifically, do we enforce those longer commutes? Which roads should be shut down? What percentage of cars should be required by law to go the long way? That is a hard question, and it is being addressed as we speak by hundreds of government-hired computer geeks around the world.
In the real world, of course, lots of other things affect traffic. Accidents and driver misinformation have huge (negative) effects, and minimizing those problems will always help tremendously. But even with perfect drivers, as long as each one acts in his own best interest, you can never reach the true ideal.
“The question is, how, specifically, do we enforce those longer commutes? Which roads should be shut down? What percentage of cars should be required by law to go the long way? That is a hard question, and it is being addressed as we speak by hundreds of government-hired computer geeks around the world.”
In general, it’s really not that hard a question. The answer has already been instituted in cities around the world and in the US: tolls and congestion charges. The specifics of location and pricing are somewhat difficult, but the major barrier is political unpopularity. e.g. http://www.citymayors.com/transport/nyc-congestion-charge.html
Hi,
The main real world issue with tolls and congestion charges as opposed to actual road closure is one of ethics. The mathematical model presented here clearly demonstrates that reducing traffic flow on the faster route decreases the average time for a journey, the problem with using a pricing system to reduce traffic is that it creates a situation where the poorer sections of society are forced into longer commutes then the more affluent. It is because of this that closing specific junctions seems, to me, the better response
“The question is, how, specifically, do we enforce those longer commutes? Which roads should be shut down? What percentage of cars should be required by law to go the long way? That is a hard question, and it is being addressed as we speak by hundreds of government-hired computer geeks around the world.”
The paper itself notes that you don’t need to require cars by law to go the long way, you can use road pricing.
Closing roads is a very bad idea because of accidents and construction. The paper assumes that the capacity function and cost function of a particular road never changes. But this happens dramatically when there’s an accident or construction.
If the normally best route suddenly loses capacity, then traffic needs to shift to alternate routes, instead of being discouraged from going there. Side streets that formerly were better off closed suddenly become of vital importance in routing traffic around.
It could be the case that closing a side street improves performance somewhat under normal conditions, but makes the entire system much more brittle by making performance much worse when there’s an accident or construction or road maintenance.
Excellent points. Even without tolling, increased stability may be worth the extra traffic under normal conditions.
Good stuff.
Tom Vanderbilt discussed this well in his book Traffic.
Thanks for the reference.
Here’s the link to the Google Books preview: http://books.google.com/books?id=SLCqCl146AsC
This is a brilliant post. I was just wondering if you’d like to do a guest post on my blog – ecostreets.net – on, basically whatever you like, dealing with sustainability, mobility or “livable streets.” And if you can manage it, in relation to university campuses. Just peruse my site and see if there’s something you’d be interested in covering – it can be as specific or general as you like.
Cheers!
This is interesting.
Tom Schelling described this problem as multi-player dilemma game, in Micro Motives and Macro Economy.
The basic idea is to model a situation in which a person has to choose between one of two actions, and the payoffs depend upon how many people choose the same action.
Schelling didn’t use graph theory to model the game, he had very simple extension of two person game theory pay-offs.
It is relatively easy to see this as a MPD in which taking the shortcut strictly dominates, except when everyone does it and then it is no worse than taking the highway.
As a strategic problem, it is very interesting. Anyone could be the saviour in this problem -at no cost or gain to themselves by switching to the highway.
What are all the ways we could encourage such switch?
The difficulty with all of the real-world examples, is that unlike a stylized mathematical problem, demand is not fixed, that is, the number of people traveling between the origin and destination changes. I do believe that such examples do exist, I just think we have a hard time proving it.
WRT to the question how we could encourage better behavior, the answer as noted by Jacobus is tolling, but the problem is that you need very precise time-varying, link specific tolls to eliminate a paradox from a particular set of links, general tolling is generally good, but may not eliminate Braess Paradox (though could reduce the Price of Anarchy)..
I’m sure you’re right. When traffic gets worse, probably there will be fewer drivers, which tends to equilibrate things a little bit.
Thanks for keeping me honest, guys. People who do physics are chronic over-simplifiers.
Here’s a link to a research paper on this on the Arxiv.
While it’s certainly true that Braess’s paradox is important, much of this analysis assumes that roads are static. It ignores the problems of accidents, construction, and road maintenance, when road capacity is different from normal. Removing an exit or road tends to make thing more brittle. Tolling is a much more robust solution. (And optimal tolling, while difficult, is superior.)
Let’s take your simplified example. Suppose we have removed the exit at C. Now suppose that there’s an accident or road construction that closes the alley from C to B. Now, if everyone knows about this, then everyone will take the bottom roads, since the top roads are impassible. Total travel time for everyone: 20 minutes. If the exit at C still exists, but there is no tolls or other pricing, everyone will still take the bottom roads, total travel time, 20 minutes. However, if there’s tolls placed on the alleys, then you can not only achieve the optimal result with normal flow, but with the alley from C to B closed you can also have half the drivers take the highway from A to C, then switch at the exit and do highway from C to B, and the other half take the bottom roads the whole way. Tolls provide a better result.
The effect is more dramatic if you assume that the total traffic flow in your example is not 10 but 16. Without exit C closed, the naive equilibrium is 6 people on highway, 10 people on alley each time (with 4 switching at exit C), for everyone traveling in 20 minutes. (People will choose the alley until it fills to 10 cars.) The optimal solution is 5 people on alley, 11 people on each highway (with 6 switching at C), for everyone traveling in 15 minutes. The Cost of Anarchy is 5 minutes per person. With exit C closed, there is some improvement, but not optimally. The result would be that 8 people choose either pair of routes, and everyone travels in 18 minutes. Still a savings, but not as good as tolling.
But now let’s imagine what happens in the 16 traffic flow example if the alley from C to B is closed due to accident. Without exit C closed, 10 people travel on the alley from A to C, 6 on the highway, then all 16 go on the highway. Total travel time for all: 20 minutes. The optimal solution is 5 on the alley from A to C, 11 on the highway, and then all 16 on the highway from C to B. Total travel time for all: 15 minutes. Now let’s see what closing exit C does. All 16 people must take alley from A to C, then highway from C to B. Total travel time for everyone: 26 minutes. Wow, closing the exit really made things worse. With tolls to discourage more than 5 people from taking the alleys, the system remains robust and people still take the optimal route.
Conclusion: Removing exits and roads may improve things for given weights and road capacities, but have a higher probability of making things worse if road capacities change due to accident or construction, and a new optimal path presents itself. It removes robustness and ability for the system to correct, making things more brittle.
That’s a great illustration. This comment probably deserves its own post.
A friend pointed me to the basketball example, but it said to come here first, so I did. Nice post and I like the phrase “price of anarchy”, but I’m an economist and I was thinking the whole time of Pigou and Knight. Some of the comments mentioned road pricing, but no one offered Knight’s solution, so I thought I’d share it.
The history goes like this: in 1920, in the first edition of his important and influential _Economics of Welfare_ (I can’t find this edition online), Pigou had an example like yours where too many cars traveled on the narrow, good road and too few on the broad, but poor road. The problem is that each driver ignores the costs imposed on others, called an externality, and this leads to a suboptimal allocation of trucks. He christened this a “market failure” and said government regulation was needed. By applying the optimal tax (or toll), the government could fix the inefficiency of the market because the drivers would be forced to take the costs of their additional congestion into account. Pigou was British and trusted government and experts to get it right.
Knight was an American who distrusted authority and government. In 1926, in the Quarterly Journal of Economics (http://www.jstor.org/stable/1884592), he said this was hardly a market failure because the problem was that no one owned the road! Knight argued that private ownership would fix the problem — the profit maximizing price equaled the optimal toll — and, best of all, without government intervention.
You ended your nice post with “Lest you think this is an academic exercise,” so I will too. Many people think private ownership of roads is silly, but Knight would have smiled when Illinois sold the Chicago Skyway (Knight became famous at U of Chicago) and I live in Indiana which sold its toll road for $4 billion a few years ago. Private roads are no mere theoretical abstraction. There’s lots more to talk about, but I gotta read about the basketball example that originally brought me here!
P.S. Knight’s idea lay dormant and Pigou’s optimal tax/subsidy (some externalities are positive — they grant benefits to others, like painting your house or education) approach was all there was for decades until Coase in 1960. His work led eventually to marketable pollution permits and cap and trade . . .
Thanks for the story Humberto. Science is always more interesting and understandable when placed in the context of the idiosyncratic people who came up with it.
very nice case. however, as a quantitive social scientist I am not so sure about the practical implications, as said above: people anticipate, form expectations and seek information etcetera, making the whole system dynamic, or “complex” (see: complex adaptive systems, Miller & Page, 2007)
julian havil (2008) also devotes a chapter to Braess rather vividly in his book: “impossible”
link:
http://books.google.com/books?id=yOQuyUthek0C&printsec=frontcover&dq=havil+impossible&ei=WFJ3SpPVForWyATcqsSDAw&hl=nl#v=onepage&q=&f=false
Braess’ paradox only works if you do not have efficient congestion pricing. Levying efficient congestion tolls always vmeans that vadding an extra link – offering people more opportunities to travel – always improves traffic welfare.