MATCH-UP: Matching Under Preferences - Algorithms and Complexity

Lead Research Organisation: University of Glasgow
Department Name: School of Computing Science

Abstract

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.

Publications

10 25 50

publication icon
Abraham D (2008) The Stable Roommates Problem with Globally Ranked Pairs in Internet Mathematics

publication icon
Biró P (2010) Size versus stability in the marriage problem in Theoretical Computer Science

publication icon
Biró P (2010) The College Admissions problem with lower and common quotas in Theoretical Computer Science

publication icon
Biró P (2012) Analysis of stochastic matching markets in International Journal of Game Theory

publication icon
Biró P (2010) Algorithms and Complexity

publication icon
BIRÓ P (2012) MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS in Discrete Mathematics, Algorithms and Applications

publication icon
Biró P (2011) Computing solutions for matching games in International Journal of Game Theory

 
Description The aim of this project was to investigate algorithms and complexity results for matching problems in which participants have preferences over some or all of the others, and the aim is to match participants together, taking account of the preferences, in a way that meets certain optimality criteria. A particular focus was on cases where the prime requirement is so-called stability, which ensures that no pair of participants can act together to improve upon their allocation in the matching. Such matching problems have been a subject of much research over many years, with a recent resurgence of interest, partly because of their intrinsic theoretical interest, but also due to their important applications in real-world centralised matching schemes. These include the allocation of applicants to positions, particularly in the medical field, school and college admission procedures, and matching programmes for kidney exchange. Such large-scale matching schemes are operational in many countries including the UK.



Progress was made in a number of directions, both in enhancing the theoretical understanding of such problems, and in improving methods of solution for practical problems that fall under this umbrella. Some of these methods have already been incorporated in real matching schemes in which the Match-UP team are involved, as described below.



Among theoretical advances resulting from the project were:

* improved efficient approximation algorithms for the hard problem of matching as many participants as possible subject to stability when tied preferences are allowed

* resolution of the computational complexity of several variants of classical stable matching, including

- the case where participants have varying sizes

- the case where some participants have both lower and upper quotas, or groups of participants have a common quota

- a natural 3-way extension of the classical 2-way stable matching problem

- the problem of finding a matching that is 'as stable as possible' in certain contexts where a stable solution does not exist

* characterisation of the structure associated with so-called popular matchings (a matching is popular if there is no other matching preferred by more of the participants), resulting in efficient algorithms for generating all such matchings and finding those that are optimal with respect to additional criteria.



Outcomes of the project with significant practical implications and applications included

* an empirical evaluation of algorithms for constructing optimal sets of kidney exchanges between incompatible donor-patient pairs

* a comprehensive empirical study involving several new algorithms for finding large stable matchings in the presence of tied preferences

* a similar study covering new and existing algorithms for finding stable matchings when some pairs of participants act together as couples

The first of these studies was associated with a collaboration with NHS Blood and Transplant on their National Matching Scheme for Paired Donation - every quarter our algorithms are used to construct optimal sets of kidney exchanges.

The latter two studies have resulted in enhancements and improvements to the SFAS matching scheme, run by NHS Education for Scotland, which annually matches medical graduates to training positions in Scotland.



