
A threeyear funded project (value
£324,087) in the Department of
Computing Science, University of Glasgow
involving research on matching algorithms.
Principal investigator: Dr Rob Irving
Coinvestigator: Dr David Manlove
Many practical situations give rise
to largescale matching problems involving sets of participants  for example
pupils and schools, schoolleavers and universities, applicants and positions 
where some or all of the participants express preferences over the others. In
many contexts such as these, centralised matching schemes are used to form
allocations, based on this preference information. For example, in the UK,
matching schemes handle centrally the allocation of pupils to schools,
probationary teachers to local authorities in Scotland, and junior doctors to
hospitals in several regions.
At the heart of these matching
schemes is a computer algorithm that is used to solve an underlying matching
problem. The allocation that a participant receives in a constructed matching
can affect his/her quality of life, so it is imperative that the algorithm
produces a matching that is, in some technical sense, optimal with respect to
the preference information. Moreover, given the numbers of participants
typically involved, it is of paramount importance that the algorithm is
efficient, since it is computationally infeasible in practice to use simplistic
or bruteforce methods. The design of efficient algorithms usually involves
some deeper insight into the underlying mathematical structure of the given
matching problem.
Many existing matching schemes
already employ efficient algorithms to construct matchings that are optimal in
various senses. However some others use rather simple, intuitive, methods
which, though superficially fair and reasonable, produce solutions that can
fall well short of optimality. These examples give rise to open questions
concerning matching problems which have theoretical, as well as practical
significance. Such questions motivate this proposal, which aims to explore the
existence of efficient algorithms for finding optimal solutions in various
classes of matching problems involving preferences.
Matching problems of this kind can
vary considerably in the detail. In some cases, the properties required of
optimal solutions are selfevident, but in other cases the relevant optimality
criteria may be unclear, or there may be different possible competing criteria.
In some matching problems, two sets
of participants are to be matched and both sets express preferences (e.g. in
the context of matching junior doctors to hospitals). Such problems have been
studied for many years, and a key optimality requirement is socalled
'stability'. Yet there is still a wide range of unsolved problems in this
context. Particular challenges arise when preferences are nonstrict, i.e.,
when participants can rank some of the others as equally acceptable.
In other situations only one of the
two sets of participants express preferences (e.g. in the context of matching
teachers to local authorities in Scotland). Matching problems of this kind have
been less thoroughly studied, and especially in this context, many alternative notions
of optimality arise. Although efficient algorithms are known for some of these
optimality criteria, many cases remain to be solved.
A third class of problems involves
just a single homogeneous set of participants, and the need is to match these
participants in pairs (e.g. in order to facilitate organ transplants). The
issue here is that optimal solutions need not exist, leading to questions as to
how to produce matchings that are close to optimal in various senses.
The deliverables of this project will
include new and improved efficient algorithms for the matching problems and
their variants in the classes described above. Where such algorithms appear not
to exist, approximation algorithms will be investigated. A further objective is
to study the relationships between different optimal solutions, to enable a
choice to be made between them. This analysis will also involve empirical
studies based on implementations of both existing and new matching algorithms
arising from this project.
The main overall aim of the proposed
project is to pursue the exploration of matching problems with preferences;
specifically to investigate the existence of efficient algorithms for
constructing various kinds of optimal matchings, where the optimality criteria
are appropriate for the context. This will involve a mixture of theoretical
research, with the intended outcomes being new efficient algorithms, complexity
results and structural relationships involving optimal matchings, and practical
software development, leading to the empirical analysis of new and existing
algorithms and of the solutions that they provide.
More specifically, the proposed
project has the following main objectives:
* To investigate a range of open
questions relating to 'bipartite' matching problems, i.e., involving two sets
of participants, where both sets express preferences. Here the optimality
criteria involves the socalled 'stability' of a matching. A primary focus will
be on variants in which preference lists may involve indifference, but the
study will also encompass other questions motivated by practical applications.
Among these will be the complex relationship between the size, stability and
'profile' (number of participants who obtain their 1st / 2nd choices etc.) of a
matching, and how these are affected by the nature of the preference lists. We
will also study cases in which some or all of the preference lists are
inherited from a single master preference list that ranks the relevant
participants, say according to some objective criteria.
* To consider various optimality
criteria for bipartite matching problems where preferences are on one side
only, particularly those relating to the matching profile. We will seek
efficient, direct algorithms for finding various kinds of optimal matchings,
and for generating all optimal matchings, and will investigate structural
relationships between optimal matchings. We will also look at more complex
optimality criteria in cases where priority measures are attached to participants,
and will extend the investigation to cover manyone and manymany matchings in
addition to the oneone case.
* To study nonbipartite matching
problems under many of the criteria mentioned earlier. These problems are often
more challenging, and some variants do not admit solutions with the desired
properties. In such cases, we will investigate alternative objectives, such as
algorithms for finding 'nearoptimal' solutions.
* To implement new and existing
matching algorithms for problems in the above classes. This will enable
experimental analyses of their performance to be undertaken, and also will
facilitate an empirical study of the properties of and relationships between
the various kinds of optimal matchings.