Jiehua Chen

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? Here, an unmatched student-college pair has an incentive to deviate if matching it (possibly by unmatching some other pairs) results in a strictly better solution for both the student and the college in the pair. 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 $\Sigma^{\text{P}}_2=\text{NP}^{\text{NP}}$.

In addition, we provide a comprehensive analysis of the problem’s complexity from the viewpoint of natural restrictions to inputs such as bounding the number of colleges $m$, students $n$, types $t$, and/or the maximum upper quota $u_\infty$, and the maximum capacity $q_\infty$, and obtain new algorithms for the problem.

====================================

The conference version and the long version of the paper can be found at IJCAI20 and on arXiv, respectively.

For more information on the complexity classes NP and Σ^P₂, please refer to e.g., Wikipedia NP and Polynomial hierarchy