Category: Research

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.

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.

In New York doing Mixed Integer Programming

I am in New York at Columbia University, attending the Mixed Integer Programming (MIP) workshop. This workshop series was started about 5 years ago, and has grown into a hundred person workshop/conference. It is still run pretty informally (no nametags: I guess it is assumed that everyone knows everyone else. Having just shaved off my beard, I would prefer letting people know my name rather than relying on their ability to recognize me!).

So far, the most interesting aspects have been approaches much different than current practice. Rekha Thomas of the University of Washington had a very nice talk on a variant of Chvatal Rank (called Small Chvatal Rank) which involved using Hilbert basis calculations to find normals of facets of the integer hull (you can think of this as Chvatal rank independent of the right hand side). I’m not sure if it is useful, but it certainly generated a number of neat results. Peter Malkin of UC-Davis talked about using systems of polynomial equations to prove the infeasibility of problems like 3-coloring. I have seen versions of this work before (given by coauthor Susan Margulies) and always begin thinking “this can’t possibly work” but they are able to prove a lack of 3-coloring for impressively large graphs.

One of the most intriguing talks was given by John Hooker, who is exploring what he calls “principled methods of modeling” (or formulation). John has a knack of looking at seemingly well-known approaches and seeing them in a new and interesting way. It is not yet clear that this principled approach gets you anything that is not folklore formulation tricks, but it is interesting to see a theoretical underpinning to some of the things we do.

Postscript. Now that I think about it a bit more, John did present a problem that would have been difficult to formulate without his principled approach. I’ll try to track down an explanation of that example.

NL8 Solved!

Almost 10 years ago, Kelly Easton, George  Nemhauser and I created something called the Traveling Tournament Problem.  The name is George’s:  I wanted to call it the Problem where Teams Play a Round Robin and Travel and Stuff, but George’s name is catchier.  The problem came from work we had done with Major League Baseball in creating their schedule.  Rather than try to post 150 pages of requests and requirements (which MLB would never let us do anyway), we abstracted out the key aspects of the schedule.  Those were:

  1. Travel:  a wish to keep the total travel down, and
  2. Flow: a wish not to be home or away for more than 3 series consecutively.

I also added a “no repeat” constraint:  if A is at B, then B cannot be at A in the next time slot.

When we put this together, we also put together the website http://mat.tepper.cmu.edu/TOURN to keep track of results and that turned out to be a great idea.  By having one site with results and instances, it has been easy to keep track of “current records”.

When I first worked on this, my goal was to show how some of our methods that we use for MLB could handle problems of reasonable size for the Traveling Tournament Problem.  That turned out to be impossible to do.  The Traveling Tournament Problem is hard!  Even solving the eight team problem turned out to be nontrivial.  Six teams is doable with a bit of work.

Kelly Easton, in her dissertation, put a lot of effort into the TTP, and even solved the eight team problem.  She used a network of 20 computers over the course of a week to prove optimality.  Unfortunately, she did not include the “no repeat” constraint, so we didn’t have the result for exactly the right problem.  While we believed that adding the “no repeat” constraint wouldn’t affect things too much, Kelly graduated, began working (for my small sports scheduling business) and we never solved the real problem.

Despite lots and lots of people working on the TTP, proving the optimality of a known solution to NL8 with value 39721 has been elusive.  In fact, relatively little (but some, thanks to Melo, Ribeiro, and Urrutia) work has been done on improving lower bounds.

I was thrilled yesterday to get an email Stefan Irnich of Aachen who, together with his master student Ulrich Schrempp, claims to have proved the optimality of 39721.  But here is when it gets hard.  How do I know?  It is easy to check feasible solutions, but unless there is a simply calculated lower bound, it it hard to confirm optimality.   Fortunately Stefan sent the slides of his work, and it seems clear that the approach they are taking is one that would work, and would be stronger than what others have tried.  So I have no hesitation in proclaiming that NL8 is now solved!  I am sure there are easily dozens (OK, half-dozens … OK, a half-dozen) people who are excited about this, and I am one of them (and it is my blog).

On to NL10!

Poker and Operations Research

I just attended a fantastic talk by Michael Bowling of the University of Alberta entitled “AI After Dark: Computers Playing Poker” where he described work by the U of A Computer Poker Research Group. Like most artificial intelligence research (particularly in games), there is no veneer of trying to mimic the human brain in this work: it is all about algorithms to compute optimal strategies, which puts it solidly within operations research by my view.

