Accommodating various policy goals in matching with constraints

Abstract

Distributional constraints are common features in many real matching markets, such as medical residency matching, school admissions, and teacher assignment. We present a model of matching with constraints that accommodates a wide variety of policy goals and apply that model to the setting of Kamada and Kojima (Am Econ Rev 105(1):67–99, 2015). We also formalize a number of other policy goals to show that they are subsumed by our model. We prove several comparative statics results such as showing that a mechanism we propose is a Pareto improvement for doctors upon the constrained medical matching mechanism currently used in Japan.

1 Introduction

Many real matching markets are subject to distributional constraints. For example, under the “regional cap” policy in Japanese medical residency matching, each region of the country is subject to a regional cap. That is, each region is assigned an upper-bound constraint on the total number of residents placed in the region. This policy was introduced to regulate the geographical distribution of doctors, which was considered to be concentrated too heavily in urban areas at the expense of rural areas. Measures that are mathematically isomorphic to the regional cap policy can be found in a wide range of contexts, such as graduate school admission in China, college admission in several European countries, residency match in the UK, and teacher assignment in Scotland.¹

Motivated by these real-life examples, Kamada and Kojima (2015) study the design of matching markets under distributional constraints. As standard stability may conflict with distributional constraints, they propose a relaxed stability concept. They show that existing mechanisms result in instability and inefficiency and offer a mechanism that finds a stable and efficient matching and is (group) strategy-proof for doctors while respecting the distributional constraints.

A major limitation of that paper, though, is that their stability concept is closely tailored to a particular governmental goal to equalize the numbers of doctors across hospitals beyond target capacities. Although such a goal may be appealing in some contexts as a first-order concern, it may not be appropriate in other applications because hospital capacities in a given region may vary wildly. For example, the maximum and the minimum capacities of hospitals in Tokyo are 69 and 2, respectively (see Fig. 1). For public elementary schools in Boston, the maximum and the minimum capacities of schools are 871 and 165, respectively (see Fig. 2).² In such cases, it may be more appropriate to equalize the ratio between the numbers of doctors (beyond the targets) and the capacities across hospitals.

Fig. 1

The data are taken from Japan Residency Matching Program (2013)

The hospital capacities in Tokyo.

Fig. 2

The data are taken from Boston Public Schools (2013)

The school capacities in public elementary schools in Boston.

There may be other reasonable policy goals as well. For instance, the government may wish to give a priority to some hospitals within a region over others for a variety of reasons.³ Thus, it is clear from these examples that focusing on a particular policy goal limits the practical applicability of the model of Kamada and Kojima (2015).⁴

To accommodate a wide range of policy goals, we offer a model in which each region is endowed with “regional preferences” over distributions of doctors within the region. The idea behind this modeling approach is to express policy goals as regional preferences, and accommodate different types of policy goals by changing regional preferences.⁵ Then, we define a stability concept that takes the regional preferences into account. A result by Kamada and Kojima (2018) implies that, under some regularity conditions, their flexible deferred acceptance mechanism finds a stable (and efficient) matching and it is group strategy-proof for doctors.

This paper offers three sets of results. First, we show that the stability notion of Kamada and Kojima (2015) is a special case of our stability concept. More specifically, their concept is a case of our stability notion in which the regional preferences satisfy a condition called the “Rawlsian” property. Moreover, when the regional preferences are Rawlsian, our flexible deferred acceptance mechanism reduces to the mechanism of Kamada and Kojima (2015). Thus, we establish the main results of Kamada and Kojima (2015) as a special case.

Second, we formalize a wide range of policy goals to demonstrate that they can be described by our regional preferences. Consequently, we establish that the corresponding flexible deferred acceptance mechanisms find a stable matching with respect to those regional preferences.

Third, we prove several policy-relevant comparative statics results. Among other things, we compare a mechanism currently used in Japan with the flexible deferred acceptance mechanism and establish that all doctors are weakly better off under the latter mechanism. Still, we also establish that all doctors are weakly worse off under the flexible deferred acceptance mechanism than under the unconstrained deferred acceptance mechanism. We note that we obtain all of our comparative statics results as straightforward corollaries of a single new comparative statics result.⁶

The rest of this paper proceeds as follows. In Sect. 2, we present the model. Section 3 states preliminary result. In Sect. 4, we offer our analysis. Section 5 concludes. Proofs are in the Appendix unless noted otherwise.

2 Model

This section introduces a model of matching under distributional constraints. We describe the model in terms of matching between doctors and hospitals with “regional caps,” that is, upper bounds on the number of doctors that can be matched to hospitals in each region. However, the model is applicable to various other situations in and out of the residency matching context. Concrete applications include Chinese graduate school admission, UK medical matching, Scottish teacher matching, and college admissions in Ukraine and Hungary.⁷

Our notation and terminology closely follow those of Kamada and Kojima (2015, 2018).

2.1 Preliminary definitions

Let there be a finite set of doctors D and a finite set of hospitals H. Each doctor d has a strict preference relation $\succ _d$ over the set of hospitals and being unmatched (being unmatched is denoted by $\emptyset$). For any $h, h' \in H \cup \{\emptyset \}$, we write $h \succeq _d h'$ if and only if $h \succ _d h'$ or $h = h'$. Each hospital h has a strict preference relation $\succ _h$ over the set of subsets of doctors. For any $D', D'' \subseteq D$, we write $D' \succeq _h D''$ if and only if $D' \succ _h D''$ or $D' = D''$. We denote by $\succ =(\succ _i)_{i\in D\cup H}$ the preference profile of all doctors and hospitals.

Each hospital $h\in H$ is endowed with a (physical) capacity$q_{h}$, which is a nonnegative integer. We say that preference relation $\succ _{h}$ is responsive with capacity$q_{h}$ (Roth 1985) if

• 1. For any $D' \subseteq D$ with $|D'| \le q_h$, $d \in D \setminus D'$ and $d' \in D'$, $(D' \cup d) \setminus d' \succeq _h D'$ if and only if $d \succeq _h d'$,

• 2. For any $D' \subseteq D$ with $|D'| \le q_h$ and $d' \in D'$, $D' \succeq _h D' \setminus d'$ if and only if $d' \succeq _h \emptyset$, and

• 3. $\emptyset \succ _h D'$ for any $D' \subseteq D$ with $|D'| > q_h$.

In words, preference relation $\succ _h$ is responsive with a capacity if the ranking of a doctor (or keeping a position vacant) is independent of her colleagues, and any set of doctors exceeding its capacity is less preferred to the outside option. We assume that preferences of each hospital h are responsive with capacity $q_h$ throughout the paper.

Doctor d is said to be acceptable to hospital h if $d \succ _h \emptyset$.⁸ Similarly, h is acceptable to d if $h \succ _d \emptyset$. It will turn out that only rankings of acceptable partners matter for our analysis, so we often write only acceptable partners to denote preferences. For example,

$${\succ _{d}}: h,h'$$

means that hospital h is the most preferred, $h'$ is the second most preferred, and h and $h'$ are the only acceptable hospitals under preferences $\succ _d$ of doctor d.

