EPSRC project in

Algorithms and Complexity

from 1 June 2007

MATCH UP: Matching Under Preferences – Algorithms and Complexity

A three-year funded project (value £324,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

Post-doctoral research assistant: Péter Biró

PhD student: Eric McDermid

Project summary

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.

Project objectives

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.