Think Adding Roads Reduces Congestion? Math Says No.

People like being stuck in traffic the way they like hearing nails against a chalk board; with the exception of a few masochistic individuals, it is universally loathed. If only the <Feds, State, County, City> would add another road no one would have to sit in this parking lot. Now of course one could imagine a number of logistical reasons to refute this fallacious line of reasoning: bottlenecking, merging delays, turning delays, signal delays, start-up delays and even further demand induced by the new connection, to name a few. While those are all certainly valid criticisms, what I intend to discuss here has nothing to do with with these more intuitive problems; there is a more fundamental problem rooted simply in mathematics and basic economic theory.

Conventional economic philosophy dictates that individuals rationally acting in their own self-interest would ultimately also benefit society as a whole– a sentiment well-captured by this panel from yesterday’s SMBC comic.

Don't hate the player hate the game

Saturday Morning Breakfast Cereal #2891. 2013-Feb-18.

That is, it was conventional until famed economist, mathematician, paranoid schizophrenic, Nobel laureate, and protagonist of the book and film, A Beautiful MindJohn Forbes Nash, forever changed the field with his concept of equilibrium in non-cooperative games. His concept became known as Nash equilibrium and went on to become a cornerstone of contemporary game theory.

User Equilibrium

Nash equilibrium is the point at which no user can benefit from changing his strategy, assuming he knows his competitors’ strategies and that they will remain constant. Simply put, it could be phrased by asking yourself the question: “can I improve my situation if everybody else keeps doing as they are now?” When everyone answers “no” to this, Nash equilibrium has been reached. This concept applies seamlessly to solving transportation network problems in the form of user equilibrium.  One common assumption made in order to determine network flows is that each user seeks a route that will minimize his or her overall travel time. In order for equilibrium to be reached, the time it takes to traverse all routes from origin to destination must be equal. If it were not, drivers would continue to adjust their routes until no one had anything to gain from doing so. However, roads of course do not have unlimited capacity. As each vehicle competes for the finite resource of road space, they will begin to increase travel time on that road. By expressing the cost of each vehicle on a road’s travel time mathematically, determining the network flows is only a matter of solving the system of equations where the total travel times along every route are equal to one another.

Tragedy of the Commons

The first unfortunate consequence of this behavior is the well-documented tragedy of the commons. This is when many users share access to the same public good in such a way that each one benefits from further exploiting it despite each further exploitation reducing the overall good. The eponymous example of this is that of the herders who are permitted to let their cattle graze in the public commons. Since each herder bears no cost and receives only benefit from the use of this land, the only rational decision is to use this land. By not doing so, he would surely be surpassed by his competitors who will further benefit from his forfeiture of the commons. Of course though, the commons is a finite resource, and with each additional herder using the land, the marginal benefit of the land continues to diminish, until eventually the land lies fallow to the detriment of all. But before the resource has been entirely depleted, the strictly rational decision for any given herder is to continue using it.

The corollary to user equilibrium should be evident. As the number of drivers on the virtually free and publicly shared road approaches its capacity, the resource (space) becomes scarcer and each additional vehicle further decreases the benefit of the system as a whole. Yet, the strictly rational travel behavior in this scenario is to continue driving. However, for every road network there is a system optimal network travel time. That is to say, that the cumulative travel time on the network is minimized, though individuals will come to increase the system time by acting in their own self-interest to decrease their personal travel time. Clearly, the system optimal solution is difficult to reconcile with rational human behavior, and so eventually the network flows would tend towards user equilibrium.

Braess’s Paradox

So what does all of this have to do with adding road capacity? Surely the travel time will decrease with more roads, even when drivers are acting in their self-interest, right? Well, not necessarily. Enter Braess’s Paradox. Simply put, it is the observation that Nash’s equilibrium is not the system optimal solution. Taking this one step further, since the user equilibrium network flows and the system optimal network flows are inherent characteristics of the network itself, changing the network in any way can either widen or narrow the gap between the two. Take the following example from Wikipedia:

Consider a road network as shown in the adjacent diagram, on which 4000 drivers wish to travel from point Start to End. The travel time in minutes on the Start-A road is the number of travelers (T) divided by 100, and on Start-B is a constant 45 minutes (likewise with the roads across from them). If the dashed road does not exist (so the traffic network has 4 roads in total), the time needed to drive Start-A-End route with A drivers would be \tfrac{A}{100} + 45. And the time needed to drive the Start-B-End route with B drivers would be \tfrac{B}{100} + 45. If either route were shorter, it would not be a Nash equilibrium: a rational driver would switch routes from the longer route to the shorter route. As there are 4000 drivers, the fact that A + B = 4000 can be used to derive the fact that A = B = 2000 when the system is at equilibrium. Therefore, each route takes \tfrac{2000}{100} + 45 = 65 minutes.

Now suppose the dashed line is a road with an extremely short travel time of approximately 0 minutes. In this situation, all drivers will choose the Start-A route rather than the Start-B route, because Start-A will only take \tfrac{T}{100} = \tfrac{4000}{100} = 40 minutes at its worst, whereas Start-B is guaranteed to take 45 minutes. Once at point A, every rational driver will elect to take the “free” road to B and from there continue to End, because once again A-End is guaranteed to take 45 minutes while A-B-End will take at most  0 + \tfrac{4000}{100} =  40  minutes. Each driver’s travel time is \tfrac{4000}{100} + \tfrac{4000}{100} = 80 minutes, an increase from the 65 minutes required when the fast A-B road did not exist. No driver has an incentive to switch, as the two original routes (Start-A-End and Start-B-End) are both now 85 minutes. If every driver were to agree not to use the A-B path, every driver would benefit by reducing their travel time by 15 minutes. However, because any single driver will always benefit by taking the A-B path, the socially optimal distribution is not stable and so Braess’s paradox occurs.

