The title comes from a famous and very readable old paper that, ultimately, helped
one of the authors to win the 2012 Nobel Prize in Economics.
Suppose there is a village in which there are N young men and an equal number of
young women. Further, imagine that all these young people have a strict ordering on
their potential mates—so, say, N=3 and Alice knows she prefers Bob to Tom to Will
and each of the men has a similarly complete ordering on Alice, Jane and Mary. Is
it always possible to match these people into couples so that it never happens that
a man in one couple fancies the woman in another more than his own partner and the
other woman feels the same way about him? It turns out that it is possible and even
easy—Gale & Shapley give a deterministic algorithm.
Further, this rather old-fashioned and unrealistic view of relationships generalises
easily to certain kinds of labour markets: essentially the same algorithm had been
discovered independently and was (and indeed, still is) in use by an organisation
that matches junior doctors to training posts in hospitals. This real-world
applicability lead to an explosion of research by mathematicians, game theorists,
and economists and produced a large body of work, some of which I’ll describe during