Monday, March 14, 2016

Gale-Shapley was rejected twice for being too simple

One of Mr Shapley’s better-known achievements is the Gale-Shapley matching algorithm, which he devised after an old university friend (David Gale) asked for help to solve a problem. Given two groups of people, each with slightly different preferences, is there a way to match them in such a way that people aren’t constantly ditching their partner? After much head-scratching, Mr Gale suspected there was no solution, but could not prove it. As Mr Shapley told it, the solution took him the best part of an afternoon.

The solution is as follows: imagine a hall full of heterosexual singletons, with equal numbers of men and women. They have done enough idle chitchat to know who prefers whom—everyone has their own ranking of people in the other group. In round one, a starting gun is fired, and each man approaches his favourite women. The women reject everyone apart from their favourite, and then the process is repeated in a second round. No man should look too smug having not been rejected; if a woman is made a better offer, she should ditch an earlier one. The rounds continue until everyone is matched. The outcome is ‘stable’; no two people would prefer to partner with each other than their current match, otherwise the algorithm would already have paired them.

Mr Shapley wrote up the paper with Mr Gale, proving without equations that this method would always yield a stable solution. After two initial rejections (for being too simple) it was published, and fifty years later in 2012 he won the Nobel Memorial Prize in Economic Sciences “for the theory of stable allocations and the practice of market design” (see Free Exchange column here).
--The Economist on Lloyd Shapley (1923-2016)