Nobel prizes and marriage markets
The committee for selecting the 2012 winners of the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel (remember, it is not an original Nobel Prize) seems to have done a better job than the Peace Prize Committee. Alvin Roth and Lloyd Shapely have been awarded the prize “for the theory of stable allocations and the practice of market design”, and they are worthy winners.
There is plenty of commentary about their contribution in the media and blogosphere, so I’ll draw attention to just one element of Shapely’s work - the 1962 development of the Gale-Shapely algorithm with David Gale, and its application to marriage markets. The Information for the Public provided by the Royal Swedish Academy of Sciences gives a good summary of this work:
How should ten women and ten men be matched, while respecting their individual preferences? The main challenge involved designing a simple mechanism that would lead to a stable matching, where no couples would break up and form new matches which would make them better off. The solution – the Gale-Shapley “deferred acceptance” algorithm – was a set of simple rules that always led straight to a stable matching.
The Gale-Shapley algorithm can be set up in two alternative ways: either men propose to women, or women propose to men. In the latter case, the process begins with each woman proposing to the man she likes the best. Each man then looks at the different proposals he has received (if any), retains what he regards as the most attractive proposal (but defers from accepting it) and rejects the others. The women who were rejected in the first round then propose to their second-best choices, while the men again keep their best offer and reject the rest. This continues until no women want to make any further proposals. As each of the men then accepts the proposal he holds, the process comes to an end. Gale and Shapley proved mathematically that this algorithm always leads to a stable matching.
If we suppose that the men are making the offers, and the women considering them, the woman should reject all the offers except for her favourite, and keep stringing them along for the possibility that someone even better will come along. However, Gale and Shapely also pointed out a more important consideration in achieving the optimal result:
The specific setup of the algorithm turned out to have important distributional consequences; it matters a great deal whether the right to propose is given to the women – as in our example – or to the men. If the women propose, the outcome is better for them than if the men propose, because some women wind up with men they like better, and no woman is worse off than if the men had been given the right to propose. Indeed, the resulting matching is better for the women than any other stable matching. Conversely, the reverse algorithm – where the men propose – leads to the worst outcome from the women’s perspective.
It’s not an entirely intuitive result, but you are better off if you are the one making the offers. No prizes for shrinking violets! However, if the relative rankings of the men and women are consistent between different men and women, which party is making the offers becomes less important.
This is, of course, a simplified model and can fall apart under all sorts of conditions (such as offers flying in both directions, search costs, time constraints and the entry of new potential partners), which provided Alvin Roth with plenty of scope to further develop the work.
I should also note that despite the prize being for economics, Shapely prefers the label of mathematician to economist.