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.

Pushing back boundaries

It is 1AM here in Cork, and an adenoidal singer with a very eclectic song selection is screaming outside my hotel window, making it difficult to sleep. So I am reading “The Science of Discworld III: Darwin’s Watch” by Terry Pratchett, Ian Stewart, and Jack Cohen. Terry Pratchett is my second favorite author (next to Patrick O’Brian), and I enjoy the “Science of Discworld” series. In these books, chapters from a novelette by Pratchett alternate with scientific discussion by Stewart and Cohen.

The first part of the book has some good things to say about the scientific process. From Pratchett:

It [a large piece of machinery in a lab] also helps in pushing back boundaries, and it doesn’t matter what boundaries these are, since any researcher will tell you it is the pushing that matters, not the boundary.

That, in essence, is the problem with much of faculty reviews, paper refereeing, and conference paper selection. Most of the time, we evaluate the pushing, with insufficient attention to the boundary. Pratchett, as (almost) always, gets it right.

Operations Research and the US Presidential Election

I am in Cork, Ireland, attending the Irish Conference on Artificial Intelligence and Cognitive Science (I gave a talk on sports scheduling and three themes of modern integer programming: complicated variables, large scale local search, and logical Benders constraints). Conversation here (when an American is in the group: presumably without an American conversation is about hurling or something) is on the US Presidential Election. Some of the historical anomalies are a bit confusing. Why is it only now that Barack Obama “accepts” the nomination from the Democratic Party: shouldn’t he have decided on this long, long ago? What if he didn’t accept the nomination?

The most confusing aspect of the election process is our use of the Electoral College to elect the President. Rather than directly electing the President, voters vote for electors, with each state being given a set number of electors. For most states, all of the state’s electors are given over to just one candidate. This makes interpreting the polls quite difficult. One recent poll had Obama (the now-nominee of the Democrats) and McCain (the presumptive Republican) tied at 47% support each. A natural leap was to then assume that the election is a toss-up. But it is really the distribution of support that counts. It is possible to win the election for President of the United States with .00001% of the vote. For instance, suppose only one voter shows up in 49 states, and those voters vote for Obama, and 10,000,000 Republicans vote for McCain in New York, then Obama would lose the national popular vote 10,000,000 to 49 but he would have an overwhelming majority in the electoral college. While the results would never be that extreme, it is certainly possible (and has happened) to win the national popular vote and lose the electoral vote.

Interpreting polls gets more complicated when you try to address the uncertainties in the polls. For instance, the 47% results above are only for those in the survey who had a preference. There are a huge number of “undecided” voters who do not yet have a preference. How should they be handled as we try to figure out who is ahead (I hate this idea of elections as a “horse race”, but if the media is going to see it as a race, they could at least accurately represent the real race)?

Sheldon Jacobson (University of Illinois), Steven Rigdon, and Ed Sewell (both of Southern Illinois University Edwardsville) are addressing this issue by taking the current poll data and determining the probability of winning the election for each candidate. They have a fascinating website that is being constantly updated.

It is worthwhile to read their methodology section.

The mathematical model employs Bayesian estimators that use available state poll results (at present, this is being taken from Rasmussen, Survey USA, and Quinipac, among others) to determine the probability that each candidate will win each of the states. These state-by-state probabilities are then used in a dynamic programming algorithm to determine a probability distribution for the number of Electoral College votes that each candidate will win in the 2008 presidential election.

There is a full paper by the above authors along with Christopher Rigdon.

They point out a few limitations of their approach. Of course, the results are only as good as the poll data: if the poll data is off, then their results are meaningless. Further, they are not (currently) treating Maine and Nebraska correctly: those two states divide their electors by congressional district, while every other state is all-or-nothing.

Currently, they have Barack Obama with an 89% chance of winning, which is pretty high, but down from the 96% chance they had him at on July 31.

Dash in FairIsaac

“A.L.” who frequently posts on sci.op-research notes

To improve service for Xpress-MP users even further, Fair Isaac closed
Dash office in Englewood Cliffs, NJ. This is what recorded message
says when office number is called. Guys from this office are still available and working from their
basements. The question is for how long.

