Too much Traffic? Reduce the number of roads.

Traffic is a problem that no major city is spared from. We all pine for the construction of new and improved roads to lessen the burden of congestion, unaware of the fact that the creation of new roads only exacerbates this problem. Surprised? Read on.

Discovered by German mathematician Dietrich Braess, the Braess’ Paradox states that reducing the presence of extensions in a network counterintuitively increases its efficiency. Consider the following example:

Sample Road Network

Case I: Network AB does not exist.

Let T denote the number of cars on a given route and t the time it takes to traverse that road (in minutes). For example, if a thousand cars were to travel from start to end using route A, it would take a total of (1000/100) + 45 minutes.

Our objective as the self-proclaimed traffic official of this city, is to minimize the total travel time for each car on this network such that each car takes the optimal route. In other words, we are trying to find a Nash equilibrium for this scenario.

“The Nash Equilibrium is the solution to a game in which two or more players have a strategy, and with each participant considering an opponent’s choice, he has no incentive, nothing to gain, by switching his strategy.”

Let us assume that there are 4,000 cars who want to go from Start to End. In this case, the Nash Equilibrium is easy: half the cars choose route A, the other half uses route B. Hence, each car on either route takes (2000/100) + 45 = 65 minutes.

No driver has anything to gain by not dividing themselves up evenly between the two routes: doing so only increases the travel time.

Sample Road Network

Case II: Network AB exists.

Consider there to be a super-fast expressway AB that allows drivers to switch routes midway. AB is so incredibly rapid that it takes zero time to travel from A to B. Using the Nash Equilibrium found in Case I, if 2000 cars were to use route A, the drivers of these cars would chance upon a remarkable epiphany: If they were to switch routes from A to B, their total time would only be (2000/100 + 2000/100) or 40 minutes!

(assuming no cars using route B have reached point B yet, given that it takes 45 minutes to do so.)

Switching routes from A to B clearly is the best strategy. Unfortunately, the drives of route B realize this too, and are seen to flock like crows to use route A instead of B to benefit from switching.

The problem is that now all 4000 cars utilize route A and switch to B. Hence, the Nash Equilibrium for Case II is a total time of (4000/100 + 4000/100) minutes, or 80 minutes.

This result is truly paradoxical: open route AB increases travel time from 65 to 80 minutes.

As strange as it may seem, using fewer roads is better for overall travel time!

But how can we be sure that equilibriums even exist for the two cases?

Proof of the existence of an equilibrium:

If one assumes the travel time for each person driving on an road (hereinafter referred to as an ‘edge’) to be equal, an equilibrium will always exist.

Let L(x) denote the total time of each driver on edge e when x people take that edge. An equilibrium exists if we minimize the “total energy” E(e) of an edge.

E(e)=

Take a choice of routes that minimizes the total energy. Such a choice must exist because there are finitely many choices of routes. That will be an equilibrium.

Assume, for contradiction, this is not the case. Then, there is at least one driver who can switch the route and improve the travel time. Suppose the original route is

route 1.1

Let E be total energy of the traffic graph, and consider what happens when route 1.1 is eliminated. The total energy E will be reduced by:

Since the energy without route 1.1 is lower than with it, it is more efficient to have fewer roads on an isolated network.

Application of Braess’ Paradox to Electronics and Biology:

The true beauty of mathematics is that seems to find a niche for itself in every facet of our lives. Consequently, it would be illogical for me to restrict this post to dealing solely with issues of traffic.

In 2012, a team of researchers in Europe published a paper proving that a increase in possible ‘networks’ in microscopic electrical cells paradoxically reduces its conductance.

In the words of Adilson E Motter, “for resource management of endangered species food webs, in which extinction of many species might follow sequentially, a deliberate elimination of a doomed species from the network could be used to bring about the positive outcome of preventing a series of further extinctions”

Citations:

1. Steinberg, R.; Zangwill, W. I. (1983). “The Prevalence of Braess’ Paradox”. Transportation Science.
2. T. Roughgarden. “The Price of Anarchy.” MIT Press, Cambridge, MA, 2005.
3. http://www.nytimes.com/1990/12/25/health/ what-if-they-closed-42d-street-and-nobody-noticed.html
4. A. Rapoport, T. Kugler, S. Dugar, and E. J. Gisches, Choice of routes in congested traffic networks: Experimental tests of the Braess Paradox.