权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

MATCH-UP: Matching Under Preferences - Algorithms and Complexity

MATCH-UP：根据偏好进行匹配 - 算法和复杂性

基本信息

批准号：
EP/E011993/1
负责人：
Robert Irving
金额：
$ 41.3万
依托单位：
University of Glasgow
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2007
资助国家：
英国
起止时间：
2007 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FE011993%2F1
关键词：
MATCH UP Matching Under Preferences

项目摘要

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.

在许多实际情况下，会产生涉及不同参与者群体的大规模匹配问题，例如学生和学校、离校生和大学、申请人和职位，其中一些或所有参与者表示对其他参与者的偏好。在许多情况下，如这些，集中式匹配方案用于形成分配，基于此偏好信息。例如，在英国，匹配方案集中处理学生到学校的分配、试用教师到苏格兰地方当局的分配以及初级医生到几个地区的医院的分配，这些匹配方案的核心是一种用于解决潜在匹配问题的计算机算法。参与者在构造匹配中获得的分配可能会影响他/她的生活质量，因此算法必须产生在某种技术意义上相对于偏好信息最优的匹配。此外，考虑到通常涉及的参与者的数量，算法的有效性是至关重要的，因为在实践中使用简单化或蛮力方法在计算上是不可行的。有效算法的设计通常涉及对给定匹配问题的底层数学结构的更深层次的理解。许多现有的匹配方案已经使用有效算法来构造在各种意义上都是最优的匹配。然而，其他一些人使用相当简单，直观的方法，虽然表面上公平合理，但产生的解决方案可能远远达不到最优。这些例子引起了开放的问题，具有理论和实践意义的匹配问题。这样的问题激发了这个建议，其目的是探索存在的有效算法，以找到最佳的解决方案，在各种类别的匹配问题，涉及preferences.Matching这类问题可以有很大的不同的细节。在某些情况下，最优解所需的属性是不言而喻的，但在其他情况下，相关的最优性标准可能不清楚，或者可能存在不同的竞争标准。在某些匹配问题中，两组参与者将被匹配，并且两组都表示偏好（例如，在将初级医生与医院匹配的上下文中）。这类问题已经研究了很多年，关键的最优性要求是所谓的“稳定性”。然而，在这方面仍然存在着广泛的未解决问题。当偏好不严格时，即，在其他情况下，只有两组参与者中的一组表达偏好（例如，在苏格兰将教师与地方当局相匹配的情况下）。这种匹配问题已经不太彻底的研究，特别是在这种情况下，出现了许多替代的最优性概念。虽然对于这些最优性标准中的一些已知的有效算法，许多情况下仍然有待解决。第三类问题只涉及一个单一的同质集合的参与者，并且需要将这些参与者配对（例如，为了促进器官移植）。这里的问题是，最佳的解决方案不一定存在，导致问题，如何产生匹配，接近最佳的各种意义上。这个项目的交付将包括新的和改进的有效算法的匹配问题和他们的变种在上面描述的类。在这种算法似乎不存在，近似算法将进行调查。另一个目标是研究不同的最佳解决方案之间的关系，使它们之间的选择。该分析还将涉及基于该项目产生的现有和新的匹配算法的实施的实证研究。