Why the secret to speedier highways might be closing some roads: the Braess paradox

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.



Share this post:

| More

Previous post:

Next post:



  • Mike

    By “social planning” do you mean “better planning of roads” or something more intrusive? “Social planning” solutions lead some to “solutions” that lean heavily on public transportation.

  • Hinheckle Jones

    Why does travelling the big empty roads take so much longer than travelling the congested narrow roads? I practice, I find that congested freeways allow faster travel than less congested side streets that have too many stop lights.

  • http://betterexplained.com Kalid

    Hi Presh, really interesting article! This seems a like a variant of the prisoner’s dilemma where both players have incentives to defect (take the shortcut), but in so doing, slow themselves down more.

    I like this example better because it’s easier to visualize in real life :) . Great article.

  • Scott

    This example really doesn’t show that “more roads” = “bad” but that “bad placement of roads” = “bad”.

    After all, if a new road was placed, say… start-C-end that was similar or identical to either start-A-end or start-B-end then that would simply result in a new equilibrium, perhaps one better then with just start-A-end and start-B-end.

    The reason why A-B is bad is because it creates a shortcut and the end result is a tragedy of the commons: everyone has a reason to exploit it but the common exploitation of it results in a bad result for everyone.

  • http://v.vezquex.com/ Vezquex

    Hinheckle, the freeway might not be going straight toward the destination like a narrow road could.

  • http://book-bot.com gilltots

    “During the holiday season…”

    maybe traffic wasn’t as bad over the holidays because tons of people get time off and don’t have to drive to work or school – your road closures due to flooding probably made the really good holiday traffic a little less good, but still better than normal.

    Also an alternative answer to “why might adding roads slow my commute?” is that every time two roads intersect you need either a stop sign or a traffic light or a turn lane or a merge lane, etc. all those things impede traffic flow and create backup ripples – but are completely left out of the network flow analysis – it’s like doing Newtonian physics and assuming no friction. sure it fits the theory but it just doesn’t work like that in the real world.

  • Rohan

    interesting article presh!

  • Scott

    Accidents changes the equation.

    Let’s say an accident on a path increases the time by A. Using a population of 1000 and going with the original scenario (no A-B road), an accident on a single road alters the equilibrium.

    The people on the accident-free road will be 12.5*A + 500.
    The people on the acciident road will be 500 – 12.5*A.

    The time for each path will be A/2 + 70.

    Let’s call the drive time when there is an accident Ta.

    Now, lets say an accident occurs every N times you take a path. Your overall average drive time is:

    (70*(N-1) + Ta)/N

    Now let’s plug all this in to the second scenario. Like before we divide it into two parts. For simplicity we will say the accident only affects travel on the half it occurs. So for the half where the accident doesn’t occur, everyone will take the 40 minute route.

    So all we have to do is calculate any new equilibriums.

    If the accident occurs on the flat 50 minute route, people will still take the 40 minute route, which will not change the overall travel time of 80 minutes.

    If the accident occurs on the 40 minute route, then this depends on the value of A. If A > 10 minutes (which isn’t unreasonable), then people will go to the 50 minute route for an overall travel time of 90 minutes.

    If an accident is as likely to happen on one side as the other then the average time only changes every other accident (on average). This makes the overall average:

    (80*(2N-1) + 90)/2N

    The purpose of this is to see under what conditions the second scenario is, on average, better than the first. So we see when the overall average time of the first scenario is less than the overall average time of the second scenario:

    (80*(2N-1) + 90)/2N < (70*(N-1) + Ta)/N
    (80*(2N-1) + 90) < 2*(70*(N-1) + Ta)
    160N – 80 + 90 < 2*(70N – 70 + Ta)
    160N + 10 < 140N – 140 + 2Ta
    20N – 2Ta < -150

    If we recall, Ta = A/2 + 70
    20N – 2(A/2 + 70) < -150
    20N – A – 140 < -150
    20N – A 10

    So when the increased time due to an accident, subtracted by 20 times the number of days between each accident is greater than 10, the second scenario is better. Let’s try it out. Let’s say an accident happens every other day and increases the travel time by 51. That makes A – 20N = 11.

    The average travel time of the scecond scenario becomes:

    (80*(2N-1) + 90)/2N = 82.5 minutes.

    The average travel time of the first scenario becomes:

    A/2 + 70 = Ta
    95.5 = Ta
    (70*(N-1) + Ta)/N = 82.75

    So on this accident ridden road, adding A-B would increase your average travel time by a quarter of a minute. Now, this is not much of an improvement and hour-long accidents happening every other day is a bit extreme, but the scenario is meant to be an abstraction and shows that, under certain circumstances, being able to switch routes may make the situation better.

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Thanks all for the comments…here are some of my thoughts:

    Mike: By social planning I meant “planning of better designed systems.” In Illinois, for instance, when the government plans “congestion relief” it almost always amounts building more roads–which as we see can backfire if you do things the wrong way! I hope they will be more creative in the future…

    Hinheckle: One possible answer: imagine all the roads are freeways but the “narrow” ones are ones with lanes closed for construction. With few cars traffic flows fine, but with many everyone has to slow down for merging.

    Kalid: Great point–this does seem like a prisoner’s dilemma where each party has a dominant strategy that leads to a suboptimal outcome.

    Scott: You’re right–it is the precise locations of the roads that determine if the system will fail. I also was thinking that widening roads would seem to reduce traffic times, but often times it is not possible to widen some roads (businesses or rivers might be in the way).

    gilltots: Yes, the roads were somewhat hazardous to drive so I was saving time since the roads were empty…Good point about adding traffic lights and signs.

    Scott: I’ll have to check your math but that’s a very interesting idea how flexibility can help in the presence of accidents.

    Accidents can slow the roads in unusual ways. There is another phenomenon called “gaper’s delay” in which a traffic jam is caused not by obstruction but instead by drivers slowing down to see the damage of the accident. Happens all the time on Illinois highways.

  • Cody

    Presh: As a resident of Michigan (A neighbor, so to speak) I can attest to Gaper’s Delay. Sometimes you are stopped by an accident up ahead, sit there for a half an hour, and when you get up to it, there is little to no lane obstruction at all. People just want to gawk.

    As for the problem in its beginning form… I like to think of it this way. The “T/25″ roads are freeways, which are faster and often times more direct, while the “50″ roads are “back roads” ie, slower, but due to speed restrictions, they are safer and congestion has a negligible effect on drive times. It’s just a different way of looking at it, but it gives the same result–if a new freeway is built which bypasses back roads, then pretty much everybody will use it (especially in winter here in Michigan), and drive times will slow for everyone.

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Cody: As a resident in the midwest, I can also attest to Gaper’s Delay :)

    As for the specific freeway/back roads distinction, I think the analogy can go either way. The bigger point is that local incentives can result in global inefficiencies–termed “the price of anarchy.”

    So what is one to do in practice? I think commuters would tend to minimize risk. That is, they don’t just take the path of expected risk, but one that has a reasonable travel time with low variance. Just my guess ;)

  • atcm

    hi,
    interesting article :)
    how about if the start-B and A-end road is 30 mins which is less than the time if compare to choosing Start-A(1,000 / 25 = 40 minutes) and the “free” road that link A to B is a 2 ways road?
    what is the equilibrium in this case? which road will the driver choose at the start?

  • Brian

    This was a very interesting article, and a good starting point for analysis. There are some simplifying assumptions which, while useful for laying out the basic outlines of the problem (as here), run so counter to reality that they need to be changed quickly to generate meaningful results. For example, the formula for the narrow road travel time, T/25, results in a travel time approaching zero if there are few travelers on that route. We know that travel time does not vary in this way, as there are certain physical constraints that cannot be overcome, for example the route covers X miles. A more realistic formula would be something on the order of X/45 (mph) + T/25. In other words, there is a minimum travel time, which increases as a function of the number of travelers on that route.

    Another assumption that does not accord with reality is the zero travel time for the AB segment. Also, in most cases, there already exist numerous routes similar to AB, as people exit on freeway and cut across to another.

    Of course, the system becomes much more complex as the number of possible routes increases. As we have learned to our great cost in the financial debacles of late, complex mathematical models which do not fully account for all potential situations, and which are not fully understood by the ultimate decision makers (think Investment Bank Executive Boards, or in this case City Councils/State Highway Authorities), but are instead viewed as “magic boxes” which give infallible answers, will lead to tragic results.

    I see the sort of practical results stemming from this approach as being more in the decision of what type of new road to build (i.e. a cutoff as in AB, or an entirely new routs, as in start-C-end, or even in simply improving existing routes), rather than in decisions on whether or not to take action.

  • Pingback: Video: Braess Paradox demonstrated with springs - Mind Your Decisions





Previous post:

Next post:

Other posts you may enjoy reading:

This site is for recreational and educational purposes only (privacy policy)

Powered by WordPress