The Price of Anarchy

Most days, I go out for coffee two or three times with a gang of economists and finance professors.  As “the OR guy”, my role is generally to ask a few dumb questions, so they can patiently explain some economic effect, at which point one of them will disagree with the other, and they will go around in circles until it is time to go back to work.  Great fun!

One of the uniting and overriding themes of economics (at least as taught in US business schools) is the overriding value of individual choice and the way markets will lead to efficiencies.  Periodically, I get into discussions on how individual’s make their choices, and how some of those choices seem computationally impractical.  For instance, most of my asset allocation problems (i.e. spending my paycheck) seem to be well modeled by mixed-integer programs, but I don’t actually set up such programs, and I likely couldn’t solve them if I did.  I just make some choices and get by.  Am I doing the best thing?  “Yes”, say my economist friends, since otherwise I would do something else.  And maybe by including the cost of setting up and solving mixed integer programs, they are right.  But once in a while we reach an understanding that frictions and information issues and all the other things that get in the way of pure rational economics are important.  And we drink a bit more coffee.

I’m reminded of this in two ways recently.  First, Hari Jagannathan Balasubramanian, author of the “Thirty letters in my name” blog (and OR person) points out an Economist article on how removing roads might reduce traffic jams.  From the article:

Hyejin Youn and Hawoong Jeong, of the Korea Advanced Institute of Science and Technology, and Michael Gastner, of the Santa Fe Institute, analysed the effects of drivers taking different routes on journeys in Boston, New York and London. Their study, to be published in a forthcoming edition of Physical Review Letters, found that when individual drivers each try to choose the quickest route it can cause delays for others and even increase hold-ups in the entire road network.

My initial impression was “How the heck could they publish something like this?”.  Haven’t they heard of Braess’s paradox?  Well, I guess they had, and that the purpose of the paper was to see how it might occur in practice in Boston.

In Boston the group looked to see if the paradox could be created by closing any of the 246 links. In 240 cases their analysis showed that a closure increased traffic problems. But closing any one of the remaining six streets reduced the POA of the new Nash equilibrium.

Still seems a funny paper for Physical Review (but I should withhold judgment until I read it).   In general, algorithms papers in Science, Nature or many of these other “non-OR, non-CS, non-Math” journals seem a little more suspect than your average Operations Research paper.

The second aspect of individual choice versus centralized choice is in the current financial crisis.   Here it seems like individual (firm) choice is great until they get a little stuck, and then they need centralized help to get out of their mess.  I do believe in individual choice, but I think somewhat better operations research models might have helped them avoid this mess in the first place.  And perhaps some OR will help out of this by pointing out how $700 billion might be allocated in order to have best, most fair, effect.

Added September 26. The paper from Physical Review Letters is now available (search on “Price of Anarchy”0.  I think (and an email from network-guru Anna Nagurney confirms:  see her Letter to the Editor of the Economist) that this is a case of physicists rediscovering what others have known for a long time.  I did find the detailed analysis of Boston quite interesting though.