(1st October 1998 - 30th September 2000)
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.
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:
The following publications and papers arose from, or were closely associated with, the Stable Matching Algorithms research project:
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:
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.
The following links are to pages giving further information on the theory and applications of stable matching algorithms.