I sent an email to Alkis Vazacopoulos who pointed out there is a FairIsaac NY office right
across the Hudson (11.5 miles away) in Manhattan where people are working. Alkis continues to be extremely upbeat about how Dash is doing within FairIsaac. I really don’t think this rather minor office move is worth getting worked up over! After spending $32 million on Dash (admittedly a small amount of money to FairIsaac, representing 4 or 5 months of corporate earnings), I don’t think they are going to mess things up in the first six months.

The Numerati

Stephen Baker of BusinessWeek has just published a book entitled The Numerati, and has a blog related to the book.  The purpose of the book is to look how mathematicians are using data to to profile people in their shopping, voting, and even dating habits.

I am not exactly an unbiased reader of the book.  I talked with Stephen during the writing of the book, and he asked me to review the two pages he wrote about “operations research” (I made a couple suggestions which didn’t make it into the final version:  I guess this is my “cutting room floor” experience).  He was kind enough to send me a review copy of the book, which I received a few weeks ago.  He also accepted my invitation to speak here at CMU to the Tepper School Faculty and doctoral students.

The book is divided into chapters corresponding to the different uses of data:  “Worker”, “Shopper”, “Voter”, “Terrorist”, “Patient” and “Lover”.  For instance, in the “Voter” section, the emphasis is on predicting voter behavior.  In the past (perhaps), geography and economics were very good predictors of voting behavior.  Now, people seem much more in flux as to their behavior.  Perhaps there are better predictors.  Or perhaps there are useful clusterings of like-minded people that would respond to a particular pitch.  If Barack Obama were to identify a cluster of “people who blog about obscure  but important mathematical modeling methods”  and would send a mailer (or email more likely) showing his deep understanding of operations research and a promise to use that phrase in his acceptance speech, then perhaps he would gain a crucial set of voters.  Barack, are you listening?

I greatly enjoyed reading the book, and did so in one sitting.  For someone like me who perhaps could be seen as one of the Numerati, there is not much technical depth to the book, but there are a number of good examples that could be used in the classroom or in conversation.  There is a bit too much “The Numerati know much about you and can use it for good or EEEVVVIILLLL” for my taste, but  perhaps I take comfort in understanding how poorly data mining and similar methods work in predicting individual behavior.  The book is very much about modeling people, so essentially ignores the way operations research is used to automate business decisions and processes.  This is a book primarily about what I would call data mining and clustering, so there are wide swathes of the “numerati” field that are not covered.  But for a popular look on how our mathematics is used to characterize and predict human behavior, The Numerati is an extremely interesting book.

Where did the summer go?

This summer seems to have been far shorter than previous summers. I start teaching next week, and it seems so unfair: I want my summer back! I think the fault is partially the conferences I went to (CPAIOR in May, IFORS in July, and MIP in August) broke up the summer too much, so I never got the multiple weeks in a row to get things done.

In retrospect, it turned out to be a reasonably productive summer, at least in terms of things I could check off my Remember The Milk lists (I am an enthusiastic, but sporadic, follower of the Getting Things Done approach to organizing one’s life). So, in the interest of letting people know what faculty do when they are not teaching, here is what got checked off since I put in my final course grades in early May:

  • 5 journal referee reports
  • 14 conference paper reports
  • 3 promotion/tenure letters
  • 2 prize nominations
  • 6 papers handled in some way as journal Associate Editor
  • 2 prize committees chaired and completed
  • 3 conferences attended
  • 3 conference presentations
  • 4 professional society reports/presentations
  • 1 university presentation
  • 1 other presentation
  • 29 OR blog posts
  • 83 trips across campus for an espresso
  • 1 computer upgraded
  • 1 baseball game attended
  • 1 elephant touched

Plus research moved on (one student ready to graduate next week), though I need to make more time for that (I think any professor would much rather have “3 papers completed and submitted” than that mess above). And Alexander is hitting a baseball much better! So overall, not a bad summer, but I would like it to last a few more weeks!

For another take on the things faculty do, particularly in the summer, be sure to check out the FemaleScienceProfessor blog (and thanks to My Biased Coin for pointing that out!)