|
A three-year funded project (value GBP324,087) in the Department of Computing Science, University of Glasgow involving research on
matching algorithms.
Principal investigator: Dr Rob Irving
Co-investigator: Dr
David Manlove
Many practical situations give rise to large-scale matching
problems involving sets of participants - for example pupils and schools,
school-leavers 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 brute-force
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
self-evident, 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 so-called 'stability'. Yet there is still a
wide range of unsolved problems in this context. Particular challenges arise
when preferences are non-strict, 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
so-called '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 many-one and many-many matchings in addition to the
one-one case.
* To study non-bipartite 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
'near-optimal' 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.