Jiehua Chen

Paper accepted at IJCAI 2020: Stable matchings with diversity constraints: Affirmative action is beyond NP

Posted on by 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 .

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 , students , types , and/or the maximum upper quota , and the maximum capacity , 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 ΣP2, please refer to e.g., Wikipedia NP and Polynomial hierarchy