Background
Motivation
In many real-life situations there is a need to match a set of applicants (for example medical students) to a set of posts (for example hospitals) where there may be preference lists on one or both "sides" (for example each student may rank three hospitals in order of preference) and capacities may be present (for example a hospital hj may have places for at most cj students). In a number of countries worldwide, centralised matching schemes automate the process of matching students to hospitals based on such preference and capacity information. These schemes incorporate efficient algorithms to solve a matching problem that is typically a variant of the classical Hospitals / Residents problem (HR).
Given the size of the datasets that are usually involved in such applications (the National Resident Matching Program in the US handles annually the assignment of some 31,000 graduating medical students, also known as residents [8]), clearly the efficiency of the underlying algorithms is of paramount importance. Moreover, given the implications of an individual's assignment for their quality of life, it is vital for the algorithms to attempt to produce an outcome that is, in a certain technical sense, optimal according to the supplied preferences.
It has been convincingly argued [6] that, where preferences exist on both sides of a "two-sided market" such as the medical matching scenario as outlined above, optimality here corresponds to stability. Informally a matching (i.e. an allocation of applicants to posts that respects the given capacity constraints) is stable if no two agents (in this case a medical student and a hospital consultant) would prefer to be matched together than remain with their current assignments. Such a pair would form a private arrangement outside of the matching, undermining its integrity.
Centralised matching schemes such as the NRMP and its counterparts in Canada and Scotland [9,4] produce matchings of medical students to hospitals that are stable in the underlying instance of HR. These schemes employ extensions of the classical Gale / Shapley (GS) algorithm [1] for HR, which operates in linear time. The GS algorithm was originally described in the context of the classical Stable Marriage problem (SM), which is a one-one restriction of HR (a many-one problem) in which the medical students and hospitals are more commonly referred to as men and women respectively.
Stable matchings in the context of SM, HR and related problems have been extensively studied for several decades [1,5,2,7]. There is a rich body of structure underlying an instance of SM, leading to a range of efficient algorithms for associated stable matching problems, as summarised by Gusfield and Irving [2]. However what has received less attention is the case where preference lists may include ties, or other forms of indifference [4]. For example, a large hospital with many applicants may find it difficult to rank all these students in strict order of preference, preferring instead to group applicants in "tied" batches. By constrast to the strictly ordered case, only recently is it the case that stable matching problems involving ties have been considered from an algorithmic perspective, and many open problems remained at the time this project was proposed.
Similarly, other stable matching problems arise naturally in practical applications, where preference lists need not include indifference. These include the Student / Project Allocation problem (SPA), a generalisation of HR, where students are to be assigned to projects offered by lecturers, subject to capacity constraints involving both projects and lecturers, and preference lists supplied by both students and lecturers. Various notions of stability arise, leading to associated algorithmic questions.
Outcomes
This project has led to a greater understanding of the algorithmic behaviour of stable matching problems with indifference. In addition, due to a broadening of its scope, the project has led to new algorithmic results for a range of stable matching problems where preference lists need not involve indifference, motivated by real-world practical applications.
For HR where preference list may include ties, we have formulated a collection of results that relate to the hardness of computing so-called "weakly stable" matchings in this context, including a range of approximability results. For so-called "strongly stable" matchings, we presented an efficient algorithm for finding such a matching, should one exist. Also, for the so-called "super-stability" criterion, we formulated a variety of algorithmic results for problems concerned with super-stable matchings, including the problem of finding "fair" super-stable matchings (favouring neither one side nor the other).
In many practical applications, the preference lists of at least one set of agents (for example medical students) tend to be short. Also the preference lists of at least one set of agents (for example hospitals) could all be derived from the same objective criteria (such as the academic performance of the students). Each of these restrictions gives rise to variants of HR in which preference lists may be of constant length and/or derived from a single "master" list. We presented many algorithmic results for problems concerned with finding weakly stable matchings in these settings.
Constraint programming techniques provide a method of coping with hard problems - we formulated a range of models of stable matching problems as instances of Constraint Satisfaction problems, to be utilised by constraint solvers.
The Stable Roommates problem is a non-bipartite variant of the Hospitals / Residents problem that models an important recent application involving kidney exchange matching schemes. (For example two patients p_1 and p_2 with incompatible donors d_1 and d_2 could obtain kidneys by an "exchange", where d_1 donates to p_2 and d_2 donates to p_1.) It is known that an instance of this problem may not admit a stable matching. We presented algorithmic results for the problem of finding matchings that are "as stable as possible" in this setting.
In the broader context of stable matching problems where preference lists need not include indifference, we presented algorithmic results for problems concerned with finding exchange-stable matchings. These matchings guarantee that there are no two persons {p, q}, each of whom prefers the other's partner to his/her own partner. Finally we also constructed algorithms for the Student Project Allocation problem, which models the assignment of students to projects in a university department and a variety of other applications besides.
Details concerning the publications arising from this project are available here.
References
- D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9-15, 1962.
- D. Gusfield and R.W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.
- R.W. Irving. Stable marriage and indifference. Discrete Applied Math., 48:261-272, 1994.
- R.W. Irving. Matching medical students to pairs of hospitals: a new variation on a well-known theme. In Proceedings of ESA ’98, LNCS vol. 1461, pp. 381-392. Springer, 1998.
- D.E. Knuth. Mariages Stables. Les Presses de L’Université de Montreál, 1976.
- A.E. Roth. The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy, 92(6):991-1016, 1984.
- A.E. Roth and M.A.O. Sotomayor. Two-sided matching: a study in game-theoretic modeling and analysis. Cambridge University Press, 1990.
- National Resident Matching Program website.
- Canadian Resident Matching Service website.