Project Abstract

Centralised Matching Proces

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.

Grant details

Funding body:
EPSRC
Grant number:
GR/R84597/01
Duration:
1/10/02 - 31/03/06