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.

1 Introduction

Since the seminal work of Gale and Shapley [13], the Hospitals/Residents problem (HR, for short), or the College Admission problem, has been studied extensively [17, 26, 35]. They proposed an algorithm that finds a stable matching in linear time for every instance. In this problem, each hospital has an upper quota for the number of doctors assigned to it. In some applications, each hospital also has a lower quota for the number of doctors it receives. That is, we want to consider the Hospitals/Residents problem with lower quotas (HR-LQ, for short). Unfortunately, for HR-LQ, we cannot ensure the existence of a stable matching. However, it is easy to decide whether there is a stable matching or not for a given HR-LQ instance, because the number of doctors assigned to each hospital is identical for any stable matching (according to the well-known Rural Hospitals Theorem [14, 32,33,34]).

When a given HR-LQ instance has no stable matching, one natural approach is to weaken stability concept while preserving some kind of fairness. Envy-freeness [38] (also called fairness in the school choice literature [8, 16]) of matchings is a relaxation of stability obtained by giving up efficiency. Similarly to stability, envy-freeness forbids the existence of a doctor who has justified envy toward some other doctor, but it tolerates the existence of a doctor who claims a hospital’s vacant seat. The importance of envy-freeness and its variants has recently been recognized in the context of constrained matching [4, 8, 16, 24, 25], and structural properties of envy-free matchings were investigated in [38].

Envy-free matchings naturally arise when we find a matching in the following ad hoc manner. For an HR-LQ instance, suppose that we find a stable matching while disregarding the lower quotas, and that the obtained matching does not meet the lower quotas. Let us reduce the upper quotas of hospitals that receive many doctors, and again find a stable matching while disregarding the lower quotas, and repeat. If we find a stable matching that meets the lower quotas after repeating such adjustments, then the obtained matching is an envy-free matching of the original instance (see Proposition 2.4).

Because an envy-free matching is a relaxation of a stable matching, it is more likely to exist. Indeed, if all doctor–hospital pairs are acceptable and the sum of lower quotas of all hospitals does not exceed the number of doctors, then we can ensure the existence of an envy-free matching (this follows from the results of Fragiadakis et al. [8]). However, if not all pairs are acceptable, then even an envy-free matching may fail to exist. Moreover, deciding the existence of an envy-free matching is not so simple because envy-free matchings have different sizes unlike stable matchings.

Our Contribution In this paper, we study envy-free matchings for the HR-LQ model and its generalizations. In our models, not all doctor–hospital pairs are acceptable (i.e., preference lists are incomplete).

We first investigate envy-free matchings in the setting of HR-LQ. We provide the following characterization of the existence of an envy-free matching. Let I be a given HR-LQ instance and let $I'$ be an HR instance obtained from I by removing lower quotas and replacing upper quotas with the original lower quotas. We prove that I has an envy-free matching if and only if every hospital is full in a stable matching of $I'$ (Theorem 2.6). Combined with the rural hospitals theorem, this characterization yields an efficient algorithm to decide the existence of an envy-free matching for an HR-LQ instance. That is, we can decide it by finding a stable matching for the HR instance whose upper quotas are the original lower quotas, and checking whether all hospitals are full or not.

Next, we move to a generalized model, in which each hospital imposes an upper and a lower quota on each subset of doctors. That is, we consider an envy-free matching version of Huang’s Classified Stable Matching [23] (CSM, for short). (See “Related Works” below for results on stable matchings of CSM and its generalizations.) In Huang’s original model, each hospital has a family of sets of doctors, called classes, and each class has an upper and a lower quota. We formulate this setting by letting each hospital have a pair of set functions defined on the set of acceptable doctors. These two functions respectively represent upper quotas and lower quotas. For this model, we show that it is NP-hard to decide the existence of an envy-free matching, even if the number of non-trivial quotas is linear (Theorem 2.6). The proof is by a reduction from the NP-complete problem (3,B2)-SAT [2].

Then, we provide a tractable special case of CSM. We show that if the pair of lower and upper quota functions of each hospital is paramodular [10] (see Sect. 4 for the definition), then we can decide the existence of an envy-free matching in polynomial time. Our proof utilizes the lattice fixed-point method for stable matchings [6, 22] and the generalized matroid structure of the family of acceptable doctor sets of each hospital. A generalized matroid [36] (also called an $M^{\natural }$-convex family [29]) is a family of subsets satisfying a certain axiom called the exchange axiom. It is known that a paramodular function pair defines a generalized matroid and vice versa. Because constraints defined on a laminar (or hierarchical) family yield a generalized matroid, our tractable special case includes a case in which each hospital defines quotas on a laminar family of doctors.

Related Works Recently, the study of matching models with lower quotas has developed substantially [1, 7, 16, 18, 19, 23, 26, 27]. The Hospitals/Residents problem with lower quotas (HR-LQ) was first studied by Hamada et al. [18, 19], who considered the minimization of the number of blocking pairs subject to upper and lower quotas. They showed the NP-hardness of the problem, gave an inapproximability result, and provided an exponential-time exact algorithm. Motivated by the matching scheme used in Hungary’s higher education sector, Biró et al. [3] considered a version of HR-LQ in which hospitals (i.e., colleges) are allowed to be closed, i.e., each hospital is assigned enough doctors or no doctor. They showed the NP-completeness to decide the existence of a stable matching.

The Classified Stable Matching problem (CSM), proposed by Huang [23], is a generalization of HR-LQ without hospital closures. In this model, each hospital (or institute, in Huang’s terminology) has a classification of doctors (i.e., applicants) based on their expertise and gives an upper and lower quota for each class. Huang showed that it is NP-complete in general to decide the existence of a stable matching, and proved that it is solvable in polynomial time if classes form a laminar family. For this tractable special case, Fleiner and Kamiyama [7] gave a concise explanation in terms of matroids, and their framework is generalized by Yokoi [39] to a framework with generalized matroids.

To cope with the nonexistence of a stable matching in constrained matching models (not only models with lower quotas but also with other types of constraints such as regional constraints), several relaxations of stability have been proposed. See, e.g., Kamada and Kojima [24, 25], Fragiadakis et al. [8], and Goto et al. [16]. Envy-freeness is one of them that places emphasis on fairness rather than efficiency. Fragiadakis et al. [8] provided a strategy-proof algorithm that always finds an envy-free matching (or fair matching, in their terminology) of HR-LQ under the assumption that all doctor–hospital pairs are acceptable. The outcome of their mechanism also fulfills a second-best efficiency (i.e., nonwastefulness) property. Their framework is generalized in Goto et al. [16] so that regional quotas can be handled.

Here we compare our models with the above models. Unlike the models of Goto et al. [16] and Kamada and Kojima [24, 25], our models cannot handle regional quotas. Instead, our CSM model (in Sects. 3 and 4) allows each hospital to have quotas on classes of doctors, which are not dealt with in their models. The setting of a tractable special case of CSM described in Sect. 4 is equivalent to a many-to-one case of Yokoi’s model [39], which studied stable matchings. Neither [39] nor the study in this paper relies on the results of the other, while both of them utilize the matroid framework of Fleiner [5, 6].

The remainder of this paper is organized as follows. Sect. 2 investigates envy-free matchings in the Hospitals/Residents problem with lower quotas (HR-LQ). In Sect. 3, we define an envy-free matching in the classified stable matching (CSM) model, and show the NP-hardness of its existence test. As its tractable special case, Sect. 4 presents results on CSM with paramodular quota functions. Proofs for the theorems and corollary in Sect. 4 are provided in Sect. 5.

2 Envy-Freeness in HR with Lower Quotas

In this section, we investigate envy-free matchings in the Hospitals/Residents problem with lower quotas (HR-LQ).

There are two disjoint sets D and H, which represent doctors and hospitals, respectively. A set of acceptable doctor–hospital pairs is denoted by $E\subseteq D\times H$. For each doctor $d\in D$, its acceptable hospital set is denoted by

and d has a preference list (strict order) $\succ _{d}$ on A(d). Similarly, for each hospital $h\in H$,

and h has a preference $\succ _{h}$ on A(h). Each hospital h has a lower quota $l_{h} \in \mathbf {Z}$ and an upper quota $u_{h}\in \mathbf {Z}$ with

$$\begin{aligned} 0\le l_{h}\le u_{h}\le |A(h)|. \end{aligned}$$

We call a tuple $I=(D, H, E, \succ _{DH}, \{(l_{h}, u_{h})\}_{h\in H})$ an HR-LQ instance, where $\succ _{DH}$ is an abbreviated notation for the union of $\{\succ _{d}\}_{d\in D}$ and $\{\succ _{h}\}_{h\in H}$. In particular, if $l_{h}=0$ for all $h\in H$, we call it an HR instance. An arbitrary subset M of E is called an assignment. For any assignment M, we denote for each $d\in D$ and for each $h\in H$. If $|M(d)|=1$, the notation M(d) is also used to refer its single element.

An assignment M is called a matching (or, said to be feasible) if $|M(d)|\le 1$ for each $d\in D$ and $l_{h}\le |M(h)|\le u_{h}$ for each $h\in H$. In a matching M, a doctor d is unassigned (resp., assigned) if $M(d)=\emptyset$ (resp., $|M(d)|=1$), and h is undersubscribed (resp., full) if $|M(h)|<u_{h}$ (resp., $|M(h)|=u_{h}$).

Definition 2.1

