Stable Matching Algorithms

EPSRC research project GR/M13329

(1st October 1998 - 30th September 2000)

[A lattice of stable matchings]

Introduction

Stable matching algorithms have applications in a variety of real-world situations, perhaps the best known of these being in the assignment of graduating medical students to their first hospital appointments. In a number of countries, an automated scheme accomplishes this task annually, by finding a stable matching of students to hospitals, based on the preferences of hospitals among students and vice versa.

A matching is stable if no student and hospital would rather be matched with each other than remain with the partners that have been assigned to them in the matching. Therefore an unstable matching allows a student and a hospital who are not matched together to reject their allocations and become assigned to each other, thereby undermining the integrity of the matching. It has been convincingly argued [Rot84] that stability is the key property that underpins any successful matching scheme.

In the US, a centralised scheme administers the annual match of some thirty thousand graduating medical students to hospitals. This matching scheme, called the National Resident Matching Program or NRMP, has been in operation since 1952. Its counterparts in Canada and Scotland are called the Canadian Resident Matching Service (CaRMS) and the Scottish Foundation Allocation Scheme (SFAS) scheme respectively. Similar schemes are in operation in Norway [Eld00] and Singapore [TST99], involving the assignment of secondary school students to universities, and primary school students to secondary schools, respectively.

In the UK prior to August 2006, the problem of matching graduating medical students to hospitals was complicated by the fact that students sought not one post (as in the US and Canada, for example) but two posts, namely a medical post and a surgical post. Thus a straightforward adaptation of the algorithms used by the NRMP, for example, did not work in this context. Student-hospital matching schemes were employed by various UK regions prior to 1999, but these suffered from the fact that either they did not produce stable matchings (such as the disbanded Newcastle and Birmingham schemes [Rot90]) or they took many days to compute a stable matching (such as the former Edinburgh scheme [Mac94]). The advent of an efficient algorithm to form the basis of a student-hospital matching scheme suitable for use in a UK context was seen as a challenging open problem.

In 1998, Rob Irving [Irv98] described how techniques involving network flow and negative weight cycles can be used in order to solve this problem. Using his algorithm, a prototype version of the SPA matching scheme (the predecessor of SFAS) was designed and implemented by Rob Irving and Gordan Low as part of an MSc project in the Department of Computing Science at the University of Glasgow. This implementation was further extended to form the basis of the SPA program, which ran for the first time in academic year 1999/00.

Although the initial results were highly satisfactory (a report on the first year of operation of the SPA scheme is available), there remained some interesting open questions arising from this implementation, which offered scope for potential improvements. The Stable Matching Algorithms research project aimed to explore some of these open problems, many of which corresponded not only to the SPA scheme, but also to the wider context of two-sided matching schemes in general.

People

[Rob Irving]

The Principal Investigator of the Stable Matching Algorithms research project was Dr. Rob Irving (pictured left), and Dr. David Manlove (pictured right) was employed as a postdoctoral research assistant.

[David Manlove]

In addition, the following former students undertook Senior Honours or MSc in IT projects involving stable matching algorithms around the lifetime of the project:

Trond Elde, "Assignment Engine", Senior Honours project 1999/00.
Gordan Low, "Matching Medical Students to Hospital Posts in the West of Scotland", MSc in IT project 1997/98.
Gareth McSorley, "Stable Matching Algorithms", Senior Honours project 1999/00.
Mark Meenan, "The Two Hospital-Applicant Problem", MSc in IT project 1998/99.
Sandy Scott, "Implementation of Matching Algorithms", MSc in IT project 1998/99.

Publications

The following publications and papers arose from, or were closely associated with, the Stable Matching Algorithms research project:

R.W. Irving and D.F. Manlove, "The Stable Roommates Problem with Ties". Journal of Algorithms, volume 43, pages 85-105, 2002.
D.F. Manlove, R.W. Irving, K. Iwama, S. Miyazaki and Y. Morita, "Hard variants of stable marriage". Theoretical Computer Science, volume 276 (1-2), pages 261-279, 2002.
D.F. Manlove, "The structure of stable marriage with indifference", Discrete Applied Mathematics, volume 122 (1-3), pages 167-181, 2002.
R.W. Irving, D.F. Manlove and S. Scott, "The Hospitals/Residents Problem with Ties", in Proceedings of SWAT 2000, the 7th Scandinavian Workshop on Algorithm Theory, volume 1851 of Lecture Notes in Computer Science (Springer-Verlag, 2000), pp. 259-271.
W. Duckworth, D.F. Manlove and M. Zito, "On the approximability of the maximum induced matching problem". Journal of Discrete Algorithms, 3(1):79-91, 2005.
K. Iwama, D. Manlove, S. Miyazaki and Y. Morita, "Stable marriage with incomplete lists and ties", in Proceedings of ICALP '99: the 26th International Colloquium on Automata, Languages and Programming, vol. 1644 of Lecture Notes in Computer Science, pp. 443-452.
D.F. Manlove, "Stable marriage with ties and unacceptable partners", Technical Report no. TR-1999-29 of the Computing Science Department of Glasgow University, January 1999.
R.W. Irving, "Matching medical students to pairs of hospitals: a new variation on a well-known theme", in Proceedings of ESA'98: the Sixth Annual European Symposium on Algorithms, vol. 1461 of Lecture Notes in Computer Science, pp. 381-392.

Software

Part of the Stable Matching Algorithms research project involved the implementation of efficient algorithms for a number of stable matching problems. On this website, we have provided source code, executable files and documentation (in the form of READ_ME files) for the following problems:

The Stable Marriage Program (Ada 95). This program will take an arbitrary instance of the Stable Marriage Problem and will construct the man-optimal and woman-optimal stable matchings.
The Stable Roommates Program (Ada 95). This program will take an arbitrary instance of the Stable Roommates Problem and will determine whether a stable matching exists, constructing one if one does.
The Stable Roommates Program (Java). This program will take an arbitrary instance of the Stable Roommates Problem and will determine whether a stable matching exists, constructing one if one does.
The Hospitals/Residents Program (Ada 95). This program will take an arbitrary instance of the Hospitals/Residents Problem and will construct the resident-optimal and hospital-optimal stable matchings.