Much of his talk revolved around a recent “Man-Machine Poker Championship” where a program they have developed played against two professional poker players: Phil “The Unabomber” Laak and Ali Eslami. Laak is known from TV appearances; I haven’t seen Eslami, but he has a computer science background and understands the work the U of A researchers do, so that might make him an even more formidable opponent. The results were, at one level, inconclusive. The humans (playing in “duplicate” poker) won two of the four 500 deal matches, lost one, and one was tied. The overall amount of money “lost” by the computer was very small. I have no doubt that most humans facing professionals would have lost a lot more. So having a competitive program is already a big step. Like most who lose at poker, Michael claimed “bad luck” but he has the technical skills to correct for the luck, and was pretty convincing that the computer outplayed the humans.

One interesting aspect is that the program does no “opponent analysis” yet, though that is an extremely active research area (75% of the U of A’s efforts, Michael said). Given a couple more years, I am pretty confident that these programs will start giving the pros a run for their money. Michael said that one goal of their work could be stated: they want to make Phil Helmuth cry. That seems a little less likely.

On the technical side, the presentation concentrated on some new ways for systems to learn to solve huge (1000000000000 state) extensive form games. They have a neat system for having systems learn by playing against themselves. It takes a month of serious computation to tune the poker player, but the method may have other applications in economics. Check out Michael’s publications for more information.

Definitely one of the best talks I have heard in a long time!

ORSNZ Recap

I was at the OR Society of New Zealand conference last week, and failed to blog it.  I am so ashamed!  You can check out some pictures and other information about the conference at its site.  I was one of the speakers, so you can see me in action.

A highlight of the conference for me was the plenary session given by Gerard Cachon of Wharton, who is visiting the University of Auckland this year.  He gave a talk on the use of game theory in operations management.  I have been a little dubious of incredible fad for game theory in the analysis of supply chains.  The assumptions of game theory are pretty strong, and it is not clear that much of the analysis is giving any real insight.  Gerard is very aware of these limitations, and much of his talk was illustrating how difficult it is to conclude things from a game theoretic analysis.  For instance, there is often a huge problem with multiple equilibria, with game theory providing little guidance as to what the “right” equilibrium is.  After the talk, I felt much happier about game theory in OM:  as long as people are talking about the limitations, I can have much more confidence when they make conclusions.

Operations Research and Voting Systems

Almost 20 years ago, I, along with my co-authors John Bartholdi and Craig Tovey, looked at the social choice (or voting theory) literature through the lens of operations research. Over and over again, we would read “we tried to figure out the winner under this rule, but it got too complicated”, or “we think A is the winner, but we are not sure”. Of course, to those trained in OR (or computer science or other related fields) this is a sure sign of some form of computational complexity. And sure enough, we found a number of NP completeness results. My two favorites are

  1. For a rule proposed by Charles Dodgson (aka Lewis Carroll of “Alice in Wonderland” fame), it is NP-complete to determine a winner
  2. there are rules for which it is easy to determine a winner, but it is hard to determine how to “manipulate” your vote by misrepresenting your preferences so as to ensure a preferred outcome.

These results were published in the social choice literature (John has a page detailing these and other results that gives complete references), where they languished for a decade or so, before being rediscovered by a generation of computer scientists and computationally minded economists. Of course, complexity theory has moved along a lot (Complexity Zoo lists 462 complexity classes) so the issues looked at are now much more subtle than our work but it is heartening to go to conferences like COMSOC and see many papers reference our early work as “foundational”. Those papers have shot up my rankings in Google Scholar!

All this started when Bartholdi came across the voting system to elect the Venetian Doge. The rules are a little complex, involving ten rounds of “voting” with some of the rounds involving choosing winners at random. From the Wikipedia article:

Thirty members of the Great Council, chosen by lot, were reduced by lot to nine; the nine chose forty and the forty were reduced by lot to twelve, who chose twenty-five. The twenty-five were reduced by lot to nine and the nine elected forty-five. Then the forty-five were once more reduced by lot to eleven, and the eleven finally chose the forty-one who actually elected the doge.

What could be the reason for such a convoluted system? We never got back to looking at the Doge, but recently Miranda Mowbray and Dieter Gollmann have examined this in a paper presented at the IEEE Computer Security Foundations Symposium. They do a very thorough analysis of the rules and discuss its effect on minority representation and other issues. But at the end, they come up with a non-mathematical argument for the approach:

Schneier [in the book Beyond Fear] has used the phrase “security theatre” to describe public actions which do not increase security, but which are designed to make the public think that the organization carrying out the actions is taking security seriously. (He describes some examples of this in response to the 9/11 suicide attacks.) This phrase is usually used pejoratively.