For a matching M, an unassigned pair $(d,h)\in E\setminus M$ is a blocking pair if (i) d is unassigned or $h\succ _{d} M(d)$ and (ii) h is undersubscribed or there is $d'\in M(h)$ with $d\succ _{h} d'$. A matching M is stable if there is no blocking pair.

For an HR instance, it is known that the algorithm of Gale and Shapley [13] always finds a stable matching. The set of stable matchings has the following property.

Proposition 2.2

(“Rural Hospitals” Theorem [14, 32, 34]) For a given HR instance, any two stable matchings $M, M'$ satisfy $|M(h)|=|M'(h)|$ for every $h\in H$. Moreover $M(h)=M'(h)$ if h is undersubscribed in M or $M'$.

As mentioned in the Introduction, if hospitals have lower quotas, then we cannot guarantee the existence of a stable matching anymore. By Proposition 2.2, however, we can easily check the existence by finding a stable matching while disregarding lower quotas, and checking whether the obtained matching meets lower quotas.

For an instance that has no stable matching, we want to obtain some matching that still has a kind of fairness. As a relaxation of the concept of stability, envy-freeness (also called fairness) of matchings has been proposed [8, 38].

Definition 2.3

For a matching M, a doctor d has justified envy toward $d'$ with $M(d')=h$ if (i) d is unassigned or $h\succ _{d} M(d)$ and (ii) $d\succ _{h} d'$. A matching M is envy-free if no doctor has justified envy.

Note that, if d has justified envy toward $d'$ with $M(d)=h$, then it means that (d, h) is a blocking pair. Thus, stability implies envy-freeness. The envy-freeness of a matching is also regarded as the stability with reduced upper quotas, as follows.

Proposition 2.4

For $I=(D, H, E, \succ _{DH}, \{(l_{h}, u_{h})\}_{h\in H})$, an assignment M is an envy-free matching if and only if M is a stable matching of $I'=(D, H, E, \succ _{DH}, \{(l_{h}, u'_{h})\}_{h\in H})$ for some $\{u'_{h}\}_{h\in H}$ with $u'_{h}\le u_{h}~(h\in H)$.

Proof

The “if” part is clear because feasibility in $I'$ implies that in I, and stability implies envy-freeness. For the “only if” part, suppose that M is envy-free in I and set $u'_{h}:=|M(h)|$ for each $h\in H$. Then, M is feasible for $I'$ and all hospitals are full, and hence there is no doctor who claims a hospital’s vacant seat. Because M is envy-free, it is stable in $I'$. $\square$

By Proposition 2.4, to check whether we can obtain a stable matching by reducing upper quotas, it suffices to check for the existence of an envy-free matching.

Under the assumption that all doctor–hospital pairs are acceptable and the sum of lower quotas does not exceed the number of doctors, Fragiadakis et al. [8] provided a strategy-proof mechanism that always finds an envy-free matching. As a corollary, we have the following.

Proposition 2.5

For an instance $I=(D, H, E, \succ _{DH}, \{(l_{h}, u_{h})\}_{h\in H})$ such that $E=D\times H$ and $|D|\ge \sum _{h\in H} l_{h}$, there exists an envy-free matching.

However, if not all pairs are acceptable, then even an envy-free matching may not exist. Figure 1 shows an instance with $D=\{d_{1}, d_{2}\}$, $H=\{h_{1}, h_{2}\}$, $E=\{(d_{1}, h_{1}), (d_{2}, h_{1}), (d_{2}, h_{2})\}$, $l_{h_{1}}=l_{h_{2}}=1$, and $u_{h_{1}}=u_{h_{2}}=2$. For this instance, $M=\{(d_{1}, h_{1}), (d_{2}, h_{2})\}$ is the unique feasible matching, but it is not envy-free because $d_{2}$ has justified envy toward $d_{1}$. Hence, there is no envy-free matching.

Fig. 1

An instance of HR-LQ with no envy-free matching

Note that an envy-free matching does exist if there is no lower quota, because the empty matching is clearly envy-free. Therefore, the existence test of an envy-free matching is non-trivial when incomplete lists and lower quotas are introduced simultaneously. Here we provide a characterization.

Theorem 2.6

$I=(D, H, E, \succ _{DH}, \{(l_{h}, u_{h})\}_{h\in H})$ has an envy-free matching if and only if some stable matching $M'$ of the HR instance $I'=(D, H, E, \succ _{DH}, \{(0, l_{h})\}_{h\in H})$ satisfies $|M'(h)|=l_{h}$ for all $h\in H$.

Proof

For the “if” part, let $M'$ be a stable matching of $I'$ satisfying $|M'(h)|=l_{h}$ for all $h\in H$. Then, $M'$ is feasible for $I'$ and no doctor has justified envy because $M'$ has no blocking pair. Thus, $M'$ is an envy-free matching of I.

For the “only if” part, assume that I has an envy-free matching M. Suppose, to the contrary, a stable matching $M'$ of $I'$ satisfies $|M'(h^{*})|<l_{h^{*}}$ for some $h^{*}\in H$. Let us denote $N=M\setminus M'$ and $N'=M'\setminus M$. For every $h\in H$, because $|M'(h)|\le l_{h}\le |M(h)|$, we have $|N'(h)|\le |N(h)|$. In particular, $|N'(h^{*})|< |N(h^{*})|$ follows from $|M'(h^{*})|<l_{h^{*}}$.

Consider a bipartite graph $G=(D, H; N\cup N')$, i.e., a graph between doctors and hospitals with edge set $N\cup N'=M\triangle M'$. Let $G^{*}$ be a connected component of G including $h^{*}$, and denote by $D^{*}$ and $H^{*}$ the sets of doctors and hospitals in $G^{*}$, respectively. Because there is no edge connecting $G^{*}$ and the outside, $\sum _{d\in D^{*}} |N(h)|=\sum _{h\in H^{*}} |N(h)|$ and $\sum _{d\in D^{*}} |N'(h)|=\sum _{h\in H^{*}} |N'(h)|$. As $|N'(h^{*})|< |N(h^{*})|$ and $|N'(h)|\le |N(h)|$ for any $h\in H^{*}$, we obtain

$$\begin{aligned} \textstyle {\sum _{d\in D^{*}} |N'(d)|=\sum _{h\in H^{*}} |N'(h)|<\sum _{h\in H^{*}} |N(h)|=\sum _{d\in D^{*}} |N(d)|}. \end{aligned}$$

Then, there exists $d^{*}\in D^{*}$ with $|N'(d^{*})|<|N(d^{*})|$, which implies $N'(d^{*})=\emptyset$ and $|N(d^{*})|=1$ because $N'=M'\setminus M$ and $N=M\setminus M'$ are subsets of matchings. As $G^{*}$ is a connected bipartite graph, there is a path $d_{0}~\!h_{0}~\!d_{1}~\!h_{1}\dots d_{k}~\!h_{k}$ with $d_{0}=d^{*}$ and $h_{k}=h^{*}$. Also, as $|N(d_{i})|\le 1$ and $|N'(d_{i})|\le 1$ for $i=0,1,\dots k$, this path alternately uses edges in $N=M\setminus M'$ and $N'=M'\setminus M$. Because $N'(d^{*})=\emptyset$ and $|N(d^{*})|=1$, we have

$$\begin{aligned} M'(d_{0})&=\emptyset ,\\ (d_{i}, h_{i})&\in M\setminus M'\quad \quad (i=0,1,\dots ,k),\\ (d_{i+1},h_{i})&\in M'\setminus M\quad \quad (i=0,1,\dots ,k-1). \end{aligned}$$

The doctor $d_{0}$ is unassigned in $M'$ and finds $h_{0}$ acceptable because $(d_{0}, h_{0})\in M$. Hence, the stability of $M'$ implies that $h_{0}$ prefers $d_{1}\in M'(h_{0})$ to $d_{0}$. Then, the envy-freeness of M implies that $d_{1}$ prefers $h_{1}=M(d_{1})$ to $h_{0}$. In this way, we obtain

$$\begin{aligned}&d_{i+1}\succ _{h_{i}} d_{i}\quad \quad (i=0,1,\dots ,k-1),\\&h_{i+1}\succ _{d_{i+1}} h_{i}\quad \quad (i=0,1,\dots ,k-1). \end{aligned}$$

Thus, $M(d_{k})=h_{k}\succ _{d_{k}} h_{k-1}=M'(d_{k})$. Because $h_{k}=h^{*}$ satisfies $|M'(h_{k})|<l_{h_{k}}$, then $(d_{k}, h_{k})$ is a blocking pair in $I'$, which contradicts the stability of $M'$. $\square$

Theorem 2.6 ensures that the following algorithm decides the existence of an envy-free matching of an HR-LQ instance $I=(D, H, E, \succ _{DH}, \{(l_{h}, u_{h})\}_{h\in H})$.

Algorithm EF-HR-LQ

Step1. :

Find a stable matching $M'$ of $I'=(D, H, E, \succ _{DH}, \{(0, l_{h})\}_{h\in H})$.

Step2. :

Return $M'$ if $|M'(h)|=l_{h}$ for all $h\in H$, and otherwise “there is no envy-free matching.”

Since the Gale-Shapley algorithm finds a stable matching of an HR instance in O(|E|) time, we obtain the following theorem.

Theorem 2.7

For any HR-LQ instance $I=(D, H, E, \succ _{DH}, \{(l_{h}, u_{h})\}_{h\in H})$, the algorithm EF-HR-LQ decides whether I has an envy-free matching or not in O(|E|) time.

3 Envy-Freeness in Classified Stable Matching

In this section, we consider the envy-freeness in a model in which each hospital has lower and upper quotas on subsets of doctors. This can be regarded as an envy-free matching version of the Classified Stable Matching, proposed by Huang [23]. Similarly to Sect. 2, we have doctors D, hospitals H, acceptable pairs $E\subseteq D\times H$, and preferences $\succ _{DH}$.

The only difference from HR-LQ is that, in the current model, each hospital $h\in H$ has a pair of functions $p_{h}, q_{h}:2^{A(h)}\rightarrow \mathbf {Z}$, instead of a pair of numbers $l_{h}, u_{h}$. These functions define a lower and an upper quota for each subset of acceptable doctors. Throughout this paper, we assume that for any hospital h, the functions $p_{h}$ and $q_{h}$ satisfy

$$\begin{aligned} 0\le p_{h}(B)\le q_{h}(B)\le |B|\qquad (B\subseteq A(h)). \end{aligned}$$

We call such a tuple $(D, H, E, \succ _{DH}, \{(p_{h}, q_{h})\}_{h\in H})$ a CSM instance. For each $h\in H$, the family of acceptable subsets of doctors is denoted by

For any $h\in H$, we say that $B\subseteq A(h)$ has a non-trivial lower (resp., upper) constraint if $p_{h}(B)>0$ (resp., $q_{h}(B)<|B|$). We denote the family of constrained subsets by

Then, we see that $\mathcal {F}(p_{h}, q_{h})$ is represented as

For a CSM instance $I=(D, H, E, \succ _{DH}, \{(p_{h}, q_{h})\}_{h\in H})$, $M\subseteq E$ is called a matching (or, said to be feasible) if $|M(d)|\le 1$ for each $d\in D$ and $M(h)\in \mathcal {F}(p_{h}, q_{h})$ for each $h\in H$.

Definition 3.1

For a matching M, an unassigned pair $(d,h)\in E\setminus M$ is a blocking pair if (i) d is unassigned or $h\succ _{d} M(d)$, and (ii) $M(h)+d\in \mathcal {F}(p_{h}, q_{h})$ or $M(h)+d-d'\in \mathcal {F}(p_{h}, q_{h})$ for some $d'\in M(h)$ with $d\succ _{h} d'$. A matching M is stable if there is no blocking pair.

In Definition 3.1, the condition $M(h)+d\in \mathcal {F}(p_{h}, q_{h})$ means that h can add d to the current assignment without violating any upper quota, and $M(h)+d-d'\in \mathcal {F}(p_{h}, q_{h})$ means that h can replace $d'$ with d without violating any upper or lower quota. The Classified Stable Matching, introduced by Huang [23], is the problem to decide the existence of a stable matching for a given CSM instance¹ . Because this is a generalization of HR-LQ, there are instances that have no stable matching. Let us consider envy-freeness for a CSM instance.

Definition 3.2

For a matching M, a doctor d has justified envy toward $d'$ with $M(d')=h$ if (i) d is unassigned or $h\succ _{d} M(d)$ and (ii) $M(h)+d-d'\in \mathcal {F}(p_{h}, q_{h})$ and $d\succ _{h} d'$. A matching M is envy-free if no doctor has justified envy.

As in the case of HR-LQ, an envy-free matching can be regarded as a stable matching with reduced upper quotas as follows. For any $h\in H$ and $k\in \mathbf {Z}$ with $0\le k\le q(A(h))$, a function $q'_{h}:2^{A(h)}\rightarrow \mathbf {Z}$ is called a k-truncation of $q_{h}$ if $q'(A(h))=k$ and $q'(B)=q(B)$ for every $B\subsetneq A(h)$. Also, we simply say that $q'_{h}$ is a truncation of $q_{h}$ if there is such $k\in \mathbf {Z}$.

Proposition 3.3

For $I=(D, H, E, \succ _{DH}, \{(p_{h}, q_{h})\}_{h\in H})$, an assignment M is an envy-free matching if and only if M is a stable matching of $I'=(D, H, E, \succ _{DH}, \{(p_{h}, q'_{h})\}_{h\in H})$ such that each $q'_{h}$ is some truncation of $q_{h}$.

