A few weeks ago during our unit on Game Theory, we discussed a phenomenon known as Braess’s paradox:

“Braess’s paradox, credited to the mathematician Dietrich Braess, states that adding extra capacity to a network, when the moving entities selfishly choose their route, can in some cases reduce overall performance.” (Wikipedia)

This leads directly to another term, the price of anarchy (PoA), which is defined as the cost of the Nash equilibrium (NE) divided by the cost of the social optimum (SO). In simple networks, the PoA is often equal to 1 because the selfish entities choose the socially optimum path. However, there are examples, such as the road network we saw in class, where the total cost of the NE is greater than the cost of the SO, resulting in a PoA of greater than one.

One of the first questions all of us had during that lecture was whether such a network was possible to create in real life. After all, one of the roads in the graph the Professor drew had a total travel time of zero. Could a network with a PoA of greater than 1 exist without having to make such impossible assumptions?

It turns out, according to a study by Michael Gastner, Hyejin Youn, and Hawoong Jeong, that the city of Boston, MA exhibits this property. Growing up in a town not far from Boston, a tale I’ve commonly heard about the city is that Boston’s road network is so convoluted (compared to cities like NYC, where the roads are arranged in a neat grid) because the roads present there today where built on top of the cattle paths from the Colonial era. It is not hard to believe that the choices made by commuters traveling through such a network are not socially optimum.

Gastner, Youn, and Jeong explain how by using Google Maps and traffic data, they were able to calculate that the worst PoA in the network created by routes from Harvard Square to Boston Common occurs when there are 10,000 vehicles passing through per hour. At this rate, the PoA is an alarming 1.3, which means “individuals waste 30% of their travel time for not being coordinated” (2).

They were also able to calculate that in most cases, removing one of the roads commuters used created an increase in travel time as expected, but there were six connections which when removed would decrease the travel time of the NE and as a result decrease the PoA.

In a relatively ancient city like Boston where very little planning has been put into the road network, it is not surprising that rare phenomena like Braess’s paradox exist. As the population of the city grows and the price of anarchy becomes ever increasing, it might be time to get a human to redo what has long been the whims of cows.

References:
Gastner, Youn, Jeong. “The Price of Anarchy in Transportation Networks: Efficiency and Optimality Control”. http://arxiv.org/PS_cache/arxiv/pdf/0712/0712.1598v4.pdf
“Braess’s Paradox”. http://en.wikipedia.org/wiki/Braess_paradox