However, security theatre has positive aspects too, provided that it is not used as a substitute for actions that would actually improve security. In the context of the election of the Doge, the complexity of the protocol had the effect that all the oligarchs took part in a long, involved ritual in which they demonstrated individually and collectively to each other that they took seriously their responsibility to try to elect a Doge who would act for the good of Venice, and also that they would submit to the rule of the Doge after he was elected.

The US system for President is also pretty convoluted, particularly when the Supreme Court gets involved, but we have a way to go before we get to the Venetian level. But there is some level of ritual and even randomness involved, making the article more pertinent to current systems than it might first appear.

Coordinating supply chains

I just attended a talk given by Tava Olsen from Washington University in St. Lous. The talk was held at the business school at the University of Auckland (who are building a spectacular new building nearby). Her talk was an overview talk on supply chain coordination. For a non-specialist like myself (albeit one who often attends supply-chain-oriented conferences), it was really useful to get an overview of how research in the area of supply chain coordination works.

Here is Tava’s “Make your own Coordination Paper” recipe for research in this area (as I interpret it):

  1. Find a supply chain and identify the actors
  2. Determine the optimal decentralized actions for the actors
  3. Determine the optimal centralized result (perhaps by pretending all the actors were one)
  4. Find an implementable contract so that the decentralized actions give the centralized result.

The example she gave was a simple two stage supply chain with a retailer ordering from a supplier in a single period, one order environment. The retailer’s problem is a simple newsvendor problem, with the amount ordered limited by the losses due to possible overordering. But if the supply chain was centrailized (think of the retailer and the supplier owned by the same company), then the loss of overordering is less (it is the production cost rather than the higher wholesale cost), so more is ordered. The result is more expected profit in the supply chain. But, crucially, that higher expected profit occurs at the supplier, not the retailer who does the ordering. How can the supply chain be coordinated so that the pair find the higher profits?

There are lots of possible solutions: a fixed payment from the supplier to the retailer for ordering the higher quantity would do, but that is rather inelegant (there are few contracts written of the form: “I’ll pay you $1000 for ordering exactly 621 items”) and requires a huge amount of information on the part of the supplier. “Better” solutions (more implementable, while still coordinating) might involve “buyback” contracts where the supplier agrees to take back unsold inventory at a particular value or quantity flexibility contracts, where the supplier agrees to provide any amount within a range of values.

Tava continued with a very nice example of supply chains like those between automobile manufacturers and suppliers whereby parts absolutely must be provided on time (penalties of thousands of dollars per minute late are common). In such cases, suppliers must expedite parts in the case of possible shortages, which can be a very expensive process. Coordinating across such a supply chain means having the manufacturer make decisions that keep in mind the expediting costs.

I was very happy to get such an overview talk: it put a lot of supply chain research into perspective.

Is most published operations research false?

Seed Magazine has an excellent article entitled “Dirty Little Secret” with a subtitle of “Are most published research findings actually false? The case for reform.” (Thanks to the Complex Intelligent Systems blog for pointing to this). The article begins with some amazing statistics:

In a 2005 article in the Journal of the American Medical Association, epidemiologist John Ioannidis showed that among the 45 most highly cited clinical research findings of the past 15 years, 99 percent of molecular research had subsequently been refuted. Epidemiology findings had been contradicted in four-fifths of the cases he looked at, and the usually robust outcomes of clinical trials had a refutation rate of one in four.

Why has this happened?

The culprits appear to be the proverbial suspects: lies, damn lies, and statistics. Jonathan Sterne and George Smith, a statistician and an epidemiologist from the university of Bristol in the UK, point out in a study in British Medical Journal that “the widespread misunderstanding of statistical significance is a fundamental problem” in medical research. What’s more, the scientist’s bias may distort statistics. Pressure to publish can lead to “selective reporting;” the implication is that attention-seeking scientists are exaggerating their results far more often than the occasional, spectacular science fraud would suggest.

Ioannidis’ paper “Why Most Published Research Findings are False” goes into a more in-depth examination of why this happens. This is no surprise to those who understand statistical significance. If 20 groups do similar research, it is pretty likely that at least one group will have a finding “at the 95% significance level” just by blind luck. And if that is the group that gets to publish (since proof of significance is much more interesting than non-proof), then the scientific literature will, by its nature, publish false findings. This is made worse by issues of bias, conflict of interest, and so on.

Ioannidis continues with some corollaries on when it is more likely that published research is false:

Corollary 1: The smaller the studies conducted in a scientific field, the less likely the research findings are to be true.

Corollary 2: The smaller the effect sizes in a scientific field, the less likely the research findings are to be true.

Corollary 3: The greater the number and the lesser the selection of tested relationships in a scientific field, the less likely the research findings are to be true.

