Wednesday, January 21, 2009

Scientific American, the Braess Paradox, and the Price of Anarchy

I was interviewed by the journalist, Linda Baker, for her article, "Detours by Design," which appears in the February 2009 issue of the Scientific American. The article talks about the Braess paradox, which dates to 1968, and demonstrates that the addition of a new road may make all travelers worse off in terms of travel time/cost. The Scientific American article highlights a recent example from Seoul, Korea, in which the inverse/converse occurred, that is, the removal of a road made users better off. The Braess paradox is classical and those of us in transportation and operations research have used it regularly in our classes and lectures. What continues to fascinate is how this paradox keeps on getting discovered and, sometimes, rediscovered in other network settings -- from the Internet to electric power distribution and generation networks. There is a clear, deep lesson here as we begin to invest in infrastructure -- one has to capture users of the network systems and their behavior (do they cooperate or act independently/selfishly) in identifying which network components (roads, cables, lines, etc.) to add and/or improve. At the same time, we are seeing a convergence of interest in networks by researchers and practitioners in different disciplines -- from operations researchers / management scientists to computer scientists, physicists, and engineers, behavioral scientitsts, economists, and even political scientists. This is very exciting but proper effort must be taken to give proper citation to the scientific literature.

Our group at the Isenberg School of Management had the privilege of hosting the visit of Professor Dietrich Braess of the Braess paradox fame. His visit took place in 2006 and we have both the original article of his (which was in German), and the translation of it, which was done by Braess, Nagurney, and Wakolbinger, along with photos and additional material, posted at: http://supernet.som.umass.edu/cfoto/braess-visit/braessvisit.html

The Braess paradox is explicated at: http://supernet.som.umass.edu/facts/braess.html

For an excellent book on the price of anarchy, which is the ratio of the total cost to society evaluated at the user-optimized flow, to the total cost to society evaluated at the minimal system cost, see the book by the same name by Tim Roughgarden, published by MIT Press in 2005.