Envy-Free Matchings with Lower Quotas

Abstract

While every instance of the Hospitals/Residents problem admits a stable matching, the problem with lower quotas (HR-LQ) has instances with no stable matching. For such an instance, we expect the existence of an envy-free matching, which is a relaxation of a stable matching preserving a kind of fairness property. In this paper, we investigate the existence of an envy-free matching in several settings, in which hospitals have lower quotas and not all doctor–hospital pairs are acceptable. We first provide an algorithm that decides whether a given HR-LQ instance has an envy-free matching or not. Then, we consider envy-freeness in the Classified Stable Matching model due to Huang (in: Procedings of 21st annual ACM-SIAM symposium on discrete algorithms (SODA2010), SIAM, Philadelphia, pp 1235–1253, 2010), i.e., each hospital has lower and upper quotas on subsets of doctors. We show that, for this model, deciding the existence of an envy-free matching is NP-hard in general, but solvable in polynomial time if quotas are paramodular.

Appendix: Importance of the Cross-Inequality

In Theorem 4.4 we proved that, for a CSM instance, it is polynomially solvable to check whether there exists an envy-free matching or not if each hospital’s quota function pair is paramodular, i.e., if each hospital has super- and submodular functions satisfying the cross-inequality. As mentioned in Remark 4.7, this problem becomes NP-hard if the cross-inequality is not imposed, which we show in this section.

Theorem A.1

It is NP-hard to decide whether a CSM instance $I=(D, H, E, \succ _{DH}, \{(p_{h}, q_{h})\}_{h\in H})$ has an envy-free matching or not even if $p_{h}$ is supermodular and $q_{h}$ is submodular for each hospital $h\in H$.

To show Theorem A.1, we use a reduction from the NP-complete problem “Disjoint Matchings” [12] described below. For two finite sets S and T with $|S|=|T|$, a subset $W\subseteq S\times T$ is a perfect matching if $|W|=|S|$ and every element of $S\cup T$ occurs in exactly one pair of W.

1.1 Disjoint Matchings (DM)

Instance: disjoint finite sets S, T with $|S|=|T|$ and sets $U_{1}, U_{2}\subseteq S\times T$.

Question: Are there perfect matchings $W_{1}\subseteq U_{1}$ and $W_{2}\subseteq U_{2}$ such that $W_{1}\cap W_{2}=\emptyset$?

Proof of Theorem A.1

Given an instance $(S, T, U_{1}, U_{2})$ of DM, we construct a corresponding CSM instance as follows. Define the sets of doctors, hospitals, and acceptable pairs by

For each $i=1,2$, let . Recall that $U_{i}\subseteq S\times T$ and define and for each $s\in S$ and $t\in T$, respectively. Then $\{D_{i}(s)\}_{s\in S}$ and $\{D_{i}(t)\}_{t\in T}$ are partitions of $D_{i}$. Let each hospital $h_{i}$ have quota functions $p_{h_i}, q_{h_i}:2^{D_{i}}\rightarrow \mathbf {Z}$ defined by

Then, we can check that $p_{h_i}$ is supermodular and $q_{h_i}$ is submodular. (In fact, $\overline{p}_{h_i}$ and $q_{h_i}$ are the matroid rank functions of the partition matroids induced by $\{D_{i}(s)\}_{s\in S}$ and $\{D_{i}(t)\}_{t\in T}$, respectively.) For any $X\subseteq D_{i}$, the condition $\forall B\subseteq D_{i}:p_{h_i}(B)\le |X\cap B|$ means that X contains at least one member of $D_{i}(s)$ for each $s\in S$ and the condition $\forall B\subseteq D_{i}:|X\cap B|\le q_{h_i}(B)$ means that X contains at most one member of $D_{i}(t)$ for each $t\in T$. Because $|S|=|T|$, these imply that a subset $X\subseteq D_{i}$ satisfies $\forall B\subseteq D_{i}:p_{h_i}(B)\le |X\cap B|\le q_{h_i}(B)$ if and only if the corresponding subset is a perfect matching between S and T, i.e., we have

By the definition of perfect matching, we see that any $X, Y\in \mathcal {F}(p_{h_i}, q_{h_i})$ with $X\ne Y$ satisfy $|X\setminus Y|\ge 2$. We define preference lists of the doctors and hospitals arbitrarily.

We first prove that any feasible matching of this CSM instance is an envy-free matching. For a feasible matching $M\subseteq E$, suppose to the contrary that some doctor d has a justified envy toward $d'$ with $M(d')=h_{i}$. Then $d\not \in M(h_{i})$, $d'\in M(h_{i})$, and $M(h_{i})+d-d'\in \mathcal {F}(p_{h_i}, q_{h_i})$ while $M(h_{i})\in \mathcal {F}(p_{h_i}, q_{h_i})$. Because $|(M(h_{i})+d-d')\setminus M(h_{i})|=1$, this contradicts the above property of $\mathcal {F}(p_{h_i}, q_{h_i})$.

By the fact that each doctor can be assigned to at most one hospital and each hospital $h_{i}$ can be assigned a doctor set corresponding to a perfect matching in $U_{i}$, it follows that this CSM instance has a feasible matching if and only if there exists disjoint perfect matchings $W_{1}\subseteq U_{1}$ and $W_{2}\subseteq U_{2}$. Because the existence of a feasible matching of this instance is equivalent to that of an envy-free matching, the proof is completed. $\square$