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.