Why the secret to speedier highways might be closing some roads: the Braess paradox
6 January 2009| by Presh TalwalkarRead more Game Theory (new article on Tuesdays)
During the holiday season, several roads in my town were temporarily closed due to flooding. I was naturally worried how the road closures would affect traffic. But in the end, my fears were unfounded. Not only was traffic mostly unaffected, I often found my travel times were reduced!
This experience made no sense to me. If traffic is about too many cars on the roads, how could blocking some roads speed my commute? Or conversely, why might adding roads slow my commute?
I did a little bit of research and came across an interesting game theoretic explanation known as the Braess paradox. It states that it’s possible that adding a road could lead to slower travel for all drivers. Let’s go through an example to see why.
A traffic question
(problem based on this excellent example)
Consider a traffic network where 1,000 drivers wish to travel from start to end. There are two main paths the drivers can take. They can either travel along the path start-A-end or along the path start-B-end:
The choice is complicated by the presence of traffic. Some roads are narrow and get congested. On these roads, the travel time for every driver depends on how many travelers T also pick that path. In this network, the roads start-A and B-end are narrow and travel time is estimated to be T / 25 minutes on average. The travel on these roads will be slower as more and more drivers choose them.
But not all roads are narrow. Some roads are so wide that they never get congested. On these roads, the travel time for every driver will be a constant number of minutes. In this network, the roads A-end and start-B are wide and travel time is estimated to be 50 minutes on average.
If every driver is optimizing travel times, as is natural in real life, how long will it take to travel from start to end?
The equilibrium
The traffic game is dynamic. Each driver has to choose a path by guessing what others will do. We can start the analysis by calculating the travel times of each route dependent on the number of drivers.
If A drivers choose the route start-A-end, then the route will take A / 25 minutes for start-A segment and then 50 minutes for A-end segment.
Similarly, if B drivers choose the route start-B-end, then the route will take 50 minutes for start-B segment and then B / 25 minutes for B-end segment.
We can graph the travel times for the two paths as follows:
In practice, there are many possible outcomes to the traffic game. For instance, it is possible that 600 drivers choose the path start-A-end yielding a travel time of 74 minutes. That would mean the other 400 drivers who took start-B-end only had a 66 minute drive. But drivers are smart, and with traffic reports they can improve their choice in the future. We can imagine that some of the drivers from the start-A-end route would change travel routes the next day.
Such switching will continue as each driver optimizes. The time people stop switching–that is, when the traffic system will be in equilibrium–is therefore when the two driving routes have equal travel times.
We can solve the equations or inspect the graph to see this happens when A = B = 500 and both routes have a travel time of 70 minutes. Now every driver is indifferent between the two choices and the game is in equilibrium.
What happens when you add a new road?
Imagine a new road is added between points A and B. We might imagine the road is so wide and small in length that it takes almost no time to traverse it (it is a “free” road):
What will happen to the game now?
Solving the new game (the Braess paradox)
The new road allows drivers more choice. Now they can switch routes by going along the “free” road. How will the game play out?
The game is surprisingly simple to solve because each driver has a dominant strategy. Consider the first choice of picking the path start-A versus start-B. We can quickly see that every driver will pick start-A. This is because start-A takes 40 minutes at worst (if all 1,000 took it, it will take 1,000 / 25 = 40 minutes) compared to start-B which takes 50 minutes for sure. So all drivers pick start-A and spend 40 minutes.
What will happen next? Once at A, the drivers have two choices. They can either stick to A-end (50 minutes for sure) or they can take the free road A-B (0 minutes) and follow the road B-end (which takes T / 25, and hence will be 40 minutes at worse). Naturally all drivers will choose the free road and B-end route.
We can conclude that all 1,000 drivers will take the path start-A-B-end. When we calculate the travel times, we find we have a grand total of 80 minutes (1,000 / 25 + 0 + 1,000 / 25).
Additionally, notice that no driver will want to switch because the alternative routes start-A-end and start-B-end now take 90 minutes each.
In this equilibrium, the roads the travelers pick are completely congested. And consequently this game’s equilibrium is 10 minutes worse than before the road A-B existed!
Further reading: this paradox happens in real life
The Braess paradox is not just an academic curiosity…some research suggests it might explain traffic in big cities like Boston, London and New York.
See this technical paper about the “price of anarchy” in traffic systems for more details (or check out the Economist’s summary of it).
Also see this fun example and explanation in the New York Times.
What’s going on?
The paradox is the consequence of individual incentives conflicting with the social optimum. If all drivers could agree not to take the “free” road A-B, then it would be possible that everyone could save 10 minutes. The problem is this proposal is not sustainable-individual drivers have an incentive to cheat and save time. Eventually the entire system breaks down when everyone cheats, making the roads congested.
The lesson is that social planning is necessary to coordinate drivers for the optimum. And that means it is sometimes best to limit options.
6 Comments » | 
Cite / Print this article
Related Posts:
by the same author.