Corollary 4: The greater the flexibility in designs, definitions, outcomes, and analytical modes in a scientific field, the less likely the research findings are to be true.

Corollary 5: The greater the financial and other interests and prejudices in a scientific field, the less likely the research findings are to be true.

Corollary 6: The hotter a scientific field (with more scientific teams involved), the less likely the research findings are to be true.

This got me thinking about the situation in operations research. How much of the published operations research literature is false? One key way of avoiding false results is replicability. If a referee (or better, any reader of the paper) can replicate the result, then many of the causes for false results go away. The referee may be wrong sometimes (in a statistical study with a true 95% confidence, the referee will get the “wrong” result 5% of the time), but the number of false publications decreases enormously.

Most major medical trials are not replicable: the cost of large trials is enormous, and the time required is too long. So you can expect false publications.

Much of OR is replicable. For more mathematical work, the purpose of a proof is to allow the reader to replicate the theorem. For most papers, this is straightforward enough that the field can have confidence in the theorems. Of course, sometimes subtle mistakes are made (or not so subtle if the referees did not do their jobs), and false theorems are published. And sometimes the proof of a theorem is so complex (or reliant on computer checking) that the level of replicability decreases. But I think it is safe to say that the majority (perhaps even the vast majority) of theorems in operations research are “true” (they may, of course, be irrelevant or uninteresting or useless, but that is another matter).

For computational work, the situation is less rosy. Some types of claims (“This is a feasible solution with this value to this model”, for example) should be easy to check, but generally are not. This leads to problems and frustrations in the literature. In my own areas of research, there are competing claims of graph coloring with k colors and cliques of size k+1 on the same graph, which is an inconsistency: I am putting together a system to try to clear out those sorts of problems. But other claims are harder to check. A claim that X is the optimal solution for this instance of a hard combinatorial problem is, by its nature, difficult to show. Worse are the claims “this heuristic is the best method for this problem” which get into many of the same issues medical research gets into (with bias being perhaps even more of an issue).

I think this is an issue that deserves much more thought. Very little of the computational work in this field is replicable (contrast this to my review of work of Applegate, Bixby, Cook, and Chvatal on the Traveling Salesman Problem, which I think is much more open than 99.9% of the work in the field), and this leads to the confusion, false paths, and wasted effort. We are much more able to replicate work than many fields, but I do not think we do so. So we have many more false results in our field than we should have.

Quantum Computing and Learning from Blogs

Scott AaronsonEver since I heard about quantum computing (it arose in the 1970s, but most of the really visible stuff started in the mid 1980s, see the Wiki timeline), I have been skeptical. This skepticism arose from a view that quantum computers could solve NP-complete problems in polynomial time. I was randomly wandering the blogosphere when I can across “Shtetl-Optimized” by Scott Aaronson, with the subtitle “Quantum computers are not known to be able to solve NP-complete problems in polynomial time”. Well, perhaps everyone else knew that, but it was somewhat annoying that something I knew for two decades was dead wrong. While practical quantum computers still seem some time away (it seems the state of the art is factoring 15=3×5), trying to determine the effect of quantum computing on OR seems like an interesting question.

One post of Scott’s that I like very much is his “The Hiring Scott Aaronson FAQ“, where he lists some of the questions he was asked in his job search (he is a postdoc at my alma mater, the University of Waterloo’s Department of Combinatorics and Optimization). I’ve interviewed for a job or two in the couple years this blog has been going, but I have not been bold enough to talk about it. Scott uses the entry as a very quick survey of what he believes in, and the interviewers don’t come across like idiots (I guess I would have asked about half the questions myself).

Check out also his article “NP-Complete Problems and Physical Reality“published a couple of years ago in the SIGACT News complexity column. Having lived through an era when NP-completeness results were being churned out by the boatload with only a few providing real insight and advance (kinda like approximation results these days), I have not advanced very much beyond what I knew ten years ago, but Scott’s writing make this look pretty interesting again.

Finally, I am jealous of Scott’s ability to write well enough and intriguingly enough to generate dozens of comments on each of his posts. He points to the following review of his blog:

OK, on to the second breakfast link. Bill Gasarch has reviewed my blog for SIGACT News (scroll down to page 15), together with Lance Fortnow’s and Luca Trevisan’s. Favorite quotes:

Lance is Walter Cronkite. Scott is Stephen Colbert.

The name of the blog, ‘Shtetl-Optimized’ does not really say what it is about. With this in mind one can never say Scott has gone ‘off topic’ since its [sic] not clear what the topic should be.

Perhaps I am sticking to the topic too much!