From Matching with Diversity Constraints to Matching with Regional Quotas

An instance $I^{S}$ of the basic school choice problem consists of a tuple $(S,C,q_{C},\mathcal{X},\succ_{S},\succ_{C})$.

There is a set of students $S=\{s_{1},s_{2},...,s_{n}\}$ and a set of schools $C=\{c_{1},c_{2},...,c_{m}\}$. Each school $c\in C$ has a capacity $q_{c}$ and let $q_{C}=(q_{c})_{c\in C}$ be a capacity vector consisting of all schools’ capacities.

Each contract $x=(s,c)$ is a student-school pair indicating that student $s$ is matched with school $c$. Let $\mathcal{X}\subseteq S\times C$ denote the set of available contracts. For any $X\subseteq\mathcal{X}$, denote $X_{s}=$ $\{(s,c)\in X|c\in C\}$ as the set of contracts involving student $s$ and $X_{c}=\{(s,c)\in X|s\in S\}$ as the set of contracts involving school $c$ in $X$.

Each student $s$ has a strict preference ordering $\succ_{s}$ over $\mathcal{X}_{s}\cup\{(s,\emptyset)\}$ where $(s,\emptyset)$ denotes the option of being unmatched for student $s$. A contract $(s,c)$ is acceptable to student $s$ if $(s,c)$ $\succ_{s}$ $(s,\emptyset)$ holds. The preference profile of all students is denoted by $\succ_{S}=\{\succ_{s_{1}},...,\succ_{s_{n}}\}$. Each school $c$ has a strict priority ordering $\succ_{c}$ over $\mathcal{X}_{c}\cup\{(\emptyset,c)\}$, where $(\emptyset,c)$ represents the option of leaving a seat vacant for school $c$. A contract $(s,c)$ is acceptable to school $c$ if $(s,c)\succ_{c}(\emptyset,c)$ holds. Let $\succ_{C}=\{\succ_{c_{1}},...,\succ_{c_{m}}\}$ denote the priority profile of all schools. Given any two preference (or priority) orderings $\succ_{p}$ and $\succ_{q}$, we say preference (or priority) ordering $\succ_{p}$ is consistent with preference (or priority) ordering $\succ_{q}$ if for any two contracts $x,y$, when $x\succ_{p}y$ holds, it implies $x\succ_{q}y$.

An outcome (or a matching) $X$ is a subset of $\mathcal{X}$. Denote $S_{c}(X)=\{s\in S|(s,c)\in X\}$ as the set of students matched to school $c$ and $C_{s}(X)=\{c\in C|(s,c)\in X\}$ as the set of schools matched to student $s$ in the outcome $X$. An outcome $X$ is feasible for $I^{S}$ if i) for each student $s,|X_{s}|\leq 1$, ii) for each school $c,|X_{c}|\leq q_{c}$. A feasible outcome $X$ is individually rational if each contract $(s,c)\in X$ is acceptable to both student $s$ and school $c$.

A mechanism $\phi$ is a function that takes an instance as input and returns a matching as an outcome. A mechanism $\phi$ is strategy-proof for students if any student $s\in S$ cannot be admitted to a better school by misreporting his preference.

An instance $\mathit{I^{D}}$ of school choice with diversity constraints is an extension of school choice problem, denoted by a tuple $(S$,$C$,$q_{C}$,$T$,$\tau$,$\overline{\eta}$,$\underline{\eta}$, $\mathcal{X}$,$\succ_{S}$,$\succ_{C})$.

Let $T=\{t_{1},t_{2},...,t_{k}\}$ be the type space with $|T|\leq|S|$. A type vector $\tau_{s}=(\tau_{s}^{t})_{t\in T}$ of student $s$ consists of $1$’s and $0$’s such that $\tau_{s}^{t}=1$ if student $s$ belongs to type $t$ and $\tau_{s}^{t}=0$ otherwise. Let $\tau$ be the type matrix of all students’ type vectors. Let $\overline{\eta}_{c}=(\overline{\eta}_{c}^{t})_{t\in T}$ be a vector of school $c$’s type-specific maximum quotas where $\overline{\eta}_{c}^{t}$ is school $c$’s maximum quota for type $t$. Similarly, $\underline{\eta}_{c}=(\underline{\eta}_{c}^{t})_{t\in T}$ is a vector of school $c$’s type-specific minimum quotas. Let $\overline{\eta}$ and $\underline{\eta}$ be two matrices consisting of all schools’ type-specific maximum vectors and minimum vectors respectively.

For any two vectors consisting of non-negative integers $\omega=(\omega_{1},...,\omega_{k})$ and $\omega^{\prime}=(\omega_{1}^{\prime},...,\omega_{k}^{\prime}),$ we compare them in the following way: i) $\omega\leq\omega^{\prime}$ if for each $i\in[1,k],\omega_{i}\leq\omega_{i}^{\prime}$ and ii) $\omega<\omega^{\prime}$ if for each $i\in[1,k],\omega_{i}<\omega_{i}^{\prime}$. An outcome $X\subseteq\mathcal{X}$ is feasible for $I^{D}$ with diversity constraints if it is feasible for $I^{S}$ and it respects diversity constraints, i.e., for each school $c\in C$, we have $\underline{\eta_{c}}\leq\sum_{s\in S_{c}(X)}\tau_{s}\leq\overline{\eta_{c}}$.

