|
| EPSRC Reference: |
GR/R84597/01 |
| Title: |
Algorithmics of Stable Matching Problems with Indifference |
| Principal Investigator: |
Dr DF Manlove |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
Computing Science |
| Organisation: |
University of Glasgow |
| Scheme: |
Fast Stream |
| Starts: |
01 October 2002 |
Ends: |
31 March 2006 |
Value (£): |
63,480
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary |
|
Stable matching problems are motivated in practice by large-scale applications such as centralised matching schemes, which assign agents together based on their preference lists. In Scotland, the USA and Canada for example, automated matching schemes annually construct stable matchings of graduating medical students to hospital posts, taking as input the preferences of students over hospitals and vice versa. Given the large numbers of participants typically involved, it is of paramount importance to employ efficient algorithms in such applications. In the case that all preference lists are strictly ordered, the underlying structure is well-understood, and this has led to the development of a range of efficient algorithms for these stable matching problems. However in practice the preference lists need not be totally ordered - hospitals may be indifferent among certain students, for example. This generalisation has not been widely studied from an algorithmic point of view, despite the important practical applications. The proposed project aims to explore in detail the algorithmic behaviour of stable matching problems with indifference - this will involve theoretical research, with the intended outcomes being new, efficient algorithms and complexity results, and also practical investigation, in the form of the empirical analysis of algorithm implementations.
|
| Final Report Summary |
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.
The classical Hospitals / Residents problem models the assignment of graduating medical students to hospital posts based on preference lists and capacity restrictions. An important generalisation of this problem arises when ties may be present in the preference lists (for example a large hospital may be indifferent among several applicants). We 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 the Hospitals / Residents problem 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 others 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.
The results of this project will be of interest to any organisation that uses a large-scale centralised matching scheme to handle a assignment process, to the individuals who participate in that process, and to the academic community in general. This project has facilitated valuable training in the methods of research for two students, namely David Abraham and Gregg OMalley. It has also involved international collaboration with researchers from Slovakia (facilitated by the visiting fellowship component of the grant), Hungary, Japan, Iceland and the US.
|
| Further Information: |
http://www.dcs.gla.ac.uk/research/algorithms/ASMPI |
| Organisation Website: |
http://www.gla.ac.uk |
|
|