# Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP

arXiv: https://arxiv.org/abs/2001.10087 · HTML: https://mlsanity.com/paper/2001.10087/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jan 2020.

## Built on by (most cited first, 1 of 1)

- [Participatory Budgeting with Donations and Diversity Constraints](https://mlsanity.com/paper/2104.15075/) (2021)

## Abstract (arXiv)

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 SigmaP2. 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.