MATCH-UP: Matching Under Preferences - Algorithms and Complexity

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.