论文标题
从与多样性限制匹配到与区域配额的匹配
From Matching with Diversity Constraints to Matching with Regional Quotas
论文作者
论文摘要
在过去的几年中，已经提出了几种新的匹配模型，并研究了复杂的分布约束。相关的工作线包括（1）学生选择学生（可能是重叠）类型的多样性限制和（2）施加各种区域配额的医院医院匹配。在本文中，我们提出了一个多项式时间的缩短，以将（1）的实例转换为（2）实例，并展示了如何在还原下保留相应匹配的可行性和稳定性。我们的还原提供了与分配约束匹配的两项重要工作之间的正式联系。然后，我们以两种方式应用减少。首先，我们表明，检查（1）是否存在可行且稳定的结果是NP的完整。由于我们的减少，这些NP完整性结果将延续到设置（2）。鉴于此，我们有助于统一文献中提出的一些结果。其次，如果我们对（2）产生阳性结果，那么我们将获得（1）的相应结果。我们的结果的一个关键结论是，医院贴上与区域配额的公理和算法方面的进一步发展将导致与多样性约束的学校选择相应的结果。
In the past few years, several new matching models have been proposed and studied that take into account complex distributional constraints. Relevant lines of work include (1) school choice with diversity constraints where students have (possibly overlapping) types and (2) hospital-doctor matching where various regional quotas are imposed. In this paper, we present a polynomial-time reduction to transform an instance of (1) to an instance of (2) and we show how the feasibility and stability of corresponding matchings are preserved under the reduction. Our reduction provides a formal connection between two important strands of work on matching with distributional constraints. We then apply the reduction in two ways. Firstly, we show that it is NP-complete to check whether a feasible and stable outcome for (1) exists. Due to our reduction, these NP-completeness results carry over to setting (2). In view of this, we help unify some of the results that have been presented in the literature. Secondly, if we have positive results for (2), then we have corresponding results for (1). One key conclusion of our results is that further developments on axiomatic and algorithmic aspects of hospital-doctor matching with regional quotas will result in corresponding results for school choice with diversity constraints.
