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.

Lloyd Shapley. Image © MFO.

Ironically the NRMP ran into problems caused by real-life marriages: as the number of female medical students grew there were more student couples, many of whom wanted to stay in the same area when they applied for internships in hospitals. The NRMP algorithm did not cope well with this demand. It had also been criticised because it favoured the hospitals, who in this case did the "proposing", over the students. In 1995 Roth, together with Elliott Peranson, was drafted in to improve the algorithm.

Roth also noticed that the original algorithm could be manipulated by those who receive the "proposals", in this case the students, by lying about their true preferences. He worked out exactly how such manipulation would function and benefit the student and made sure that the revised algorithm couldn't be tampered with in this way. Computer experiments have shown that, in practice, the algorithm is equally robust when it comes to manipulation by the hospitals. The new method was implemented in 1997 and has worked well ever since.

Shapley and Gale's work has delivered new insights into a whole range of problems, from matching kidneys to patients to internet auctions. "Even though these two researchers worked independently of one another, the combination of Shapley's basic theory and Roth's empirical investigations, experiments and practical design has generated a flourishing field of research and improved the performance of many markets," says the Nobel Prize press release. "This year's prize is awarded for an outstanding example of economic engineering."

You can find out more in the public information document on the Nobel Prize website and in the previous article here on Plus.