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)