Proof

To show the “only if” part, let M be an envy-free matching of I. For each $h\in H$, let $q'_{h}$ be the |M(h)|-truncation of $q_{h}$. Then $M(h)\in \mathcal {F}(p_{h}, q'_{h})$ and $M(h)+d\not \in \mathcal {F}(p_{h}, q'_{h})$ for every $d\in A(h)\setminus M(h)$. That is, M is feasible for $I'$ and there is no doctor who claims a hospital’s vacant seat. Therefore, if there is a blocking pair $(d,h)\in E\setminus M$ for $I'$, it follows that d has a justified envy toward some $d'$ with $M(d')=h$, which contradicts the envy-freeness of M. Thus, M is a stable matching of $I'$.

For the “if” part, let M be a stable matching of $I'$. Clearly, M is feasible for I. Suppose, to the contrary, some doctor d has justified envy toward $d'$ with $M(d')=h$ with respect to I. Then d is unassigned or $h\succ _{d}M(d)$. Also, we have $d\succ _{h}d'$ and $M(h)+d-d'\in \mathcal {F}(p_{h}, q_{h})$. Then, $M(h)+d-d'\in \mathcal {F}(p_{h}, q'_{h})$ follows because $|M(h)+d-d'|=|M(h)|$. Hence, (d, h) is a blocking pair in $I'$, a contradiction. $\square$

We provide a hardness result for deciding the existence of an envy-free matching. Here, we assume that evaluation oracles of set functions $p_{h}$ and $q_{h}$ are available for each hospital h.

Theorem 3.4

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. The problem is NP-complete even if the size of $\mathcal {C}(p_{h}, q_{h})$ is at most 4 for each $h\in H$.

Proof

We use reduction from the NP-complete problem (3, B2)-SAT [2], which is a restriction of SAT such that each clause contains exactly three literals and each variable occurs exactly twice as a positive literal and exactly twice as a negative literal. Let $\varphi =c_{1}\wedge c_{2}\wedge \cdots \wedge c_{m}$ be an instance of (3, B2)-SAT with Boolean variables $v_{1}, v_{2},\dots ,v_{n}$. Then, each clause $c_{j}$ is a disjunction of three literals, (e.g., $c_{j}=v_{1}\vee \lnot v_{2}\vee \lnot v_{3}$) and each of literals $v_{i}$ and $\lnot v_{i}$ appears in exactly two clauses. For each variable $v_{i}$, denote by $j^{*}(i,1)$, $j^{*}(i,2)$ the indices of two clauses that contain $v_{i}$. Similarly, denote by $j^{*}(i,-1)$, $j^{*}(i,-2)$ the indices of clauses that contain $\lnot v_{i}$.

We now define a CSM instance corresponding to $\varphi$. We have a variable-hospital $h_{i}$ for each variable $v_{i}$, and a clause-hospital $h_{j}$ for each clause $c_{j}$. For each variable $v_{i}$, we have four doctors . For each doctor $d_{i,t}$, we have

$$\begin{aligned} A(d_{i,t})=\{h_{i},h_{j^{*}(i,t)}\},\quad h_{i}\succ _{d_{i,t}} h_{j^{*}(i,t)}. \end{aligned}$$

The set E is defined as the set of all pairs $(d_{i,t},h)$ such that $h\in A(d_{i,t})$. Then, for each variable-hospital $h_{i}$ and clause-hospital $h_{j}$, we have

Note that $d_{i,t}\in A(h_{j})$ implies $v_{i}\in c_{j}$ or $\lnot v_{i}\in c_{j}$. Also, each of $v_{i}\in c_{j}$ and $\lnot v_{i}\in c_{j}$ implies $d_{i,t}\in A(h_{j})$ for some unique $t\in \{1,2,-1,-2\}$. Therefore, $|A(h_{j})|=3$ for each clause-hospital $h_{j}$. For each variable-hospital $h_{i}$, define $p_{h_{i}}$ and $q_{h_{i}}$ so that

Then, we see that $\mathcal {F}(p_{h_{i}}, q_{h_{i}})=\{D^{+}_{i}, D^{-}_{i}\}$, where $D^{+}_{i}:=\{d_{i,1}, d_{i,2}\}$ and $D^{-}_{i}:=\{d_{i,-1}, d_{i,-2}\}$. For each clause-hospital $h_{j}$, define $p_{h_{i}}$ and $q_{h_{i}}$ so that

$$\begin{aligned} \mathcal {C}(p_{h_{j}}, q_{h_{j}})=\{A(h_{j})\},~~ p_{h_{j}}(A(h_{j}))=1,~~q_{h_{j}}(A(h_{j}))=|A(h_{j})|=3. \end{aligned}$$

We define preference lists of hospitals arbitrarily. Note that $|\mathcal {C}(p_{h}, q_{h})|\le 4$ for every hospital. We show that this CSM instance has an envy-free matching if and only if $\varphi =c_{1}\wedge c_{2}\wedge \cdots \wedge c_{m}$ is satisfiable.

The “only if” part: Suppose that there is an envy-free matching M. Then, for every variable-hospital $h_{i}$, $M(h_{i})$ is $D^{+}_{i}$ or $D^{-}_{i}$. For each $h_{i}$, set variable $v_{i}$ to FALSE if $M(h_{i})=D^{+}_{i}$, and to TRUE if $M(h_{i})=D^{-}_{i}$. This Boolean assignment satisfies every clause $c_{j}$ of $\varphi$ as follows. Because $M(h_{j})\in \mathcal {F}(p_{h_{j}}, q_{h_{j}})$, we have $|M(h_{j})|\ge 1$. Hence, some $d_{i,t}$ with $j^{*}(i,t)=j$ is assigned to $h_{j}$. Then, $d_{i,t}\not \in M(h_{i})$. There are two cases: (i) $t\in \{1,2\}$, (ii) $t\in \{-1,-2\}$. In the case (i), $d_{i,t}\not \in M(h_{i})$ implies $M(h_{i})\ne D^{+}_{i}$, and hence $v_{i}$ is set to TRUE. Also, $t\in \{1,2\}$ and $j^{*}(i,t)=j$ imply $v_{i}\in c_{j}$. Hence, clause $c_{j}$ is satisfied. Similarly, in the case (ii), we see that $v_{i}$ is set to FALSE and we have $\lnot v_{j}\in c_{j}$. Hence, clause $c_{j}$ is satisfied.

The “if” part: Suppose that there is a Boolean assignment satisfying $\varphi$. Define an assignment M so that

• $M(h_{i})=D^{-}_{i}$ if $v_{i}$ is TRUE, and $M(h_{i})=D^{+}_{i}$ if $v_{i}$ is FALSE, and

• .

We can observe that $|M(d)|=1$ for every doctor d, and $M(h_{i})\in \mathcal {F}(p_{h_{i}},q_{h_{i}})$ for every variable-hospital $h_{i}$. Also, because all clauses are satisfied, the above definition implies $M(h_{j})\in \mathcal {F}(p_{h_{j}},q_{h_{j}})$ for every clause-hospital $h_{j}$. Then, M is feasible. We now show the envy-freeness of M. Suppose, to the contrary, $d_{i,t}$ has justified envy toward $d'$. Because we have $|M(d_{i,t})|=1$, $A(d_{i,t})=\{h_{i}, h_{j^{*}(i,t)}\}$, and $h_{i}\succ _{d_{i,t}} h_{j^{*}(i,t)}$, this justified envy implies conditions $d'\in M(h_{i})$, $d_{i,t}\not \in M(h_{i})$ and $M(h_{i})+d_{i,t}-d'\in \mathcal {F}(p_{h_{i}}, q_{h_{i}})$. As $M(h_{i})\in \mathcal {F}(p_{h_{i}}, q_{h_{i}})=\{D^{+}_{i}, D^{-}_{i}\}$, then we have $\{M(h_{i})+d_{i,t}-d', M(h_{i})\}=\{D^{+}_{i}, D^{-}_{i}\}$, which contradicts $|D^{+}_{i}\setminus D^{-}_{i}|=|D^{-}_{i}\setminus D^{+}_{i}|=2$. $\square$

Remark 3.5

For the existence test of a stable matching of a CSM instance, Huang [23] showed the NP-completeness in a strong form, which states that the problem is NP-complete even if there is no lower quota. His proof uses a reduction from the One-in-Three SAT problem [15]; a CSM instance without lower quota is constructed so that it has a stable matching if and only if the given One-in-Three SAT instance is satisfiable. On the other hand, in the case of envy-free matching, we have to utilize lower quotas in a reduction because an envy-free matching trivially exists for every instance without lower quota. (Note that the empty matching is envy-free.)

4 Envy-Freeness in CSM with Paramodular Quotas

In Sect. 3, we showed that it is NP-hard in general to decide whether a CSM instance has an envy-free matching or not. This section shows that the problem is solvable in polynomial time if the pair of quota functions is paramodular for each hospital. The proofs of the theorems and corollary in this section are provided in Sect. 5. We first introduce the notion of paramodularity [10].

Let A be a finite set and let $p, q:2^{A}\rightarrow \mathbf {Z}$. The pair (p, q) is paramodular (or, called a strong pair [11]) if

• p is supermodular, i.e., $p(B)+p(B')\le p(B\cup B')+p(B\cap B')$ for every $B, B'\subseteq A$,

• q is submodular, i.e., $q(B)+q(B')\ge q(B\cup B')+q(B\cap B')$ for every $B, B'\subseteq A$, and

• the cross-inequality$q(B)-p(B')\ge q(B\setminus B')-p(B'\setminus B)$ holds for every $B, B'\subseteq A$.

The notion of paramodularity was introduced independently by Frank [9] and Hassin [20, 21]. Here we provide examples of constraints that can be represented by paramodular pairs. (See Yokoi [39, Appendices A and B].)

Example 4.1

(Laminar Constraints) Let $\mathcal {L}\subseteq 2^{A}$ be a laminar (or hierarchical) classification (i.e., any $B, B'\subseteq \mathcal {L}$ satisfy $B\subseteq B'$ or $B\supseteq B'$ or $B\cap B'\ne \emptyset$). Let ${\hat{p}}, {\hat{q}}: \mathcal {L}\rightarrow \mathbf {Z}$ be functions that define a lower and an upper quota for each class. Denote the acceptable set family by . If $\mathcal {J}(\mathcal {L}, {\hat{p}}, {\hat{q}})$ is nonempty, then $\mathcal {J}(\mathcal {L}, {\hat{p}}, {\hat{q}})=\mathcal {F}(p,q)$ for some paramodular pair (p, q).

Example 4.2

(Staffing Constraints) For a finite set S (e.g., a set of sections of a hospital), let $\Gamma :S\rightarrow 2^{A}$ and ${\hat{l}}, \hat{u}:S\rightarrow \mathbf {Z}$ be functions such that $\Gamma (s)\subseteq A$ represents the set of members acceptable to $s\in S$ and ${\hat{l}}(s), \hat{u}(s)\in \mathbf {Z}$ represent a lower and an upper quota of $s\in S$. Let $\mathcal {J}(S,\Gamma ,{\hat{l}}, \hat{u})\subseteq 2^{A}$ be a family of subsets $X\subseteq A$ such that there exists a function $\pi :X\rightarrow S$ satisfying $\forall d\in X: d\in \Gamma (\pi (d))$ and . If $\mathcal {J}(S,\Gamma ,{\hat{l}}, \hat{u})$ is nonempty, then $\mathcal {J}(S,\Gamma ,{\hat{l}},\hat{u})=\mathcal {F}(p,q)$ for some paramodular pair (p, q).

For a set function $p:2^{A}\rightarrow \mathbf {Z}$, its complement$\overline{p}:2^{A}\rightarrow \mathbf {Z}$ is defined by

$$\begin{aligned} \overline{p}(B)=p(A)-p(A\setminus B)\quad (B\subseteq A). \end{aligned}$$

Recall that a CSM instance is represented as a tuple $(D, H, E, \succ _{DH}, \{(p_{h}, q_{h})\}_{h\in H})$, where it is assumed that $0\le p_{h}(B)\le q_{h}(B)\le |B|$ for every $h\in H$ and $B\subseteq A(h)$. Here is the main theorem of this section. We denote by $\mathbf{0}$ a set function that is identically zero.

Theorem 4.3

For a CSM instance $I=(D, H, E, \succ _{DH}, \{(p_{h}, q_{h})\}_{h\in H})$, suppose that $(p_{h}, q_{h})$ is paramodular for each $h\in H$. Then, $I':=(D, H, E, \succ _{DH}, \{(\mathbf{0},\overline{p_{h}})\}_{h\in H})$ has at least one stable matching and the following three conditions are equivalent.

• (a) I has an envy-free matching.

• (b) Some stable matching $M'$ of $I'$ satisfies $|M'(h)|=p_{h}(A(h))$ for all $h\in H$.

• (c) Every stable matching $M'$ of $I'$ satisfies $|M'(h)|=p_{h}(A(h))$ for all $h\in H$.

Also, if (b) holds, then $M'$ is an envy-free matching of I.

As will be shown in Sect. 5.4, the existence of a stable matching of $I'$ and the equivalence between (b) and (c) follows from Fleiner’s results on the matroid framework [5, 6]. The most difficult part is showing the equivalence between conditions (a) and (b). To show that (a) implies (b), we construct a stable matching $M'$ of $I'$ from an envy-free matching M of I. This construction is achieved by using the fixed-point method of Fleiner [6]. The paramodularity of each $(p_{h}, q_{h})$ (or a generalized matroid structure of each $\mathcal {F}(p_{h}, q_{h})$) is essential to show the existence of a fixed-point satisfying a required condition (see Lemma 5.16 in Sect. 5.4 for the details).

By Theorem 4.3, when quota function pairs are paramodular, we can decide the existence of an envy-free matching of $I=(D, H, E, \succ _{DH}, \{(p_{h}, q_{h})\}_{h\in H})$ by the following algorithm.

Step1.:

Find a stable matching $M'$ of $I'=(D, H, E, \succ _{DH}, \{(\mathbf{0}, \overline{p_{h}})\}_{h\in H})$.

Step2.:

If $|M'(h)|=p_{h}(A(h))$ for every $h\in H$, then return $M'$. Otherwise, return “there is no envy-free matching.”

As will be shown in Sect. 5, Step 1 (i.e., finding a stable matching of $I'$) can be done efficiently by the generalized Gale-Shapley algorithm studied in [5, 6]. The detailed description of the algorithm is as follows. Here, for each $h\in H$, $N\subseteq E$, and $d\in N(h)$, we use the notation and .

In Sect. 5, we show that the assignment $M'$ obtained in the algorithm is indeed a stable matching of $I'$. Also, it will be shown that $N_{D}$ is monotone decreasing and $N_{H}$ is monotone increasing in the algorithm, and hence the “while loop” is iterated at most 2|E| times. Thus, we obtain the following theorem. (See Sect. 5.5 for the details.)

Theorem 4.4

For a CSM instance $I=(D, H, E, \succ _{DH}, \{(p_{h}, q_{h})\}_{h\in H})$ such that each $(p_{h}, q_{h})$ is paramodular, the algorithm EF-Paramodular-CSM decides whether I has an envy-free matching or not in $O(|E|^{2})$ time, provided that evaluation oracles of $\{p_{h}\}_{h\in H}$ are available.

As is shown in Examples 4.1 and 4.2, when the family of acceptable doctor sets of each hospital $h\in H$ is defined by a laminar constraint $\mathcal {J}_{h}:=\mathcal {J}(\mathcal {L}_{h}, {\hat{p}}_{h}, {\hat{q}}_{h})$ or by a staffing constraint $\mathcal {J}_{h}:=\mathcal {J}(S_{h}, \Gamma _{h}, {\hat{l}}_{h}, \hat{u}_{h})$, then there is a paramodular pair $(p_{h}, q_{h})$ such that $\mathcal {J}_{h}=\mathcal {F}(p_{h}, q_{h})$. The following corollary states that, in such a case, we can decide the existence of an envy-free matching of $I=(D, H, E, \succ _{DH}, \{(p_{h}, q_{h})\}_{h\in H})$ even if evaluation oracles of $\{p_{h}\}_{h\in H}$ are not provided.

Corollary 4.5

Suppose that, for each $h\in H$, the family of acceptable doctor sets is defined in the form $\mathcal {J}_{h}:=\mathcal {J}(\mathcal {L}_{h}, {\hat{p}}_{h}, {\hat{q}}_{h})\ne \emptyset$ (resp., $\mathcal {J}_{h}:=\mathcal {J}(S_{h}, \Gamma _{h}, {\hat{l}}_{h}, \hat{u}_{h})\ne \emptyset$ ). Let $(p_h, q_{h})$ be a paramodular pair such that $\mathcal {J}_{h}=\mathcal {F}(p_h, q_{h})$. Then, given $\mathcal {L}_{h}, {\hat{p}}_{h}, {\hat{q}}_{h}$ (resp., $S_{h}, \Gamma _{h}, {\hat{l}}_{h}, \hat{u}_{h}$ ) for each $h\in H$, one can decide whether $I=(D, H, E, \succ _{DH}, \{(p_{h}, q_{h})\}_{h\in H})$ has an envy-free matching or not in time polynomial in |E| (resp., in |E| and $\max _{h\in H}|S_{h}|$ ).

Proof

Since we have Theorem 4.4, it completes the proof to show that we can simulate an evaluation oracle of each $p_{h}$ in time polynomial in |E| (resp., in |E| and $|S_{h}|$). By Proposition 5.1 in Sect. 5.1, for each $B\subseteq A(h)$, the value of $p_{h}(B)$ is obtained as $p_{h}(B)=\min \{~|X\cap B|\mid X\in \mathcal {J}_{h}\}$. Consider a weight function $w_{B}$ on A(h) such that $w_{B}(d)=1$ for every $d\in B$ and $w_{B}(d)=0$ for every $d\in A(h)\setminus B$. Then, $p_{h}(B)$ is written as , which is a weight minimization problem on a generalized matroid. As explained in [39, Appendix C], when $\mathcal {J}_{h}$ is given in the form above, this can be reduced to the minimum cost circulation problem, which can be solved in strongly polynomial time [31, 37]. (See [39] for the details of the reduction.) Thus, the proof is completed.

Remark 4.6

Theorems 4.3 and 4.4 generalize Theorems 2.6 and 2.7 as follows. For a pair $(l_{h}, u_{h})$ of nonnegative integers with $0\le u_{h}\le l_{h}\le |A(h)|$, define $p_{h}, q_{h}:2^{A(h)}\rightarrow \mathbf {Z}$ by

$$\begin{aligned}&p_{h}(B)=\max \{0, l_{h}-|A(h)\setminus B|\},\quad q_{h}(B)=\min \{u_{h}, |B|\},\qquad (B\subseteq A(h)). \end{aligned}$$

Then, $(p_{h}, q_{h})$ is paramodular and . Hence, envy-freeness for $(D, H, E, \succ _{DH}, \{l_{h}, u_{h}\}_{h\in H})$ coincides with that for $(D, H, E, \succ _{DH}, \{p_{h}, q_{h}\}_{h\in H})$. Also, we can check $p_{h}(A(h))= \max \{0, l_{h}-|A(h)\setminus A(h)|\}=l_{h}$.

Remark 4.7

Theorem 4.4 says that we can efficiently check the existence of an envy-free matching if each quota function pair is paramodular, where the paramodurality of a function pair is defined by the super- and submodularity of each function and the cross-inequality between them. We remark that the cross-inequality is essential for this tractability. Without this condition, it is NP-hard to check the existence of an envy-free matching even if each quota function pair consists of super- and submodular functions. See the Appendix for the proof, which uses a reduction from the NP-complete problem Disjoint Matchings [12].

5 Proofs

In this section, we provide proofs of Theorems 4.3, 4.4. This section consists of five subsections. The first three introduce notions and previous results needed for the proofs. More precisely, Sects. 5.1, 5.2, and 5.3 respectively introduce notions of generalized matroids, choice functions induced from matroids, and the lattice fixed-point method for stable matchings. Using them, the last two subsections provide the proofs of our results.

5.1 Generalized Matroids

For a finite set A and a family $\mathcal {J}\subseteq 2^{A}$, the pair $(A,\mathcal {J})$ is called a generalized matroid [36] (g-matroid, for short) if $\mathcal {J}$ is nonempty and satisfies the following property called simultaneous (or symmetric) exchange property² [30].

(B$^{\natural }$-EXC):

For any $X, Y\in \mathcal {J}$ and $e\in X\setminus Y$, we have

(i):

$X-e\in \mathcal {J}$, $Y+e\in \mathcal {J}$ or

(ii):

there exists some $e'\in Y\setminus X$ such that $X-e+e'\in \mathcal {J}$, $Y+e-e'\in \mathcal {J}$.

The family $\mathcal {J}$ of a g-matroid $(A, \mathcal {J})$ is also called an $\mathbf{M}^{\natural }$-convex family [28, 29]. (There are various characterizations for g-matroids. See, e.g., Tardos [36], Frank [10] and Murota [28] for more information on g-matroid and its extensions.)

For set functions $p,q:2^{A}\rightarrow \mathbf {Z}$, the pair (p, q) is called g-matroidal if it is paramodular and satisfies $0\le p(B)\le q(B)\le |B|$ for every $B\subseteq A$. As its name indicates, there is a one-to-one correspondence between generalized matroids and g-matroidal pairs (see, e.g., [10, 11]).

Proposition 5.1

A pair $(A,\mathcal {J})$ is a g-matroid if and only if $\mathcal {J}=\mathcal {F}(p,q)$ for some g-matroidal pair (p, q). Such a g-matroidal pair is uniquely defined by

$$\begin{aligned} p(B)=\min \{|X\cap B|\mid X\in \mathcal {J}\}\qquad (B\subseteq A),\\ q(B)=\max \{|X\cap B|\mid X\in \mathcal {J}\}\qquad (B\subseteq A). \end{aligned}$$

By Proposition 5.1, the families $\mathcal {J}(\mathcal {L}, {\hat{p}}, {\hat{q}})$ and $\mathcal {J}(S,\Gamma ,{\hat{l}}, \hat{u})$ defined in Examples 4.1 and 4.2 are the independent set families of g-matroids. (See Yokoi [39, Appendices A and B] for examples and operations of g-matroids.)

A function $r:2^{A}\rightarrow \mathbf {Z}$ is called a matroid rank function if it is submodular, monotone (i.e., $B\subseteq B'\subseteq A$ implies $r(B)\le r(B')$), and satisfies $0\le r(B)\le |B|$ for every $B\subseteq A$. The submodularity of r is equivalent to the following diminishing returns property: for any $B'\subseteq B\subseteq A$ and $e\in A\setminus B$, we have

$$\begin{aligned} r(B+e)-r(B)\le r(B'+e)-r(B'). \end{aligned}$$

In particular, a matroid rank function satisfies $0\le r(B+e)-r(B)\le r(\{e\})-r(\emptyset )\le 1$ for any $B\subseteq A$ and $e\in A\setminus B$.

A pair $(A,\mathcal {I})$ is called a matroid if it is a g-matroid and $\emptyset \in \mathcal {I}$. In terms of quota functions, a pair $(A,\mathcal {I})$ is a matroid if there is a matroid rank function r such that $\mathcal {I}=\mathcal {F}(\mathbf{0},r)$. Indeed, we can check that the pair $(\mathbf{0}, r)$ is g-matroidal for any matroid rank function r.

5.2 Choice Functions Induced from Matroid Rank Functions

Let $r:2^{A}\rightarrow \mathbf {Z}$ be a matroid rank function on A and $\succ$ be a linear order on A. Let $\mathscr {M}=(A, r,\succ )$ and define a function $C_{\!\mathscr {M}}:2^{A}\rightarrow 2^{A}$ as follows. Let $n=|A|$ and, for $i=1,2,\dots , n$, let $e_{i}$ be the i-th best element of A with respect to $\succ$, i.e. $e_{1}\succ e_{2}\succ \cdots \succ e_{n}$. Let $A_{0}:=\emptyset$ and $A_{i}:=\{e_{1}, e_{2},\dots ,e_{i}\}$ for each $i=1,2, \dots ,n$. Then, define $C_{\!\mathscr {M}}$ by

We call $C_{\!\mathscr {M}}$ the choice function induced from$\mathscr {M}=(A, r,\succ )$. Note that, for any $e_{i}\in A$ and $X\subseteq A$, the value of $r(A_{i}\cap X)-r(A_{i-1}\cap X)$ is 1 or 0 by the monotonicity and submodularity of r. Also, if $e_{i}\not \in X$, then clearly $r(A_{i}\cap X)-r(A_{i-1}\cap X)=0$. Hence, for any $X\subseteq A$,

(1)

(2)

Such a choice function was introduced by Fleiner [5, 6] and used in several works [3, 7, 39]. In these works, matroids are usually given by independent set families rather than matroid rank functions. The following propositions (Propositions 5.2–5.6) are known facts, but we provide alternative proofs in terms of matroid rank functions.

Proposition 5.2

For any $X\subseteq A$, we have $C_{\!\mathscr {M}}(X)\in \mathcal {F}(\mathbf{0},r)$.

Proof

It suffices to show $|C_{\!\mathscr {M}}(X)\cap B|\le r(B)$ for any $B\subseteq A$. By (1), we have . For any $e_{i}\in B$, since $A_{i-1}\cap X\cap B\subseteq A_{i-1}\cap X$ and $A_{i}\cap X\cap B=(A_{i-1}\cap X\cap B)+e_{i}$, the diminishing returns property of r implies

$$\begin{aligned} r(A_{i}\cap X)-r(A_{i-1}\cap X)\le r(A_{i}\cap X\cap B)-r(A_{i-1}\cap X\cap B). \end{aligned}$$

Thus, $e_{i}\in B$, $r(A_{i}\cap X)-r(A_{i-1}\cap X)=1$ imply $r(A_{i}\cap X\cap B)-r(A_{i-1}\cap X\cap B)=1$. Therefore,

The monotonicity of r implies $r(X\cap B)\le r(B)$, and the proof is completed. $\square$

Proposition 5.3

For every $X\subseteq A$ and $j=1,2,\dots , n$, we have $|C_{\!\mathscr {M}}(X)\cap A_{j}|=r(A_{j}\cap X)$. In particular, $|C_{\!\mathscr {M}}(X)|=r(X)$.

Proof

By (1), . This implies $|C_{\!\mathscr {M}}(X)\cap A_{i}| =\textstyle {\sum _{i:1\le i\le j}} [~r(A_{i}\cap X)-r(A_{i-1}\cap X)~] =r(A_{j}\cap X)-r(A_{0}\cap X)=r(A_{j}\cap X)$. $\square$

Proposition 5.4

$C_{\!\mathscr {M}}$ is substitutable, i.e., $X\subseteq Y\subseteq A$ implies $X\setminus C_{\!\mathscr {M}}(X)\subseteq Y\setminus C_{\!\mathscr {M}}(Y)$.

Proof

Suppose that $e_{i}\in X\setminus C_{\!\mathscr {M}}(X)$ for some i. This implies $r(A_{i}\cap X)-r(A_{i-1}\cap X)=0$ by (2). By the diminishing returns property and $X\subseteq Y$, the value of $r(A_{i}\cap Y)-r(A_{i-1}\cap Y)$ is also 0, and hence $e_{i}\in Y\setminus C_{\!\mathscr {M}}(Y)$ by (2). $\square$

Proposition 5.5

$C_{\!\mathscr {M}}$ is size-monotone, i.e., $X\subseteq Y\subseteq A$ implies $|C_{\!\mathscr {M}}(X)|\le |C_{\!\mathscr {M}}(Y)|$.

Proof

This immediately follows from Proposition 5.3 and the monotonicity of r. $\square$

Proposition 5.6

For any $X\subseteq A$, the set $C_{\!\mathscr {M}}(X)$dominates every element in $X\setminus C_{\!\mathscr {M}}(X)$. That is, the following two hold.

• For every $e\in X\setminus C_{\!\mathscr {M}}(X)$, we have $C_{\!\mathscr {M}}(X)+e\not \in \mathcal {F}(\mathbf{0}, r)$.

• For every $e\in X\setminus C_{\!\mathscr {M}}(X)$ and $e'\in C_{\!\mathscr {M}}(X)$, if $e\succ e'$, then $C_{\!\mathscr {M}}(X)+e-e'\not \in \mathcal {F}(\mathbf{0}, r)$.

Proof

Let i be the index such that $e=e_{i}$, i.e., e is the i-th best element for $\succ$. By Proposition 5.3, we have $|C_{\!\mathscr {M}}(X)\cap A_{i}|=r(A_{i}\cap X)$. With $C_{\!\mathscr {M}}(X)\subseteq X$ and $e_{i}\in X\setminus C_{\!\mathscr {M}}(X)$, this implies $|(C_{\!\mathscr {M}}(X)+e_{i})\cap (A_{i}\cap X)|=|C_{\!\mathscr {M}}(X)\cap A_{i}|+1>r(A_{i}\cap X)$, and hence $C_{\!\mathscr {M}}(X)+e_{i}\not \in \mathcal {F}(\mathbf{0}, r)$.

For the second claim, let $i'$ be the index such that $e'=e_{i'}$. Then, $e\succ e'$ implies $i<i'$, and hence $e_{i'}\not \in A_{i}$. This yields $|(C_{\!\mathscr {M}}(X)+e_{i}-e_{i'})\cap (A_{i}\cap X)|=|C_{\!\mathscr {M}}(X)\cap A_{i}|+1>r(A_{i}\cap X)$, which implies $C_{\!\mathscr {M}}(X)+e_{i}-e_{i'}\not \in \mathcal {F}(\mathbf{0}, r)$. $\square$

5.3 Fixed-point Method for Stable Matchings on Matroids

Here we introduce the lattice fixed-point framework for stable matchings on matroids, studied by Fleiner [5, 6]. (Note that in [6] a substitutable choice function is called a “comonotone function,” and also note that in [5, 6] results are given for general “matroid kernels” rather than stable matchings on matroids. See also [39, Lemma 9], which says that stable matchings correspond to matroid kernels in the current setting.)

Let $I=(D, H, E, \succ _{DH}, \{\mathbf{0}, r_{h}\}_{h\in H})$ be a CSM instance such that $r_{h}$ is a matroid rank function for each $h\in H$. That is, each hospital has a matroidal upper quota function and no lower quota.

From $(D, E, \{\succ _{d}\}_{d\in D})$, we define doctors’ joint choice function $C_{D}:2^{E}\rightarrow 2^{E}$. For any set $N\subseteq E$, let $C_{D}(N)$ be the set of each doctor’s best choices among N, i.e.,

From $(H, E, \{\succ _{h}\}_{h\in H}, \{r_{h}\}_{h\in H})$, we define hospitals’ joint choice function $C_{H}:2^{E}\rightarrow 2^{E}$. First, for each hospital $h\in H$, let $C_{h}:2^{A(h)}\rightarrow 2^{A(h)}$ be a choice function induced from $(A(h), r_{h}, \succ _{h})$ as in Sect. 5.2. Then, define $C_{H}$ by

Define rejection functions $R_{D}, R_{H}:2^{E}\rightarrow 2^{E}$ by

$$\begin{aligned} R_{D}(N)=N\setminus C_{D}(N),\quad R_{H}(N)=N\setminus C_{H}(N)\quad (N\subseteq E), \end{aligned}$$

and a function $F_{I}:2^{E}\times 2^{E}\rightarrow 2^{E}\times 2^{E}$ by

$$\begin{aligned} F_{I}(N_{D}, N_{H})=(E\setminus R_{H}(N_{H}),~ E\setminus R_{D}(N_{D}))\quad (N_{D}, N_{H}\subseteq E). \end{aligned}$$

Then a fixed-point of $F_{I}$ gives a stable matching of the CSM instance I (see Claim 17 and the proofs of Theorems 11 and 18 in [6]).

Proposition 5.7

(Fleiner [6]) For $I=(D, H, E, \succ _{DH}, \{\mathbf{0}, r_{h}\}_{h\in H})$ such that each $r_{h}$ is a matroid rank function, if $(N_{D}, N_{H})$ is a fixed-point of $F_{I}$, then $N_{D}\cap N_{H}=C_{D}(N_{D})=C_{H}(N_{H})$ holds and $N_{D}\cap N_{H}$ is a stable matching of I.

Let $\ge$ be a partial order defined on $2^{E}\times 2^{E}$ as

$$\begin{aligned} (N_{D}, N_{H})\ge (N'_{D}, N'_{H})\iff [N_{D}\supseteq N'_{D}, ~N_{H}\subseteq N'_{H}] \end{aligned}$$

Recall that $C_{h}$ is substitutable for each $h\in H$, This implies the following property of $F_{I}$ (see, Claim 17 and the proof of Theorem 11 of [6]).

Proposition 5.8

(Fleiner [6]) For $I=(D, H, E, \succ _{DH}, \{\mathbf{0}, r_{h}\}_{h\in H})$ such that each $r_{h}$ is a matroid rank function, the function $F_{I}$ is monotone with respect to $\ge$. That is, $(N_{D}, N_{H})\ge (N'_{D}, N'_{H})$ implies $F_{I}(N_{D}, N_{H})\ge F_{I}(N'_{D}, N'_{H})$.

The monotonicity of $F_{I}$ implies the existence of a stable matching as follows (see the first two paragraphs in [6, p.113] and the proof of Theorem 2 in [5]).

Proposition 5.9

(Fleiner [5, 6]) Let $I=(D, H, E, \succ _{DH}, \{\mathbf{0}, r_{h}\}_{h\in H})$ be an instance such that each $r_{h}$ is a matroid rank function. One can find a stable matching in $O(|E|\cdot \mathrm{EO}_{DH})$ time, where $\mathrm{EO}_{DH}$ is a time to compute $C_{D}(N)$ and $C_{H}(N)$ for any $N\subseteq E$.

Proof

Since $(E,\emptyset )$ is the maximum in $2^{E}\times 2^{E}$ with respect to $\ge$, we have $(E,\emptyset )\ge F_{I}(E,\emptyset )$. As $F_{I}$ is monotone by Proposition 5.8, then

$$\begin{aligned} (E,\emptyset )\ge F_{I}(E,\emptyset )\ge F_{I}(F_{I}(E,\emptyset ))\ge \cdots \ge F_{I}^{k}(E,\emptyset )\ge \cdots . \end{aligned}$$

Since $2^{E}\times 2^{E}$ is a finite lattice whose longest chain is of length 2|E|, we have $F_{I}^{k}(E,\emptyset )=F_{I}(F_{I}^{k}(E,\emptyset ))$ for some $k\le 2|E|$. Then, $(N^{*}_{D}, N^{*}_{H}):=F_{I}^{k}(E,\emptyset )$ is a fixed-point of $F_{I}$ and, by Proposition 5.7, $N^{*}_{D}\cap N^{*}_{H}$ is a stable matching of I. $\square$

The following proposition is an immediate consequence of Fleiner’s result on the structure of the set of stable matchings (see Corollary 27 in [6] and the proof of Theorem 3 in [5]).

Proposition 5.10

(Fleiner [5, 6]) Let $I=(D, H, E, \succ _{DH}, \{\mathbf{0}, r_{h}\}_{h\in H})$ be an instance such that each $r_{h}$ is a matroid rank function. For any two stable matchings $M, M'\subseteq E$ of I and any hospital $h\in H$, we have $|M(h)|=|M'(h)|$.

5.4 Proof of Theorem 4.3

We are now ready to show Theorem 4.3. Recall that I and $I'$ are defined as

$$\begin{aligned}&I=(D, H, E, \succ _{DH}, \{(p_{h}, q_{h})\}_{h\in H}),\\&I'=(D, H, E, \succ _{DH}, \{(\mathbf{0},\overline{p_{h}})\}_{h\in H}), \end{aligned}$$

where $(p_{h}, q_{h})$ is g-matroidal (i.e., is paramodular and satisfies $0\le p_{h}(B)\le q_{h}(B)\le |B|$) for each $h\in H$. Here, $\overline{p_{h}}$ is the complement of $p_{h}$ defined as $\overline{p_{h}}(B)=p_{h}(A(h))-p_{h}(A(h)\setminus B)$. Observe the following basic fact of a g-matroidal pair.

Claim 5.11

$\overline{p_{h}}$ is a matroid rank function and $\overline{p_{h}}(A(h))=p_{h}(A(h))$ for each $h\in H$.

Proof

Since $(p_{h}, q_{h})$ is g-matroidal, $p_{h}$ is supermodular and $0\le p_{h}(B)\le |B|$ for any $B\subseteq A(h)$. Also, Proposition 5.1 implies that $p_{h}$ is monotone. Therefore, $\overline{p_{h}}$ is submodular, monotone, and $0\le \overline{p_{h}}(B)\le |B|$ for every $B\subseteq A(h)$, i.e., $\overline{p_{h}}$ is a matroid rank function. In addition, we see that $\overline{p_{h}}(A(h))=p_{h}(A(h))-p_{h}(\emptyset )=p_{h}(A(h))$. $\square$

By Claim 5.11, Propositions 5.9 and 5.10 imply the following.

Lemma 5.12

$I'$ has a stable matching. Also, for any stable matchings M and $M'$ of I and any hospital $h\in H$, we have $|M(h)|=|M'(h)|$.

Lemma 5.12 implies that $I'$ has a stable matching and that conditions (b) and (c) in Theorem 4.3 are equivalent.

What is left is to show that the condition (a) is also equivalent. For this purpose, we prepare the following three claims. The first and second claims are basic facts of paramodular functions [10]. The third one utilizes the exchange property of g-matroids (M$^{\natural }$-convex families).

Claim 5.13

For any $h\in H$ and $X\subseteq A(h)$, suppose that $|X|=\overline{p_{h}}(A(h))=p_{h}(A)$ holds. Then, we have $X\in \mathcal {F}(\mathbf{0}, \overline{p_{h}})$ if and only if $X\in \mathcal {F}(p_{h}, q_{h})$.

Proof

We abbreviate $p_{h}$, $q_{h}$, A(h) to p, q, A, respectively, and denote $\overline{B}:=A\setminus B$ for $B\subseteq A$.

To show the “if” part, suppose $X\in \mathcal {F}(p,q)$. Then $|X\cap \overline{B}|\ge p(\overline{B})$ for any $B\subseteq A$. Since $|X|=p(A)$, then $|X\cap B|=|X|-|X\cap \overline{B}|\le p(A)-p(\overline{B})=\overline{p}(B)$. Thus, $X\in \mathcal {F}(\mathbf{0}, \overline{p})$.

To show the “only if” part, suppose $X\in \mathcal {F}(\mathbf{0}, \overline{p})$. We show $p(B)\le |X\cap B|\le q(B)$ for any $B\subseteq A$. By the cross-inequality $q(B)-p(A)\ge q(B\setminus A)-p(A\setminus B)$, we have $q(B)\ge p(A)-p(\overline{B})$, which implies $|X\cap B|\le \overline{p}(B)=p(A)-p(\overline{B})\le q(B)$, and thus $|X\cap B|\le q(B)$. Also, since $|X\cap \overline{B}|\le \overline{p}(\overline{B})=p(A)-p(B)$, we have $|X\cap B|=|X|-|X\cap \overline{B}|\ge p(B)$. $\square$

Since $\overline{p_{h}}$ is a matroid rank function for each $h\in H$, we can define the choice function $C_{h}:2^{A(h)}\rightarrow 2^{A(h)}$ induced from $(A(h), \overline{p_{h}},\succ _{h})$ as in Sect. 5.3.

Claim 5.14

For any $h\in H$, let $C_{h}$ be the choice function induced from $(A(h), \overline{p_{h}},\succ _{h})$. For $Y\subseteq A(h)$, if there exists $X\in \mathcal {F}(p_{h}, q_{h})$ such that $X\subseteq Y$, then $|C_{h}(Y)|=p_{h}(A(h))$.

Proof

We abbreviate $p_{h}$, $q_{h}$, A(h), $C_{h}$ to p, q, A, C, respectively.

By Proposition 5.2, $C(Y)\in \mathcal {F}(\mathbf{0}, \overline{p})$, and hence $|C(Y)|=|C(Y)\cap A|\le \overline{p}(A)$. Also, Propositions 5.3 and 5.5 implies $\overline{p}(X)=|C(X)|\le |C(Y)|$. Since $X\in \mathcal {F}(p,q)$, we have $0\le p(A\setminus X)\le |X\cap (A\setminus X)|=0$, and hence $\overline{p}(X)=p(A)-p(A\setminus X)=p(A)=\overline{p}(A)$. Combining these yields $\overline{p}(A)\le |C(Y)|\le \overline{p}(A)$, and hence $|C(Y)|=\overline{p}(A)=p(A)$. $\square$

Claim 5.15

For any $h\in H$, let $C_{h}$ be the choice function induced from $(A(h), \overline{p_{h}},\succ _{h})$. Suppose that $X, Y\subseteq A(h)$ satisfy

• $X\in \mathcal {F}(p_{h}, q_{h})$ and $X\subseteq Y$, and

• for every $d\in Y\setminus X$ and $d'\in X$, if $d\succ _{h} d'$, then $X+d-d'\not \in \mathcal {F}(p_{h}, q_{h})$.

Then, $C_{h}(Y)\subseteq X$.

Proof

We abbreviate $p_{h}$, $q_{h}$, A(h), $C_{h}$ to p, q, A, C, respectively.

By Claim 5.14, $X\in \mathcal {F}(p,q)$ and $X\subseteq Y$ imply $|C(Y)|=p(A)=\overline{p}(A)$. Also, $C(Y)\in \mathcal {F}(\mathbf{0}, \overline{p})$ by Proposition 5.2. Then, Claim 5.13 implies $C(Y)\in \mathcal {F}(p,q)$. Thus, $X, C(Y)\in \mathcal {F}(p,q)$. Suppose, to the contrary, $C(Y)\subsetneq X$. Then there is some $d\in C(Y)\setminus X$. By the symmetric exchange axiom $(\mathbf{B}^{\natural }$-EXC) for C(X), Y, and d, we have either (i) $C(Y)-d, ~X+d\in \mathcal {F}(p,q)$, or (ii) $\exists d'\in X\setminus C(Y): C(Y)-d+d',~X+d-d'\in \mathcal {F}(p,q)$. Note that (i) cannot hold since $C(Y)-d\not \in \mathcal {F}(p,q)$ follows from $|C(Y)-d|<|C(Y)|=p(A)$. Then, (ii) holds, i.e., there exists $d'\in X\setminus C(Y)$ such that $C(Y)-d+d',~X+d-d'\in \mathcal {F}(p,q)$.

By $|C(Y)-d+d'|=|C(Y)|=p(A)$, Proposition 5.13 and $C(Y)-d+d'\in \mathcal {F}(p,q)$ imply $C(Y)-d+d'\in \mathcal {F}(\mathbf{0}, \overline{p})$. As $d\in C(Y)$ and $d'\in X\setminus C(Y)\subseteq Y\setminus C(Y)$, this implies $d\succ _{h} d'$ by Proposition 5.6. On the other hand, by $d\in Y\setminus X$, $d'\in X$, and $X+d-d'\in \mathcal {F}(p,q)$, the assumption of the claim implies $d'\succ _{h} d$, a contradiction.

$\square$

We now complete the proof of Theorem 4.3 by showing the following lemma, which states the equivalence between conditions (a) and (b) in Theorem 4.3.

Lemma 5.16

I has an envy-free matching if and only if some stable matching $M'$ of $I'$ satisfies $|M'(h)|=p_{h}(A(h))$ for all $h\in H$.

Proof

The “if” part: Let $M'$ be a stable matching of $I'$ such that $|M'(h)|=p_{h}(A(h))$ for all $h\in H$. We show that $M'$ is also an envy-free matching of I.

As $M'$ is feasible for $I'$, we have $|M'(d)|\le 1$ for every $d\in D$ and $M'(h)\in \mathcal {F}(\mathbf{0}, \overline{p_{h}})$ for every $h\in H$. By Claim 5.13 and $|M'(h)|=p_{h}(A(h))$, then $M'(h)\in \mathcal {F}(p_{h}, q_{h})$, and hence $M'$ is also a matching in I. Suppose, to the contrary, that there is a doctor $d\in D$ who has justified envy toward $d'\in D$ with $M'(d')=h$. Then, (i) d is unassigned or $h\succ _{h} M'(d)$ and (ii) $M'(h)+d-d'\in \mathcal {F}(p_{h}, q_{h})$ and $d\succ _{h} d'$. Note that $|M'(h)+d-d'|=|M'(h)|=p_{h}(A(h))$. Then, Claim 5.13 implies $M'(h)+d-d'\in \mathcal {F}(\mathbf{0}, \overline{p_{h}})$. This means that (d, h) is a blocking pair for $M'$ in $I'$, a contradiction.

The “only if” part: Suppose that I has an envy-free matching M. We now construct a stable matching $M'$ of $I'$ satisfying $|M'(h)|=p_{h}(A(h))$ for all $h\in H$.

For $I'=(D, H, E, \succ _{DH}, \{(\mathbf{0},\overline{p_{h}})\}_{h\in H})$, define $C_{D}, C_{H}:2^{E}\rightarrow 2^{E}$ as in Sect. 5.3. That is, $C_{D}$ returns the set of each doctor’s best choices and $C_{H}$ is defined by combining $\{C_{h}\}_{h\in H}$, where $C_{h}$ is induced from $(A(h), \overline{p_{h}},\succ _{h})$. From $C_{D}$ and $C_{H}$, we define $F_{I'}:2^{E}\times 2^{E}\rightarrow 2^{E}\times 2^{E}$ as in Sect. 5.3. Define two supersets $N_{D}, N_{H}\subseteq E$ of M by

Note that $N_{H}\setminus M=E\setminus N_{D}$, and hence every $(d, h)\subseteq N_{H}\setminus M$ satisfies $(d,h)\not \in N_{D}$, and hence $h\succ _{d} M(d)$. Since M is an envy-free matching, then for every $d'\in M(h)$ with $d\succ _{h} d'$ we have $M(h)+d-d'\not \in \mathcal {F}(p_{h}, q_{h})$, since otherwise d has justified envy toward $d'$. Thus, we have

• $M(h)\in \mathcal {F}(p_{h}, q_{h})$ and $M(h)\subseteq N_{H}(h)$, and

• for every $d\in N_{H}(h)\setminus M(h)$ and $d'\in M(h)$, if $d\succ _{h} d'$, then $M(h)+d-d'\not \in \mathcal {F}(p_{h}, q_{h})$.

Claim 5.15 then implies $C_{h}(N_{H}(h))\subseteq M(h)$ for each $h\in H$, and hence we have $C_{H}(N_{H})\subseteq M$. This implies

$$\begin{aligned} E\setminus R_{H}(N_{H})=(E\setminus N_{H})\cup C_{H}(N_{H})\subseteq (E\setminus N_{H})\cup M=N_{D}. \end{aligned}$$

(3)

Also, by the definition of $C_{D}$ and $N_{D}$, we have $C_{D}(N_{D})=M$, which implies

$$\begin{aligned} E\setminus R_{D}(N_{D})=(E\setminus N_{D})\cup C_{D}(N_{D})=(E\setminus N_{D})\cup M=N_{H}. \end{aligned}$$

(4)

Recall the partial order $\ge$ defined on $2^{E}\times 2^{E}$ in Sect. 5.3. By (3) and (4), we have

$$\begin{aligned} (N_{D}, N_{H})\ge (E\setminus R_{H}(N_{H}), E\setminus R_{D}(N_{D}))=F_{I'}(N_{D}, N_{H}). \end{aligned}$$

Since $F_{I'}$ is monotone by Proposition 5.8, this implies

$$\begin{aligned} (N_{D}, N_{H})\ge F_{I'}(N_{D}, N_{H})\ge F_{I'}(F_{I'}(N_{D}, N_{H}))\ge \cdots \ge F_{I'}^{k}(N_{D}, N_{H})\ge \cdots , \end{aligned}$$

and hence there is k such that $F_{I'}^{k}(N_{D}, N_{H})$ is a fixed-point of $F_{I'}$. Denote it by $(N^{k}_{D}, N^{k}_{D})$ and define $M':=C_{H}(N^{k}_{H})$. By Proposition 5.7, $M'$ is a stable matching of $I'$.

What is left is to show $|M'(h)|=p_{h}(A(h))$ for all $h\in H$. Since $(N_{D}, N_{H})\ge F_{I'}^{k}(N_{D}, N_{H})=(N^{k}_{D}, N^{k}_{D})$, we have $N_{H}\subseteq N^{k}_{H}$. Then $M\subseteq N_{H}\subseteq N^{k}_{H}$, and hence $M(h)\subseteq N^{k}_{H}(h)$ for each $h\in H$. By $M(h)\in \mathcal {F}(p_{h}, q_{h})$ and Claim 5.14, $|M'(h)|=|C_{h}(N^{k}_{H}(h))|=p_{h}(A(h))$. $\square$

Combining Lemmas 5.12 and 5.16 completes the proof of Theorem 4.3.

5.5 Proof of Theorem 4.4

We first show that the “while loop” of the algorithm EF-Paramodular-CSM computes a stable matching of $I'=(D, H, E, \succ _{DH}, \{(\mathbf{0},\overline{p_{h}})\}_{h\in H})$. By the proof of Proposition 5.9, it suffices to show that, each iteration updates $(N_{D}, N_{H})$ to $F_{I'}(N_{D}, N_{H})$. That is, we show that the subsets $R_{D}$ and $R_{H}$ defined as

coincide with $N_{D}\setminus C_{D}(N_{D})$ and $N_{H}\setminus C_{H}(N_{H})$, respectively, where $C_{D}$ and $C_{H}$ are defined for $I'$ as in Sect. 5.3. By definition, $R_{D}=N_{D}\setminus C_{D}(N_{D})$ can be checked easily. To show $R_{H}=N_{H}\setminus C_{H}(N_{H})$, recall the definition of $C_{H}$ in Sect. 5.3.

Here, each $C_{h}:2^{A(h)}\rightarrow 2^{A(h)}$ is a choice function induced from $(A(h), \overline{p_{h}}, \succ _{h})$. By definitions of $C_{h}$ and $\overline{p_{h}}$, for any $N\subseteq E$, we have

By the monotonicity of $p_{h}$ (shown in the proof of Claim 5.11), for any $d\in N(h)$, we have $p_{h}(A(h)\setminus N(h)_{\succeq _{h} d})\le p_{h}(A(h)\setminus N(h)_{\succ _{h} d})$. Then, for any $h\in H$, $N\subseteq E$, and $d\in N(h)$,

$$\begin{aligned} d\in N(h)\setminus C_{h}(N(h)) \iff p_{h}(A(h)\setminus N(h)_{\succeq _{h} d})=p_{h}(A(h)\setminus N(h)_{\succ _{h} d}). \end{aligned}$$

Thus, we have $R_{H}=N_{H}\setminus C_{H}(N_{H})$.

We now analyze the time complexity. As shown in the proof of Proposition 5.9, a stable matching is found by computing $F_{I'}$ at most 2|E| times, i.e., the “while loop” is iterated O(|E|) times. Also, we see that each iteration can be done in O(|E|) time. Checking the condition $|M'(h)|=p_{h}(A(h))~(h\in H)$ is done in O(|E|) time. Thus, the algorithm runs in $O(|E|^2)$ time.

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$