A significant event associated with the project was the Match-UP workshop held in Reykjavik in July 2008 as a satellite of the annual ICALP conference. The PI and co-investigator took leading roles in the organisation of this workshop, which attracted 38 participants from 11 countries. Partly as a consequence of this workshop, a special issue of the journal Algorithmica, devoted to matching problems under preferences, has been published, with the PI and co-investigator as guest editors. Finally, the project investigators were responsible for three invited chapters on matching algorithms in the recently published Springer Encyclopaedia of Algorithms.
Exploitation Route Collaboration with NHS Education Scotland (Matching schemes for postgraduate medical training) and NHS Blood and Transplant (Matching schemes for live kidney donation) Results of the research were incorporated in large scale practical matching schemes, such as those operated by NHS Education Scotland for matching postgraduate medical students to hospital training posts and by NHS Blood and Transplant for matching live kidney donors to recipients.
Sectors Digital/Communication/Information Technologies (including Software),Education,Healthcare

 
Description Development of algorithms and software for use by NHS Blood and Transplant in matching kidney donors to recipients. A patient who requires a kidney transplant, and who has a willing but incompatible donor, may be able to "swap" their donor with that of another patient in a similar position. This creates a "kidney exchange", involving two or more pairs swapping kidneys in a cyclic manner. Altruistic donors can also trigger "domino paired donation chains" involving incompatible patient-donor pairs, with the final donor donating a kidney to the deceased donor waiting list. NHS Blood and Transplant (NHSBT) operate a UK-wide matching scheme, as part of the National Living Donor Kidney Sharing Schemes, which identifies potential kidney exchanges and domino paired donation chains involving incompatible patient-donor pairs and altruistic donors on their database every three months. Since July 2008, NHSBT have used software produced by David Manlove, Peter Biro, Gregg O'Malley and other colleagues at the School of Computing Science, University of Glasgow in order to construct an optimal solution to the underlying optimisation problem at each quarterly matching run. This software emerged from research carried out as part of the EPSRC-funded MATCH-UP project, and has led to at least 166 actual transplants to date. . Beneficiaries: Kidney transplant patients Matching of Medical Graduates to Foundation Training Programmes in Scotland. The matching of final year medical students to hospital Foundation Programmes in Scotland, taking into account the preferences of all parties, has been carried out since 1999 by software designed and implemented under the supervision of Rob Irving. The changing requirements of the system have necessitated changes to the complex algorithms used as the basis of this software. The most recent changes have been to take account of the joint preferences of couples, and the algorithms for so doing were developed as part of the MATCH-UP project. Beneficiaries: Those involved in postgraduate medical education in Scotland
Sector Education,Healthcare
Impact Types Cultural,Societal

 
Description Efficient Algorithms for Mechanism Design Without Monetary Transfer
Amount £599,000 (GBP)
Funding ID EP/K01000X/1 and EP/K010042/1 
Organisation Engineering and Physical Sciences Research Council (EPSRC) 
Sector Public
Country United Kingdom
Start 06/2013 
End 06/2016
 
Description Kidney Paired Exchange Data Analysis Toolkit
Amount £32,000 (GBP)
Organisation Engineering and Physical Sciences Research Council (EPSRC) 
Sector Public
Country United Kingdom
Start 07/2011 
End 12/2011
 
Description Optimising options and strategies for living donor kidney transplantation for incompatible donor-recipient pairs
Amount £151,000 (GBP)
Funding ID project 10-11-ODT 
Organisation NHS England 
Sector Public
Country United Kingdom
Start 01/2012 
End 06/2013
 
Description Software for the National Matching Scheme for Paired Donation
Amount £108,000 (GBP)
Organisation NHS England 
Sector Public
Country United Kingdom
Start 04/2010 
End 06/2011
 
Description NHS Blood and Transplant 
Organisation NHS Blood and Transplant (NHSBT)
Country United Kingdom 
Sector Public 
PI Contribution Collaboration on National Living Donor Kidney Sharing Schemes
Collaborator Contribution Provide optimality criteria (resulting from policy decisions taken by the Kidney Advisory Group) for the matching algorithms to meet
Impact Increased number of kidney transplants. Shorter waiting times. Consequent financial savings for the NHS.
Start Year 2008
 
Description NHS Education Scotland 
Organisation NHS Education for Scotland (NES)
Country United Kingdom 
Sector Public 
PI Contribution Collaboration on SFAS Matching Scheme
Collaborator Contribution Providing guidance on the specific criteria that the matching algorithm should satisfy
Impact Better outcomes for junior doctors in terms of the hospitals they are assigned to
 
Description MATCH-UP 2008: the First International Workshop on Matching Under Preferences 
Form Of Engagement Activity Scientific meeting (conference/symposium etc.)
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Participants in your research or patient groups
Results and Impact Workshop, July 2008, Reykjavik.

A workshop related to the MATCH-UP project, entitled "MATCH-UP: Matching Under Preferences - Algorithms and Complexity" was held in July 2008 in Reykjavik as a satellite workshop of the ICALP 2008 conference. The event attracted 41 participants from 12 countries; see http://www.optimalmatching.com/workshop for more details.
Year(s) Of Engagement Activity 2008
 
Description MATCH-UP 2012: the Second International Workshop on Matching Under Preferences 
Form Of Engagement Activity Scientific meeting (conference/symposium etc.)
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Participants in your research or patient groups
Results and Impact Workshop, July 2012, Budapest.

A successor, entitled "MATCH-UP 2012: the Second International Workshop on Matching Under Preferences" was held in July 2012 in Budapest. Robert Irving was a keynote speaker. The event attracted 68 participants from 17 countries; see http://econ.core.hu/english/res/MATCH-UP_2012.html for more details.
Year(s) Of Engagement Activity 2012