The following definition is a natural extension of classical stability concept by Roth (1985) to the setting of diversity constraints.

Definition 1 states that given a feasible outcome $X$, student $s$ and school $c$ will form a blocking pair if student $s$ prefers school $c$ to his current assignment $X_{s}$ (which could be empty if $X_{s}=(s,\emptyset)$), and there exists a set of students $S^{\prime}$ (which could be empty) that are matched to school $c$ in the outcome $X$ such that i) each student $s^{\prime}\in S^{\prime}$ has lower priority than student $s$ and ii) school $c$ could admit student $s$ by (possibly) removing the set of students $S^{\prime}$.

We can decompose the blocking pair in Definition 1 into two cases: when the set of students $S^{\prime}$ is non-empty, we say student $s$ has justified envy towards students $S^{\prime}$ and a feasible outcome $X$ is fair if $X$ admits no justified envy. If the set of students $S^{\prime}$ is empty, then we say the outcome $X$ is wasteful. Alternatively, a feasible outcome $X$ is stable if it is individually rational, fair and non-wasteful.

An instance $\mathit{I^{H}}$ of hospital-doctor matching is isomorphic to an instance $\mathit{I^{S}}$ of basic school choice problem, denoted by a tuple $(D,H,q_{H},\mathcal{Y},\succ_{D},\succ_{H})$.

Let $D=\{d_{1},...,d_{n}\}$ denote a set of doctors and $H=\{h_{1},...,h_{m}\}$ denote a set of hospitals. Let $q_{H}=(q_{h})_{h\in H}$ be the vector consisting of each hospital’s capacity where $q_{h}$ is the capacity of hospital $h$.

A contract $y=(d,h)$ is a doctor-hospital pair such that $d$ is matched with $h$. Let $\mathcal{Y}\subseteq D\times H$ denote a finite set of available contracts. For any $Y\subseteq\mathcal{Y},$ let $Y_{d}=\{(d,h)\in Y|h\in H\}$ be the set of contracts involving doctor $d$ and $Y_{h}=\{(d,h)\in Y|d\in D\}$ be the set of contracts involving hospital $h$.

Each doctor $d$ has a strict preference ordering $\succ_{d}$ over $\mathcal{Y}_{d}\cup\{(d,\emptyset)\}$ and a contract $(d,h)$ is acceptable to doctor $d$ if $(d,h)\succ_{d}(d,\emptyset)$. Each hospital $h$ has a strict priority ordering over $\mathcal{Y}_{h}\cup\{(\emptyset,h)\}$ and a contract $(d,h)$ is acceptable to hospital $h$ if $(d,h)\succ_{h}(\emptyset,h)$. Let $\succ_{D}$ and $\succ_{H}$ denote the preference and priority profiles of $D$ and $H$ respectively.

An outcome (or a matching) $Y$ is a subset of $\mathcal{Y}$. Denote $D_{h}(Y)=\{d\in D|(d,h)\in Y\}$ as the set of doctors matched to hospital $h$ and $H_{d}(Y)=\{h\in H|(d,h)\in Y\}$ as the set of hospitals matched to doctor $d$ in the outcome $Y$. An outcome $Y\subseteq\mathcal{Y}$ is feasible for $I^{H}$ if i) for each doctor $d$, we have $|Y_{d}|\leq 1$, ii) for each hospital $h$, $|Y_{h}|\leq q_{h}$, and iii) for any doctor $d$ and any hospital $h$, we have $d\in D_{h}(Y)$ if and only if $H_{d}(Y)=\{h\}$.

An instance $\mathit{I^{R}}$ of hospital-doctor matching with regional quotas is a tuple $(D,H,R,q_{H},\overline{\delta},\underline{\delta},\mathcal{Y},\succ_{D},\succ_{H},\succ_{R})$ with additional entries $R,\overline{\delta}$, $\underline{\delta}$ and $\succ_{R}$.

Let $R=\{r_{1},...,r_{j}\}$ denote a set of regions where each region $r_{i}\in R$ is a subset of $H$, i.e., $r_{i}\subseteq H$. A collection of regions $P\subseteq R$ forms a partition of a subset of hospitals $H^{\prime}\subseteq H$, if $\bigcup_{r\in P}r=H^{\prime}$ and for any two different regions $r,r^{\prime}\in P$, we have $r\cap r^{\prime}=\emptyset$. A collection of regions $F\subseteq R$ forms a hierarchy of hospitals $H^{\prime}\subseteq H$, if $\bigcup_{r\in F}r=H^{\prime}$ and for any two regions $r,r^{\prime}(\neq r)\in F$, one of the three conditions holds: i) $r\cap r^{\prime}=\emptyset$, ii) $r\subseteq r^{\prime}$, or iii) $r^{\prime}\subseteq r$.

