(1st October 1998 - 30th September 2000)

[ Top | Introduction | People | Publications | Software | Links ]

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.

[ Top | Introduction | People | Publications | Software | Links ]

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. |

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.

[ Top | Introduction | People | Publications | Software | Links ]

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.

[ Top | Introduction | People | Publications | Software | Links ]

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.

To demonstrate a typical algorithm in action, we have provided a Java Applet which incorporates the Gale/Shapley algorithm for the classical Stable Marriage problem.

[ Top | Introduction | People | Publications | Software | Links ]

The following links are to pages giving further information on the theory and applications of stable matching algorithms.

- Scottish Foundation Allocation Scheme. This is the website for the matching scheme in Scotland which handles the annual allocation of Pre-Registration House Officers (PRHOs) to hospital appointments.
- SPA scheme. This web document, written by Gordan Low, contains an overview of the algorithms used by the SPA scheme (the predecessor to SFAS, as mentioned above).
- National Resident Matching Program (NRMP). This is the website for the matching program in the US which involves the annual allocation of some 31,000 graduating medical students to hospital appointments.
- Canadian Resident Matching Service (CaRMS). This website is for the Canadian counterpart of the NRMP. It contains a discussion of how the matching algorithm works.
- National Matching Services Inc. This is the website of a Toronto-based commercial organisation which specialises in administering and supporting matching programs in the US and Canada, including the NRMP and CaRMS.
- Al Roth's game theory and experimental economics page. Contains a bibliography of two-sided matching markets.

[ Top | Introduction | People | Publications | Software | Links ]