Another look at OR and US Presidential Elections

Mike Sheppard of Michigan State has a wonderful page that answers the question:  For each US Presidential Election, how few votes needed to change in order to reverse the result?  Most of us remember that in Bush-Gore 2000, just a few hundred Floridians needed to change their vote (269 by the official count:  I won’t get into the controversy on what the real number is (or even its sign!)) in order to give Florida to Gore who would then win the election.  But I hadn’t known that in 1976, Ford would have beaten Carter if just 9246 people (in Ohio and Hawaii) changed their vote!  The most one-sided election?  McGovern would have needed more than 3 million vote changes to beat Nixon in 1972.

Why is this operations research?  The question of which states need to switch is nicely modeled in integer programming, so this problem makes a nice (minor) modeling challenge.

You can also check out Mike’s use of linear programming to eat at McDonalds.

Tip of the hat to Greg Fulco for the pointer.

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.

Further Consolidation of Optimization Companies

i2 Technologies is going to be acquired by JDA Software for $346 million, continuing a wave of acquisitions in the optimization world (including ILOG and Dash). While this acquisition stays within the “supply chain optimization” space, it does cut down on the number of independent players. Manufacturing Business Technology makes an excellent point in the dynamics of this:

Ironically, ILOG may have contributed to the demise of several supply chain vendors—including i2—by selling its once-groundbreaking optimization technology to other companies wanting to create packaged systems. With so many so-called supply chain specialists relying on ILOG’s engine as the foundation of their systems, there was less differentiation in the market, and that made it easier for the Oracle’s and SAP’s of the world to move into the supply chain space.

Warrent Buffett has said “In business, I look for economic castles protected by unbreachable moats”. With great integer optimization codes available, the moat around supply chain optimization companies is quite narrow.