# How to make a marriage stable

We've always got our finger on the pulse here at Plus. This year's Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel has been awarded for work closely related to something we covered in an article back in August. The Prize was announced this morning and the laureates are Alvin E. Roth of Harvard University and Harvard Business School and Lloyd S. Shapley of the University of California, Los Angeles.

Alvin Roth. Image: Newtown graffiti.

The work they have been honoured for concerns matching problems: how do you best allocate students to universities, doctors to hospitals, or kidneys to transplant patients? Lloyd Shaply started investigating such problems in the 1950s, and substantially developed an area called cooperative game theory in the process. In 1962 he published a short paper together with the mathematician David Gale on pairwise matchings. They phrased their problem in terms of marriages: suppose you have a group of men and a group of women and you want to marry them off in a way that keeps everyone as happy as possible. A central concept here is that the matching should be stable: there should be no two people who prefer each other to the partners they actually got.

Shaply and Gale described a straight-forward algorithm for doing the matching and showed that it always leads to a stable outcome (this is the algorithm we looked at in our article Mixing doubles). They also showed that the algorithm leads to very different outcomes for the two groups, depending on how it is applied. If the women do the proposing and the men decide who to accept and who to reject, then the algorithm is optimal for the women: no other stable matching is better (from the women's point of view) than the one given by the algorithm. The same is true for the men if they do the proposing.

Shaply and Gale's work was theoretical, but in the 1980s Alvin Roth made the connection to real world applications. He investigated the National Resident Matching Program (NRMP), which had been introduced in the US to allocate medical graduates to hospitals and seemed to work rather well. Roth showed that the algorithm used by the program was closely related to that of Shaply and Gale and he conjectured that the reason why it worked was because it produced stable matches. He went off to investigate similar medical matching problems in the UK and found that stability really was the secret to success: algorithms that produced stable matches worked, while others didn't.