Monday 15 October 2012

Understanding the Nobel Prize

It's not often - maybe never before now - that I've understood technical aspects of the work behind a Nobel Prize.

But today I found out that Shapley has shared the Nobel Prize in Economics with Al Roth.  Sadly Gale has died so cannot be awarded the prize.

The crux of the work is the Gale-Shapley algorithm on "stable marriages."  So yes, deep down the Nobel prize has been awarded for an algorithm.

The idea of a stable marriage is when men want women and women want men, but we don't want marriages which will break up.  A marriage will break up if there is an "unstable pair", two people who would rather be with each other than their spouses.   It's all theoretical - it doesn't assume same-sex marriages, polygamous ones, or romantic preferences that change with time.  But it leads to a lovely algorithm, and interesting insights.  It's really interesting stuff and lovely.  I've written some papers on it from the point of view of constraint programming, my research area.

11 years ago I co-wrote a paper on this topic for the big conference in Constraints.   It was a privilege to work with Rob Irving and David Manlove.   And I don't think that Barbara or David or me will mind admitting that in that case the key authors of the paper were Rob and Patrick Prosser.   The thing that interested me on the topic was that it turned out we could turn the efficient Gale-Shapley algorithm into an efficient constraints algorithm (in a certain technical sense, no need to go into that here.)    But what was even better was that this technical efficiency turned out to be interesting in its own right, and analysis of it led to a big part of a PhD, specifically Martin Green's to be precise, Holloway, 2005.   Not the only PhD in constraints and stable matching neither - here's to Chris Unsworth -  but maybe the one that took our work in an unexpected direction.

However for practical purposes, our work in Constraints didn't really take off.  We hoped it might, but it didn't.  The real practical purpose of this work is kidney-matching.  This is a huge ethical problem for which people quite rightly (in most people's view) don't think money is the right solution.  The solution is a stable matching where everyone benefits.   That's what part of this Nobel prize for, for Al Roth.  And that is what David Manlove uses this work for - of course extending it as well for scientific interest, but also helping people get kidney transplants they wouldn't otherwise get.

So this is what a Nobel Prize means if you understand something about its technicalities.  It turns out it has influenced people many decades later in other countries, and then their work influences other people in turn, in a research area some way off the original.  And then people get new kidneys.

p.s. Yes I know it's not really the Nobel Prize, it's the Nobel Memorial Prize, but everybody calls it the Nobel Prize in Economics including the BBC and the Guardian.