The takeaway here is that by adding what can be considered a route with zero cost, travel time at user equilibrium increased substantially! The user equilibrium flows on the original network before construction of the A-B link were in fact closer to the system optimal than before its construction.

A Final Word

This is not to say that every change to the network will increase overall travel time, however this is far form what some would consider to be the “common sense” assumption that more roads equate to less congestion. Given all of this, I will conclude with the following points:

  • Network time can be up to twice as high for user equilibrium than it would be at system optimal conditions.
  • Although real-world transportation networks are far too complex for such clean mathematical representations, one well-reputed study found that adding a link was just as likely to increase travel times as it was to decrease them! This implies that the effect is essentially random with a 50% chance of going one way or the other.
  • Contrary to strong public outcries, closing select streets may actually decrease travel times for drivers, even in New York City where traffic flow improved when 42 Street was closed for Earth Day in 1990 and more recently when the now-permanent 2009 closure of Broadway at Times Square and Herald Square was implemented.
  • In addition to these fundamentally mathematical reasons, there are many more intuitive reasons why travel time may increase, as mentioned previously, and in addition to improving network performance, there are many other good reasons to close select streets to traffic. I will explore these issues in greater detail at a later date.
About these ads

5 comments

  1. mattd4488

    This could just be my ignorance, but I am having trouble with connecting the Wikipedia example to any real-life example, given how unrealistic it is. Clearly, it was designed to prove a point, but what is the point of proving a hypothetical? Since there are no roads with constant travel time, be it 45 minutes or 0 minutes, this can’t be directly adapted to any real-life situation. In real life, drivers have traffic reports, and know that driving a long a congested road is a silly idea when there’s another road that’s completely empty.

    Speaking of which, I wonder how much the system could be improved, not by adding or subtracting routes, but by installing electronic signage to inform drivers about traffic conditions elsewhere.

    Anyway, the article was interesting. It does provide some information why adding a new route could actually increase traffic time. Clearly, real-life examples are more difficult to analyze, but I wonder if you could do an article showing why this has happened before, say in 2009 at the closing of Broadway at Times Square.

  2. williamjacobfarrell

    I am thinking about writing a follow-up to address this and similar questions I have received on Facebook. But let this suffice for now:

    Obviously this is a theoretical example but you could imagine how they may model real life. Picture a road with constant travel time as one with so much capacity that it will not exceed its capacity. While this assumption will never be true indefinitely, it could certainly be true in practice- say a six-lane highway in the middle of Manitoba. A travel time of 0 may simply represent a connect that has been added that allows vehicles to change roads in a location they could not previously- say a new interchange between highways that were previously inaccesible to one another. In this case it can be thought of as a one-way interchange, where vehicles can only travel from one highway to the other, but not in reverse.

    But I think the larger point you miss is that in this scenario, both routes that contain the fixed 45 minute time will *always* be longer due to the way the network is set up. One of the main assumptions of this method is that the drivers have perfect information, so adding electric signs would only further this. The more information the drivers have, the more rationally they will behave in terms of user equilibrium.

    The point of this simple example was only to illustrate the concept, but in my next post I will attempt to create a more “realistic” example and explore some case-studies as well. The thing is that in real life you have that host of other factors I mentioned. One of the reasons cited for the Broadway improvements for example is the increased green time given to the remaining 2 streets- that is they did not have to share limited green time in the light cycle between 3 directions of travel.

  3. diplodocuscoffeespot

    The key point that is missing from this analysis is that with well defined property rights the tragedy of the commons would not be a problem. If the common resource were owned by a single entity (and thus aggregating the benefits of all drivers and taking into account the negative effect each additional driver imposes on others) the problem would be solved. In particular, if you let a monopolist own the roads the problem should be solved. This means that a number of people will not be able to drive anymore but that is the optimal solution. There are too many people on the roads and having a monopolist charge the correct price (the price that takes the negative effect of more drivers on the road) would help.

    Not to knit pick, but the tragedy of the commons refers to a situation where a common resource which is finite has no clearly defined property rights. If the good were a public good, adding more users would not deplete the good.

    • williamjacobfarrell

      I completely agree that the tragedy-of-the-commons effect takes place only because the commodity is undervalued. In fact, that is the essence of this effect in general. Charging market value for using the roads, as tolls and congestion pricing attempt to do, a certainly a step in the right direction.

  4. Georges Jacquemart

    Although I agree with the general message of the article and the “tragedy of the commons” the math example is flawed. Even though I could see an example where the travel time remains constant at 45 min (a freeway with lots of lanes), the travel time eqaution on the other link (t=T/100) is not realistic. If we have 4000 vehicles on that link it takes 40 minutes, and if we have 10 vehicles it would take 0.1 minute. Not realistic. If we change the travel time formula to t=square root of T, a slightly more reasonable relationship, the math example falls apart. And yes add a travel time to go from A to B with 4000 vehicles on that link, the math falls apart even further.
    The relationship between highway capacity increase (or decreases) and congestion is more complex and involves changes in land-use, human behavior and culture.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s