There is a finite set R which we call the set of regions. The set of hospitals H is partitioned into hospitals in different regions, that is, $H_r \cap H_{r'}=\emptyset {\text { if }}r \ne r'$ and $H=\cup _{r \in R} H_r$ , where $H_r$ denotes the set of hospitals in region $r \in R$. For each $h \in H$, let r(h) denote the region r such that $h \in H_{r}$. For each region $r \in R$, there is a regional cap$q_r$, which is a nonnegative integer.

A matching$\mu$ is a mapping from $D\cup H$, where we write “$\mu _i$” for “$\mu (i)$” for each $i\in D\cup H$. This mapping satisfies (i) $\mu _d\in H \cup \{\emptyset \}$ for all $d\in D$, (ii) $\mu _h\subseteq D$ for all $h\in H$, and (iii) for any $d \in D$ and $h \in H$, $\mu _d=h$ if and only if $d \in \mu _h$. That is, a matching simply specifies which doctor is assigned to which hospital (if any). A matching is feasible if $|\mu _{r}| \le q_r$ for all $r \in R$, where $\mu _{r}=\cup _{h \in H_r} \mu _h$. In other words, feasibility requires that the regional cap for every region is satisfied. This requirement distinguishes the current environment from the standard model without regional caps: We allow for (though do not require) $q_r < \sum _{h \in H_r}q_h$, that is, the regional cap can be smaller than the sum of hospital capacities in the region.

To accommodate the regional caps, we introduce a concept that generalizes the standard stability notion. For that purpose, we first define two basic concepts. A matching $\mu$ is individually rational if (i) for each $d \in D$, $\mu _d \succeq _d \emptyset$, and (ii) for each $h \in H$, $d \succeq _h \emptyset$ for all $d \in \mu _h$, and $|\mu _h| \le q_h$. That is, no agent is matched with an unacceptable partner and each hospital’s capacity is respected.

Given matching $\mu$, a pair (d, h) of a doctor and a hospital is called a blocking pair if $h \succ _d \mu _d$ and either (i) $|\mu _h|<q_h$ and $d \succ _h \emptyset$, or (ii) $d \succ _h d'$ for some $d' \in \mu _h$. In words, a blocking pair is a pair of a doctor and a hospital who want to be matched with each other (possibly rejecting their partners in the prescribed matching) rather than following the proposed matching.

When there are no binding regional caps (in the sense that $q_r > \sum _{h \in H_r}q_h$ for every $r\in R$), a matching is said to be stable if it is individually rational and there is no blocking pair. Gale and Shapley (1962) show that there exists a stable matching in that setting. In the presence of binding regional caps, however, there may be no such matching that is feasible (in the sense that all regional caps are respected). Thus, in some cases every feasible and individually rational matching may admit a blocking pair.

A mechanism$\varphi$ is a function that maps preference profiles to matchings. The matching under $\varphi$ at preference profile $\succ$ is denoted $\varphi (\succ )$ and agent i’s match is denoted by $\varphi _i(\succ )$ for each $i\in D\cup H$.

A mechanism $\varphi$ is said to be strategy-proof for doctors if there does not exist a preference profile $\succ$, a doctor $d \in D$, and preferences $\succ '_{d}$ of doctor d such that $\varphi _d(\succ _d',\succ _{-d}) \succ _d \varphi _d(\succ )$. A mechanism $\varphi$ is said to be group strategy-proof for doctors if there is no preference profile $\succ$, a subset of doctors $D'\subseteq D$, and a preference profile $(\succ '_{d'})_{d' \in D'}$ of doctors in $D'$ such that

$$\begin{aligned} \varphi _d((\succ '_{d'})_{d' \in D'},(\succ _i)_{i\in D\cup H\setminus D'}) \succ _d \varphi _d(\succ ) {\text { for all }}d \in D'. \end{aligned}$$

That is, no subset of doctors can jointly misreport their preferences to receive a strictly preferred outcome for every member of the coalition under the mechanism.

As this paper analyzes the effect of regional caps in matching markets, it is useful to compare it with the standard matching model without regional caps. Gale and Shapley (1962) consider a matching model without any binding regional cap, which corresponds to a special case of our model in which $q_r > \sum _{h \in H_r}q_h$ for every $r \in R$. In that model, they propose the following (doctor-proposing) deferred acceptance algorithm:

• Step 1: Each doctor applies to her first choice hospital. Each hospital rejects the lowest-ranking doctors in excess of its capacity and all unacceptable doctors among those who applied to it, keeping the rest of the doctors temporarily (so doctors not rejected at this step may be rejected in later steps).

In general,

• Step t: Each doctor who was rejected in Step $(t-1)$ applies to her next highest choice (if any). Each hospital considers these doctors and doctors who are temporarily held from the previous step together and rejects the lowest-ranking doctors in excess of its capacity and all unacceptable doctors, keeping the rest of the doctors temporarily (so doctors not rejected at this step may be rejected in later steps).

The algorithm terminates at a step in which no rejection occurs. The algorithm always terminates in a finite number of steps. Gale and Shapley (1962) show that the resulting matching is stable in the standard matching model without any binding regional cap.

Even though there exists no strategy-proof mechanism that produces a stable matching for all possible inputs, the deferred acceptance mechanism is (group) strategy-proof for doctors (Dubins and Freedman 1981; Roth 1982). This result has been extended by many subsequent studies, suggesting that the incentive compatibility of the mechanism is quite robust and general.⁹

Kamada and Kojima (2015) present examples that show that a simple adaptation of the deferred acceptance mechanism results in inefficiency and instability. Motivated by this problem, the current paper presents a theory of stable matching under distributional constraints in the subsequent sections.

2.2 Model with regional preferences

Let regional preferences$\succeq _r$ be a weak ordering over nonnegative-valued integer vectors $W_r:=\{w=(w_h)_{h \in H_r}| w_h \in {\mathbb {Z}}_+\}$. That is, $\succeq _r$ is a binary relation that is complete and transitive (but not necessarily antisymmetric). We write $w \succ _r w'$ if and only if $w \succeq _r w'$ holds but $w' \succeq _r w$ does not. Vectors such as w and $w'$ are interpreted to be supplies of acceptable doctors to the hospitals in region r, but they only specify how many acceptable doctors apply to each hospital and no information is given as to who these doctors are. Given $\succeq _r$, a function $\tilde{\text {Ch}}_r: W_r \rightarrow W_r$ is an associated quasi choice rule if $\tilde{\text {Ch}}_r(w) \in \mathop {\hbox {arg max}}\nolimits _{\succeq _r} \{w'| w' \le w\}$ for any non-negative integer vector $w=(w_h)_{h \in H_r}$.¹⁰ We require that the quasi choice rule $\tilde{\text {Ch}}_r$ be consistent, that is, $\tilde{\text {Ch}}_r(w) \le w' \le w \Rightarrow \tilde{\text {Ch}}_r(w')=\tilde{\text {Ch}}_r(w)$.¹¹ This condition requires that, if $\tilde{\text {Ch}}_r(w)$ is chosen at w and the supply decreases to $w' \le w$ but $\tilde{\text {Ch}}_r(w)$ is still available under $w'$, then the same choice $\tilde{\text {Ch}}_r(w)$ should be made under $w'$ as well. Note that there may be more than one quasi choice rule associated with a given weak ordering $\succeq _r$ because the set $\mathop {\hbox {arg max}}\nolimits _{\succeq _r} \{w'| w' \le w\}$ may not be a singleton for some $\succeq _r$ and w. Note also that there always exists a consistent quasi choice rule.¹² We assume that the regional preferences $\succeq _r$ satisfy the following mild regularity conditions:

• 1. $w' \succ _r w$ if $w_h > q_h \ge w'_h$ for some $h \in H_r$ and $w'_{h'}=w_{h'}$ for all $h' \ne h$.

  This property says that the region desires no hospital to be forced to be assigned more doctors than its real capacity. This condition implies that, for any w, the component $[\tilde{\text {Ch}}_r(w)]_h$ of $\tilde{\text {Ch}}_r(w)$ for h satisfies $[\tilde{\text {Ch}}_r(w)]_h \le q_h$ for each $h \in H_r$, that is, the capacity constraint for each hospital is respected by the (quasi) choice of the region.

• 2. $w' \succ _r w$ if $\sum _{h \in H_r} w_h > q_r \ge \sum _{h \in H_r} w'_h$.

  This property simply says that region r prefers the total number of doctors in the region to be at most its regional cap. This condition implies that $\sum _{h \in H_r}(\tilde{\text {Ch}}_r(w))_h \le q_r$ for any w, that is, the regional cap is respected by the (quasi) choice of the region.

• 3. If $w' \lneq w \le q_{H_r}:=(q_h)_{h \in H_r}$ and $\sum _{h \in H_r} w_h \le q_r$, then $w \succ _r w'$.

  This condition formalizes the idea that region r prefers to fill as many positions of hospitals in the region as possible so long as doing so does not lead to a violation of the hospitals’ real capacities or the regional cap. This requirement implies that any associated quasi choice rule is acceptant, that is, for each w, if there exists h such that $[\tilde{\text {Ch}}_r(w)]_h < \min \{q_h,w_h\}$, then $\sum _{h' \in H_r}[\tilde{\text {Ch}}_r(w)]_{h'}=q_r$.¹³ This captures the idea that the social planner should not waste caps allocated to the region: If some doctor is rejected by a hospital even though she is acceptable to the hospital and the hospital’s capacity is not binding, then the regional cap should be binding.

Definition 1

The regional preferences $\succeq _r$ are substitutable if there exists an associated quasi choice rule $\tilde{\text {Ch}}_r$ that satisfies $w \le w' \Rightarrow \tilde{\text {Ch}}_r(w) \ge \tilde{\text {Ch}}_r(w') \wedge w$.¹⁴

Notice that the condition in this definition is equivalent to

$$\begin{aligned} w \le w' \Rightarrow [\tilde{\text {Ch}}_r(w)]_h \ge \min \{[\tilde{\text {Ch}}_r(w')]_h, w_h\} \text { for every }h \in H_r. \end{aligned}$$

(1)

This condition says that, when the supply of doctors is increased, the number of accepted doctors at a hospital can increase only when the hospital has accepted all acceptable doctors under the original supply profile.¹⁵ Formally, condition (1) is equivalent to

$$\begin{aligned} w \le w'{ \text { and }} [\tilde{\text {Ch}}_r(w)]_h < [\tilde{\text {Ch}}_r(w')]_h \Rightarrow [\tilde{\text {Ch}}_r(w)]_h =w_h. \end{aligned}$$

(2)

To see that condition (1) implies condition (2), suppose that $w \le w'$ and $[\tilde{\text {Ch}}_r(w)]_h < [\tilde{\text {Ch}}_r(w')]_h$. These assumptions and condition (1) imply $[\tilde{\text {Ch}}_r(w)]_{h} \ge w_{h}.$ Since $[\tilde{\text {Ch}}_r(w)]_h \le w_h$ holds by the definition of $\tilde{\text {Ch}}_r$, this implies $[\tilde{\text {Ch}}_r(w)]_h =w_h$. To see that condition (2) implies condition (1), suppose that $w \le w'$. If $[\tilde{\text {Ch}}_r(w)]_h \ge [\tilde{\text {Ch}}_r(w')]_h$, the conclusion of (1) is trivially satisfied. If $[\tilde{\text {Ch}}_r(w)]_h < [\tilde{\text {Ch}}_r(w')]_h$, then condition (2) implies $[\tilde{\text {Ch}}_r(w)]_h =w_h$, thus the conclusion of (1) is satisfied.

Given a profile of regional preferences $(\succeq _r)_{r \in R}$, stability is defined as follows.

Definition 2

A matching $\mu$ is stable if it is feasible, individually rational, and if (d, h) is a blocking pair then (i) $|\mu _{r(h)}|=q_{r(h)}$, (ii) $d' \succ _h d$ for all doctors $d' \in \mu _h$, and

(iii) either $\mu _d \notin H_{r(h)}$ or $w \succeq _{r(h)} w'$,

where $w_{h'}=|\mu _{h'}|$ for all $h' \in H_{r(h)}$ and $w'_h=w_h+1$, $w'_{\mu _d}=w_{\mu _d}-1$ and $w'_{h'}=w_{h'}$ for all other $h' \in H_{r(h)}.$

As stated in the definition, only certain blocking pairs are tolerated under stability. Any blocking pair that may remain is in danger of violating the regional cap since condition (i) implies that the cap for the blocking hospital’s region is currently full, and condition (ii) implies that the only blocking involves filling a vacant position.

There are two possible cases under (iii). The first case implies that the blocking doctor is not currently assigned in the hospital’s region, so the blocking pair violates the regional cap. The second part of condition (iii) considers blocking pairs within a region (note that $\mu _d\in H_{r(h)}$ holds in the remaining case). It states that if the blocking pair does not improve the doctor distribution in the region with respect to its regional preferences, then it is not regarded as a legitimate block.¹⁶

The way that regional preferences are determined could depend on the policy goal of the region or the social planner. One possibility for regional preferences, studied in detail by Kamada and Kojima (2015), is to prefer distributions of doctors that have “fewer gaps” from the target capacities; see Sect. 4.1 for detail. Other regional preferences are analyzed in Sect. 4.2.

Clearly, our stability concept reduces to the standard stability concept of Gale and Shapley (1962) if there are no binding regional caps. Kamada and Kojima (2017) show that a stable matching is constrained efficient, i.e., there is no feasible matching $\mu '$ such that $\mu _i' \succeq _i \mu _i$ for all $i \in D \cup H$ and $\mu _i'\succ _i\mu _i$ for some $i\in D\cup H$.

3 Preliminaries

This section has two goals. The first goal is to demonstrate that a stable matching exists under our general definition of stability under distributional constraints. The second goal is to show that a stable matching can be found by a mechanism that is strategy-proof for doctors. To achieve these goals, we begin by introducing the following (generalized) flexible deferred acceptance algorithm:

The (Generalized) Flexible Deferred Acceptance Algorithm For each region r, fix an associated quasi choice rule $\tilde{\text {Ch}}_r$ which satisfies condition (1). Note that the assumption that $\succeq _r$ is substitutable assures the existence of such a quasi choice rule.

• 1. Begin with an empty matching, that is, a matching $\mu$ such that $\mu _d=\emptyset$ for all $d \in D$.

• 2. Choose a doctor d arbitrarily who is currently not tentatively matched to any hospital and who has not applied to all acceptable hospitals yet. If such a doctor does not exist, then terminate the algorithm.

• 3. Let d apply to the most preferred hospital ${\bar{h}}$ at $\succ _d$ among the hospitals that have not rejected d so far. If d is unacceptable to ${\bar{h}}$, then reject this doctor and go back to Step 2. Otherwise, let r be the region such that ${\bar{h}} \in H_r$ and define vector $w=(w_h)_{h \in H_r}$ by (a) $w_{{\bar{h}}}$ is the number of doctors currently held at ${\bar{h}}$ plus one, and (b) $w_h$ is the number of doctors currently held at h if $h \ne {\bar{h}}$.

• 4. Each hospital $h \in H_r$ considers the new applicant d (if $h = {\bar{h}}$) and doctors who are temporarily held from the previous step together. It holds its $(\tilde{\text {Ch}}_r(w))_h$ most preferred applicants among them temporarily and rejects the rest (so doctors held at this step may be rejected in later steps). Go back to Step 2.

We define the (generalized) flexible deferred acceptance mechanism to be a mechanism that produces, for each input, the matching given at the termination of the above algorithm.

This algorithm is a generalization of the deferred acceptance algorithm of Gale and Shapley (1962) to the model with regional caps. The main differences are found in Steps 3 and 4. Unlike the deferred acceptance algorithm, this algorithm limits the number of doctors (tentatively) matched in each region r at $q_r$. This results in rationing of doctors across hospitals in the region, and the rationing rule is governed by regional preferences $\succeq _r$. Clearly, this mechanism coincides with the standard deferred acceptance algorithm if all the regional caps are large enough and hence non-binding.

We take the following result as the starting point of our analysis.

Proposition 0

(A Corollary of Theorem 1 of Kamada and Kojima (2018)) Suppose that$\succeq _r$is substitutable for every$r \in R$. Then, the flexible deferred acceptance algorithm stops in finite steps. The mechanism produces a stable matching for any input and is group strategy-proof for doctors.

This proposition offers a sense in which it is possible to design a desirable mechanism even under distributional constraints and various policy goals. As will be seen in subsequent sections, the class of substitutable regional preferences subsumes the “Rawlsian” regional preferences motivated by a residency matching application (see Sect. 4.1) as well as others (see Sect. 4.2). For each of these cases, the flexible deferred acceptance mechanism finds a stable matching that addresses a given policy goal, while inducing truthful reporting by doctors. Moreover, because stability implies efficiency (Kamada and Kojima 2017), the algorithm produces an efficient matching.

A formal proof for a more general case can be found in Kamada and Kojima (2018), while a proof that is adapted to our present setting is in Appendix 1.¹⁷ We illustrate a sketch of the proof here.

Our proof strategy is to connect our matching model with constraints to the “matching with contracts” model (Hatfield and Milgrom 2005).¹⁸ More specifically, given the original matching model under constraints, we define an “associated model,” a hypothetical matching model between doctors and regions instead of doctors and hospitals; In the associated model, we regard each region as a hypothetical consortium of hospitals that acts as one agent. By imagining that a region (hospital consortium) makes a coordinated employment decision, we can account for the fact that acceptance of a doctor by a hospital may depend on doctor applications to other hospitals in the same region, an inevitable feature in markets under distributional constraints. This association necessitates, however, that we distinguish a doctor’s placements in different hospitals in the given region. We account for this complication by defining a region’s choice function over contracts rather than doctors, where a contract specifies a doctor–hospital pair to be matched. We construct such a choice function using two pieces of information: the preferences of all the hospitals in the given region, and regional preferences. The idea is that each hospital’s preferences are used for choosing doctors given the number of allocated slots, while regional preferences are used to regulate slots allocated to different hospitals in the region. In other words, regional preferences trade off multiple hospitals’ desires to accept more doctors, when accepting more is in conflict with the regional cap. With the help of this association, we demonstrate that any stable allocation in the associate model with contracts induces a stable matching in the original model with distributional constraints (Proposition 9).

Once this association is established, with some work we show that the key conditions in the associated model—the substitutes condition and the law of aggregate demand—are satisfied (Proposition 8). This enables us to invoke existing results for matching with contracts, namely that an existing algorithm called the “cumulative offer process” finds a stable allocation, and it is (group) strategy-proof for doctors in the associated model (Hatfield and Milgrom 2005; Hatfield and Kojima 2009; Hatfield and Kominers 2012). Then, we observe that the outcome of the cumulative offer process corresponds to the matching produced by the flexible deferred acceptance algorithm in the original model with constraints (Remark 1). This correspondence establishes that the flexible deferred acceptance mechanism finds a stable matching in the original problem and this algorithm is group strategy-proof for doctors, proving Proposition 0.

The full proof, presented in Appendix 1, formalizes this idea. The proof is somewhat involved because one needs to exercise some care when establishing correspondences between the two models and confirming that a property in one model induces the corresponding property in the other.

4 Results

4.1 Stability in Kamada and Kojima (2015)

In this section, we establish the main result of Kamada and Kojima (2015) by showing that their stability concept can be rewritten using a substitutable regional preferences.

In Kamada and Kojima (2015), there is an exogenously given (government-imposed) nonnegative integer ${\bar{q}}_h \le q_h$ called target capacity, for each hospital h such that $\sum _{h \in H_r} {\bar{q}}_h \le q_r$ for each region $r \in R$. Given a profile of target capacities, they define a stability concept. We refer to this concept as T-stability (where “T” signifies target capacities) to avoid confusion with stability defined earlier.

Definition 3

A matching $\mu$ is T-stable if it is feasible, individually rational, and if (d, h) is a blocking pair then (i) $|\mu _{r(h)}|=q_{r(h)}$, (ii) $d' \succ _h d$ for all doctors $d' \in \mu _h$, and

(iii) either $\mu _d \notin H_{r(h)}$ or $|\mu _h'| - {\bar{q}}_h > |\mu _{\mu _d}'| - {\bar{q}}_{\mu _d}$,

where $\mu '$ is the matching such that $\mu _d'=h$ and $\mu _{d'}'=\mu _{d'}$ for all $d' \ne d$.

Kamada and Kojima (2015) define the flexible deferred acceptance algorithm in their setting as follows. For each $r \in R$, specify an order of hospitals in region r: Denote $H_r=\{h_1,h_2,\dots , h_{|H_r|}\}$ and order $h_i$ earlier than $h_j$ if $i<j$. Given this order, consider the following algorithm.

• 1. Begin with an empty matching, that is, a matching $\mu$ such that $\mu _d=\emptyset$ for all $d \in D$.

• 2. Choose a doctor d who is currently not tentatively matched to any hospital and who has not applied to all acceptable hospitals yet. If such a doctor does not exist, then terminate the algorithm.

• 3. Let d apply to the most preferred hospital ${\bar{h}}$ at $\succ _d$ among the hospitals that have not rejected d so far. Let r be the region such that ${\bar{h}} \in H_r$.

• 4. (a) For each $h \in H_r$, let $D'_h$ be the entire set of doctors who have applied to but have not been rejected by h so far and are acceptable to h. For each hospital $h \in H_r$, choose the ${\bar{q}}_h$ best doctors according to $\succ _h$ from $D_h'$ if they exist, and otherwise choose all doctors in $D_h'$. Formally, for each $h \in H_r$ choose $D_h''$ such that $D''_h \subset D'_h$, $|D''_h| =\min \{{\bar{q}}_h, |D'_h|\}$, and $d \succ _h d'$ for any $d \in D_h''$ and $d' \in D'_h \setminus D_h''$. (b) Start with a tentative match $D_h''$ for each hospital $h \in H_r$. Hospitals take turns to choose (one doctor at a time) the best remaining doctor in their current applicant pool. Repeat the procedure (starting with $h_1$, proceeding to $h_2, h_3,\dots$ and going back to $h_1$ after the last hospital) until the regional quota $q_r$ is filled or the capacity of the hospital is filled or no doctor remains to be matched. All other applicants are rejected.¹⁹

Kamada and Kojima (2015) define the flexible deferred acceptance mechanism to be a mechanism that produces, for each input, the matching at the termination of the above algorithm.²⁰ The following proposition is stated as the main result of Kamada and Kojima (2015).

Proposition 1

(Theorem 2 of Kamada and Kojima (2015)) In the setting of Kamada and Kojima (2015), the flexible deferred acceptance algorithm stops in finite steps. The mechanism produces a T-stable matching for any input and is group strategy-proof for doctors.

In the remainder of this section, we establish this result as a corollary of the main result of the present paper, Proposition 0.

To start the analysis, fix a region r. Given the target capacity profile $({\bar{q}}_{h})_{h \in H_r}$ and the vector $w \in W_r$, define the ordered excess weight vector$\eta (w)=(\eta _1(w),\ldots ,\eta _{|H_r|}(w))$ by setting $\eta _i(w)$ to be the i’th lowest value (allowing repetition) of $\{w_h - {\bar{q}}_h| h \in H_r\}$ (we suppress dependence of $\eta$ on target capacities). For example, if $w=(w_{h_1}, w_{h_2},w_{h_3},w_{h_4})=(2,4,7,2)$ and $({\bar{q}}_{h_1}, {\bar{q}}_{h_2},{\bar{q}}_{h_3},{\bar{q}}_{h_4})=(3,2,3,0)$, then $\eta _1(w)=-1,\eta _2(w)=\eta _3(w)=2, \eta _4(w)=4$.

Consider the regional preferences $\succeq _r$ that compare the excess weights lexicographically. More specifically, let $\succeq _r$ be such that $w \succ _r w'$ if and only if there exists an index $i \in \{1,2,\dots ,|H_r|\}$ such that $\eta _j(w)=\eta _j(w')$ for all $j<i$ and $\eta _i(w)>\eta _i(w')$. The associated weak regional preferences $\succeq _r$ are defined by $w \succeq _r w'$ if and only if $w \succ _r w'$ or $\eta (w)=\eta (w')$. We call such regional preferences Rawlsian.

Proposition 2

T-stability is a special case of stability such that the regional preferences of each region are Rawlsian.

Proof

See Appendix 2.1. $\square$

Consider the (generalized) flexible deferred acceptance algorithm in a previous subsection. With the following quasi choice rule, this algorithm is equivalent to the flexible deferred acceptance algorithm in Kamada and Kojima (2015): For each $w' \in W_r$,

$$\begin{aligned} \tilde{\text {Ch}_r}(w')=\underset{\sum _{h\in H_r}w_h \le q_r}{\max _{w=w^k\text { for some }k}}w, \end{aligned}$$

(3)

where $w^0=(\min \{ w_h',\bar{q}_h\})_{h\in H_r}$ and $w^k \in W_r$$(k=1,2,\dots )$ is defined by

$$\begin{aligned} w_{h_j}^{k}=\min \{w'_{h_j}, q_{h_j}, w_{h_j}^{k-1}+{\mathbb {I}}_{j \equiv k\;\text {(mod}\; |H_r|)}\} \quad \text { for each } j=1,2,\dots ,|H_r|, \end{aligned}$$

with “${\mathbb {I}}$” being an indicator function. Note that there is a unique maximum in (3) because $w^{k'}\le w^{k'+1}$ for every $k'=1,2,\dots$ by the definition of $w^k$.²¹

Proposition 3

Rawlsian preferences are substitutable with the associated quasi choice rule (3).

Proof

See Appendix 2.1. $\square$

Propositions 0, 2, and 3 imply Theorem 2 of Kamada and Kojima (2015).

In Appendix 4, we discuss how to allocate target capacities among hospitals in a region, within the Rawlsian framework. There we observe that the allocation problem is similar to the celebrated “bankruptcy problem,” and consider several rules studied in that literature.

4.2 Alternative criteria

Although Kamada and Kojima (2015) focus on a particular stability concept (T-stability) and corresponding regional preferences, called Rawlsian preferences, it is quite plausible that some societies may prefer to impose different criteria from the Rawlsian preferences. This section proposes other criteria that seem to be appealing. They are examples of regional preferences that satisfy substitutability defined in Definition 1. Therefore, the corresponding flexible deferred acceptance mechanisms find a stable matching with respect to those regional preferences.

In the following, we assume that $0 \succ _r w$ for any weight vector w such that $\sum _{h \in H_r}w_h>q_r$ or $w_h > q_h$ for some $h \in H_r$. Thus in (1)–(4) below, we assume that any weight vector w satisfies $\sum _{h \in H_r}w_h \le q_r$ and $w_h \le q_h$ for all $h \in H_r$.

• 1. Equal gains Let the region prefer a distribution that equalizes the weights across hospitals in the region as much as possible. Formally, such a preference, which we call the equal gains preferences, can be expressed as the Rawlsian preferences for the special case in which the target capacity for every hospital is set at zero. Since Proposition 3 shows that the Rawlsian preferences are substitutable for any target capacity profile, the equal gains preferences satisfy substitutability.

• 2. Equal Losses Let the region prefer to equalize the “losses,” that is, the differences between the (physical) capacities and the weights across hospitals in the region. More generally, one could consider the preferences for equal losses above target capacities, that is, the regional preferences first prefer to fill as many positions as possible to meet target capacities and then (lexicographically less importantly) prefer to equalize the losses. To formally define such preferences $\succ _r$, recall that $\eta (w)$ denotes the ordered excess weight vector as defined in Sect. 4.1, and define ${\hat{\eta }}(w)$ as a $|H_r|$-dimensional vector whose i’th component ${\hat{\eta }}_i(w)$ is the i’th highest value (allowing repetition) of $\{q_h-w_h|h \in H_r\}$. We let $w \succ _r w'$ if and only if (a) there exists an index $i \in \{1,2,\dots ,|H_r|\}$ such that $\min \{\eta _j(w),0\}=\min \{\eta _j(w'),0\}$ for all $j<i$ and $\min \{\eta _i(w),0\}>\min \{\eta _i(w'),0\}$, or (b) $\min \{\eta _i(w),0\}=\min \{\eta _i(w'),0\}$ for every index $i \in \{1,2,\dots ,|H_r|\}$, and there exists an index $i \in \{1,2,\dots ,|H_r|\}$ such that ${\hat{\eta }}_j(w),={\hat{\eta }}_j(w')$ for all $j<i$ and ${\hat{\eta }}_i(w)<{\hat{\eta }}_i(w')$.

• 3. Proportional The proportional regional preferences prefer to allocate positions to hospitals in a proportional manner subject to integer constraints. More precisely, define ${\tilde{\eta }}(w)$ as a $|H_r|$-dimensional vector whose i’th component ${\tilde{\eta }}_i(w)$ is the i’th lowest value (allowing repetition) of $\{w_h/q_h|h \in H_r\}$. We let $w \succ _r w'$ if there exists an index $i \in \{1,2,\dots ,|H_r|\}$ such that ${\tilde{\eta }}_j(w),={\tilde{\eta }}_j(w')$ for all $j<i$ and ${\tilde{\eta }}_i(w)>{\tilde{\eta }}_i(w')$. As above, one could consider preferences for proportional losses as well. Also, these preferences can be generalized so that these concerns enter only above target capacities (this generalization is somewhat tedious but straightforward, and can be done as in Item 2). Finally, when constructing $\tilde{\eta }_i$, we can use a denominator different from $q_h$.²²

• 4. Hospital-lexicographic Let there be a pre-specified order over hospitals, and the region lexicographically prefers filling a slot in a higher-ranked hospital to filling that of a lower-ranked hospital. For instance, the region may desire to fill positions of hospitals that are underserved within the region (say, a prefecture may desire to fill positions of a hospital in a remote island within the prefecture before other hospitals). Formally, hospital-lexicographic regional preferences $\succ _r$ are defined as follows. Fix an order over hospitals in r, denoted by $h_1,h_2,\dots ,$ and $h_{|H_r|}$. Let $w \succ _r w'$ if and only if there exists an index $i \in \{1,2,\dots ,|H_r|\}$ such that $w_{h_j}=w_{h_j}'$ for all $j<i$ and $w_{h_i}>w_{h_i}'$. We note that one can also consider hospital-lexicographic preferences above targets using the criterion for hospital-lexicographic preferences for weights above targets.

All the above regional preferences have associated quasi choice rules that satisfy the property that we call “order-respecting.” To define this property, let there be a finite sequence of hospitals in region r such that each hospital h appears, potentially repeatedly, $q_h$ times in the sequence, and the total size of the sequence is $\sum _{h\in H_r}q_h$. Consider a quasi choice rule that increases the weights of hospitals one by one following the specified order.²³ Formally, fix a vector $(h_1,h_2,\dots ,h_{\sum _{h\in H_r}q_h}) \in (H_r)^{\sum _{h\in H_r}q_h}$ such that $\#\{i \in \{1,2,\dots , \sum _{h\in H_r}q_h\}| h_i=h\} = q_h$ for each $h \in H_r$, and define $\tilde{\text {Ch}}_r(w)$ through the following algorithm:

• 1. Let $w^0$ be the $|H_r|$-dimensional zero vector, indexed by hospitals in $H_r$.

• 2. For any $t \ge 0$, if $\sum _{h \in H_r} w^t_h =q_r$ or $w^t_h=\min \{q_h,w_h\}$ for all $h \in H_r$, then stop the algorithm and define $\tilde{\text {Ch}}_r(w)=w^t$ . If not, define $w^{t+1}$ by: (a) If $w^t_{h_{t+1}}<\min \{q_{h_{t+1}},w_{h_{t+1}}\}$, then let $w^{t+1}_{h_{t+1}}=w^t_{h_{t+1}}+1$; otherwise, let $w^{t+1}_{h_{t+1}}=w^t_{h_{t+1}}$. (b) For every $h \ne h_{t+1}$, let $w^{t+1}_{h}=w^t_{h}$.

It is easy to see that any order-respecting quasi choice rule satisfies the condition in the definition of substitutability. Also it is easy to see that, for each of the above regional preferences (1)–(4), there exists an associated quasi choice rule that is order-respecting. By these observations, all the above regional preferences are substitutable.

4.3 Comparative statics

As illustrated in Sect. 3, our analytical approach is to construct an associated matching model with contracts and to utilize results from that model to obtain corresponding results in the original market. This connection enables us to exploit structural properties of stable allocations in the matching model with contracts. In particular, we obtain many comparative statics results as corollaries of a new general result in the matching with contract model (Lemma 1 in Appendix 2.2).

We begin by stating various comparative statics results presented in Kamada and Kojima (2015). They formalize the current practice in Japan, the Japan Residency Matching Program (JRMP) mechanism. The JRMP mechanism is a rule that produces the matching resulting from the deferred acceptance algorithm except that, for each hospital h, it uses ${\bar{q}}_h \le q_h$ instead of $q_h$ as the hospital’s capacity. In words, the JRMP mechanism pretends that the target capacities are actual physical capacities.

The first result establishes comparisons across the flexible deferred acceptance, JRMP, and the (unconstrained) deferred acceptance algorithms:

Proposition 4

(Theorem 3 of Kamada and Kojima (2015)) Consider the model of Kamada and Kojima (2015). For any preference profile,

• 1. Each doctor$d\in D$weakly prefers a matching produced by the deferred acceptance mechanism to the one produced by the flexible deferred acceptance mechanism to the one produced by the JRMP mechanism.

• 2. If a doctor is unmatched in the deferred acceptance mechanism, she is unmatched in the flexible deferred acceptance mechanism. If a doctor is unmatched in the flexible deferred acceptance mechanism, she is unmatched in the JRMP mechanism.

The next result pertains to the effect of changes in regional caps.

Proposition 5

(Proposition 3 of Kamada and Kojima (2015)) Consider the model of Kamada and Kojima (2015). Fix a picking order in the flexible deferred acceptance mechanism. Let$(q_r)_{r \in R}$and$(q'_r)_{r \in R}$be regional caps such that$q'_r \le q_r$for each$r \in R$. Then, the following statements hold.

• 1. Each doctor$d\in D$weakly prefers a matching produced by the flexible deferred acceptance mechanism under regional caps$(q_r)_{r \in R}$to the one under$(q'_r)_{r \in R}$.

• 2. For each regionrsuch that$q_r=q'_r$, the number of doctors matched in r at a matching produced by the flexible deferred acceptance mechanism under regional caps$(q'_r)_{r \in R}$is weakly larger than at the matching under$(q_r)_{r \in R}$.

Another comparative statics result is about the changes in the imposed constraints under the JRMP mechanism.

Proposition 6

(Proposition 4 of Kamada and Kojima (2015)) Consider the model of Kamada and Kojima (2015). Let$({\bar{q}}_h)_{h \in H}$and$({\bar{q}}'_h)_{h \in H}$be target capacities such that${\bar{q}}'_h \le {\bar{q}}_h$for each$h \in H$. Then, the following statements hold.²⁴

• 1. Each doctor$d\in D$weakly prefers a matching produced by the JRMP mechanism under target capacities$({\bar{q}}_h)_{h \in H}$to the one under$({\bar{q}}'_h)_{h \in H}$.

• 2. Each hospital$h\in H$such that${\bar{q}}_h = {\bar{q}}_h'$weakly prefers a matching produced by the JRMP mechanism under target capacities$({\bar{q}}'_h)_{h \in H}$to the one under$({\bar{q}}_h)_{h \in H}$. Moreover, the number of doctors matched to any suchhin the former matching is weakly larger than that in the latter.

The following result, also from Kamada and Kojima (2015), shows that, whenever a hospital or a region is underserved under the flexible deferred acceptance mechanism, the (unconstrained) deferred acceptance mechanism cannot improve the match at such a hospital or a region.

Proposition 7

(Proposition 2 of Kamada and Kojima (2015)) Consider the model of Kamada and Kojima (2015).

• 1. If the number of doctors matched with$h\in H$in the flexible deferred acceptance mechanism is strictly less than its target capacity, then the set of doctors matched withhunder the (unconstrained) deferred acceptance mechanism is a subset of the one under the flexible deferred acceptance mechanism.

• 2. If the number of doctors matched in$r \in R$in the flexible deferred acceptance mechanism is strictly less than its regional cap, then each hospitalhinrweakly prefers a matching produced by the flexible deferred acceptance mechanism to the one under the (unconstrained) deferred acceptance mechanism. Moreover, the number of doctors matched to any suchhin the former matching is weakly larger than that in the latter.

We obtain all these results as corollaries of a single general comparative statics result in the matching with contracts model. More specifically, we establish that if the choice function of a region becomes larger in the set inclusion sense, then all doctors are made weakly better off and all other regions are made weakly worse off in the doctor-optimal stable allocation (Lemma 1 in Appendix 2.2). Also, Hatfield and Milgrom (2005) show that the outcome of a cumulative offer process is a doctor-optimal allocation. Given these results, we can prove all the above results by demonstrating that all the comparisons above can be interpreted as comparisons of outcomes of cumulative offer processes under different choice functions of regions. The formal statement of the Lemma and proofs of all the results in this section can be found in Appendix 2.2.

5 Conclusion

This paper presented a model of matching under distributional constraints. Building upon an approach of Kamada and Kojima (2015), we defined a stability concept that takes distributional constraints into account. We presented a general model to allow for a variety of policymaker preferences over doctor distributions. We showed that the generalization subsumes the model of Kamada and Kojima (2015) as a special case, while admitting a number of other practically relevant cases. Using our general model, we proved policy-relevant comparative statics results.

We note that our analysis builds upon a new connection between matching with constraints and matching with contracts. After the first draft of this paper was written, a similar approach was adopted by other studies such as Goto et al. (2014), Goto et al. (2016), and Kojima et al. (2018).²⁵

In addition to its intrinsic theoretical interest, our major motivation for a general theory was the desire to accommodate various constraints and policy preferences in practice, thus enabling applications to diverse types of real problems. As already mentioned, geographic and other distributional constraints are prevalent in practice; Concrete examples include British and Japanese medical matches, Chinese graduate admission, European college admissions, and Scottish teacher allocation, just to name a few. Although all these markets are subject to distributional constraints, because of differences in details, the same mechanism may be suitable in one market while unfit in another. This is a major reason that a general theory is needed. Moreover, we are quite confident that there are many other markets with specific constraints which have yet to be recognized or addressed in the literature. We hope that this paper provides a useful building block for market design in those undiscovered markets and stimulates further research in matching under constraints and, more generally, practical market design.

Appendices

Appendix 1: Proof of Proposition 0

As stated earlier, Proposition 0 is a special case of Theorem 1 of Kamada and Kojima (2018). We provide the proof of Proposition 0 for the reader’s convenience, while the language in the proof closely follows that of Kamada and Kojima (2018).

Let there be two types of agents, doctors in D and regions in R. Note that we regard a region, instead of a hospital, as an agent in this model. There is a set of contracts $X=D \times H$.

We assume that, for each doctor d, any set of contracts with cardinality two or more is unacceptable, that is, a doctor wants to sign at most one contract. For each doctor d, her preferences $\succ _d$ over $(\{d\} \times H) \cup \{\emptyset \}$ are given as follows.²⁶ We assume $(d,h) \succ _d (d,h')$ in this model if and only if $h \succ _d h'$ in the original model, and $(d,h) \succ _d \emptyset$ in this model if and only if $h \succ _d \emptyset$ in the original model.

For each region $r \in R$, we assume that the region has preferences $\succeq _r$ and its associated choice rule $\text {Ch}_r(\cdot )$ over all subsets of $D \times H_r$. For any $X' \subset D \times H_r$, let $w(X'):=(w_h(X'))_{h \in H_r}$ be the vector such that $w_h(X')=|\{(d,h) \in X'| d \succ _h \emptyset \}|$. For each $X'$, the chosen set of contracts $\text {Ch}_r(X')$ is defined by

$$\begin{aligned} \text {Ch}_r(X')=\bigcup _{h \in H_r} \left\{ (d,h) \in X' \,\; \Big| \;\, \left| \{d' \in D| (d',h) \in X', d' \succeq _h d\}\right| \le (\tilde{\text {Ch}}_r(w(X')))_h \right\} . \end{aligned}$$

(4)

That is, each hospital $h \in H_r$ chooses its $(\tilde{\text {Ch}}_r(w(X')))_h$ most preferred contracts available in $X'$.

We extend the domain of the choice rule to the collection of all subsets of X by setting $\text {Ch}_r(X')=\text {Ch}_r(\{(d,h) \in X'| h \in H_r\})$ for any $X' \subseteq X$.

Definition 4

(Hatfield and Milgrom (2005)) Choice rule $\text {Ch}_r(\cdot )$ satisfies the substitutes condition if there does not exist contracts $x,x'\in X$ and a set of contracts $X'\subseteq X$ such that $x' \notin \text {Ch}_{r}(X'\cup \{x'\})$ and $x'\in \text {Ch}_{r}(X'\cup \{x,x'\})$.

In other words, contracts are substitutes if adding a contract to the choice set never induces a region to choose a contract it previously rejected. Hatfield and Milgrom (2005) show that there exists a stable allocation (defined in Definition 6) when contracts are substitutes for every region.

Definition 5

(Hatfield and Milgrom (2005)) Choice rule $\text {Ch}_r(\cdot )$ satisfies the law of aggregate demand if for all $X^{\prime }\subseteq X^{\prime \prime }\subseteq X$, $|\text {Ch}_r (X^{\prime })|\le |\text {Ch}_r(X^{\prime \prime })|$.²⁷

Proposition 8

Suppose that $\succeq _r$ is substitutable. Then, choice rule $\text {Ch}_r(\cdot )$ defined above satisfies the substitutes condition and the law of aggregate demand. ²⁸

Proof

Fix a region $r\in R$. Let $X' \subseteq X$ be a subset of contracts and $x=(d,h) \in X \setminus X'$ where $h \in H_r$. Let $w=w(X')$ and $w'=w(X' \cup x)$. To show that $\text {Ch}_r$ satisfies the substitutes condition, we consider a number of cases as follows.

• 1. Suppose that $\emptyset \succ _h d$. Then, $w'=w$ and, for each $h'\in H_r$, the set of acceptable doctors available at $X' \cup x$ is identical to the one at $X'$. Therefore, by inspection of the definition of $\text {Ch}_r$, we have $\text {Ch}_r(X' \cup x)=\text {Ch}_r(X')$, satisfying the conclusion of the substitutes condition in this case.

• 2. Suppose that $d \succ _h \emptyset$. (a) Consider a hospital $h' \in H_r \setminus h$. Note that we have $w'_{h'}=w_{h'}$. This and the inequality $[\tilde{\text {Ch}}_r(w')]_{h'} \le w'_{h'}$ (which always holds by the definition of $\tilde{\text {Ch}}_r$) imply that $[\tilde{\text {Ch}}_r(w')]_{h'} \le w_{h'}.$ Thus, we obtain $\min \{ [\tilde{\text {Ch}}_r(w')]_{h'}, w_{h'}\}=[\tilde{\text {Ch}}_r(w')]_{h'}.$ Since $w' \ge w$ and condition (1) holds, this implies that

  $$\begin{aligned}{}[\tilde{\text {Ch}}_r(w)]_{h'} \ge [\tilde{\text {Ch}}_r(w')]_{h'}. \end{aligned}$$

  (5)

  Also observe that the set $\{d' \in D| (d',h') \in X'\}$ is identical to $\{d' \in D| (d',h') \in X' \cup x\}$, that is, the sets of doctors that are available to hospital $h'$ are identical under $X'$ and $X' \cup x$. This fact, inequality (5), and the definition of $\text {Ch}_r$ imply that if $x'=(d',h') \notin \text {Ch}_r(X')$, then $x' \notin \text {Ch}_r(X' \cup x)$, obtaining the conclusion for the substitute condition in this case. (b) Consider hospital h. (i) Suppose that $[\tilde{\text {Ch}}_r(w)]_h \ge [\tilde{\text {Ch}}_r(w')]_h$. In this case, we follow an argument similar to (but slightly different from) Case (2a): Note that the set $\{d' \in D| (d',h) \in X'\}$ is a subset of $\{d' \in D| (d',h) \in X' \cup x\}$, that is, the set of doctors that are available to hospital h under $X'$ is smaller than under $X' \cup x$. These properties and the definition of $\text {Ch}_r$ imply that if $x'=(d',h) \in X' \setminus \text {Ch}_r(X')$, then $x' \in X' \setminus \text {Ch}_r(X' \cup x)$, obtaining the conclusion for the substitute condition in this case. (ii) Suppose that $[\tilde{\text {Ch}}_r(w)]_h < [\tilde{\text {Ch}}_r(w')]_h$. This assumption and (2) imply $[\tilde{\text {Ch}}_r(w)]_h =w_h$. Thus, by the definition of $\text {Ch}_r$, any contract $(d',h) \in X'$ such that $d' \succ _h \emptyset$ is in $\text {Ch}_r(X')$. Equivalently, if $x'=(d',h) \in X' \setminus \text {Ch}_r(X')$, then $\emptyset \succ _h d'$. Then, again by the definition of $\text {Ch}_r$, it follows that $x' \notin \text {Ch}_r(X' \cup x)$ for any contract $x'=(d',h) \in X' \setminus \text {Ch}_r(X')$. Thus, we obtain the conclusion of the substitute condition in this case.

To show that $\text {Ch}_r$ satisfies the law of aggregate demand, simply note that $\tilde{\text {Ch}}_r$ is acceptant by assumption. This leads to the desired conclusion. $\square$

A subset $X'$ of $X=D \times H$ is said to be individually rational if (1) for any $d \in D$, $|\{(d,h) \in X'|h \in H\}| \le 1$, and if $(d,h) \in X'$ then $h \succ _d \emptyset$, and (2) for any $r \in R$, $\text {Ch}_r(X')=X' \cap (D \times H_r)$.

Definition 6

A set of contracts $X^{\prime }\subseteq X$ is a stable allocation if

• 1. it is individually rational, and

• 2. there exists no region $r \in R$, hospital $h \in H_r$, and a doctor $d \in D$ such that $(d,h) \succ _d x$ and $(d,h) \in \text {Ch}_r(X' \cup \{(d,h)\})$, where x is the contract that d receives at $X'$ if any and $\emptyset$ otherwise.

When condition (2) is violated by some (d, h), we say that (d, h) is a block of $X^{\prime }$. A doctor-optimal stable allocation in the matching model with contracts is a stable allocation that every doctor weakly prefers to every other stable allocation (Hatfield and Milgrom 2005).

Given any individually rational set of contracts $X'$, define a corresponding matching$\mu (X')$ in the original model by setting $\mu _d(X')=h$ if and only if $(d,h) \in X'$ and $\mu _d(X')=\emptyset$ if and only if no contract associated with d is in $X'$. Since each doctor regards any set of contracts with cardinality of at least two as unacceptable, each doctor receives at most one contract at $X'$ and hence $\mu (X')$ is well defined for any individually rational $X'$.

Proposition 9

If $X'$ is a stable allocation in the associated model with contracts, then the corresponding matching $\mu (X')$ is a stable matching in the original model.

Proof

Suppose that $X'$ is a stable allocation in the associated model with contracts and denote $\mu :=\mu (X')$. Individual rationality of $\mu$ is obvious from the construction of $\mu$. Suppose that (d, h) is a blocking pair of $\mu$. Denoting $r:=r(h)$, by the definition of stability, it suffices to show that the following conditions (6) and (7) hold if $\mu _d \not \in H_r$, and (6), (7) and (8) hold if $\mu _d \in H_r$:

$$\begin{aligned}&|\mu _{H_r}|=q_r, \end{aligned}$$

(6)

$$\begin{aligned}&d' \succ _h d \text { for all }d' \in \mu _h, \end{aligned}$$

(7)

$$\begin{aligned}&w \succeq _r w', \end{aligned}$$

(8)

where $w=(w_h)_{h \in H_r}$ is defined by $w_{h'}=|\mu _{h'}|$ for all $h' \in H_r$ while $w'=(w'_h)_{h \in H_r}$ is defined by $w'_h=w_h+1$, $w'_{\mu _d}=w_{\mu _d}-1$ (if $\mu _d \in H_r$) and $w'_{h'}=w_{h'}$ for all other $h' \in H_r$.

Claim 1

Conditions (6) and (7) hold (irrespectively of whether$\mu _d \in H_r$or not).

Proof

First note that the assumption that $h \succ _d \mu _d$ implies that $(d,h) \succ _d x$ where x denotes the (possibly empty) contract that d signs under $X'$. Let $w''=(w''_h)_{h \in H_r}$ be defined by $w''_h=w_h+1$ and $w''_{h'}=w_{h'}$ for all other $h' \in H_r$.

• 1. Assume by contradiction that condition (7) is violated, that is, $d \succ _h d'$ for some $d' \in \mu _h$. First, by consistency of $\tilde{\text {Ch}}_r$, we have $[\tilde{\text {Ch}}_r(w'')]_h \ge [\tilde{\text {Ch}}_r(w)]_h$.²⁹ That is, weakly more contracts involving h are signed at $X' \cup (d,h)$ than at $X'$. This property, together with the assumptions that $d \succ _h d'$ and that $(d',h) \in X'$ imply that $(d,h) \in \text {Ch}_r(X' \cup (d,h))$.³⁰ Thus, together with the above-mentioned property that $(d,h) \succ _d x$, (d, h) is a block of $X'$ in the associated model of matching with contracts, contradicting the assumption that $X'$ is a stable allocation.

• 2. Assume by contradiction that condition (6) is violated, so that $|\mu _{H_r}| \ne q_r$. Then, since $|\mu _{H_r}| \le q_r$ by the construction of $\mu$ and the assumption that $X'$ is individually rational, it follows that $|\mu _{H_r}|<q_r$. Then, $(d,h) \in \text {Ch}_r(X' \cup (d,h))$ because (a) $d \succ _h \emptyset$ by assumption, (b) since $\sum _{h \in H_r}w_h=\sum _{h \in H_r}|\mu _h|=|\mu _{H_r}|<q_r$, it follows that $\sum _{h \in H_r}w''_h = \sum _{h \in H_r}w_h+1 \le q_r$. Moreover, $|\mu _h|<q_h$ because (d, h) is a blocking pair by assumption and (7) holds, so $w''_h=|\mu _h|+1 \le q_h$. These properties and the assumption that $\tilde{\text {Ch}}_r$ is acceptant imply that $\tilde{\text {Ch}}_r(w'')=w''$. In particular, this implies that all contracts $(d',h) \in X' \cup (d,h)$ such that $d' \succ _h \emptyset$ is chosen at $\text {Ch}_r(X' \cup (d,h))$. Thus, together with the above-mentioned property that $(d,h) \succ _d x$, (d, h) is a block of $X'$ in the associated model of matching with contract, contradicting the assumption that $X'$ is a stable allocation.

$\square$

To finish the proof of the proposition suppose that $\mu _d \in H_r$ and by contradiction that (8) fails, that is, $w' \succ _r w$. Then, it should be the case that $[\tilde{\text {Ch}}_r(w'')]_h=w''_h=w_h+1=|\mu _h|+1$.³¹ Also, we have $|\mu _h|<q_h$ and hence $|\mu _h|+1 \le q_h$ and $d \succ _h \emptyset$, so

$$\begin{aligned} (d,h) \in \text {Ch}_r(X' \cup (d,h)). \end{aligned}$$

This relationship, together with the assumption that $h \succ _d \mu _d$, and hence $(d,h) \succ _d x$, is a contradiction to the assumption that $X'$ is stable in the associated model with contracts. $\square$

Remark 1

Each step of the flexible deferred acceptance algorithm corresponds to a step of the cumulative offer process (Hatfield and Milgrom 2005), that is, at each step, if doctor d proposes to hospital h in the flexible deferred acceptance algorithm, then at the same step of the cumulative offer process, contract (d, h) is proposed. Moreover, the set of doctors accepted for hospitals at a step of the flexible deferred acceptance algorithm corresponds to the set of contracts held at the corresponding step of the cumulative offer process. Therefore, if $X'$ is the allocation that is produced by the cumulative offer process, then $\mu (X')$ is the matching produced by the flexible deferred acceptance algorithm.

Proof of Proposition 0

By Proposition 8, the choice function of each region satisfies the substitutes condition and the law of aggregate demand in the associate model of matching with contracts. By Hatfield and Milgrom (2005), Hatfield and Kojima (2009), and Hatfield and Kominers (2012), the cumulative offer process with choice functions satisfying these conditions produces a stable allocation and is (group) strategy-proof.³² The former fact, together with Remark 1 and Proposition 9, implies that the outcome of the flexible deferred acceptance algorithm is a stable matching in the original model. The latter fact and Remark 1 imply that the flexible deferred acceptance mechanism is (group) strategy-proof for doctors. $\square$

Appendix 2: Proofs for Sect. 4

1.1 2. 1 Proofs for Sect. 4.1

Proof of Proposition 2

Let $\mu$ be a matching and w be defined by $w_{h'}=|\mu _{h'}|$ for each $h' \in H_r$ and $w'$ by $w'_h=w_h+1$, $w'_{\mu _d}=w_{\mu _d}-1$, and $w'_{h'}=w_{h'}$ for all $h' \in H_r \setminus \{h,\mu _d\}$. It suffices to show that $w \succeq _r w'$ if and only if $|\mu _h|+1 - {\bar{q}}_h > |\mu _{\mu _d}| - 1 - {\bar{q}}_{\mu _d}$.

Suppose that $|\mu _h|+1 - {\bar{q}}_h > |\mu _{\mu _d}| - 1 - {\bar{q}}_{\mu _d}$. This means that $w_h+1 -{\bar{q}}_h >w_{{\mu _d}}-1 -{\bar{q}}_{\mu _d}$, which is equivalent to either $w_h -{\bar{q}}_h =w_{{\mu _d}}-1 -{\bar{q}}_{\mu _d} \text { or } w_h -{\bar{q}}_h \ge w_{{\mu _d}} -{\bar{q}}_{\mu _d}.$ In the former case, obviously $\eta (w)=\eta (w')$, so $w \succeq _r w'$. In the latter case, $\{h' |w'_{h'} - {\bar{q}}_{h'}<\left| \mu _{\mu _d}\right| -{\bar{q}}_{\mu _d}\}=\{h' |w_{h'} - {\bar{q}}_{h'}<\left| \mu _{\mu _d}\right| -{\bar{q}}_{\mu _d}\} \cup \{\mu _d\}$, and $w_{h'}=w'_{h'}$ for all $h' \in \{h' |w_{h'} - {\bar{q}}_{h'}<\left| \mu _{\mu _d}\right| -{\bar{q}}_{\mu _d}\}$. Thus, we obtain $w \succ _r w'$.

If $|\mu _h|+1 - {\bar{q}}_h \le |\mu _{\mu _d}| - 1 - {\bar{q}}_{\mu _d}$, then obviously $w' \succ _r w$. This completes the proof. $\square$

Proof of Proposition 3

It is clear that the quasi choice rule $\tilde{\text {Ch}}_r$ defined in (3) satisfies the condition (1) for substitutability (as well as consistency and acceptance). Thus, in the following, we will show that $\tilde{\text {Ch}}_r$ indeed satisfies $\tilde{\text {Ch}}_r(w) \in \mathop {\hbox {arg max}}\nolimits _{\succeq _r}\{x| x \le w\}$ for each w. Let $w'=\tilde{\text {Ch}}_r(w)$. Assume by contradiction that $w' \notin \mathop {\hbox {arg max}}\nolimits _{\succeq _r}\{x| x \le w\}$ and consider an arbitrary $w'' \in \mathop {\hbox {arg max}}\nolimits _{\succeq _r}\{x| x \le w\}$. Then, we have $w'' \succ _r w'$, so there exists i such that $\eta _j(w'')=\eta _j(w')$ for every $j<i$ and $\eta _i(w'')>\eta _i(w')$. Consider the following cases.

• 1. Suppose $\sum _{j}\eta _j(w'')>\sum _{j}\eta _j(w')$. First, note that $\sum _{j}\eta _j(w'')+\sum _{h}{\bar{q}}_h=\sum _{h}w''_h \le q_r$ because $w'' \in \mathop {\hbox {arg max}}\nolimits _{\succeq _r}\{x| x \le w\}$. Thus $\sum _{h}w'_h=\sum _{j}\eta _j(w') +\sum _{h}{\bar{q}}_h< \sum _{j}\eta _j(w'') +\sum _{h}{\bar{q}}_h\le q_r$. Moreover, the assumption implies that there exists a hospital h such that $w'_h < w''_h \le \min \{q_h,w_h\}$. These properties contradict the construction of $\tilde{\text {Ch}}_r$.

• 2. Suppose $\sum _{j}\eta _j(w'')<\sum _{j}\eta _j(w')$. First note that $\sum _{j}\eta _j(w')+\sum _{h}{\bar{q}}_h=\sum _{h}w'_h \le q_r$ by construction of $\tilde{\text {Ch}}_r$. Thus, $\sum _{h}w''_h=\sum _{j}\eta _j(w'')+\sum _{h}{\bar{q}}_h < \sum _{j}\eta _j(w')+\sum _{h}{\bar{q}}_h \le q_r$. Moreover, the assumption implies that there exists a hospital h such that $w''_h < w'_h \le \min \{q_h,w_h\}$. Then, $w'''$ defined by $w'''_h=w_h''+1$ and $w'''_{h'}=w_{h'}''$ for all $h' \ne h$ satisfies $w''' \le w$ and $w''' \succ _r w''$, contradicting the assumption that $w'' \in \mathop {\hbox {arg max}}\nolimits _{\succeq _r}\{x| x \le w\}$.

• 3. Suppose that $\sum _{j}\eta _j(w'')=\sum _{j}\eta _j(w')$. Then, there exists some k such that $\eta _k(w'')<\eta _k(w')$. Let $l=\min \{k|\eta _k(w'')<\eta _k(w')\}$ be the smallest of such indices. Then, since $l >i$, we have $\eta _i(w')<\eta _i(w'') \le \eta _l(w'') < \eta _l(w')$. Thus, it should be the case that $\eta _i(w') +2 \le \eta _l(w')$. By the construction of $\tilde{\text {Ch}}_r$, this inequality holds only if $w'_h=\min \{q_h, w_h\}$, where h is an arbitrarily chosen hospital such that $w'_h -{\bar{q}}_h=\eta _i(w')$. Now, it should be the case that $w''_h=\min \{q_h, w_h\}$ as well, because otherwise $w'' \notin \mathop {\hbox {arg max}}\nolimits _{\succeq _r}\{x| x \le w\}$.³³ Thus $w'_h=w''_h$. Now consider the modified vectors of both $w'$ and $w''$ that delete the entries corresponding to h. All the properties described above hold for these new vectors. Proceeding inductively, we obtain $w_h'=w_h''$ for all h, that is, $w'=w''$. This is a contradiction to the assumption that $w' \notin \mathop {\hbox {arg max}}\nolimits _{\succeq _r}\{x| x \le w\}$ and $w'' \in \mathop {\hbox {arg max}}\nolimits _{\succeq _r}\{x| x \le w\}$.

The above cases complete the proof. $\square$

1.2 2. 2 Proofs for Sect. 4.3

The following result, which applies not only to matching with contract models defined over the set of contracts $D\times H$ but also to those defined over general environments, proves useful.

Lemma 1

Consider a model of matching with contracts. Fix the set of doctors and regions as well as doctor preferences. Assume that choice rules$Ch:=(Ch_r)_{r \in R}$and$Ch':=(Ch'_r)_{r \in R}$satisfy$Ch'_r(X') \subseteq Ch_r(X')$for every subset of contracts$X'$and regionr. Then, the following two statements hold:

• 1. Each doctor weakly prefers the outcome of the cumulative offer process with respect toChto the result with respect to$Ch'$. Hence, each doctor weakly prefers the doctor-optimal stable allocation underChto the doctor-optimal stable allocation under$Ch'$.

• 2. The set of contracts that have been offered up to and including the terminal step of the cumulative offer process underChis a subset of the corresponding set under$Ch'.$

Proof

Let $Y_d$ and $Y'_d$ be the contracts allocated to d by the cumulative offer processes under Ch and $Ch'$, respectively. Also, let C(t) be the set of contracts that have been offered up to and including step t of the cumulative offer process under Ch, and $C'(t)$ be the corresponding set for the cumulative offer process under $Ch'$. Let T and $T'$ be the terminal steps for the cumulative offer processes under Ch and $Ch'$, respectively. We first prove Part 2 of the lemma, and then show Part 1.

Part 2: Suppose the contrary, i.e., that $C(T)\not \subseteq C'(T')$. Then, there exists a step $t'$ such that $C(t)\subseteq C'(T')$ for all $t<t'$ and $C(t')\not \subseteq C'(T')$ holds. That is, $t'$ is the first step such that an application not made in the cumulative offer process under $Ch'$ is made in the cumulative offer process under Ch. Let x be the contract that d offers in this step under Ch. Notice that $Y'_d\succ _d x$. This implies that $Y'_d\ne \emptyset$ and that $Y'_d$ is rejected by $r'$ in some steps of the cumulative offer process under Ch, where $r'$ is the region associated with $Y_d'$. Let the first of such steps be $t''$. Since in the cumulative offer process doctors make offers in order of their preferences, $Y'_d\succ _d x$ implies that $t''<t'$, which in turn implies $C(t'')\subseteq C'(T')$ by the definition of $t'$.

Now, we show that the set of contracts accepted by $r'$ at step $t''$ of the cumulative offer process under Ch is a superset of the set of contracts accepted by $r'$ from the application pool $C(t'')$ (which is a subset of $C'(T')$) at step $T'$ of the cumulative offer process under $Ch'$. To see this, note that if the same application pool $C'(T')$ is given, the set of contracts accepted by $r'$ in the cumulative offer process under Ch is weakly larger than that under $Ch'$ by the assumption that $Ch_r'(X') \subseteq Ch_r(X')$ for all $X' \subseteq X$ and $r \in R$. Since Ch is substitutable, subtracting applications in $C'(T')\setminus C(t'')$ does not shrink the set of contracts accepted by $r'$ within $C(t'')$ at step $t''$ of the cumulative offer process under Ch, which establishes our claim.

However, this contradicts our earlier conclusion that $Y'_d$ is rejected by $r'$ at step $t''$ of the cumulative offer process under Ch while she is allocated $Y'_d$ in the cumulative offer process under $Ch'$. Hence, we conclude that $C(T)\subseteq C'(T')$.

Part 1: Now, since in the cumulative offer process each doctor d make offers of contracts in order of her preferences, $Y_d$ is $\emptyset$ or the worst contract for d in the set of contracts associated with d in C(T). Similarly, for each doctor d, $Y'_d$ is $\emptyset$ or the worst contract for d in the set of contracts associated with d in $C'(T')$. If $Y_d\ne \emptyset$, this and $C(T)\subseteq C'(T')$ imply that $Y_d\succeq _d Y_d'$. If $Y_d= \emptyset$, d has applied to all acceptable contracts in the cumulative offer process under Ch. Thus, $C(T)\subseteq C'(T')$ implies that she has applied to all acceptable contracts in the algorithm under $Ch'$, too. Let $x'$ be the worst acceptable contract in X for d, and r be a region associated with $x'$. At this point, we already know that $Y'_d$ is either $x'$ or $\emptyset$, and we will show that $Y'_d= \emptyset$ in what follows. Again, $C(T)\subseteq C'(T')$ implies that all applications associated with r in C(T) are in $C'(T')$. In particular, d’s application to $x'$ is in $C'(T')$. Since Ch is substitutable, subtracting applications in $C'(T')\setminus C(T)$ does not shrink the set of doctors accepted by r within C(T) at step T of the deferred acceptance, so d not being accepted by r from C(T) at step T of the cumulative offer process under Ch implies that she is not accepted by r from $C'(T')$ in step $T'$ of the process under $Ch'$ either. But since we have shown that d’s offer of contract $x'$ to r is in $C'(T')$, this implies that in the cumulative offer process under $Ch'$, $x'$ is rejected by r. Because $x'$ is the worst acceptable contract for d and d’s applications that are made in order of her preferences, we conclude that $Y'_d=\emptyset$, thus in particular $Y_d\succeq _d Y'_d$.

This shows that each doctor $d\in D$ weakly prefers a contract allocated by the cumulative offer process under Ch to the one under $Ch'$.

Since the outcome of the cumulative offer process is the doctor-optimal stable allocation, the preceding proof has also shown that the doctor-optimal stable allocation under Ch is weakly more preferred to the doctor-optimal stable allocation under $Ch'$. $\square$

Lemma 1 is a generalization of a number of existing results. Gale and Sotomayor (1985a, b) establish comparative statics results in one-to-one and many-to-one matching with respect to the extension of an agent’s list of her acceptable partners or an addition of an agent to the market, and Crawford (1991) generalizes the results to many-to-many matching. Konishi and Ünver (2006) consider many-to-one matching and obtain a comparative statics result with respect to the changes of hospital capacities.³⁴ All these changes are special cases of changes in the choice rules, so these results are corollaries of Lemma 1.

Lemma 1 may be of independent interest as the most general comparative statics result known to date. In addition, the lemma implies various results that are directly relevant to the current study of regional caps, such as Propositions 4, 5, 6, and 7 in the main text.

Proof of Proposition 4

Part 1: Let $\text {Ch}^F=(\text {Ch}^F_r)_{r \in R}$ be the choice rule associated with the flexible deferred acceptance as defined earlier, that is, for each region $r \in R$ and subset of contracts $X' \subseteq X=D \times H$, the chosen set of contracts $\text {Ch}^F_r(X')$ is defined by

$$\begin{aligned} {\text{Ch}}^{F}_{r} (X^{\prime})= {\bigcup}_{h \in H_{r}} \left\{(d,h) \in X^{\prime} \; \Big{|} \; \left| \{d^{\prime} \in D (d^{\prime},h) \in X^{\prime}, d^{\prime} {\succeq}_{h} d\}\right| \le (\tilde{{\text{Ch}}}_r(w(X^{\prime})))_{h} \right\}.\end{aligned}$$

where $\tilde{\text {Ch}}_r$ corresponds to a Rawlsian regional preference of region r and $w(X')=(w_h(X'))_{h \in H_r}$ is the vector such that $w_h(X')=|\{(d,h) \in X'| d \succ _h \emptyset \}|$ (this is a special case of the choice rule (4)).

Moreover, consider choice rules $Ch^D=(Ch^D_r)_{r \in R}$ and $Ch^J=(Ch^J_r)_{r \in R}$ such that, for each $X'$ and r,

$$\begin{aligned} {{\text {Ch}}^D_r}(X')=\bigcup _{h \in H_r} \left\{ (d,h) \in X' \, \Big|\;\, \left| \{d' \in D| (d',h) \in X', d' \succeq _h d\}\right| \le q_h \right\} ,\\ {{\text {Ch}}^J_r}(X')=\bigcup _{h \in H_r} \left\{ (d,h) \in X' \,\; \Big|\;\, \left| \{d' \in D| (d',h) \in X', d' \succeq _h d\}\right| \le {\bar{q}}_h \right\} . \end{aligned}$$

Clearly, both $\text {Ch}^D$ and $\text {Ch}^J$ satisfy the substitute condition and the law of aggregate demand. Moreover, the matchings corresponding to the results of the cumulative offer processes under $\text {Ch}^D$ and $\text {Ch}^J$ are identical to the results of the deferred acceptance algorithm and the JRMP mechanism, respectively. Because $\min \{{\bar{q}}_h,w_h\} \le (\tilde{\text {Ch}}_r(w(X')))_h \le q_h$ for all $h \in H_r$ and $X'$, by inspection of the above definitions of the choice rules we obtain $\text {Ch}^J_r(X') \subseteq \text {Ch}^F_r(X') \subseteq \text {Ch}^D_r(X')$ for all $X'$ and r. Thus, the desired conclusion follows by Part 1 of Lemma 1.

Part 2: This is a direct corollary of Part 1 and the fact that none of the algorithms considered here matches a doctor to an unacceptable hospital. $\square$

Proof of Proposition 5

Let $\text {Ch}=(\text {Ch}_r)_{r \in R}$ and $\text {Ch}^{'}=(\text {Ch}^{'}_r)_{r \in R}$ be the choice rules associated with the flexible deferred acceptance mechanisms (as defined in the proof of Proposition 4) with respect to $(q_r)_{r \in R}$ and $(q'_r)_{r \in R}$, respectively.

Part 1: Because $q'_r \le q_r$ for each $r \in R$, the definition of these choice rules implies $\text {Ch}'_r(X') \subseteq \text {Ch}_r(X')$ for all $X'$ and r. Hence, the desired conclusion follows by Part 1 of Lemma 1.

Part 2: Since $\text {Ch}'_r(X') \subseteq \text {Ch}_r(X')$ for all $X'$ and r as mentioned in the proof of Part 1, Part 2 of Lemma 1 implies that $C(T)\subseteq C'(T')$, where C, T, $C'$, and $T'$ are as defined in Part 2 of the lemma. Note that the sets of contracts allocated to hospitals in r at the conclusions of the cumulative offer processes under Ch and $Ch'$ are given as r’s choice from contracts associated with r in C(T) and $C'(T')$, respectively. Because the choice rules satisfy the law of aggregate demand and the set-inclusion relationship $C(T) \subseteq C'(T')$ holds, for any r such that $q_r=q'_r$, the number of doctors matched in r under a matching produced by the flexible deferred acceptance mechanism under regional caps $(q'_r)_{r \in R}$ is weakly larger than that in the matching under $(q_r)_{r \in R}$, completing the proof. $\square$

Proof of Proposition 6

Let $\text {Ch}=(\text {Ch}_r)_{r \in R}$ and $\text {Ch}^{'}=(\text {Ch}^{'}_r)_{r \in R}$ be the choice rules associated with the JRMP mechanisms (as defined in the proof of Proposition 4) with respect to $({\bar{q}}_h)_{h \in H}$ and $({\bar{q}}'_h)_{h \in H}$, respectively.

Part 1: Because ${\bar{q}}'_h \le {\bar{q}}_h$ for each $h \in H$, the definition of these choice rules implies $\text {Ch}'_r(X') \subseteq \text {Ch}_r(X')$ for all $X'$ and r. Hence, the desired conclusion follows by Part 1 of Lemma 1.

Part 2: Since $\text {Ch}'_r(X') \subseteq \text {Ch}_r(X')$ for all $X'$ and r as mentioned in the proof of Part 1, Part 2 of Lemma 1 implies that $C(T)\subseteq C'(T')$, where C, T, $C'$, and $T'$ are as defined in Part  2 of Lemma 1. Note that the matchings for h at the conclusions of the cumulative offer processes under Ch and $Ch'$ are given as h’s most preferred acceptable doctors up to ${\bar{q}}_h={\bar{q}}'_h$ from contracts associated with h in C(T) and $C'(T')$, respectively. Thus, the set-inclusion relationship $C(T) \subseteq C'(T')$ implies both the statements of Part 2. $\square$

Proof of Proposition 7

Part 1: First, by Part 2 of Lemma 1 and the proof of Proposition 4, the set of contracts that have been offered up to and including the terminal step under the deferred acceptance mechanism is a subset of the one under the flexible deferred acceptance mechanism. Second, by the construction of the flexible deferred acceptance algorithm, and the assumption that hospital h’s target capacity is not filled, under the flexible deferred acceptance mechanism h is matched to every doctor who is acceptable to h and who applied to h in some step of the algorithm. These two facts imply the conclusion.

Part 2: First, by Part 2 of Lemma 1 and the proof of Proposition 4, the set of contracts that have been offered up to and including the terminal step under the deferred acceptance mechanism is a subset of the one under the flexible deferred acceptance mechanism. Second, by the construction of the flexible deferred acceptance algorithm, and the assumption that region r’s regional cap is not filled, under the flexible deferred acceptance mechanism any hospital h in region r is matched to every doctor who is acceptable and who is among the most preferred $q_h$ doctors who applied to h in some step of the algorithm. These two facts imply the conclusion. $\square$

Appendix 3: Further statistics on heterogeneity of capacities

Across prefectures in Japan, the mean and the median of the ratios of the maximum and the minimum hospital capacities are 20.98 and 19, respectively (see Fig. 3). The mean and the median of the Gini coefficients across prefectures are both 0.48, showing that the heterogeneity of hospital capacities is quite significant.³⁵ Capacities differ substantially in the school choice context as well; see Table 1 that reports data from Boston Public Schools (2013). The ratios of the maximum and the minimum of school capacities range from 1.80 to 16.19 with the median of 5.28, and all the Gini coefficients are no less than 0.10.

Fig. 3

The ratios of the maximum and the minimum hospital capacities across prefectures

Table 1 Heterogeneity in size by school category

Appendix 4: Allocating target capacities

A problem related to, but distinct from, our discussion in Sect. 4.2 is how to allocate target capacities among hospitals in a region, within the simple, Rawlsian framework of Kamada and Kojima (2015). We will not try to provide a final answer to the normative question of how to do so for several reasons. First, there may be different ways to specify the quasi choice rule even given the same target capacity profile, as we have seen in this section, and in fact there may be reasonable quasi choice rules that do not even presuppose the existence of target capacities. Second, even if we fix a quasi choice rule, the relation between target capacities and the desirability of the resulting outcome is ambiguous. An example in Kamada and Kojima (2015) shows that the effect on hospital welfare is ambiguous.³⁶

Despite these reservations, hospitals may still find having higher targets intuitively appealing in practice, so the problem seems to be practically important. Motivated by this observation, we present several methods to allocate target capacities that seem to be reasonable.

To do so, our starting point is to point out that the problem of allocating target capacities is similar to the celebrated “bankruptcy problem” (see Thomson (2003)). This is a useful association in the sense that, in the bankruptcy problem, there are known analyses (e.g., axiomatic characterizations) of various allocation rules, which can be utilized to judge which rule is appropriate for a given application.

To make this association, recall that in the standard bankruptcy problem, there is a divisible asset and agents whose claims sum up to (weakly) more than the amount of the available asset. Our problem is a discrete analogue of the bankruptcy problem. The regional cap $q_r$ is an asset, hospitals in region r are agents, and physical capacity $q_h$ is the claim of hospital h. Just as in the bankruptcy problem, the sum of the physical capacities may exceed the available regional cap, so the target capacity profile $({\bar{q}}_h)_{h \in H_r}$ needs to be decided subject to the constraint $\sum _{h \in H_r}{\bar{q}}_h \le q_r$.

This association suggests adaptations of well-known solutions in the bankruptcy problem to our problem, with the modification due to the fact that both the asset and the claims are discrete in our problem. The following are a few examples (in the following, we assume $\sum _{h \in H_r} q_h \ge q_r$; otherwise set ${\bar{q}}_h=q_h$ for all h).

• 1. “Constrained Equal Awards Rule”: This solution allocates the targets as equally as possible except that, for any hospital, it does not allocate a target larger than the capacity. This rule is called the constrained equal awards rule in the literature on the bankruptcy problem. In our context, this solution should be modified because all the targets need to be integers. Formally, a constrained equal awards rule in our context can be defined as follows: (a) Find $\lambda$ that satisfies $\sum _{h \in H_r} \min \{\lambda ,q_h\}=q_r$. (b) For each $h \in H_r$, if $\lambda >q_h$, then set ${\bar{q}}_h=q_h$. Otherwise, set ${\bar{q}}_h$ to be either $\lfloor \lambda \rfloor$ (the largest integer no larger than $\lambda$) or $\lfloor \lambda \rfloor +1$, subject to the constraint that $\sum _{h \in H_r} {\bar{q}}_h=q_r$. The rule to decide which hospital receives $\lfloor \lambda \rfloor$ or $\lfloor \lambda \rfloor +1$ is arbitrary: For any decision rule, the resulting target profiles satisfy conditions assumed in Kamada and Kojima (2015). The decision can also use randomization, which may help achieve ex ante fairness.

• 2. “Constrained Equal Losses Rule”: This solution allocates the targets in such a way that it equates losses (that is, differences between the capacities and the targets) as much as possible, except that none of the allocated targets can be strictly smaller than zero. This rule is called the constrained equal losses rule in the literature on the bankruptcy problem. As in the case of the constrained equal awards rule, this solution should be modified because all the targets need to be integers. Formally, a constrained equal losses rule in our context can be defined as follows: (a) Find $\lambda$ that satisfies $\sum _{h \in H_r} \max \{q_h-\lambda ,0\}=q_r$. (b) For each $h \in H_r$, if $q_h-\lambda <0$, then set ${\bar{q}}_h=0$. Otherwise, set ${\bar{q}}_h$ to be either $q_h-\lfloor \lambda \rfloor$ or $q_h-\lfloor \lambda \rfloor -1$, subject to the constraint that $\sum _{h \in H_r} {\bar{q}}_h=q_r$. As in the constrained equal awards rule, the rule to decide which hospital receives $q_h-\lfloor \lambda \rfloor$ or $q_h-\lfloor \lambda \rfloor -1$ is arbitrary: For any decision rule, the resulting target profiles satisfy conditions assumed in Kamada and Kojima (2015). The decision can also use randomization, which may help achieve ex ante fairness.

• 3. “Proportional Rule”: This solution allocates the targets in a manner that is as proportional as possible to the hospitals’ capacities. This rule is called the proportional rule in the literature on the bankruptcy problem. As in the case of the previous rules, this solution should be modified because all the targets need to be integers. Formally, a proportional rule in our context can be defined as follows: (a) Find $\lambda$ that satisfies $\sum _{h \in H_r} \lambda q_h=q_r$. (b) For each $h \in H_r$, set ${\bar{q}}_h$ be either $\lfloor \lambda q_h \rfloor$ or $\lfloor \lambda q_h \rfloor +1$, subject to the constraint that $\sum _{h \in H_r} {\bar{q}}_h=q_r$. As in the previous cases, the rule to decide which a hospital receives $\lfloor \lambda q_h \rfloor$ or $\lfloor \lambda q_h \rfloor +1$ is arbitrary: For any decision rule, the resulting target profiles satisfy conditions assumed in Kamada and Kojima (2015). The decision can also use randomization, which may help achieve ex ante fairness.

  The proportional rule seems to be fairly appealing in practice. This rule is used in Japanese residency match and Chinese graduate school admission, for example.