论文标题
与多样性约束的稳定匹配：平权行动超出了NP
Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP
论文作者
论文摘要
我们研究以下多样性限制（SMTI多样）的以下多一对一稳定的匹配问题：鉴于一组学生和一组彼此偏爱的大学，这些大学的偏好，学生都有重叠的类型，并且各自的总能力以及对个人类型的配额（多样性约束）都不满足所有不同的限制。 众所周知，Smti-Doverse是NP-HARD。但是，与文献中的NP-Membership主张相反[Aziz等，Aamas 2019; Huang，Soda 2010]，我们证明它超出了NP：对于复杂性类别$σ^{\ text {p}} _ 2 $的复杂性类别。此外，我们从自然限制的投入的观点中对问题的复杂性进行了全面分析，并为问题获得了新的算法。
We investigate the following many-to-one stable matching problem with diversity constraints (SMTI-Diverse): Given a set of students and a set of colleges which have preferences over each other, where the students have overlapping types, and the colleges each have a total capacity as well as quotas for individual types (the diversity constraints), is there a matching satisfying all diversity constraints such that no unmatched student-college pair has an incentive to deviate? SMTI-Diverse is known to be NP-hard. However, as opposed to the NP-membership claims in the literature [Aziz et al., AAMAS 2019; Huang, SODA 2010], we prove that it is beyond NP: it is complete for the complexity class $Σ^{\text{P}}_2$. In addition, we provide a comprehensive analysis of the problem's complexity from the viewpoint of natural restrictions to inputs and obtain new algorithms for the problem.