Let $\overline{\delta}=(\overline{\delta}_{r})_{r\in R}$ denote a vector consisting of each region’s maximum quota where $\overline{\delta}_{r}$ is region $r$’s maximum quota. Similarly $\underline{\delta}=(\underline{\delta}_{r})_{r\in R}$ is a vector of each region’s minimum quota.

For any $Y\subseteq\mathcal{Y},$ let $Y_{r}=\bigcup_{h\in r}Y_{h}$ be the set of contracts involving region $r$ and let $D_{r}(Y)=\{d\in D|(d,h)\in Y_{r}\}$ denote the set of doctors matched to region $r$ in the outcome $Y$.

The introduction of regional priorities was intended to resolve the conflicts when a region confronts more applicants of doctors than it could accommodate (Kamada and Kojima, 2017a, 2018).¹¹1In (Kamada and Kojima, 2017a, 2018), regional preferences are defined in a weaker way that regions only concern about how many doctors are matched rather than which doctors are matched. We followed this idea and assume that each region $r$ has a strict priority ordering over $\mathcal{Y}_{r}$ and a contract $(d,h)\in\mathcal{Y}_{r}$ is acceptable to region $r$ if $(d,h)\succ_{h}(\emptyset,h)$ holds.²²2Similar ideas to regional preferences have already been considered. Kamada and Kojima (2015) studied the model where all regions form a partition of hospitals $H$ and they assume that each region specifies a precedence ordering over hospitals. Let $\succ_{R}$ denote the priority profile of all regions.

An outcome $Y\subseteq\mathcal{Y}$ is feasible for $I^{R}$ with regional quotas if $Y$ is feasible for $I^{H}$ and it respects regional quotas, i.e., for any region $r$ we have $\underline{\delta}_{r}\leq|D_{r}(Y)|\leq\overline{\delta}_{r}$.

The following stability concept captures the idea that a blocking pair is not considered as legitimate if it does not take regional priorities into account.

Definition 2 states that given a feasible outcome $Y$, doctor $d$ and hospital $h$ will form a blocking pair if doctor $d$ prefers hospital $h$ to his assigned hospital $H_{d}(Y)$ (which could be empty), and there exists a set of doctors $D^{\prime}$ (which could be empty) that are matched to hospital $h$ in the outcome $X$ such that i) each doctor $d^{\prime}\in D^{\prime}$ has lower priority than doctor $d$, ii) for each region $r$ that is associated with hospital $h$, each doctor $d^{\prime}\in D^{\prime}$ has lower regional priority than doctor $d$ and iii) hospital $h$ could admit doctor $d$ by (possibly) removing the set of doctors $D^{\prime}$.

The difference between Definition 1 and Definition 2 is that a blocking pair for an instance of matching with regional quotas should respect the priorities of both hospitals and regions. When distribution constraints do not exist, both definitions collapse to the original stability concept (Roth, 1985).

We can decompose the blocking pair in the Definition 2 into two cases: when the set of doctors $D^{\prime}$ is non-empty, we say doctor $d$ has justified envy towards $D^{\prime}$ with regional priorities and an outcome is fair with regional priorities if it admits no justified envy. When the set of doctors $D^{\prime}$ is empty, we say the outcome is wasteful.

Next we provide a polynomial-time reduction from (3,3)-Set cover problem to school choice problem with diversity constraints. Gonzalez (1985) has proved that (3,3)-Set cover is NP-complete.

Although Goto et al. (2014) proved it is NP-complete to check the existence of feasible outcomes for setting (2), their original reduction requires both regional minimum quotas and regional maximum quotas (which needs to be equal for each region). Under the assumption that no doctor is unmatched in any feasible outcome (as discussed in last section), they infer that “checking whether a feasible matching exists or not is NP-complete where there are only regional minimum quotas or only regional maximum quotas”. However, if we relax the assumption, it can be done in polynomial-time to check whether a feasible matching exists when there are only regional maximum quotas, since an empty matching satisfies feasibility. With the help of our reduction, we further show this NP-completeness result even holds for a more restrictive setting when there are only minimum quotas in the following corollary:

In another recent work on public housing allocation with diversity constraints, Benabbou et al. (2018) showed that it is NP-complete to check whether there exists a feasible assignment with maximum social welfare, which is different from ours.

Now we move on to the complexity question of deciding the existence of a stable outcome. In previous work, Huang (2010) showed that it is NP-hard to compute a stable matching for school choice with diversity constraints when both minimum and maximum quotas exist. Next we show that if there are no minimum quotas, it is NP-complete to check whether a stable outcome exists under strict preferences. The following reduction is inspired by the work on hospital-doctor matching with couples by Ronn (1990) and McDermid and Manlove (2010).