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.

Not the way the world's greatest sportest event should be

Thanks to Neil Moore for this link. The article quotes one Prof Forrest: "We have identified four sports where there is virtually no chance that anyone from a poor country can win a medal - equestrian, sailing, cycling and swimming"

Meanwhile today the UK just won a gold medal in triathlon which combines two of those sports (plus running.) And celebratory BBC news article says "Further medals could follow on Tuesday in cycling, dressage and windsurfing." Which are - you guessed it - three of the four rich-country sports. With the triathlon gold partly for swimming to complete the set. 

I am genuinely happy about British success but at the same time very saddened that poor countries are eliminated from competition in many key areas of the games. Not the way the world's greatest sporting event should be. 

Athletics is more or less an exception. If you can run fast you can make enough money to compete at the highest level wherever you are. And critically be identified early enough to be trained well enough in the USA. So I think it's wonderful that the 10000m champion was born in Somalia, grew up in the UK and ran for Britain, and lives in Portland Oregon.

Shooting a googlewhackblatt in the foot

A googlewhackblatt is a single word query to Google that gets one hit.   And one such word is autopedoballistic.   Made up to mean shooting yourself in the foot.   But since I have just posted this page, I am guilty of autopedoballistics by ruining it myself.  So here's the proof.

Ada Lovelace day

Kind of sad that I didn't see Ada Lovelace day coming.   I don't know if it needs better publicity, but I hope it's no reflection on a perceived lack of importance of women in computing.  For sure we're not at a point where there's no need to enhance women's position in the discipline.

So a woman who influenced me in computing?

The more I thought about it the more obvious it became.

Margaret Gent, of course.  My mother.   So apart from obvious motherly things, then here are some things about her which influenced me in computing.

Curta Calculator, from Wikipedia

She gave my dad his Curta calculator, roughly 1950 or so.    He later gave it to me, and I still think it is the most beautiful object I own.  Bearing in mind of course I don't own my wife or children.


A long time ago, she made a 4 bit adder out of components, a large piece of board, switches and solder.    To illustrate how computers work for her students - she was a maths teacher.   I don't know when it was done but the 1960s is a safe bet - I remember it when I was very young.   It seemed almost magical to me.  Brilliant.

TI-57 Calculator, from Wikipedia

She bought me - to be honest I don't know how much the split of decision making was with my father - my first programmable calculator, the wondrous TI-57.    Not quite my first programming as that had been done on an HP 25 borrowed by my dad from work - or lent by Spencer Noble.

She got my name into print for computing for the first time by commissioning me to calculate a table for her book "Maths for Scientists".    So yes, my first ever computing publication in any form was published by Mills & Boon!

Fairey Swordfish, image from Wikipedia

Nothing to do with computing.    But during World War II, as a radar technician at TRE Malvern, she once swapped cockpits in a Swordfish in mid air.   A good idea to look at the picture, as you'll see this is not swapping seats in a jumbo, it's a lot more fun than that.   More notably perhaps, to this day she denies it as being anything of note to have done it.


Maybe not so surprising that the first thing I did when I was promoted to Professor was to make sure my mother could come to the ceremony.

How to steal a laptop

Years ago my colleague (who we'll call Woolf T Flywheel) had his laptop stolen.  How did it happen?

His laptop developed a fault, so he called up Compaq to get it repaired under warranty.  (I told you it was years ago, they were later bought by HP.)   They sent out DHL to take it back to their service centre. 

A day or two later a nice chap from Compaq rang up to ask what the problem was with the laptop.   Woolf told him, of course.

A few days later Woolf rang up Compaq to ask what had happened to his laptop.   The reply was "What laptop?  We never got it."  

It had been stolen, the police came to the office.  It more or less must have been an inside job at DHL. Somebody's insurers (probably DHL's) paid Woolf back, and laptop prices had fallen so much that the difference was enough for Woolf to buy a £600 fat boy lazy chair (or was it two?)   

But what has always stuck in my mind was the brilliance of ringing up to ask what was wrong with the laptop.    It did two things at once.  First, it delayed for a few days Woolf ringing up to ask what had happened.  And second, they could find out what was wrong with it so they could fix it  before selling it!  

Future Theatre Director

Just came back from the Shakespeare School's Festival. 4x 30 minute productions by various high schools. Outstanding production of The Tempest directed by one Alex Horan of Balwearie High School. Turns out she's 16! Director of the charity (who also commisioned the animated Shakespeare for S4C) says she wants to work as a director - she could make it.

55% doesn't seem right.

In the general hoopla about the LibDem-Con coalition, one thing has received little attention, though it has been picked up by a couple of people like Peter Hennessey.

This is that to make fixed term parliaments stickable, they want to change the law so that a government can't be brought down without a 55% majority against them.   But this is to confuse two things.   One is whether a government survives or not, and the other is whether to have a general election.   In principle they are separate.   The fact that David Cameron is PM now should not give him a lease until 2015, even if all the individual MPs do have that lease.    He needs to be able to be brought down in a confidence vote, possibly leading to another prime minister, either Tory or from another party.

For a confidence vote in the government, which means in practice in the Prime Minister, it should be 50% + 1 against to win.   Otherwise there is the ridiculous idea of a government which can't put any of its business through, but which can't be kicked out.

On the other hand, to stop the PM calling an election when he wants, you need a larger number than 55%.    Many PMs with a large majority could have got 55% of their MPs on their own.   Both of Tony Blair's first parliaments for example, and the second of Maggie's three victories.    So it doesn't really stop a dominant PM calling an election.   Even in this parliament, Tories plus Lib Dems have more than 55%, so could if they agreed force an election.

And this seems a nicely tuned number ... Con + LD is > 55% so can call an election anytime.  But Con >  45% so can't be defeated on a vote of confidence anytime.  So, theoretically, Cons could discard the coalition and form an invincible minority government.    Have the Lib Dems been sold a pup on this one?

In practice confidence votes to bring down a government are very rare - the last one in 1979 only months before the end of the parliament.    So it's unlikely this matters very much.  But my main point remains.  There needs to be the standard threshold for bringing down a government, but a much higher threshold than 55% to call an election.