10. A Faster Way:
The Braess Paradox:
The question:
All streets lead to Rome, says an old adage. This means that in the vast Roman empire hosecarts transporting wheat and other goods, legionnaires walking to their deployment destination, centurions riding high, probably encountered very light traffic along the ways. But in the city of Cityville there are only Avenue A and Aveneu B that lead from Downtown to Uptown. During rush hour on any given day, one is clogged, the other is nearly free of traffic. One never knows ahead of time which one will be jammed up, because people decide randomly to take one avenue or the other.
To alleviate the bottleneck, the city councillors get together and decide to build a connecting road linking Avenue A to Avenue B at about halfway between Uptown and Downtown. Then, when the radio announces that the avenue that they are on has heavy traffic ahead, drivers can switch to the other. Construction of this new road will certainly alleviate the traffic jams.
Right?
The paradox:
Wrong again! In a scholarly paper published in a German journal and overlooked for several decades, the mathematician Dieter Braess wrote that in certain road networks “an extension of the road network may cause a redistribution of the traffic that results in longer individual running times.” The reason is that such an extension “may cause a redistribution of the traffit which results in longer individual running times.” In other words, adding a road may increase traffic jams!
Few people took notice of Braess’s paper, mainly because it was written in German. Only in 2005 was a translation into English published.[1] Some experts had taken notice, however. In 1990, two mathematicians concluded that “It seems intuitively obvious that adding routes and capacity to an existing transportation network should decrease, or at worst not change, the average time individuals require to travel through the network from a source to a destination. In an uncongested transportation network, the obvious is true. In a congested transportation network, the obvious need not be true.”[2] The additional road can actually create even worse jams.
Background:
Dieter Braess’s research was motivated by an occurrence in the late 1960s. In the city of Stuttgart in Germany, the authorities decided to upgrade their notoriously clogged road network. But to the disappointment of everyone, the investment did not lighten the traffic. Most surprisingly, however, the situation improved markedly after the city fathers decided to close a section of the newly built network.
In April 1990, several years after the event in Stuttgart, the City of New York celebrated Earth Day with outdoor performances, environmental exhibitions and street fairs. Numerous activities were taking place all over the city. To enhance the festivites, and with a nod to the environmental spirit, the Transportation Commissioner decided to close the permanently clogged 42nd Street to all traffic. Many a New Yorker expected a traffic disaster since 42nd Street was a major crosstown throughfare. To everyone’s surprise, the disaster did not materialize. In fact, traffic flowed more easily in the surrounding streets and avenues.
Meanwhile, in South Korea, in the early aughts, city planners in Seoul, South Korea, replaced a six-lane highway with a five-mile-long park. Traffic flow improved! Then, in 2009, New York’s Mayor Bloomberg ran some experiments with road closures. They were deemed a success and the closures were made permanent. Times Square and Herald Square are now pedestrian plazas that have not worsened traffic problems.
Once the Braess paradox had been identified in road networks, it suddenly reared its head in all kinds of networks, like the internet, airline travel, power transmission. Even sports are not immune. In basketball, for example, the route to scoring a basket is akin to a network. Relegating a star athlete to the bench, analogous to closing access to a shortcut, could conceivably lead to a better performance by the team.
Dénouement:
The genesis for the emergence of a Braess situation lies at the junction where the connecting road leads to the parallel avenue. Frustrated drivers, eager to minimize their travelling time, must make a decision: switch to the other avenue and hope that it is free-flowing, or stay on their jammed-up avenue and hope for the best. What may happen is that so many drivers switch from the jammed-up avenue to the other that a jam arises there; but not enough drivers do so to alleviate the jam on the former. Now both avenues are blocked.
Once we understand the reason for this phenomenon, it no longer surprises. Even Braess concedes on his website that his paradox is not really a paradox but only a situation which is counterintuitive.
Technical Supplement:
Since drivers must decide at the junction which avenue to take, the phenomenon belongs to the realm of game theory, developed by John von Neumann and Oskar Morgenstern. (See the chapter on the Independence of Irrelevant Alternatives.) However, it is not what is commonly called a zero-sum game, where some participants gain what the others lose. In the Braess situation nobody gains and many lose. In the lingo of mathematical economics, one must distinguish between an equilibrium (both avenues blocked) and an optimum (one blocked, the other free).
“If every driver takes the path that looks most favorable to him,” Braess had written in his surprising paper, “the resultant running times need not be minimal.” And in the words of Youn, Gastner and Jeong, “uncoordinated individuals in human society pursuing their personally optimal strategies do not always achieve …the most beneficial state to the society as a whole. … Society, therefore, has to pay a price of anarchy for the lack of coordination among its members.”
If there were a central controller to manage traffic flow, at least part of the drivers would have their travel time shortened. But when all drivers strive to optimize their travelling time on their own, additional blockages may arise. So, in the absence of a central controller, the solution may be close certain streets.
[1] Braess, Dietrich, et al., “On a Paradox of Traffic Planning:, Transportation Science, Vol 39, No 4.
[2] Cohen, Joel E., and Frank P. Kelly. 1990. A paradox of congestion in a queuing network. Journal of Applied Probability 27:730–734.
Comments, corrections, observations:
