STABILITY AND STRATEGY-PROOFNESS FOR MATCHING WITHCONSTRAINTS: A NECESSARY AND SUFFICIENT CONDITION
YUICHIRO KAMADA AND FUHITO KOJIMA

Abstract. Distributional constraints are common features in many real matching markets, such as medical residency matching, school admissions, and teacher assignment. We
develop a general theory of matching mechanisms under distributional constraints. We
identify the necessary and sufficient condition on the constraint structure for the existence of a mechanism that is stable and strategy-proof for the individuals. Our proof
exploits a connection between a matching problem under distributional constraints anda matching problem with contracts.
JEL Classification Numbers: C70, D47, D61, D63.
Keywords: matching with constraints, medical residency matching, school choice, stability, strategy-proofness, matching with contracts, hierarchy
Note: This paper subsumes and supersedes part of our unpublished paper “General
Theory of Matching under Distributional Constraints,” cited as Kamada and Kojima(2015b) in this paper.

Date: May 12, 2017.
Kamada: Haas School of Business, University of California, Berkeley, Berkeley, CA 94720,
y.cam.24@gmail.com. Kojima: Department of Economics, Stanford University, Stanford, CA 94305,
fkojima@stanford.edu. We are grateful to Mustafa Oguz Afacan, Péter Biró, Eric Budish, Sylvain Chassang, Vincent Crawford, Hisao Endo, Clayton Featherstone, Tamás Fleiner, Drew Fudenberg, Tadashi
Hashimoto, John William Hatfield, Christian Hellwig, Toshiaki Iizuka, Rob Irving, Ryo Jinnai, Onur
Kesten, Scott Duke Kominers, Hideo Konishi, Mihai Manea, David Manlove, Taisuke Matsubae, Aki
Matsui, Yusuke Narita, Muriel Niederle, Parag Pathak, Al Roth, Dan Sasaki, Tayfun Sönmez, Satoru
Takahashi, William Thomson, Alexis Akira Toda, Kentaro Tomoeda, Utku Ünver, Jun Wako, Alex Westkamp, Yosuke Yasuda, Bumin Yenmez, and participants at numerous seminars and conferences for helpfulcomments. Doctor Masaaki Nagano answered our questions about medical residency in Japan. Jin Chen,
Irene Hsu, Seung Hoon Lee, Stephen Nei, Bobak Pakzad-Hurson, Neil Prasad, Fanqi Shi, Pete Troyan,
Wei Wen, and Rui Yu provided excellent research assistance. Kojima gratefully acknowledges financial
support from the Sloan Foundation, as well as financial support from the National Research Foundation
through its Global Research Network Grant (NRF- 2013S1A2A2035408).
1

2

1. Introduction
The theory of two-sided matching has been extensively studied ever since the seminal
contribution by Gale and Shapley (1962), and it has been applied to match individuals
and institutions in various markets in practice (e.g., students and schools, doctors andhospitals, and workers and firms). However, many real matching markets are subject todistributional constraints, i.e., caps are imposed on the numbers of individuals who canbe matched to some subsets of institutions. Traditional theory cannot be applied to suchsettings because it has assumed away those constraints.
The objective of this paper is to understand the implication of the structure of distributional constraints, by investigating the extent to which a desirable mechanism canbe designed under constraints. More specifically, we identify the necessary and sufficientcondition on the constraint structure for the existence of a mechanism that is stable andstrategy-proof for the individuals.1 The necessary and sufficient condition is that constraints form a “hierarchy,” that is, for any pair of subsets of institutions that are subject
to constraints, the two are disjoint or one is a subset of the other.2,3
To understand implications of our result, consider matching doctors with hospitals.
Suppose –as is the case in many countries– the government desires to keep geographicalimbalance of doctors in check, leading to constraints imposed on different regions of thecountry (Kamada and Kojima, 2015a). Since the family of regions form a partition of thecountry, a special case of a hierarchy, our result implies that there exists a mechanism
which is stable and strategy-proof for doctors. The same positive conclusion holds even if
the geographical constraints are imposed on a hierarchy of regions, for instance on states
and counties (here, the constraints form a hierarchy because counties are mutually disjoint
and subsets of states).
Next, suppose that the government desires to impose caps not only on the number ofdoctors in different regions, but also on the number of doctors working in different medical
specialties (this is also a common public health policy issue; see Section 4 for a concrete
policy debate). The constraints do not form a hierarchy in this case because a region and1

We formally define a stability concept under constraints in Section 2. Our stability concept reduces

to the standard stability concept of Gale and Shapley (1962) if there are no binding constraints.
2

Such a hierarchical structure is called a “laminar family” in the mathematics literature.

3Budish, Che, Kojima, and Milgrom (2013) consider a random object allocation problem with floor

and ceiling constraints and show that “bi-hierarchical” constraints are necessary and sufficient for implementability of random assignments. Although the condition they reach is similar to ours, their implementability is unrelated to stability and strategy-proofness that we study here. See also Milgrom(2009).

3a specialty partially overlap with each other. Therefore, the necessity part of our result
implies that it is impossible to design a mechanism that is stable and strategy-proof
for doctors. By contrast, if the constraints are imposed on doctors exercising different
medical specialties in each region, then the constraints regain a hierarchical structure, so
our result implies that a desirable mechanism exists.
Our result also has implications for the design of school choice mechanisms (Abdulkadiroğlu and Sönmez, 2003). Suppose that the school district wants to maintain certainbalance of student body at each school in terms of socio-economic class. Different socioeconomic classes form a partition (and thus a hierarchy), so a stable and strategy-proof
mechanism exists. By contrast if, for instance, the school district desires to maintainbalance in both socio-economic class and gender, then the constraints do not form ahierarchy, so a desirable mechanism does not exist.4
In addition to its applied value, we believe that our analytical approach is of independentinterest. The approach for showing the sufficiency of a hierarchy is to find a connection
between our model and the “matching with contracts” model (Hatfield and Milgrom,2005).5 More specifically, we define a hypothetical matching problem between doctors
and the “hospital side” instead of doctors and hospitals; We regard the hospital side
as a hypothetical consortium of hospitals that acts as one agent. By imagining that thehospital side (hospital consortium) makes a common employment decision, we can accountfor interrelated doctor assignments across hospitals, an inevitable feature in markets under
distributional constraints. This association necessitates, however, that we distinguish a
doctor’s matching in different hospitals. We account for this complication by constructing
4Abdulkadiroğlu and Sönmez (2003) and Abdulkadiroğlu (2005) show that a stable and strategy-proof

mechanism exists under constraints on socio-economic class and give an example that shows nonexistence
when constraints are imposed also on gender. There are three main differences between their work andours. First, we consider a different formulation from theirs. Second, our characterization of the necessary
condition for existence is new. Third, we show existence under hierarchical constraints. See also Roth(1991) on gender balance in labor markets, Ergin and Sönmez (2006), Hafalir, Yenmez, and Yildirim(2013), Ehlers, Hafalir, Yenmez, and Yildirim (2014), and Echenique and Yenmez (2015) on diversity inschools, Westkamp (2013) on trait-specific college admission, Abraham, Irving, and Manlove (2007) on
project-specific quotas in projects-students matching, and Biró, Fleiner, Irving, and Manlove (2010) on
college admission with multiple types of tuitions.
5Fleiner (2003) considers a framework that generalizes various mathematical results. A special case of
his model corresponds to the model of Hatfield and Milgrom (2005), although not all results of the latter(e.g., those concerning incentives) are obtained in the former. See also Crawford and Knoer (1981) who
observe that wages can represent general job descriptions in their model, given their assumption thatfirm preferences satisfy separability.

4

the hospital side’s choice defined over contracts rather than doctors, where a contract
specifies a doctor-hospital pair to be matched. Once this connection is established, withsome work we show that results in the matching-with-contract model can be applied toour matching model under distributional constraints.6 This method shows that there
exists a mechanism that is stable and strategy-proofness for doctors. Note that our
technique is different from those in school choice with diversity constraints which haveschools’ aggregated preferences over different types of students as primitives. By contrast,
aggregated preferences of the hospital side are not primitives of our model, and ourcontribution is to construct an appropriate hypothetical model with an aggregated choicefunction. We envision that analyzing a hypothetical model of matching with contracts
may prove to be a useful approach for tackling complex matching problems one may
encounter in the future.7,8
A recent paper by Hatfield, Kominers, and Westkamp (2015) characterizes the class ofchoice functions over abstract contracts such that there exists a mechanism that is stable
and strategy-proof for doctors (see a related contribution by Hirata and Kasuya (2015) aswell). Our result and theirs are independent of each other because our model and stability
concept are different from theirs: Our model is that of matching with constraints and,even though we can associate our stability concept to theirs through our technique, theseconcepts are still not equivalent (Kamada and Kojima, 2015a).
This paper is part of our research agenda to study matching with constraints. Let us
explain the contribution of the present paper relative to our other papers on the agenda.
Kamada and Kojima (2015a) consider the case in which constraints form a partition andshow that a desirable mechanism exists. In practice, however, non-partitional constraints
are prevalent. In order to understand what kinds of applications can be accommodated,
the present paper does not presume a partition structure, and instead investigates a conceptual question. More specifically, we find a necessary and sufficient condition for the
6Specifically, we invoke results by Hatfield and Milgrom (2005), Hatfield and Kojima (2009, 2010), andHatfield and Kominers (2009, 2012).
7Indeed, after we circulated the first draft of the present paper, this technique was adopted by otherstudies such as Goto, Iwasaki, Kawasaki, Yasuda, and Yokoo (2014), Goto, Hashimoto, Iwasaki, Kawasaki,
Ueda, Yasuda, and Yokoo (2014), and Kojima, Tamura, and Yokoo (2015) in the context of matchingwith distributional constraints. See Sönmez and Switzer (2013) for a more direct application of matchingwith contracts model, where a cadet can be matched with a branch under one of two possible contracts.
See also Sönmez (2013) and Kominers and Sönmez (2012).
8See also Hatfield, Kominers, Nichifor, Ostrovsky, and Westkamp (2013) who connect stability in a
trading network with stability in an associated model of many-to-one two-sided matching with transfer
due to Kelso and Crawford (1982).

5existence of a desirable mechanism in terms of the constraint structure. Kamada andKojima (2016) investigate how to define the “right” stability concept for matching withconstraints, defining what they call strong stability and weak stability. They show strong
stability suffers from a non-existence problem whenever constraints are “non-trivial” while
weakly stable matchings exist for a wide range of constraints and are efficient. Stability
defined in the present paper is weaker than strong stability but stronger than weak stability. In contrast to strong and weak stability, the definition of stability in this paper
uses information about policy goals of regions in terms of how to allocate their limitedseats.9 Thus our stability is particularly appropriate when such information is available.
Instead of exploring many kinds of stability concepts, the present paper fixes one stability
concept (the stability defined in the present paper) and asks the implication of constraint
structures for the existence of desirable mechanisms.
The rest of this paper proceeds as follows. In Section 2, we present the model. Section
3 states the main result. Section 4 presents applications of the main result, and Section 5
provides a proof sketch. Section 6 concludes. Appendix provides the formal proof of theresult as well as a number of discussions.
2. ModelThis 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 eachregion. However, the model is applicable to various other situations in and out of theresidency matching context. For example, in medical residency applications, a region can
represent a geographical region, medical specialty, or a combination of them.10 Anotherexample is school choice, where a region can represent a socio-economic class of students.
We begin with preliminary definitions for two-sided matching in Section 2.1. Then
Section 2.2 introduces our model of matching with constraints.
2.1. Preliminary Definitions.
Let there be a finite set of doctors D and a finite set of hospitals H. Each doctor dhas a strict preference relation d over the set of hospitals and being unmatched (being
unmatched is denoted by ∅). For any h, h0 ∈ H ∪ {∅}, we write h d h0 if and only if
9This usage of such information will be expressed in the definition of “illegitimate” doctor-hospital

pairs.
10In real medical matching, a hospital may have multiple residency programs in it. These programs
may differ from one another in terms of emphasis on specialties, for example. In such a case, the term“a hospital” should be understood to mean a residency program.

6h d h0 or h = h0 . Each hospital h has a strict preference relation h over the set ofsubsets of doctors. For any D0 , D00 ⊆ D, we write D0 h D00 if and only if D0 h D00 or
D0 = D00 . We denote by = (i )i∈D∪H the preference profile of all doctors and hospitals.
Doctor d is said to be acceptable to hospital h if d h ∅.11 Similarly, h is acceptableto d if h d ∅. It will turn out that only rankings of acceptable partners matter for ouranalysis, so we often write only acceptable partners to denote preferences. For example,
d : h, h0means that hospital h is the most preferred, h0 is the second most preferred, and h andh0 are the only acceptable hospitals under preferences d of doctor d.
Each hospital h ∈ H is endowed with a (physical) capacity qh , which is a nonnegative
integer. We say that preference relation h is responsive with capacity qh (Roth,
1985) if
(1) For any D0 ⊆ D with |D0 | ≤ qh , d ∈ D \ D0 and d0 ∈ D0 , (D0 ∪ d) \ d0 h D0 if andonly if d h d0 ,(2) For any D0 ⊆ D with |D0 | ≤ qh and d0 ∈ D0 , D0 h D0 \ d0 if and only if d0 h ∅,and(3) ∅ h D0 for any D0 ⊆ D with |D0 | > qh .
In words, preference relation 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 unacceptable. We assume that preferences of each hospital h areresponsive with capacity qh throughout the paper.
A matching µ is a mapping that satisfies (i) µd ∈ H ∪ {∅} for all d ∈ D, (ii) µh ⊆ D
for all h ∈ H, and (iii) for any d ∈ D and h ∈ H, µd = h if and only if d ∈ µh . That is, amatching simply specifies which doctor is assigned to which hospital (if any).
A matching µ is individually rational if (i) for each d ∈ D, µd d ∅, and (ii) for
each h ∈ H, d h ∅ for all d ∈ µh , and |µh | ≤ qh . That is, no agent is matched with anunacceptable partner and each hospital’s capacity is respected.
Given matching µ, a pair (d, h) of a doctor and a hospital is called a blocking pair if
h d µd and either (i) |µh | < qh and d h ∅, or (ii) d h d0 for some d0 ∈ µh . In words,
a blocking pair is a pair of a doctor and a hospital who want to be matched with eachother (possibly rejecting their partners in the prescribed matching) rather than following
the proposed matching.
11We denote singleton set {x} by x when there is no confusion.

7(a) A non-hierarchical set of regions R.

(b) A hierarchical set of regions R0 .

Figure 1. An example of sets of regions in Example 1.
2.2. Model with Constraints.
Region Structure. A collection R ⊆ 2H \{∅} is called a set of regions. Assume {h} ∈ R
for all h ∈ H and H ∈ R.
A collection of regions S ⊂ R is called a partition of r ∈ R if S 6= {r},S

r0 ∈S r0= r,

and r1 ∩ r2 = ∅ for all r1 , r2 ∈ S with r1 6= r2 . A partition S of r is called a largest
partition of r if there exists no partition S 0 6= S of r such that r0 ∈ S implies r0 ⊆ r00
for some r00 ∈ S 0 . Note that, for a given region r, there can be more than one largest
partition of r. We denote by LP(r) the collection of largest partitions of r. For r ∈ R
and S ∈ LP(r), we refer to each element of S as a subregion of r with respect to S.
A set of regions R is a hierarchy if r, r0 ∈ R implies r ⊆ r0 or r0 ⊆ r or r ∩ r0 = ∅.
Below is an example of a set of regions.
Example 1. There are hospitals h1 , h2 , and h3 . The regions are
R = {H, r1 , r2 , {h1 }, {h2 }, {h3 }},where r1 = {h1 , h2 } and r2 = {h2 , h3 }. See Figure 1a for a graphical representation. In
this example, the largest partitions of H are S = {r1 , {h3 }} and S 0 = {{h1 }, r2 }. Regions
r1 and {h3 } are subregions of H with respect to S, and {h1 } and r2 are subregions of H
with respect to S 0 . R is not a hierarchy because r1 6⊆ r2 , r2 6⊆ r1 , and r1 ∩ r2 = {h2 } =6 ∅.
By contrast, R0 := R\{r2 } is a hierarchy (see Figure 1b for a graphical representation). 
Regional Preferences. When a given region is faced with applications by more doctors
than the regional cap, the region has to allocate limited seats among its subregions. We

8consider the situation in which regions have policy goals in terms of doctor allocations,and formalize such policy goals using the concept of “regional preferences.” For example,
a situation in which the government has a policy goal regarding doctor allocations acrossdifferent geographic regions can be captured by the regional preferences of the grand region
H. The regional preferences of a geographical region r whose subregions are all singleton
sets captures r’s policy goal in terms of doctor allocations across different hospitals in r.
For each r ∈ R that is not a singleton set and S ∈ LP(r), a regional preference for r,
denoted Dr,S , is a weak ordering over Wr,S := {w = (wr0 )r0 ∈S |wr0 ∈ Z+ for every r0 ∈ S}.
That is, Dr,S is a binary relation that is complete and transitive (but not necessarily
antisymmetric). We write w Br,S w0 if and only if w Dr,S w0 holds but w0 Dr,S w doesnot. Vectors such as w and w0 are interpreted to be supplies of acceptable doctors to
the subregions of region r, but they only specify how many acceptable doctors apply tohospitals in each subregion and no information is given as to who these doctors are. We
denote by D the profile (Dr,S )r∈R,S∈LP(r) .
Given Dr,S , a function
˜ r,S : Wr,S × Z+ → Wr,SCh
˜ r,S (w; t) ∈ arg maxD {w0 |w0 ≤ w, P 0 w0 0 ≤is an associated quasi choice rule if Ch
r ∈S rr,St} for any non-negative integer vector w = (wr0 )r0 ∈S and non-negative integer t.12 Intu˜ r,S (w, t) is a best vector of numbers of doctors allocated to subregions of r given
itively, Ch
a vector of numbers w under the constraint that the sum of the numbers of doctors cannot
exceed the quota t. Note that there may be more than one quasi choice rule associatedPwith a given weak ordering Dr,S because the set arg maxDr,S {w0 |w0 ≤ w, r0 ∈S wr0 0 ≤ t}
may not be a singleton for some w and t.
We assume that the regional preferences Dr,S satisfy w Br,S w0 if w0

w. This condition

formalizes the idea that region r prefers to fill as many positions in its subregions as
possible. This requirement implies that any associated quasi choice rule is acceptant in
˜ r,S (w; t)]r0 < wr0 ,the sense that, for each w and t, if there exists r0 ∈ S such that [ChP
˜ r,S (w; t)]r00 = t.13 This captures the idea that the social planner should notthen r00 ∈S [Chwaste 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 regionalcap should be binding.
12For any two vectors w = (w 0 ) 0r

for all r0 ∈ S. We write w

r ∈S and w

0= (wr0 0 )r0 ∈S , we write w ≤ w0 if and only if wr0 ≤ wr0 0

w0 if and only if w ≤ w0 and wr0 < wr0 0 for at least one r0 ∈ S. For any

0
0
0
0
Wr,S
⊆ Wr,S , arg maxDr,S Wr,S
is the set of vectors w ∈ Wr,Ssuch that w Dr,S w0 for all w0 ∈ Wr,S.
13This condition is a variant of properties used by Alkan (2001) and Kojima and Manea (2010) in thecontext of choice functions over matchings.

9

˜ r,S
We say that Dr,S is substitutable if there exists an associated quasi choice rule Ch
that satisfies
˜ r,S (w; t) ≥ Ch
˜ r,S (w0 ; t0 ) ∧ w.
w ≤ w0 and t ≥ t0 ⇒ Ch
Just as in the standard definition (e.g., Hatfield and Milgrom (2005)), our concept of
substitutability requires that weakly more doctors be rejected if more doctors apply toeach hospital. In addition, our substitutability requires that weakly more doctors be
accepted if the quota increases. We provide a detailed discussion of this concept in Appendix B. Throughout our analysis, we assume that Dr,S is substitutable for any r ∈ R
and S ∈ LP(r).
Stability. We assume that each region r ∈ R is endowed with a nonnegative integer κrcalled a regional cap.14 We denote by κ = (κr )r∈R the profile of regional caps acrossall regions in R. A matching is feasible if |µr | ≤ κr for all r ∈ R, where µr = ∪h∈r µh .
In other words, feasibility requires that the regional cap for every region is satisfied. For
R0 ⊆ R, we say that µ is Pareto superior to µ0 for R0 if (|µr0 |)r0 ∈S Dr,S (|µ0r0 |)r0 ∈S forall (r, S) where r ∈ R0 and S ∈ LP(r), with at least one of the relations holding strictly.
Given a matching µ, denote by µd→h the matching such that µdd→h= µd0 for all d0 ∈ D\{d}0and µd→h= h.
dGiven these concepts, let us now introduce two key notions to define stability. First,
we say that a pair (d, h) is infeasible at µ if µd→h is not feasible. Second, we say that apair (d, h) is illegitimate at µ if there exists r ∈ R with |µr | = κr such that µd→h is not
Pareto superior to µ for {r0 ∈ R | µd , h ∈ r0 and r0 ⊆ r}.
Definition 1. A matching µ is stable if it is feasible, individually rational, and if (d, h)
is a blocking pair then d0 h d for all doctors d0 ∈ µh and (d, h) is either infeasible orillegitimate at µ.
The standard definition of stability without regional caps requires individual rationality
and the absence of blocking pairs. With regional caps, however, there are cases in which
every feasible and individually rational matching admits a blocking pair. For this reason,
we allow for the presence of some blocking pairs. To keep the spirit of stability, however,
we require only certain kinds of blocking pairs remain. Specifically, we demand that all
remaining blocking pairs be either infeasible or illegitimate. Below we provide justification
for the choice of these restrictions.
14Kamada and Kojima (2015a) use q

r to denote a regional cap, but here we use the notation κr to

reduce confusion with hospital capacities.

10

A pair of a doctor d and a hospital h is infeasible if moving d to h while keeping otherparts of the matching unchanged leads to a violation of a regional cap. To the extent
that regional caps encode what matchings are allowed in the given situation, a demand
by a blocking pair that would cause a violation of a regional cap does not have the same
normative support as in the case without regional caps. For this reason, our stability
concept allows for infeasible blocking pairs to remain.
A doctor-hospital pair is illegitimate if the movement of doctor d to h does not lead to a
Pareto superior distribution of doctors for a certain set of regions.We require any region r0
in this set satisfy two conditions. First, we require that r0 contains both hospitals µd (theoriginal hospital for d) and h, as this corresponds to the case in which r0 is in charge ofcontrolling distributions of doctors involving these hospitals. Second, the region r0 should
be currently “constrained.” That is, it is a subset of some region r whose regional cap isfull in the present matching: In such a case, the region r should ration the distributionof doctors among its subregions, each of which needs to ration the distribution among its
subregions, and so forth, which indirectly constrains the number of doctors that can bematched in r0 . The requirement that r0 is (indirectly) constrained limits the case in which
a blocking pair is declared illegitimate. This is in line with our motivation to keep the
spirit of stability, i.e., to allow for the presence of blocking pairs only in a conservative
manner.15
The implicit idea behind the definition is that the government or some authority caninterfere and prohibit a blocking pair from being executed if regional caps are an issue.
Thus, our preferred interpretation is that stability captures a normative notion that it isdesirable to implement a matching that respects participants’ preferences to the extent
possible. Justification of the normative appeal of stability has been established in the
recent matching literature, and Kamada and Kojima (2015a) offer further discussion on
this point, so we refer interested readers to that paper for details.
Remark 1. Kamada and Kojima (2016) define two other stability concepts, which theycall strong stability and weak stability. Strong stability is more demanding than stability,
requiring any blocking pairs lead to infeasibility. Weak stability is less demanding thanstability, allowing for some blocking pairs that are neither infeasible nor illegitimate.
Kamada and Kojima (2016) establish that a matching is strongly stable if and only if itis stable for all possible regional preference profiles, while a matching is weakly stable if
and only if there exists a regional preference profile under which it is stable.
15For the case of hierarchies, we provide an alternative interpretation of stability in Remark 5 in the

Appendix.

11

Remark 2. Kamada and Kojima (2016) show that any weakly stable matching is (constrained) efficient, i.e., there is no feasible matching µ0 such that µ0i i µi for all i ∈ D ∪ H
and µ0i i µi for some i ∈ D ∪ H.16 Because stability implies weak stability, a stablematching is efficient for any regional preferences, which provides one normative appeal of
our stability concept.
Remark 3. Kamada and Kojima (2016) demonstrate that (i) there does not necessarily
exist a strongly stable matching, and (ii) if a mechanism produces a strongly stablematching whenever there exists one, then it is not strategy-proof for doctors. Given thesenegative findings, the present paper focuses on stability as defined in Definition 1.
Remark 4. Practically, moving a doctor from one hospital to another involves administrative tasks on the part of relevant regions (we give examples of possible organizations
dealing with such administration in Section 4), hence disallowing only those blocking pairsthat Pareto-improve the relevant regions is, in our view, the most plausible notion in ourenvironment. An alternative notion of illegitimacy may be that a doctor-hospital pair issaid to be illegitimate if moving doctor d to h leads to a Pareto inferior distribution of
doctors for the set of regions that we consider here. This notion not only is inconsistent
with our view just described, but also leads to nonexistence.17

Mechanism. Recall that κ denotes the profile of regional caps, and D denotes the profile
of regional preferences. A mechanism ϕ is a function that maps preference profiles tomatchings for a given profile (κ, D). The matching under ϕ at preference profile  isdenoted ϕκ,D (), and agent i’s match is denoted by ϕκ,Di () for each i ∈ D ∪ H.
A mechanism ϕ is said to be stable if, for each (κ, D) and a preference profile , thematching ϕκ,D () is stable.
A mechanism ϕ is said to be strategy-proof for doctors if there do not exist (κ, D),a preference profile , a doctor d ∈ D, and preferences 0d of doctor d such that
κ,D
0
ϕκ,D
d (d , −d ) d ϕd ().
16Since regional caps are a primitive of the environment, we consider a constrained efficiency concept.
17To see this, consider a two-doctor two-hospital example with one region with cap 1, where doctori ∈ {1, 2} likes hospital i best and hospital j 6= i second, and hospital i likes doctor j 6= i best and doctor
i second. If the region containing hospitals 1 and 2 are indifferent between allocations (1, 0) and (0, 1),
then there exists no matching that satisfies the strengthened version of stability. A similar logic is used
to show there exists no strongly stable matching in Kamada and Kojima (2016).

12

That is, no doctor has an incentive to misreport her preferences under the mechanism.18
3. Characterization Theorem
Theorem 1. Fix D with |D| ≥ 2, H, and a set of regions R. The following statements
are equivalent.
(1) R is a hierarchy.
(2) There exists a mechanism that is stable and strategy-proof for doctors.
The proof of Theorem 1 is involved, and the proof approach is of independent interest.
Thus, we illustrate a proof sketch in the next section, while relegating the formal proof
to Appendices C and D.
The theorem identifies the conditions on the markets for which we can find a mechanism that is stable and strategy-proof for doctors. Since our proof for the assertion thatstatement (1) implies statement (2) is constructive, for those markets in which constraints
are a hierarchy, the theorem tells us that we can directly use the mechanism we construct.
Also, for those markets in which constraints do not form a hierarchy, the theorem showsthat there is no hope of adopting a mechanism that is stable and strategy-proof for doctors. To understand these points in concrete examples, the next section considers practicalapplications.
4. Applications
This section discusses various applications of Theorem 1. The main goal of this section
is to illustrate the implications of Theorem 1 about what types of environments andconstraints in practice allow for a desirable mechanism.
4.1. Geographical constraints in medical match. Consider the medical matchingmarket in Japan. In order to keep geographical imbalance of doctors in check, the Japanese
government imposes caps on the numbers of doctors in different prefectures that partition
the country. Kamada and Kojima (2015a) propose a mechanism that produces a stablematching and is strategy-proof for doctors. Since partitions are a special case of hierarchy,
their result can be derived as a corollary of Theorem 1.19
In addition, it may be of interest to consider multiple layers of geographical regions. In
our private communication with Japanese government officials, they expressed concerns
18Roth (1982) shows that there is no mechanism that produces a stable matching for all possible

preference profiles and is strategy-proof for both doctors and hospitals even in a market without regional
caps.
19See Kamada and Kojima (2015b) for details.

13about imbalance of doctors not only across prefectures but also within each prefecture.
Theorem 1 provides solutions to this concern by considering hierarchical constraints withineach prefecture. For example, according to the Medical Care Act of Japan, each prefecture
is divided into smaller geographic units called Iryo-ken (medical areas) on which various
health care policies are implemented.20 This is a case of a hierarchy, and hence Theorem
1 implies that a desirable mechanism exists.
4.2. Geographical and speciality constraints in medical match. Consider medical
match with prefecture-level constraints as in the last subsection, but suppose that the
government also desires to impose caps on medical specialities. In the Japanese context,
this concern is clearly exemplified by a proposal made to the governmental committee
meeting, which is titled “Measures to Address Regional Imbalance and Specialty Imbalance of Doctors” (Ministry of Health, Labour and Welfare, 2008).21 Suppose for now thatthe government decides to impose nationwide caps on each specialty. In this situation, ahospital program may be in the “obstetrics” region at the same time as in “Tokyo” region,
where neither of the two is a subset of the other. Theorem 1 implies that there exists
no mechanism that is stable and strategy-proofness for doctors in this environment. Thissuggests that the policy maker should either give up one of these desiderata, or rethink
which institution/committee to give authority to claim a certain number of doctors anddeclare their regional preferences. For instance, the policy maker may decide not to give
authority to claim caps and preferences to nationwide organizations such as Japan Societyof Obstetrics and Gynecology, but to give it to each of the regional ones such as Tokyo
Association of Obstetricians & Gynecologists.22 To the extent that doctors treat patientsin person, imposing specialty constraints in each region rather than nationally may bereasonable. Constraints form a hierarchy in such a situation, so Theorem 1 implies that
there exists a mechanism with our desired properties.
4.3. Field and financial constraints in college admission. In Hungarian college
admission, there are upper-bound constraints on the number of students in terms of
20Article 30-4 of the Medical Care Act of Japan.
21In 2008, Japan took a measure that intended to address (only) regional imbalance, but even in 2007,

the sense of crisis about specialty imbalance is shared by the private sector as well: In a sensationallyentitled article, “Obstetricians Are in Short Supply! Footsteps of Obstetrics Breakdown,” NTT Com
Research (2007) reports that many obstetrics hospitals have been closed even in urban areas such as
Tokyo.
22See

http://www.jsog.or.jp

for

Japan

Societyof

Obstetrics

and

http://www.taog.gr.jp for Tokyo Association of Obstetricians & Gynecologists.

Gynecology

and

14

different fields of study as well as whether the study is subsidized by the government.
In this problem, the constraints formed a hierarchy until 2007, but then the constraints
were modified such that they do not form a hierarchy any more (Biró, Fleiner, Irving,and Manlove, 2010). Thus, Theorem 1 implies that our mechanism achieves stability andstrategy-proofness for students in the old environment, but no mechanism can achievethese properties after the change.
4.4. Diversity constraints in school choice. Consider the design of school choicemechanisms (Abdulkadiroğlu and Sönmez, 2003). Maintaining diversity is a major concern
in school choice, and many school districts have used policies to achieve this goal, e.g.
New York City (NY), Chicago (IL), Seattle (WA), Jefferson County (KY), Louisville(KY), Minneapolis (MN), and White Plains (NY) (Abdulkadiroğlu, Pathak, and Roth,
2005; Hafalir, Yenmez, and Yildirim, 2013; Dur, Pathak, and Sönmez, 2016).
Suppose first that the school district wants to maintain certain balance of student bodyat each school in terms of socio-economic class such as race.23 Theorem 1 implies that astable and strategy-proof mechanism exists in this case as different socio-economic classes
form a partition, a special case of hierarchy. However, the constraints do not form ahierarchy if, for example, the policy of the school district is to maintain balance in termsof both socio-economic class and gender. Therefore, Theorem 1 implies that a desirable
mechanism does not exist in this case.
5. Proof Sketch of Theorem 1
The proof of Theorem 1 is involved. Thus, we illustrate a sketch of the proof in thissection, while presenting the formal proof in Appendix C. We illustrate the basic ideas
for the case of hierarchy first and then explain the remaining case.
5.1. Hierarchy. For the case of hierarchies, our proof strategy is to connect our matchingmodel 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 the “hospitalside” instead of doctors and hospitals; In the associated model, we regard the hospital side
as a hypothetical consortium of all hospitals that acts as one agent. By imagining thatthe hospital side (hospital consortium) makes a coordinated employment decision, we canaccount for the fact that acceptance of a doctor by a hospital in one region may depend
23Affirmative action based on race has been declared illegal in, for instance, Parents Involved inCommunity Schools v. Seattle School District No. 1. Currently, many school districts use other criteriasuch as income or neighborhood of the family.

15

on doctor applications to other hospitals in the same region, an inevitable feature inmarkets under distributional constraints. This association necessitates, however, that we
distinguish a doctor’s placements in different hospitals. We account for this complication
by defining the hospital side’s choice function over contracts rather than doctors, wherea contract specifies a doctor-hospital pair to be matched. We construct such a choicefunction by using two pieces of information: the preferences of all the hospitals andregional 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 other words, regional preferences trade off multiple
hospitals’ desires to accept more doctors, when accepting more is in conflict with theregional cap. With the help of this association, we demonstrate that any stable allocationin the associated model with contracts induces a stable matching in the original modelwith distributional constraints (Proposition 2).
In order to use this association, we show that the key conditions in the associatedmodel—the substitutes condition and the law of aggregate demand—are satisfied (Proposition 1).24 This enables us to invoke existing results for matching with contracts, namelythat 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).
The full proof in the Appendix formalizes this idea. In particular, we introduce a newalgorithm in the original matching model with constraints, called the flexible deferred
acceptance algorithm. That algorithm is a generalization of the deferred acceptance algorithm, in which the acceptance by hospitals in each step is made in a coordinated way thatis consistent with the regional constraints. We establish that, with the hierarchical region
structure, the outcome of the cumulative offer process in the associated model corresponds
to the matching produced by the flexible deferred acceptance algorithm in the originalmodel (Remark 6). This correspondence establishes that the flexible deferred acceptancealgorithm finds a stable matching in the original problem and this algorithm is (group)
strategy-proof for doctors, proving the statement for the hierarchy case in Theorem 1.
For illustration, our proof approach is represented as a chart in Figure 2.
5.2. Non-Hierarchy. To illustrate the proof for this part, we present an example ofnon-hierarchy and show that, in that example, there is no mechanism that is stable and24Substitutability of regional preferences plays a crucial role in the proof of Proposition 1, and we

regard it as reasonable in our applications. Substitutability is commonly assumed in various domains in
the matching literature.

16

Matching under Constraint(the original problem)

Matching with Contracts(the associated problem)

Matching between doctors and hospitals

Matching between doctors and the “hospital side,” H

Regional preferences are subs:tutable
Theorem 1: (1) !(2)We use green andblue arrows to prove
this.

H’s choice func:on sa:sﬁes• the subs:tutes condi:on
Proposi:on 1 • the law of aggregate demand

ϕ is a ﬂexible deferred
acceptance mechanism

ϕ is a cumula:ve oﬀer process
Remark 4

ϕ produces a stable alloca:on

ϕ produces a stable matching
Proposi:on 2

ϕ is (group) strategy-proof
for doctors

ϕ is (group) strategy-proof
for doctors

HaKield and Milgrom (2005)
HaKield and Kojima (2009)
HaKield and Kominers (2010)

Figure 2. Proof sketch for (1) ⇒ (2) of Theorem 1.
strategy-proof for doctors. The general case is somewhat more involved, but the mainidea can be seen in this example.
Consider the problem described in Example 1: In that example, there are 3 hospitals,
h1 , h2 , and h3 . The regions are R = {H, r1 , r2 , {h1 }, {h2 }, {h3 }}, where r1 = {h1 , h2 } andr2 = {h2 , h3 }. Recall Figure 1a for a graphical representation. Note that h1 ∈ r1 \ r2 ,h2 ∈ r1 ∩ r2 , and h3 ∈ r2 \ r1 , so R is not a hierarchy. We will show that there does notexist a mechanism that is stable and strategy-proof for doctors.
Clearly, S1 := {{h1 }, {h2 }} is the unique largest partition of r1 . Similarly, S2 :={{h2 }, {h3 }} is the unique largest partition of r2 . Suppose that, under Br1 ,S1 , region
r1 prefers a vector such that the coordinate corresponding to {h1 } is 1 and the othercoordinate is 0 to a vector such that the coordinate corresponding to {h2 } is 1 and theother coordinate is 0. Also suppose that, under Br2 ,S2 , region r2 prefers a vector such that17

the coordinate corresponding to {h2 } is 1 and the other coordinate is 0 to a vector suchthat the coordinate corresponding to {h3 } is 1 and the other coordinate is 0. Finally, letκr1 = κr2 = 1 and, for each r̃ ∈ R \ {r1 , r2 }, κr̃ is sufficiently large so that it never binds.25
Suppose that there are two doctors, d1 and d2 . Finally, assume that preferences ofdoctors and hospitals are as follows:d1 : h3 ,

d2 : h2 , h1 ,

h1 : d2 , d1 ,

h2 : d1 , d2 ,

h3 : d2 , d1 ,and the capacity of each hospital is sufficiently large so that it never binds.26
By inspection, it is straightforward to see that the following two are the only stablematchings given the above preferences:µ=h1 h2 h3

∅

∅

d1

d2

∅

!
,

µ0 =

h1 h2 h3
d2

∅

d1

!
.

We consider two cases.
Case 1: Suppose that a mechanism produces µ given the above preference profile. Consider
d1 ’s preferences
0d1 : h1 , h2 , h3 .
Under the preference profile (0d1 , d2 , h1 h2 , h3 ) it is straightforward to check that µ0
is a unique stable matching. Note that d1 is matched to h3 under this new preference
profile, which is strictly better under d1 than d1 ’s match ∅ under the original preference
profile (d1 , d2 , h1 h2 , h3 ). This implies that if a mechanism is stable and produces µ
given preference profile (d1 , d2 , h1 h2 , h3 ), then it is not strategy-proof for doctors.
Case 2: Suppose that a mechanism produces µ0 given the above preference profile. Consider d2 ’s preferences
0d2 : h2 , h3 , h1 .
Under the preference profile (d1 , 0d2 , h1 h2 , h3 ) it is straightforward to check that µ
is a unique stable matching. Note that d2 is matched to h2 under this new preference
profile, which is strictly better under d2 than d2 ’s match h1 under the original preference
profile (d1 , d2 , h1 h2 , h3 ). This implies that if a mechanism is stable and produces µ0
given preference profile (d1 , d2 , h1 h2 , h3 ), then it is not strategy-proof for doctors.
25For example, let κr̃ = 3 for each r̃ ∈ R \ {r1 , r2 }.

26For instance, let q

h1 = qh2 = qh3 = 3.

18

6. Conclusion
This paper presented a model of matching under distributional constraints. We identified the necessary and sufficient condition on the constraint structure for the existenceof a mechanism that is stable and strategy-proof for the individuals. The necessary andsufficient condition is that the constraints form a hierarchy.
The fact that our condition is both sufficient and necessary gives us a clear guide to
future research. First, our sufficiency result implies that, in applications with hierarchicalconstraints, one can utilize our theory to design a desirable mechanism. We hope that
this result will stimulate future works on specific applications. Second, our necessity
result suggests that, if the constraints do not form a hierarchy, one needs to weaken either
strategy-proofness for doctors or the stability concept as desiderata for a mechanism to
be designed.27 Then, the critical questions will be how such weakening should be done,
and what mechanism satisfies the weakened criteria.
Finally, it is worth noting the connection between matching with constraints and matching with contracts that we used in proving the sufficiency result. This technique was subsequently adopted by other studies such as Goto, Iwasaki, Kawasaki, Yasuda, and Yokoo(2014), Goto, Hashimoto, Iwasaki, Kawasaki, Ueda, Yasuda, and Yokoo (2014), and Kojima, Tamura, and Yokoo (2015). We envision that this approach may prove useful fortackling complex matching problems one may encounter in the future.
References
Abdulkadiroğlu, A. (2005): “College admissions with affirmative action,” International Journal of Game Theory, 33(4), 535–549.
Abdulkadiroğlu, A., P. A. Pathak, and A. E. Roth (2005): “The New York
City High School Match,” American Economic Review, Papers and Proceedings, 95,
364–367.
Abdulkadiroğlu, A., and T. Sönmez (2003): “School Choice: A Mechanism Design
Approach,” American Economic Review, 93, 729–747.
Abraham, D. J., R. Irving, and D. Manlove (2007): “Two algorithms for the
student-project allocation problem,” Journal of Discrete Algorithms, 5, 73–90.
27In addition to the applications studied in Section 4, the case with floor constraints is worth men-tioning. If we translate those constraints to ceiling constraints like ours, the resulting problem does not
generally admit a hierarchy. Contributions in the literature studying floor constraints seek different solutions from ours. Fragiadakis and Troyan (2015), for instance, find a mechanism that is strategy-proof
for students and has desirable efficiency properties. We plan to further study floor constraints in future
work.

19

Alkan, A. (2001): “On preferences over subsets and the lattice structure of stablematchings,” Review of Economic Design, 6(1), 99–111.
(2002): “A class of multipartner matching markets with a strong lattice structure,” Economic Theory, 19(4), 737–746.
Alkan, A., and D. Gale (2003): “Stable Schedule Matching Under Revealed Preferences,” Journal of Economic Theory, 84, 73–94.
Aygün, O., and T. Sönmez (2012): “Matching with Contracts: The Critical Role of
Irrelevance of Rejected Contracts,” Discussion paper, Boston College Department of
Economics.
Biró, P., T. Fleiner, R. W. Irving, and D. F. Manlove (2010): “The College
Admissions problem with lower and common quotas,” Theoretical Computer Science,
411, 3136–3153.
Blair, C. (1988): “The lattice structure of the set of stable matchings with multiple
partners,” Mathematics of operations research, 13(4), 619–628.
Budish, E., Y.-K. Che, F. Kojima, and P. R. Milgrom (2013): “Designing Random Allocation Mechanisms: Theory and Applications,” American Economic Review,103(2), 585–623.
Crawford, V., and E. M. Knoer (1981): “Job Matching with Heterogeneous Firms
and Workers,” Econometrica, 49, 437–450.
Dur, U., P. A. Pathak, and T. Sönmez (2016): “Explicit vs. Statistical Preferential
Treatment in Affirmative Action: Theory and Evidence from Chicago’s Exam Schools,”
Discussion paper, National Bureau of Economic Research.
Echenique, F., and B. Yenmez (2015): “How to control controlled school choice,”
American Economic Review, 105(8), 2679–2694.
Ehlers, L., I. E. Hafalir, M. B. Yenmez, and M. A. Yildirim (2014): “School
choice with controlled choice constraints: Hard bounds versus soft bounds,” Journal of
Economic Theory.
Ergin, H., and T. Sönmez (2006): “Games of School Choice under the Boston Mechanism,” Journal of Public Economics, 90, 215–237.
Fleiner, T. (2003): “A Fixed-Point Approach to Stable Matchings and Some Applications,” Mathematics of Operations Research, 28, 103–126.
Fragiadakis, D., and P. Troyan (2015): “Improving Matching under Hard Distributional Constraints,” mimeo.
Gale, D., and L. S. Shapley (1962): “College Admissions and the Stability of Marriage,” American Mathematical Monthly, 69, 9–15.

20

Goto, M., N. Hashimoto, A. Iwasaki, Y. Kawasaki, S. Ueda, Y. Yasuda,and M. Yokoo (2014): “Strategy-proof matching with regional minimum quotas,”

AAMAS2014.
Goto, M., A. Iwasaki, Y. Kawasaki, Y. Yasuda, and M. Yokoo (2014): “Improving Fairness and Efficiency in Matching Markets with Regional Caps: Prioritylist based Deferred Acceptance Mechanism,” mimeo (the latest version is available at
http://mpra.ub.uni-muenchen.de/53409/).
Hafalir, I. E., M. B. Yenmez, and M. A. Yildirim (2013): “Effective affirmative
action in school choice,” Theoretical Economics, 8(2), 325–363.
Hatfield, J. W., and F. Kojima (2009): “Group Incentive Compatibility for Matchingwith Contracts,” Games and Economic Behavior, pp. 745–749.
(2010): “Substitutes and Stability for Matching with Contracts,” Journal of
Economic Theory, pp. 1704–1723.
Hatfield, J. W., and S. D. Kominers (2009): “Contract Design and Stability in
Matching Markets,” mimeo.
(2012): “Matching in Networks with Bilateral Contracts,” American Economic
Journal: Microeconomics, 4(1), 176–208.
(2013): “Hidden Substitutes,” Discussion paper, Working paper, Harvard Univ.
Hatfield, J. W., S. D. Kominers, A. Nichifor, M. Ostrovsky, and A. Westkamp (2013): “Stability and Competitive Equilibrium in Trading Networks,” Journalof Political Economy, 121, 966–1005.
Hatfield, J. W., S. D. Kominers, and A. Westkamp (2015): “Stability, StrategyProofness, and Cumulative Offer Mechanisms,” Discussion paper, mimeo.
Hatfield, J. W., and P. Milgrom (2005): “Matching with Contracts,” American
Economic Review, 95, 913–935.
Hirata, D., and Y. Kasuya (2015): “On stable and strategy-proof rules in matchingmarkets with contracts,” Available at SSRN 2654639.
Kamada, Y., and F. Kojima (2015a): “Efficient Matching under Distributional Constraints: Theory and Applications,” American Economic Review, 105(1), 67–99.
(2015b): “General Theory of Matching under Distributional Constraints,”
mimeo.
(2016): “Stability Concepts in Matching with Distributional Constraints,”
mimeo.
Kelso, A., and V. Crawford (1982): “Job Matching, Coalition Formation, and Gross
Substitutes,” Econometrica, 50, 1483–1504.

21

Kojima, F., and M. Manea (2010): “Axioms for Deferred Acceptance,” Econometrica,
78(2), 633–653.
Kojima, F., A. Tamura, and M. Yokoo (2015): “Designing Matching Mechanisms
under Constraints: An Approach from Discrete Convex Analysis,” mimeo.
Kominers, S., and T. Sönmez (2012): “Matching with Slot-Specific Priorities: Theory,” forthcoming, Theoretical Economics.
Milgrom, P. (2009): “Assignment messages and exchanges,” American Economic Journal: Microeconomics, 1(2), 95–113.
Ministry of Health,Labour and Welfare (2008):“Measures to Ad-

dress Regional Imbalance and Specialty Imbalance of Doctors (in Japanese),”http://www.mhlw.go.jp/shingi/2008/08/dl/s0823-3e.pdf.
NTT Com Research (2007): “Obstetricians Are in Short Supply! Footsteps of Obstetrics Breakdown,” http://research.nttcoms.com/database/data/000687/.
Roth, A. E. (1982): “The Economics of Matching: Stability and Incentives,” Mathematics of Operations Research, 7, 617–628.
(1985): “The College Admission Problem is not Equivalent to the Marriage
Problem,” Journal of Economic Theory, 36, 277–288.
(1991): “A Natural Experiment in the Organization of Entry Level Labor Markets: Regional Markets for New Physicians and Surgeons in the U.K.,” American Economic Review, 81, 415–440.
Roth, A. E., and M. A. O. Sotomayor (1990): Two-sided Matching: a Study inGame-theoretic Modeling and Analysis. Econometric Society monographs, Cambridge.
Sönmez, T. (2013): “Bidding for army career specialties: Improving the ROTC branching mechanism,” Journal of Political Economy, 121(1), 186–219.
Sönmez, T., and T. B. Switzer (2013): “Matching With (Branch-of-Choice) Contracts
at the United States Military Academy,” Econometrica, 81(2), 451–488.
Westkamp, A. (2013): “An Analysis of the German University Admissions System,”Economic Theory, 53(3), 561–589.

22

APPENDIX
Appendix A defines the flexible deferred acceptance mechanism under the assumptionthat the set of regions forms a hierarchy. Appendix B establishes several properties ofsubstitutability that prove useful in subsequent analysis. The proof of Theorem 1 isprovided in Appendix C ((1) ⇒ (2)) and Appendix D ((2) ⇒ (1)). Appendix E provides
additional discussions.
Appendix A. Flexible Deferred Acceptance Mechanism
Throughout this section, suppose that R is a hierarchy. It is straightforward to see
that, for any non-singleton region r ∈ R, LP(r) is a singleton set. Given this fact, denoteby S(r) the unique element of LP(r), and call each element of S(r) a subregion of r.
˜ r for Ch
˜ r,S(r) . We say that r ∈ R is a
We use simplified notation Dr for Dr,S(r) and Ch
smallest common region of hospitals h and h0 if h, h0 ∈ r, and there is no r0 ∈ R withr0 ( r such that h, h0 ∈ r0 . For any h and h0 , it is straightforward to see that a smallest
common region of h and h0 exists and is unique. Given this fact, denote the smallest
common region of h and h0 by SC(h, h0 ).
We say that region r is of depth k if |{r0 ∈ R|r ⊆ r0 }| = k. Note that the depth of a“smaller” region is larger. The standard model without regional caps can be interpreted
as a model with regions of depths less than or equal to 2 (H and singleton sets), and themodel of Kamada and Kojima (2015a) has regions of depths less than or equal to 3 (H,“regions,” and singleton sets), both with κH sufficiently large.
˜ Let
We proceed to define a quasi choice rule for the “hospital side,” denoted Ch:w= min{wh , qh , κ{h} } and, for each nonκ̃H = κH . Given w = (wh )h∈H , we define v{h}Psingleton region r, inductively define vrw = min{ r0 ∈S(r) vrw0 , κr }. Intuitively, vrw is the

maximum number that the input w can allocate to its subregions given the feasibility
constraints that w and regional caps of subregions of r impose. Note that vrw is weakly
0

increasing in w, that is, w ≥ w0 implies vrw ≥ vrw .
˜
We inductively define Ch(w)following a procedure starting from Step 1, where Step k
for general k is as follows:˜
Step k: If all the regions of depth k are singletons, then let Ch(w)= (κ̃w{h} )h∈Hand stop the procedure. For each non-singleton region r of depth k, set κ̃wr0 =˜ r ((v w00 )r00 ∈S(r) ; κ̃w )]r0 for each subregion r0 of r. Go to Step k + 1.
[Ch
r

r

˜
That is, under Ch(w),doctors are allocated to subregions of H, and then the doctors
allocated to region r are further allocated to subregions of r, and so forth until thebottom of the hierarchy is reached. In doing so, the capacity constraint of each hospital

23

and the feasibility constraint are taken into account. For example, if the capacity is 5 at
hospital h, then no more than five doctors at h are allocated to the regions containing h.
Assume that Dr is substitutable for every region r. Now we are ready to define theflexible deferred acceptance algorithm:
˜ r for which the conditions for
For each region r, fix an associated quasi choice rule Ch
substitutability are satisfied (note that the assumption that Dr is substitutable assuresthe existence of such a quasi choice rule.)(1) Begin with an empty matching, that is, a matching µ such that µd = ∅ for alld ∈ 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 h̄ at d among the hospitals that have
not rejected d so far. If d is unacceptable to h̄, then reject this doctor and go backto Step 2. Otherwise, define vector w = (wh )h∈H by(a) wh̄ is the number of doctors currently held at h̄ plus one, and(b) wh is the number of doctors currently held at h if h 6= h̄.
(4) Each hospital h ∈ H considers the new applicant d (if h = h̄) and doctors who
˜
are temporarily held from the previous step together. It holds its [Ch(w)]h mostpreferred applicants among them temporarily and rejects the rest (so doctors heldat this step may be rejected in later steps). Go back to Step 2.
We define the flexible deferred acceptance mechanism to be a mechanism that
produces, for each input, the matching given at the termination of the above algorithm.28
This algorithm is a generalization of the deferred acceptance algorithm of Gale andShapley (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 ofdoctors (tentatively) matched in each region r at κr . This results in rationing of doctors
across hospitals in the region, and the rationing rule is governed by regional preferences
Dr . Clearly, this mechanism coincides with the standard deferred acceptance algorithm
if all the regional caps are large enough and hence non-binding.

28Note that this algorithm terminates in a finite number of steps because each doctor makes anapplication to a particular hospital at most once. In Appendix C we will show that the outcome of thealgorithm is independent of the order in which doctors make their applications during the algorithm.

24

Appendix B. Remarks on Substitutability
The substitutability condition plays an important role in our proofs. This section
presents three remarks on substitutability.
First, the condition in the definition of substitutability can be decomposed into twoparts, as follows:(B.1)

˜ r,S (w; t) ≥ Ch
˜ r,S (w0 ; t) ∧ w, andw ≤ w0 ⇒ Ch

(B.2)

˜ r,S (w; t) ≥ Ch
˜ r,S (w; t0 ).
t ≥ t0 ⇒ Ch

Condition (B.1) imposes a condition on the quasi choice rule for different vectors w and w0
with a fixed parameter t while Condition (B.2) places restrictions for different parameterst and t0 with a fixed vector w. The former condition requires that, given cap t, 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. This condition is similar to the standard substitutability condition except that itdeals with multiunit supplies (that is, coefficients in w can take integers different from 0 or
1).29 The latter condition may appear less familiar, and it requires that the choice increase(in the standard vector sense) if the allocated quota is increased. Conditions (B.1) and(B.2) are independent of each other. One might suspect that these conditions are related
to responsiveness of preferences, but these conditions do not imply responsiveness. In
Appendix E.2 we provide examples to distinguish these conditions.
Second, Condition (B.1) is equivalent to(B.3)

˜ r,S (w; t)]r0 ≥ min{[Ch˜ r,S (w0 ; t)]r0 , wr0 } for every r0 ∈ S.
w ≤ w0 ⇒ [ChThis 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 (B.3) is equivalent to(B.4)

˜ r,S (w; t)]r0 < [Ch
˜ r,S (w0 ; t)]r0 ⇒ [Ch
˜ r,S (w, t)]r0 = wr0 .
w ≤ w0 and [Ch

˜ r,S (w; t)]r0 <To see that condition (B.3) implies condition (B.4), suppose that w ≤ w0 and [Ch
˜ r,S (w0 ; t)]r0 . These assumptions and condition (B.3) imply [Ch˜ r,S (w; t)]r0 ≥ wr0 . Since[Ch
29Condition (B.1) is analogous to persistence by Alkan and Gale (2003), who define the condition on a

choice function in a slightly different context. While our condition is similar to substitutability as definedin standard matching models (see Chapter 6 of Roth and Sotomayor (1990) for instance), there are twodifferences: (i) it is now defined on a region as opposed to a hospital, and (ii) it is defined over vectorsthat only specify how many doctors apply to hospitals in the region, and it does not distinguish different
doctors.

25

˜ r,S (w; t)]r0 ≤ wr0 holds by the definition of Ch
˜ r,S , this implies [Ch
˜ r,S (w; t)]r0 = wr0 . To[Ch
˜ r,S (w; t)]r0 ≥see that condition (B.4) implies condition (B.3), suppose that w ≤ w0 . If [Ch
˜ r,S (w0 ; t)]r0 , the conclusion of (B.3) is trivially satisfied. If [Ch
˜ r,S (w; t)]r0 < [Ch
˜ r,S (w0 ; t)]r0 ,[Ch
˜ r,S (w; t, )]r0 = wr0 , thus the conclusion of (B.3) is satisfied.
then condition (B.4) implies [ChFinally, in the proof of Theorem 1, (1) ⇒ (2), we use the fact that substitutability
˜ r,S isimplies the following natural property called “consistency”: A quasi choice rule Ch
˜ r,S (w; t) ≤ w0 ≤ w ⇒ Ch
˜ r,S (w0 ; t) = Ch
˜ r,S (w; t).30
said to be consistent if for any t, Ch
˜ r,S (w; t) is chosen at w and the supply decreases to w0 ≤ w
Consistency requires that, if Ch
˜ r,S (w; t) is still available under w0 , then the same choice Ch
˜ r,S (w; t) should be
but Chmade under w0 as well. Note that there may be more than one consistent quasi choicerule associated with a given weak ordering Dr,S because the set arg maxDr,S {w0 |w0 ≤P
w, r0 ∈S wr0 0 ≤ t} may not be a singleton for some Dr,S , w, and t. Note also that there
always exists a consistent quasi choice rule associated with a given weak ordering Dr,S .31
Claim 1. Condition (B.1) implies consistency.32
˜ r,S , and suppose that for some
Proof. Fix Dr,S and its associated quasi choice rule Ch
˜ r,S (w0 ; t) ≤ w ≤ w0 . Suppose also that condition (B.1) holds. We will provet, Ch
˜ r,S (w; t) = Ch
˜ r,S (w0 ; t). Condition (B.1) implies w ≤ w0 ⇒ Ch
˜ r,S (w; t) ≥ Ch
˜ r,S (w0 ; t) ∧Ch
˜ r,S (w0 ; t) ≤ w implies Ch
˜ r,S (w0 ; t) ∧ w = Ch
˜ r,S (w0 ; t), this means thatw. Since Ch
˜ r,S (w0 ; t) ≤ Ch
˜ r,S (w; t) ≤ w0 . If Ch
˜ r,S (w; t) 6= Ch
˜ r,S (w0 ; t) then by the assumptionCh˜ r,S is acceptant, we must have Ch
˜ r,S (w; t) Br,S Ch
˜ r,S (w0 ; t). But then Ch
˜ r,S (w0 ; t)that ChP
˜ r,S (w; t) ∈cannot be an element of arg maxDr,S {w00 |w00 ≤ w0 , r0 ∈S wr000 ≤ t} because ChP
˜ r,S (w0 ; t) = Ch
˜ r,S (w; t).
w000 ≤ t}. Hence we have Ch{w00 |w00 ≤ w0 ,
0
r ∈S

r

Appendix C. Proof of Theorem 1, (1) ⇒ (2)With the definition of the flexible deferred acceptance mechanism, we are now ready topresent the following statement.
30More precisely, it is Condition (B.1) of substitutability that implies consistency.
31To see this point consider preferences D0

0
0
0
0
0
0
r,S such that wBr,S w if wBr,S w and w = w if wDr,S w andP
w0 D0r,S w. The quasi choice rule that chooses (the unique element of) arg maxD0r,S {w0 |w0 ≤ w, r0 ∈S wr0 0 ≤t} for each w is clearly consistent.
32
Fleiner (2003) and Aygün and Sönmez (2012) prove analogous results although they do not work on
substitutability defined over the space of integer vectors. Conditions that are analogous to our consistency
concept are used by Blair (1988), Alkan (2002), and Alkan and Gale (2003) in different contexts.

26

Suppose that R is a hierarchy and Dr is substitutable for every r ∈ R. Thenthe flexible deferred acceptance mechanism produces a stable matching for
any input and is group strategy-proof for doctors.
This statement suffices to show Theorem 1, (1) ⇒ (2). Therefore, the remainder of thissection establishes the above statement.
It is useful to relate our model to a (many-to-many) matching model with contracts(Hatfield and Milgrom, 2005). Let there be two types of agents, doctors in D and the“hospital side” (thus there are |D| + 1 agents in total). Note that we regard the hospitalside, instead of each hospital, as an agent in this model. There is a set of contracts
X = D × H.
We assume that, for each doctor d, any set of contracts with cardinality two or moreis unacceptable, that is, a doctor can sign at most one contract. For each doctor d, herpreferences d over ({d} × H) ∪ {∅} are given as follows.33 We assume (d, h) d (d, h0 )in this model if and only if h d h0 in the original model, and (d, h) d ∅ in this model if
and only if h d ∅ in the original model.
For the hospital side, we assume that it has preferences and its associated choice rule
Ch(·) over all subsets of D × H. For any X 0 ⊂ D × H, let w(X 0 ) := (wh (X 0 ))h∈H be
the vector such that wh (X 0 ) = |{(d, h) ∈ X 0 |d h ∅}|. For each X 0 , the chosen set ofcontracts Ch(X 0 ) is defined by[n(d, h) ∈ X 0
Ch(X ) =0o0˜|{d ∈ D|(d , h) ∈ X , d h d}| ≤ [Ch(w(X ))]h .
0

0

0

0

h∈H
0
˜
That is, each hospital h ∈ H chooses its [Ch(w(X))]h most preferred contracts fromacceptable contracts in X 0 .
Definition 2 (Hatfield and Milgrom (2005)). Choice rule Ch(·) satisfies the substitutes
condition if there do not exist contracts x, x0 ∈ X and a set of contracts X 0 ⊆ X suchthat x0 ∈/ Ch(X 0 ∪ {x0 }) and x0 ∈ Ch(X 0 ∪ {x, x0 }).
In other words, contracts are substitutes if adding a contract to the choice set neverinduces a region to choose a contract it previously rejected. Hatfield and Milgrom (2005)
show that there exists a stable allocation (defined in Definition 4) when contracts aresubstitutes for the hospital side.
33We abuse notation and use the same notation model and in the associated model with contracts.

d for preferences of doctor d both in the original

27

Definition 3 (Hatfield and Milgrom (2005)). Choice rule Ch(·) satisfies the law of aggregate demand if for all X 0 ⊆ X 00 ⊆ X, |Ch(X 0 )| ≤ |Ch(X 00 )|.34
Proposition 1. Suppose that Dr is substitutable for all r ∈ R.
(1) Choice rule Ch(·) defined above satisfies the substitutes condition.35(2) Choice rule Ch(·) defined above satisfies the law of aggregate demand.
Proof. Part 1. Fix X 0 ⊂ X. Suppose to the contrary, i.e., that there exist X 0 , (d, h) and(d0 , h0 ) such that (d0 , h0 ) 6∈ Ch(X 0 ∪ {(d0 , h0 )}) and (d0 , h0 ) ∈ Ch(X 0 ∪ {(d, h), (d0 , h0 )}). We
will lead to a contradiction.
Let w0 = w(X 0 ∪ {(d0 , h0 )}) and w00 = w(X 0 ∪ {(d, h), (d0 , h0 )}). The proof consists ofthree steps.
000w
Step 1: In this step we observe that κ̃w{h0 } < κ̃{h0 } . To see this, note that otherwise
00

0

0
w
we would have κ̃w{h0 } ≥ κ̃{h0 } , hence by the definition of Ch we must have [Ch(X ∪{(d0 , h0 )})]h0 ⊇ [Ch(X 0 ∪ {(d, h), (d0 , h0 )})]h0 \ {(d, h)}. This contradicts (d0 , h0 ) 6∈ Ch(X 0 ∪{(d0 , h0 )}) and (d0 , h0 ) ∈ Ch(X 0 ∪ {(d, h), (d0 , h0 )}).
000

w
Step 2: Consider any r such that h0 ∈ r. Let κ̃wr and κ̃r be as defined in the procedure
˜ 0 ) and Ch(w˜ 00 ), respectively. Let r0 ∈ S(r) be the subregion such thatto compute Ch(w
0

00

0

00

0

00

w
w
w
h0 ∈ r0 . Suppose κ̃w
r0 < κ̃r0 . We will show that κ̃r < κ̃r . To see this, suppose the
00

0

0
00
00
w
w
0
w
contrary, i.e., that κ̃wr ≥ κ̃r . Let v := (vr00 )r00 ∈S(r) and v := (vr00 )r00 ∈S(r) . Since w ≤ w

and vrw00 is weakly increasing in w for any region r00 , it follows that v 0 ≤ v 00 . This andsubstitutability of Dr imply
˜ r (v 0 ; κ̃w0 )]r0 ≥ min{[Ch˜ r (v 00 ; κ̃w00 )]r0 , v 0 0 }.
[Ch
r
r
r
0

00

w
Since we assume κ̃w
r0 < κ̃r0 , or equivalently
000

˜ r (v 0 ; κ̃w )]r0 < [Ch˜ r (v 00 ; κ̃w )]r0 ,[Chrr
˜ r (v 0 ; κ̃w0 )]r0 ≥ v 0 0 . But then by [Ch˜ r (v 0 ; κ̃w0 )]r0 ≤ v 0 0 (from the definition
this means [Ch
r
r
r
r
0
w0
0
˜
˜
of Ch) we have [Chr (v ; κ̃ )]r0 = v 0 . This contradicts the assumption that (d0 , h0 ) 6∈
r

0

0

0

r

0

Ch(X ∪{(d , h )}), while d is acceptable to h0 (because (d0 , h0 ) ∈ Ch(X 0 ∪{(d, h), (d0 , h0 )})).
000w
Thus we must have that κ̃w
r < κ̃r .
34Analogous conditions called cardinal monotonicity and size monotonicity are introduced by Alkan(2002) and Alkan and Gale (2003) for matching models without contracts.
35Note that choice rule Ch(·) allows for the possibility that multiple contracts are signed between thesame pair of a region and a doctor. Without this possibility, the choice rule may violate the substitutes
condition (Sönmez and Switzer, 2013; Sönmez, 2013). Hatfield and Kominers (2013) explore this issue
further.

28
0

00

w
Step 3: Step 1 and an iterative use of Step 2 imply that κ̃w
H < κ̃H . But we specifiedκ̃w
H for any w to be equal to κH , so this is a contradiction.
Part 2. To show that Ch satisfies the law of aggregate demand, let X 0 ⊆ X and (d, h)be a contract such that d h ∅. We shall show that |Ch(X 0 )| ≤ |Ch(X 0 ∪ {(d, h)})|. To
show this, denote w = w(X 0 ) and w0 = w(X 0 ∪ {(d, h)}). By definition of w(·), we havethat wh0 = wh + 1 and wh0 0 = wh0 for all h0 6= h. Consider the following cases.
P(1) Suppose r0 ∈S(r) vrw0 ≥ κr for some r ∈ R such that h ∈ r. Then we have:0

Claim 2. vrw0 = vrw0 unless r0 ( r.
Proof. Let r0 be a region that does not satisfy r0 ( r. First, note that if r0 ∩ r = ∅,0then the conclusion holds by the definitions of vrw0 and vrw0 because wh0 0 = wh0 for
any h0 ∈/ r. Second, consider r0 such that r ⊆ r0 (since R is hierarchical, theseP
cases exhaust all possibilities). Since vrw = min{ r0 ∈S(r) vrw0 , κr }, the assumptionPw
r0 ∈S(r) vr0 ≥ κr implies vr (w) = κr . By the same argument, we also obtain0

vr (w0 ) = κr . Thus, for any r0 such that r ⊆ r0 , we inductively obtain vrw0 = vrw0 . 
0The relation vrw0 = vrw0 for all r0 ( r implies that, together with the construction
˜of Ch,0˜ 0 )]h0 = [Ch(w)]
˜
[Ch(w
/ r.
h0 for any h ∈

(C.1)

P
w
To consider hospitals in r, first observe that r satisfies
r0 ∈S(r) vr0 ≥ κr byP
0
assumption, so vrw = min{ r0 ∈S(r) vrw0 , κr } = κr , and similarly vrw = κr , so vrw =0
˜ we also have v w0 = v w0 0 for any region r0v w . Therefore, by construction of Ch,rr

0such that r ⊆ r .

This implies κ̃w
r

=

0
κ̃w
r ,

where κ̃wr
0

r
0
and κ̃wr

are the assigned

regional caps on r under weight vectors w and w , respectively, in the algorithm
˜
to construct Ch.
P
Now note the following: For any r0 ∈ R, since vrw0 is defined as min{ r00 ∈S(r0 ) vrw00 , κr0 }and all regional preferences are acceptant, the entire assigned regional cap κ̃w
r0 is
P
0
w
w
allocated to some subregion of r , that is, κ̃r0 = r00 ∈S(r0 ) κ̃r00 . Similarly we also
P0
w00
have κ̃w
r0 =r00 ∈S(r0 ) κ̃r00 . This is the case not only for r = r but also for all
subregions of r, their further subregions, and so forth. Going forward until thisreasoning reaches the singleton sets, we obtain the relationXX˜ 0 )]h0 =
˜
(C.2)
[Ch(w
[Ch(w)]
h0 .
h0 ∈r

h0 ∈r

29

By (C.1) and (C.2), we conclude thatXX˜˜ 0 )]h0 = |Ch(X 0 ∪ {(d, h)})|,
0|Ch(X 0 )| =[Ch(w)]
=
[Ch(w
h
h0 ∈H

h0 ∈H

completing the proof for this case.
P(2) Suppose r0 ∈S(r) vrw0 < κr for all r ∈ R such that h ∈ r. Then the regional cap forr is not binding for any r such that h ∈ r, so we have(C.3)

˜ 0 )]h = [Ch(w)]˜[Ch(wh + 1.
In addition, the following claim holds.
0˜˜ 0 )]h0 = [Ch(w)]Claim 3. [Ch(wh0 , for all h 6= h.
0

Proof. First, note that vrw = vrw + 1 for all r such that h ∈ r because the regionalcap for r is not binding for any such r. Then, consider the largest region H. By
P
assumption, κH has not been reached under w, that is, r0 ∈S(H) vrw0 < κH . Thus,
˜ H is acceptant, the entire vector (vr0 (w))r0 ∈S(H) is accepted by Ch
˜ H , thatsince Chw
0
is, κ̃w/ r0 , both its assigned regionalr0 = vr0 . Hence, for any r ∈ S(H) such that h ∈0w
cap and all v’s in their regions are identical under w and w0 , that is, κ̃w
r0 = κ̃r0 and

wh0 0 = wh0 for all h0 ∈ r0 . So, for any hospital h0 ∈ r0 , the claim holds.
Now, consider r ∈ S(H) such that h ∈ r. By the above argument, the assigned
regional cap has increased by one in w0 compared to w. But since r’s regional cap
κr has not been binding under w, all the v’s in the subregions of r are accepted inboth w and w0 . This means that (1) for each subregion r0 of r such that h ∈/ r0 , itgets the same assigned regional cap and v’s, so the conclusion of the claim holds
for these regions, and (2) for the subregion r0 of r such that h ∈ r0 , its assigned
regional cap is increased by one in w0 compared to w, and its regional cap κr0
has not been binding. And (2) guarantees that we can follow the same argument
inductively, so the conclusion holds for all h 6= h0 .



By equation (C.3) and Claim 3, we obtainXX0˜ 0 )]h0 =˜|Ch(X 0 ∪ {(d, h)})| =[Ch(w[Ch(w)]
h0 + 1 = |Ch(X )| + 1,
h0 ∈H

h0 ∈H

so we obtain |Ch(X 0 ∪ {(d, h)})| > |Ch(X 0 )|, completing the proof.
A subset X 0 of X = D × H is said to be individually rational if (1) for any d ∈ D,|{(d, h) ∈ X 0 |h ∈ H}| ≤ 1, and if (d, h) ∈ X 0 then h d ∅, and (2) Ch(X 0 ) = X 0 .

30

Definition 4. A set of contracts X 0 ⊆ X is a stable allocation if(1) it is individually rational, and(2) there exists no hospital h ∈ H and a doctor d ∈ D such that (d, h) d x and(d, h) ∈ Ch(X 0 ∪ {(d, h)}), where x is the contract that d receives at X 0 if any and∅ otherwise.
When condition (2) is violated by some (d, h), we say that (d, h) is a block of X 0 .
Given any individually rational set of contracts X 0 , define a corresponding matchingµ(X 0 ) in the original model by setting µd (X 0 ) = h if and only if (d, h) ∈ X 0 and µd (X 0 ) = ∅if and only if no contract associated with d is in X 0 . For any individually rational X 0 ,µ(X 0 ) is well-defined because each doctor receives at most one contract at such X 0 .
Proposition 2. Suppose that Dr is substitutable for all r ∈ R. If X 0 is a stable allocationin the associated model with contracts, then the corresponding matching µ(X 0 ) is a stablematching in the original model.
Proof. First, the following observation is straightforward.
Observation 1. Suppose that R is a hierarchy. Then a matching µ is stable if and only
if it is feasible, individually rational, and if (d, h) is a blocking pair then there exists r ∈ Rwith h ∈ r such that (i) |µr | = κr , (ii) d0 h d for all doctors d0 ∈ µh , and (iii) eitherPµd ∈/ r or (wr0 )r0 ∈S(SC(h,µd )) DSC(h,µd ) (wr0 0 )r0 ∈S(SC(h,µd )) , where wr0 =h0 ∈r0 |µh0 | for all
r0 ∈ S(r) and wr0 h = wrh + 1, wr0 d = wrd − 1 and wr0 0 = wr0 for all other r0 ∈ S(r) whererh and rd are subregions of r such that h ∈ rh0 , and µd ∈ rd .
Suppose that X 0 is a stable allocation in the associated model with contracts and denoteµ := µ(X 0 ). Individual rationality of µ is obvious from the construction of µ. Supposethat (d, h) is a blocking pair of µ. By the above observation, it suffices to show that
there exists a region r that includes h such that the following conditions (C.4), (C.5), andµd 6∈ r hold, or (C.4), (C.5), (C.6), and h, µd ∈ r hold:(C.4)|µr | = κr ,(C.5)

d0 h d for all d0 ∈ µh ,(C.6)

(wr00 )r00 ∈S(SC(h,µd )) DSC(h,µd ) (wr0 00 )r00 ∈S(SC(h,µd )) ,where for any region r0 we write wr00 =P

h0 ∈r00 |µh0 | for all r
00
0

00

∈ S(r0 ) and wr0 h = wrh + 1,

wr0 d = wrd − 1 and wr0 00 = wr00 for all other r ∈ S(r ) where rh , rd ∈ S(r), h ∈ rh , andµd ∈ rd . Let w = (wh )h∈H .

31For each region r that includes h, let wr000 = wr0 + 1 for r0 such that h ∈ r0 and wr0000 = wr00
for all other r00 ∈ S(r). Let w00 = (wh00 )h∈H .
Claim 4. Condition (C.5) holds, and there exists r that includes h such that Condition(C.4) holds.
Proof. First note that the assumption that h d µd implies that (d, h) d x where x
denotes the (possibly empty) contract that d signs under X 0 .
(1) Assume by contradiction that condition (C.5) is violated, that is, d h d0 for some˜ 00 )]h ≥ [Ch(w)]˜
d0 ∈ µh . First, note that [Ch(wh . That is, weakly more contracts
involving h are signed at X 0 ∪ (d, h) than at X 0 . This is because for any r andr0 ∈ S(r) such that h ∈ r0 ,00

˜ r ((v w00 )r00 ∈S(r) ; κ̃r )]r0 ≥ [Ch˜ r ((v w00 )r00 ∈S(r) ; κ̃0 )]r0 if κ̃r ≥ κ̃0 .
[Ch
r
r
r
r

(C.7)

˜ r ((v w00 )r00 ∈S(r) ; κ̃r )]r0 ≥ [Ch˜ r ((v w00 )r00 ∈S(r) ; κ̃0 )]r0 by
To see this, first note that [Chrrr
˜ r and v w0000 ≥ v w00 for every region
substitutability of Dr . Also, by consistency of Ch
r

r

00

r , the inequality
˜ r ((v w0000 )r00 ∈S(r) ; κ̃r )]r0 ≥ [Ch˜ r ((v w00 )r00 ∈S(r) ; κ̃r )]r0[Chrr
follows,36 showing condition (C.7). An iterative use of condition (C.7) gives us the
˜ 00 )]h ≥ [Ch(w)]˜desired result that [Ch(wh . This property, together with the assumptions that d h d0 and that (d0 , h) ∈ X 0 imply that (d, h) ∈ Ch(X 0 ∪ (d, h)).37
Thus, together with the above-mentioned property that (d, h) d x, (d, h) is a
block of X 0 in the associated model of matching with contracts, contradicting theassumption that X 0 is a stable allocation.
(2) Assume by contradiction that condition (C.4) is violated, so that |µr | =6 κr forevery r that includes h. Then, for such r, since |µr | ≤ κr by the construction of
36To show this claim, let v = (v w ) 000000

= (vrw00 )r00 ∈S(r) for notational simplicity and assume
˜ r (v 00 ; κ̃r )]r0 < [Ch˜ r (v; κ̃r )]r0 . Then, [Ch˜ r (v 00 ; κ̃r )]r0 < [Ch˜ r (v; κ̃r )]r0 ≤ vr0 .
for contradiction that [Ch
00
00
0
00
˜ r (v 00 )]r00 ≤ v 0000 =Moreover, since v 00 = vr00 for every r 6= r by the construction of v , it follows that [Chr 00 r ∈S(r) and vrr˜ r (v 00 ) ≤ v. Also we have v ≤ v 00 by the definition of
vr00 . Combining these inequalities, we have that Ch
˜ r (v 00 ) ≤ v ≤ v 00 . Thus, by consistency of Ch
˜ r , we obtain Ch
˜ r (v 00 ) = Ch˜ r (v), a
v 00 , so it follows that Ch
˜ r (v 00 )]r0 < [Ch˜ r (v)]r0 .
contradiction to the assumption [Ch37The proof of this claim is as follows. Ch(X 0 ) induces hospital h to select its [Ch(w)]˜h most preferred
contracts while Ch(X 0 ∪ (d, h)) induces h to select a weakly larger number [Ch(w00 )]h of its most preferred00˜
contracts. Since (d0 , h) is selected as one of the [Ch(w)]h most preferred contracts for h at X and d h d ,0˜
we conclude that (d, h) must be one of the [Ch(w00 )]h (≥ [Ch(w)]h ) most preferred contracts at X ∪(d, h),thus selected at X 0 ∪ (d, h).

32µ and the assumption that X 0 is individually rational, it follows that |µr | < κr .
Then (d, h) ∈ Ch(X 0 ∪ (d, h)) because,(a) d h ∅ by assumption,PPP00(b) since r0 ∈S(r) wr0 =h∈r |µh | = |µr | < κr , it follows thatr0 ∈S(r) wr0 =P
˜
r0 ∈S(r) wr0 + 1 ≤ κr . This property and the fact that Chr is acceptant and˜ 00 ) = w00 . In
the definition of the function vr0 for regions r0 imply that Ch(wparticular, this implies that every contract (d0 , h) ∈ X 0 ∪ (d, h) such thatd0 h ∅ is chosen at Ch(X 0 ∪ (d, h)).
Thus, together with the above-mentioned property that (d, h) d x, (d, h) is a
block of X 0 in the associated model of matching with contract, contradicting theassumption that X 0 is a stable allocation.
To finish the proof of the proposition suppose for contradiction that there is no r that
includes h such that (C.4), (C.5), and µd 6∈ r hold, and that condition (C.6) fails. That is,
we suppose (wr0 00 )r00 ∈S(SC(h,µd )) BSC(h,µd ) (wr00 )r00 ∈S(SC(h,µd )) . Then it must be the case that00˜ r ((v w0000 )r00 ∈S(SC(h,µ )) ; κ̃w00)]r0 = w000 = wr0 + 1 = |µh | + 1, where h ∈ r0 and κ̃w
[Ch
r

d

SC(h,µd )rSC(h,µd )˜ 00 ).38 Note that for all r0 such that h ∈ r0
is as defined in the procedure to compute Ch(wand r0 ( SC(h, µd ), it follows that µd ∈/ r0 . Also note that (C.5) is satisfied by Claim 4.
Therefore we have |µr0 | < κr0 for all r0 ( SC(h, µd ) that includes h by assumption and
w00
w00
SC(h,µd ) ((vr 00 )r 00 ∈S(SC(h,µd )) ; κ̃SC(h,µd ) )]r 0 ≤00
Let v := (vrw00 )r00 ∈S(SC(h,µd )) and v 00 := (vrw00 )r00 ∈S(SC(h,µd )) . Since wr0000 = wr00 for any
00

38To show this claim, assume for contradiction that [Ch˜

wr0 where h ∈ r0 .

r00 6= r0 by the definition of w , it follows that00˜ SC(h,µ ) (v 00 ; κ̃w00
Ch
SC(h,µd ) ) ≤ (wr 00 )r 00 ∈SC(h,µd ) ≤ (wr 00 )r 00 ∈SC(h,µd ) .
d0˜ SC(h,µ ) (v; κ̃w
00
But ChdSC(h,µd ) ) = (wr )r 00 ∈SC(h,µd ) because X is a stable allocation in the associated modelof matching with contracts, which in particular implies v = (wr00 )r00 ∈SC(h,µd ) . Since v ≤ v 00 , this meansthat00
˜ SC(h,µ ) (v 00 ; κ̃w00
Ch
SC(h,µd ) ) ≤ v ≤ v .
d

˜ SC(h,µ ) , we obtain
Thus by consistency of Chdw00
˜ SC(h,µ ) (v 00 ; κ̃w00
˜
Ch
SC(h,µd ) ) = ChSC(h,µd ) (v; κ̃SC(h,µd ) ).
d

But
tain

˜ SC(h,µ ) (v; κ̃w=(wr00 )r00 ∈SC(h,µd ) ,again by ChdSC(h,µd ) )w00
˜
ChSC(h,µ ) (v; κ̃)=(wr00 )r00 ∈SC(h,µ ) ,thus

by substitutability
˜ SC(h,µ ) (v 00 ; κ̃w00
Ch

we

SC(h,µd ) )00(wr00 )r00 ∈SC(h,µd ) .
This is a contradiction because≤ (wr00 )r00 ∈SC(h,µd )
00
00
0
˜
00
v
and (wr00 )r00 ∈SC(h,µd ) BSC(h,µd ) (wr )r00 ∈SC(h,µd )while ChSC(h,µd ) (v 00 ; κ̃w
SC(h,µd ) )P00
arg maxDSC(h,µ ) {(wr00000 )r00 ∈SC(h,µd ) |(wr00000 )r00 ∈SC(h,µd ) ≤ v 00 , r00 ∈S(SC(h,µd )) wr00000 ≤ κ̃w
SC(h,µd ) }.
ddSC(h,µd )d(wr0 00 )r00 ∈SC(h,µd )

d

ob=
=
∈

33

hence |µr0 | + 1 ≤ κr0 for all such r0 . Moreover we have d h ∅, thus(d, h) ∈ Ch(X 0 ∪ (d, h)).
This relationship, together with the assumption that h d µd , and hence (d, h) d x, is acontradiction to the assumption that X 0 is stable in the associated model with contracts.
Remark 5. The definition of stability in this paper is based on Pareto improvement for
multiple regions. For the case of hierarchies, we provide an alternative interpretation
here. The idea of Condition (iii) in Observation 1 is to invoke a region’s preferences whena doctor moves within a region whose regional cap is binding (region r in the definition).
However, when r is a strict superset of SC(h, µd ), we do not invoke region r’s regional
preferences, but the preferences of SC(h, µd ). The use of preferences of SC(h, µd ) reflects
the following idea: if the regional cap at r is binding then holding fixed the number ofdoctors matched in r but not in SC(h, µd ), there is essentially a binding cap for SC(h, µd ).
This motivates our use of the regional preferences of SC(h, µd ). The reason for not using
preferences of r (or any region between r and SC(h, µd )) is that the movement of a
doctor within the region SC(h, µd ) does not affect the distribution of doctors on which
preferences of r (or regions of any smaller depth than SC(h, µd )) are defined.



Remark 6. Each step of the flexible deferred acceptance algorithm corresponds to a stepof 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 thesame step of the cumulative offer process, contract (d, h) is proposed. Moreover, the setof 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 0 is the allocation that is produced by the cumulative offer process,then µ(X 0 ) is the matching produced by the flexible deferred acceptance algorithm.
Proof of Theorem 1, (1) ⇒ (2). By Proposition 1, the choice rule Ch(·) satisfies the substitutes condition and the law of aggregate demand in the associated model of matchingwith contracts. By Hatfield and Milgrom (2005), Hatfield and Kojima (2009), and Hatfield and Kominers (2012), the cumulative offer process with choice rules satisfying these
conditions produces a stable allocation and is (group) strategy-proof.39 The former fact,
39Aygün and Sönmez (2012) point out that a condition called path-independence (Fleiner, 2003) orirrelevance of rejected contracts (Aygün and Sönmez, 2012) is needed for these conclusions. Aygün andSönmez (2012) show that the substitutes condition and the law of aggregate demand imply this condition.

34

together with Remark 6 and Proposition 2, implies that the outcome of the flexible deferred acceptance algorithm is a stable matching in the original model. The latter fact andRemark 6 imply that the flexible deferred acceptance mechanism is (group) strategy-proof
for doctors.

Appendix D. Proof of Theorem 1, (2) ⇒ (1)Fix R, and suppose that it is not a hierarchy. Then, there exist r, r0 ∈ R and h1 , h2 , h3 ∈H such that h1 ∈ r \ r0 , h2 ∈ r ∩ r0 , and h3 ∈ r0 \ r. We will show that there does notexist a mechanism that is stable and strategy-proof for doctors.
To see this, first pick r1 ∈ R such that (i) {h1 , h2 } ⊆ r1 ⊆ r and (ii) there is nor̃ ∈ R with the property that {h1 , h2 } ⊆ r̃ ( r1 . Similarly, pick r2 ∈ R such that (i){h2 , h3 } ⊆ r2 ⊆ r0 and (ii) there is no r̃ ∈ R with the property that {h2 , h3 } ⊆ r̃ ( r2 .
By the construction of r1 , there exist S1 ⊆ R and r̂1 , r̂2 ∈ R such that (i) S1 is a largest
partition of r1 , (ii) r̂1 ∈ S1 and h1 ∈ r̂1 , and (iii) r̂2 ∈ S1 and h2 ∈ r̂2 . Similarly, by theconstruction of r2 , there exist S2 ⊆ R and r̃2 , r̃3 ∈ R such that (i) S2 is a largest partitionof r2 , (ii) r̃2 ∈ S2 and h2 ∈ r̃2 , and (iii) r̃3 ∈ S2 and h3 ∈ r̃3 .
Let ŵ1 be a vector of nonnegative integers over the set S1 such that the coordinate
corresponding to r̂1 is 1 and other coordinates are 0. Also, let ŵ2 be a vector of nonnegative
integers over the set S1 such that the coordinate corresponding to r̂2 is 1 and othercoordinates are 0. Suppose that ŵ1 Br1 ,S1 ŵ2 . Similarly, let w̃2 be a vector of nonnegative
integers over the set S2 such that the coordinate corresponding to r̃2 is 1 and othercoordinates are 0. Also, let w̃3 be a vector of nonnegative integers over the set S2 suchthat the coordinate corresponding to r̃3 is 1 and other coordinates are 0. Suppose thatw̃2 Br2 ,S2 w̃3 .
Let κr1 = κr2 = 1, and κr̄ = |D| + 1 for all r̄ ∈ R \ {r1 , r2 }. Fix two doctors d1 and d2
in D. Finally, assume that preferences of doctors and hospitals are as follows:d1 : h3 ,

d2 : h2 , h1 ,

h1 : d2 , d1 ,

h2 : d1 , d2 ,

h3 : d2 , d1 ,the capacity of h1 , h2 , and h3 are sufficiently large so that they never bind,40 and all
doctors in D \ {d1 , d2 } regard all hospitals unacceptable.41
Since the choice rules in our context satisfy the substitutes condition and the law of aggregate demand,the conclusions go through.
40For instance, let q

h1 = qh2 = qh3 = |D| + 1.

41Preferences for hospitals in H \ {h , h , h } can be arbitrary.
1

2

3

35

By inspection, it is straightforward to see that the following two are the only stablematchings given the above preferences:µ=µ0 =h1 h2 h3 other hospitals
∅

d2

∅

h1 h2 h3
d2

∅

d1

∅

∅

···∅···

d1 other doctors!
other hospitals∅.
···∅···
other doctors!
,

We consider two cases.
Case 1: Suppose that a mechanism produces µ given the above preference profile. Consider
d1 ’s preferences
0d1 : h1 , h2 , h3 .
Under the preference profile (0d1 , d2 , h1 h2 , h3 ) it is straightforward to check that µ0
is a unique stable matching. Note that d1 is matched to h3 under this new preference
profile, which is strictly better under d1 than d1 ’s match ∅ under the original preference
profile (d1 , d2 , h1 h2 , h3 ). This implies that if a mechanism is stable and produces µ
given preference profile (d1 , d2 , h1 h2 , h3 ), then it is not strategy-proof for doctors.
Case 2: Suppose that a mechanism produces µ0 given the above preference profile. Consider d2 ’s preferences
0d2 : h2 , h3 , h1 .
Under the preference profile (d1 , 0d2 , h1 h2 , h3 ) it is straightforward to check that µ
is a unique stable matching. Note that d2 is matched to h2 under this new preference
profile, which is strictly better under d2 than d2 ’s match h1 under the original preference
profile (d1 , d2 , h1 h2 , h3 ). This implies that if a mechanism is stable and produces µ0
given preference profile (d1 , d2 , h1 h2 , h3 ), then it is not strategy-proof for doctors.
Appendix E. Additional Discussions
E.1. Group strategy-proofness. The statement of Theorem 1 holds when we strengthen
the incentive compatibility requirement. A mechanism ϕ is said to be group strategyproof for doctors if there are no (κ, D), preference profile , a subset of doctors D0 ⊆ D,
and a preference profile (0d0 )d0 ∈D0 of doctors in D0 such that
κ,D
0
0
ϕκ,D
d ((d0 )d0 ∈D0 , (i )i∈D∪H\D0 ) d ϕd () for all d ∈ D .

That is, no subset of doctors can jointly misreport their preferences to receive a strictlypreferred outcome for every member of the coalition under the mechanism. Clearly, thisproperty is stronger than strategy-proofness for doctors. The proof in the Appendix shows36that the statement of Theorem 1 holds when we replace strategy-proofness for doctors
with group strategy-proofness for doctors.
E.2. Further Discussion on Substitutability. The following examples show that conditions (B.1) and (B.2) of substitutability are independent.
Example 2 (Regional preferences that violate (B.1) while satisfying (B.2)). There is aregion r in which two hospitals h1 and h2 reside. S = {{h1 }, {h2 }} is the unique largest
partition of r. The capacity of each hospital is 2. Region r’s preferences are as follows.
Br,S : (2, 2), (2, 1), (1, 2), (2, 0), (0, 2), (1, 1), (1, 0), (0, 1), (0, 0).
One can check by inspection that condition (B.2) and consistency are satisfied. To showthat (B.1) is not satisfied, observe first that there is a unique associated choice rule
˜ r,S . The above preferences imply that(since preferences are strict), and denote it by Ch
˜ r,S ((1, 2); 2) = (0, 2) and Ch
˜ r,S ((2, 2); 2) = (2, 0). But this is a contradiction to (B.1)
Ch
˜ r,S ((1, 2); 2) ≥ Ch
˜ r,S ((2, 2); 2) ∧ (1, 2) does not hold (the left
because (1, 2) ≤ (2, 2) but Ch
hand side is (0, 2) while the right hand side is (1, 0)).



Example 3 (Regional preferences that violate (B.2) while satisfying (B.1)). There is aregion r in which three hospitals h1 , h2 , and h3 reside. S = {{h1 }, {h2 }, {h3 }} is theunique largest partition of r. The capacity of each hospital is 1. Region r’s preferences
are as follows.
Br,S : (1, 1, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 0, 0).
One can check by inspection that condition (B.1) (and hence consistency by Claim 1) aresatisfied. To show that (B.2) is not satisfied, observe first that there is a unique associated˜ r,S . The above preferences
choice rule (since preferences are strict), and denote it by Ch
˜ r,S ((1, 1, 1); 1) = (0, 0, 1) and Ch
˜ r,S ((1, 1, 1); 2) = (1, 1, 0). But this is a
imply that Ch
˜ r,S ((1, 1, 1); 1) ≤ Ch
˜ r,S ((1, 1, 1); 2) does notcontradiction to (B.2) because 1 ≤ 2 but Ch
hold (the left hand side is (0, 0, 1) while the right hand side is (1, 1, 0)).

