EKKYO MATCHING: HOW TO INTEGRATE FRAGMENTED
MATCHING MARKETS FOR WELFARE IMPROVEMENTYUICHIRO KAMADA AND FUHITO KOJIMA

Abstract. We consider a school-choice matching model that allows for inter-regionaltransfer of students (ekkyo admission), with the “balancedness” constraint: each student
and school belongs to a region, and a matching is said to be balanced if, for each region,
the outflow of students from that region to other regions is equal to the inflow of students from the latter to the former. Using a directed bipartite graph defined on students
and schools, we characterize the set of Pareto efficient matchings among those that are
individually rational, balanced and fair. We also provide a class of polynomial-time algorithms to compute such matchings. The outcome of an algorithm from this class weakly
improves student welfare upon the one produced when each region independently uses adeferred acceptance algorithm.
JEL Classification Numbers: C70, D47, D61, D63.
Keywords: ekkyo, balancedness, fairness, algorithm, efficiency, daycare allocation, school
choice, matching with constraints

Date: December 8, 2023.
Kamada: Haas School of Business, University of California, Berkeley, and Department of Economics, University ofTokyo, Tokyo, Japan, y.cam.24@gmail.com. Kojima: Department of Economics, University of Tokyo, Tokyo, Japan, fuhitokojima1979@gmail.com. We thank Itai Ashlagi, Bettina Klaus, Shunya Noda, Mike Ostrovsky, Bobak Pakzad-Hurson,
and Koji Yokote for helpful comments. Yutaro Akita, Nanami Aoi, Yusuke Iwase, Ayana Kono, Kyohei Okumura, Akira
Matsushita, Sota Minowa, Daiji Nagara, Ryosuke Sato, Kazuki Sekiya, and Ayano Yago provided excellent research assistance. Fuhito Kojima is supported by the JSPS KAKENHI Grant-In-Aid 21H04979.

1

2

1. Introduction
Matching theory has been applied in numerous real-life markets with a purpose of centralizing market transactions, but the centralized clearinghouses are still often organized
at a (often small) local level. As a consequence of such fragmentation, some efficiency
gains are being missed. In Japan, for instance, allocation of slots at accredited daycares
are conducted by individual municipal governments and, with few exceptions, a child can
only attend a daycare in the municipality of their residence. The City of Tokyo, for example, is divided into 23 small municipalities with the average size being about a halfof Manhattan’s, and each conducts a matching independently.1 Due to the small sizes of
the regions, many families find that daycare centers outside the regions of their residence
are among the closest. Moreover, it is often convenient to put their children to a daycare
center close to their workplace while many people cross a regional boundary to commute.2
For these reasons, inter-regional admission—which is called the ekkyo admission—is anappealing option for many families and it is indeed legal. However, ekkyo matching israre under the current practice.
We study how to integrate fragmented matching markets. Specifically, we analyze
mechanisms that improve upon mechanisms organized at the local level and achieve desirable fairness and efficiency properties. To do so, we depart from the standard modelof matching between students and schools (Balinski and Sönmez, 1999; Abdulkadiroğlu
and Sönmez, 2003) by assuming that each school belongs to exactly one region while each
student is a resident of exactly one region. We consider a balancedness constraint that
requires that, for each region, the number of residents of other regions who are matched
to a school in it, called the inflow, must be equal to the number of its residents who arematched to a school in other regions, called the outflow.
Why is balancedness a reasonable requirement? In the context of Japanese daycare allocation, for instance, although ekkyo matching is legal—in fact, the Japanese government
amended its Children and Childcare Act to encourage ekkyo matching in 2018—, the law
makes it clear that it is each municipality’s responsibility to provide daycare services.3
Therefore, it is impractical to organize a daycare allocation in a fully integrated manner
across multiple municipalities. Moreover, each municipality heavily subsidizes daycares,
1

The average area of each of the 23 municipalities is 10.4 square miles, while Manhattan’s area is 22.7

square miles.
2
To get a sense of the magnitude, over 3.5 million people get on or get off a train in Tokyo’s Shinjuku
Station each day.
3
Revision to Article 14(4) of the Supplementary Provision to Children and Childcare Act of Japan,
https://elaws.e-gov.go.jp/document?lawid=424AC0000000065.

3

so enrolling residents from other municipalities can be a severe financial burden. Ourbalancedness constraint is meant to alleviate municipalities’ concerns by guaranteeingthat no municipality carries an excessive burden. Given those considerations, we design
mechanisms that achieve desirable properties under the balancedness constraint. In otherwords, we aim at partial integration of the regions instead of full integration.
We find that there does not always exist a balanced matching that satisfies stability, astandard desideratum in school choice literature that is equivalent to individual rationality,
fairness, and non-wastefulness. Given this observation, we weaken our desideratum to only
require individual rationality, balancedness and fairness. Among the matchings satisfying
all the three conditions (there always exists such a matching4), which we call the iBF s,
we focus on the ones that cannot be further improved upon in terms of students’ welfare,which we call efficient iBFs.
We first characterize efficient iBFs. To this end, we define a novel bipartite graph calleda fair improvement graph (FIG henceforth) on a matching, where the vertices on one side
represent the students and those on the other side represent the schools, and existence ofan arrow between two vertices depends on preferences, priorities, and the given matching.
We show that an iBF is an efficient iBF if and only if there exists no “FIG cycle,” a cycleon the FIG, for the matching.
Based on our characterization of efficient iBF, we then provide a polynomial-time algorithm that finds an efficient iBF. The algorithm is called the FIG cycles algorithm andis illustrated in some detail with an example in Section 1.1. Roughly, each step of the
FIG cycles algorithm checks if the current iBF allows for a FIG cycle and, if so, finds
a relocation of students that improves outcomes for students while retaining individual
rationality, balancedness and fairness.
To better understand the markets with the balancedness constraint, we provide further
discussions. First, we characterize when balancedness and stability are compatible witheach other. Second, we examine strategic properties. Third, comparative statics areprovided to evaluate the effect of merging and splitting regions. Fourth, we consider thecase with weak priority, which often arises in school choice applications.
We would like to emphasize that our analysis is applicable beyond daycare allocation.
Also in Japan, choice systems for public elementary and middle schools are organizedat the small municipal level as well. Naturally, there exist much potential demand forenrolling in schools in other municipalities, but opportunities for interdistrict school choice4

All the conditions are satisfied by the matching where no student is matched to any school.

4

are severely limited.5 The issue is not limited to Japan either. In the U.S., for example,
school choice is basically organized at a highly local level, but some form of interdistrict
school choice is practiced in 43 States.6 The analysis of our paper, and particularly the
FIG cycles algorithm, could be applied to improve efficiency of school choice mechanisms.
At a high level, the fragmented nature of resource allocation is widespread beyond daycare allocation or school choice. In kidney exchange in the U.S., for instance, individualtransplant centers often conduct exchanges on their own before sending remaining participants to national exchange, resulting in significant efficiency loss (Agarwal et al., 2019).
In COVID-19 vaccine allocation in Japan in 2021, individual municipalities were charged
with vaccinating their respective residents, which resulted in situations in which vaccine
stocks run out quickly in one municipality while extra stocks remain unused in another.7
We envision that research is called for to understand how to overcome inefficiency fromthe fragmented nature of the allocation problems in a practical manner when existing
legal, institutional and other constraints prohibit full integration.

1.1. Illustrative Example. In this paper we introduce an algorithm of inter-regionaltransfer that improves students’ welfare while respecting the balancedness condition andfairness. To gain intuition for why inter-regional transfer may improve welfare, consider
the following simple environment (see Figure 1 for an illustration). There are two regions,r and r0 . One school s1 and two students i1 and i2 reside in r while one school s2 and one
student i3 reside in r0 . School s1 has the capacity of two while school s2 has the capacity5

For instance, Nerima (one of the 23 municipalities of Tokyo City) declares that it ad-

mits a non-resident child “only in truly unavoidable circumstances.”

See Nerima’s website,

https://www.city.nerima.tokyo.jp/kosodatekyoiku/kyoiku/shochu/8jyo-9jyo-n1.html,
last accessed on September 8, 2023.
6
See
the
websiteoftheEducation

Commission

of

the

States,https://ecs.my.salesforce-sites.com/mbdata/mbquest4e?rep=OE1705, last accessed on
September 12, 2023.
7
For instance, in an interview at the time with NHK, the national public broadcasting organization, an epidemiology expert pointed out that “adjustment of vaccine supply across municipalities islimited, and it is necessary to introduce a centralized system at a larger scale.” See NHK’s website, https://www3.nhk.or.jp/news/html/20210922/k10013272411000.html, last accessedon September 21, 2023.

5

Figure 1. Illustrative Example. Each white dotted square in a school
represents a seat in the school. The thick and thin arrows represent the
FIG while the thick arrows represent a FIG cycle.
of one. Student preferences and school priorities are given as follows:i1 : s2 ,

s1 : i1 , i2 , i3 ,

i2 : s2 , s1 ,

s2 : i3 , i1 , i2 .

i3 : s1 , s2 ,If an assignment of students to schools is determined region by region and there is nointer-regional transfer, the efficient matching for students is given by!
s1 s2 ∅µ=,
i2 i3 , i 1
which is realized by, for instance, running the student-proposing deferred acceptance algorithm in each region separately. However, with inter-regional transfer, a Pareto improvement for students is possible while respecting the balancedness condition. Specifically, if
the two students i1 and i3 are sent to the schools in each other’s regions, that is, if i1 goesto s2 and i3 goes to s1 , then in the realized matching,
!
s
s
∅
1
2
µ0 =
,
i2 , i3 i1 ∅6these students are matched with their respective first-best school. In doing so, region r1
takes in one student from outside (student i3 ) while sending one student outside (student
i1 ), so the balancedness condition is satisfied.
Two things are noteworthy here. First, the number of students who are matched tosome school is increased from µ to µ0 . This is because, by swapping students between
the two regions, the unmatched student i1 was able to be matched with a school. We
introduce an algorithm to make such an improvement possible.8
Second, there is another matching that respects the balancedness condition and Pareto
dominates µ, which isµ00 =s1 s2 ∅
i3

i2 i1

!
.

However, this matching is not fair according to our definition, as i1 is ranked higher thani2 at s2 . This suggests that care is needed about who can be moved to new schools
across regions. The algorithm we introduce ensures that fairness is respected when an
improvement is made.
We aim to achieve efficiency via inter-regional transfer like the one described in theabove example. Specifically, we propose an algorithm that takes an arbitrary iBF as an
input and achieves a Pareto improvement. The algorithm is based on a directed bipartite
graph between students and schools that we call the fair improvement graph (or the FIG),
and in each of its steps it “implements” a cycle in this graph—called a FIG cycle—, i.e.,
we move a student to a school that she points to. The outcome of repeatedly implementing
FIG cycles turns out to be an efficient iBF. In fact, our main results characterize efficientiBF using cycles: we show that an iBF is an efficient iBF if and only if there is no FIG
cycle on it.
Let us now discuss these results in the context of the aforementioned example. In our
FIG, each school is pointed to by the top student (according to its priority) among those
who strictly prefer the school to their current match and are acceptable to the school.
This means that, under µ, s1 is pointed to by i3 while s2 is pointed to by i1 . Note that i2
cannot point to s2 as he is not the “top student” for s2 (i1 is). Also, each school points
to the students that are matched to the school. So, s1 points to i2 and s2 points to i3 .
The above pointing rule is based on a standard idea in the previous literature that use
cycles (e.g., Erdil and Ergin (2008) and Top Trading Cycles). However, in the present
example, the graph constructed in this way does not have a cycle even though matching µ
8As we will explain in more detail later, this type of improvement is in a sharp contrast with most exist-

ing literature where the number of matched students is constant between before and after an improvement.

7

is not an efficient iBF. In order to achieve a Pareto improvement, we additionally requirethat each school with a vacancy points to any student matched to another school in theschool’s region as well as any unmatched students living in that region. In our example,
this lets s1 point to i1 .9 With this, there is a cycle “i1 → s2 → i3 → s1 → i1 .” Ourcharacterization result shows that this implies µ is not an efficient iBF. Indeed, µ is notan efficient iBF because it is Pareto dominated by µ0 , which is an iBF. In fact, the Paretoimprovement µ0 is obtained by “implementing” this cycle. On µ0 , the FIG now lets i2 pointto (only) s2 and lets s2 point to i1 , but does not let i1 point to any school (because i1 ismatched to her first choice school). Since i3 does not point to any school either (because
i3 is matched to her first choice school), there is no FIG cycle on µ0 . Our characterization
result shows that this implies µ0 is an efficient iBF. Indeed, one can verify that there is
no iBF that Pareto dominates µ0 .
The remainder of this paper proceeds as follows. Section 2 provides a model where
we define efficient iBF. Section 3 introduces the fair improvement graph (FIG) and FIG
cycles. Section 4 provides our main theorem, which characterizes efficient iBF by nonexistence of FIG cycles. Section 5 defines the FIG cycles algorithm which outputs anefficient iBF. Section 6 provides various discussions, and Section 7 concludes. Proofs of
all results are provided in the Appendix unless stated otherwise.
2. Model2.1. Preliminary Definitions. Let there be a finite set of students I and a finite setof schools S. Each student i has a strict preference relation i over the set of schools
and being unmatched (being unmatched is denoted by ∅). For any s, s0 ∈ S ∪ {∅}, wewrite s i s0 if and only if s i s0 or s = s0 . Each school s has a strict priority order sover the set of students and leaving a position vacant (which is denoted by ∅).10 For any
i, i0 ∈ I ∪ {∅}, we write i s i0 if and only if i s i0 or i = i0 . Each school s ∈ S is endowedwith a (physical) capacity qs , which is a nonnegative integer.
Student i is said to be acceptable to school s if i s ∅ (and unacceptable otherwise).
Similarly, s is acceptable to i if s i ∅.11 It will turn out that only rankings of acceptable
9In this example, the school with a vacancy points to an unmatched student. The benefit from requiringa school to point to a student matched to another school in the same region does not appear in the current
example. We will explain this point in “Example 2, Continued” in Section 3.2.
10Strictness of priorities is assumed just for the sake of simplicity. In Section 6.4, we consider the casewhen indifferences are allowed and show that most results carry over to such a case.
11In some applications, all schools may regard all students as acceptable. None of our results will hingeon the assumption that some students can be unacceptable to some schools.

8partners matter for our analysis, so we often write only acceptable partners to denotepreferences and priorities. For example,
i : s, s0
means that school s is the most preferred, s0 is the second most preferred, and s and s0
are the only acceptable schools under preferences i of student i.
A matching µ is a mapping that satisfies (i) µi ∈ S ∪ {∅} for all i ∈ I, (ii) µs ⊆ I and|µs | ≤ qs for all s ∈ S, and (iii) for any i ∈ I and s ∈ S, µi = s if and only if i ∈ µs . Thatis, a matching simply specifies which student is assigned to which school (if any).
A matching is individually rational if no student or school is matched with an unacceptable partner.
Given a matching µ, we say that a student i has justified envy to j ∈ I if there is aschool s ∈ S such that (i) µj = s, (ii) s i µi , and (iii) i s j. We say that a matching µ
is fair if there is no pair of students (i, j) ∈ I 2 such that i has justified envy to j.
Finally, a matching µ weakly Pareto dominates a matching µ0 if µi i µ0i for everyi ∈ I. A matching µ Pareto dominates µ0 if µ weakly Pareto dominates µ0 and there
exists i ∈ I such that µi i µ0i .
2.2. Regions, Balancedness, and Efficient iBF. There is a set of regions, denoted
R, which is a partition of I ∪ S. Formally, R satisfies the following conditions:(1) Each r ∈ R is a nonempty subset of I ∪ S.
(2) r ∩ r0 = ∅ for any r, r0 ∈ R such that r 6= r0 .
S(3) r∈R r = I ∪ S.
The interpretation is that each s belongs to a single r ∈ R and each i is a resident of asingle r ∈ R. Let r(s) be the region r such that s ∈ r, and similarly for r(i).
We call E = (I, S, (a )a∈I∪S , (qs )s∈S , R) an environment.
We are now ready to introduce the key concept of this paper, “balancedness.”Definition 1. A matching µ is balanced if for each r ∈ R,
X
X
(2.1)
|{i|i ∈ µs , i 6∈ r}| =|{i|i ∈ µs , i ∈ r}|
s6∈r

s∈r

|

{z

inflow to r

}

|

{z

outflow from r}

As (2.1) shows, balancedness means that for any given region r, the inflow of students
to r is the same as the outflow of students. Note that balancedness is not a “pairwise”
notion, that is, it does not necessarily require that for every pair of regions r and r0 , thenumber of students who live in r and are matched to a school in r0 is the same as the9Figure 2. Three-way transfer (Example 1).
number of students who live in r0 and are matched to a school in r. The next example
illustrates.
Example 1 (Three-way transfer). Let I = {i1 , i2 , i3 }, S = {s1 , s2 , s3 }, R = {r1 , r2 , r3 }and rk = {ik , sk } for each k = 1, 2, 3. Letµ=s1 s2 s3 ∅
i3

i1

i2 ∅

!
.

See Figure 2 for a graphical representation. Note that under µ, the number of students
who live in r1 and are matched to a school in r2 is 1 while the number of students who livein r2 and are matched to a school in r1 is 0. Matching µ is, however, balanced because it
satisfies (2.1): For each region, the inflow and outflow are both 1.



We say that a matching is an iBF if it is individually rational, balanced, and fair.
Below is the main solution concept of this paper.
Definition 2. A matching µ is said to be an efficient iBF if µ is an iBF and there is noiBF µ0 that Pareto dominates µ.
In the standard environment without the balancedness constraint, there is a uniqueefficient iBF, which corresponds to a “student-optimal stable matching.” In our setting,there may be multiple efficient iBFs. The following example illustrates.

10

Figure 3. Multiple efficient iBFs (Example 2). Both µ and µ0 are an
efficient iBF.
Example 2 (Multiple efficient iBFs). Let I = {i1 , i2 , i3 }, S = {s1 , s2 , s3 }, R = {r, r0 }where r = {i1 , s1 , s2 } and r0 = {i2 , i3 , s3 }. Each school has the capacity of one. Student
preferences and school priorities are given as follows:i1 : s3 , s1 ,

s1 : i2 , i1 ,

i2 : s1 ,

s2 : i3 ,

i3 : s2 ,

s3 : i1 .

Letµ=s1 s2 s3 ∅
i2

∅

!

i1 i3

µ0 =

,

s1 s2 s3 ∅
∅

i3

i1 i2

!
.

See Figure 3 for a graphical representation. We show that both µ and µ0 are an efficientiBF. To see this, first notice that there are only four individually rational and balanced
matchings. They are µ, µ0 ,µ00 =s1 s2 s3∅∅

i2 , i3

i1

∅

!
,

and the empty matching (i.e., the matching where no student is matched to any school).
The latter two matchings are Pareto dominated by µ and µ0 while µ and µ0 do not Pareto
dominate each other, and one can verify by inspection that both µ and µ0 are fair, andhence an efficient iBF.



11

Let us compare our notion of iBF with the standard notion of stability. Specifically, we
say that a matching µ is nonwasteful if there is no pair (i, s) of a student and a school suchthat s i µi , i s ∅, and |µs | < qs , and that µ is stable if it is individually rational, fair,and non-wasteful (but not necessarily balanced). A matching is the student-optimal
stable matching if it is stable and is weakly preferred to every stable matching by all
students. In the environment of Example 2, the unique stable matching (and hence thestudent-optimal stable matching) would be:µ000 =!
s1 s2 s3 ∅
i2

i3

i1 ∅

.

But µ000 is not balanced because the inflow to region r is 2 while the outflow from r is 1.
This example demonstrates that the balancedness condition is not necessarily compatible with stability. In Section 6.1, we characterize when those properties are compatible
with each other.
3. FIG (Fair Improvement Graph) Cycles
3.1. Definition of FIG Cycle. The key steps of our analysis involve defining bipartite
directed graphs over the sets of students and schools, and identifying cycles on them.
A bipartite directed graph on I and S, or simply a graph, G ⊆ (I × S) ∪ (S × I), isa set of ordered pairs of agents in I ∪ S. An interpretation is that if (i, s) ∈ G, thenthere is an arrow pointing from i to s. In this case, we say “i points to s.” The caseof (s, i) ∈ G is analogous. Given a graph G, a cycle in G is any sequence of the form
(i1 , s1 , i2 , s2 , . . . , im , sm ) such that for each k ∈ {1, . . . , m},(1) ik points to sk , i.e., (ik , sk ) ∈ G,(2) sk points to ik+1 , i.e., (sk , ik+1 ) ∈ G, where we set im+1 := i1 ,(3) ik 6= ik0 for all k 0 6= k, and(4) sk 6= sk0 for all k 0 6= k.
We will regard any two cycles as defined here, (i1 , s1 , . . . , im , sm ) and (ik+1 , sk+1 , . . . , im , sm , i1 , s1 , . . . , ik , sk ),as identical to each other.
Let Dsµ := {i ∈ I|s i µi }, and T ops (I 0 ) be the student i ∈ I 0 who has the highest
priority among those in I 0 at s .
Now we define a particular type of a graph and a cycle on it. This cycle will be used
to characterize efficient iBF as well as to define our algorithm.
Definition 3. Given a matching µ, the fair improvement graph (FIG) for µ is agraph such that, for any i ∈ I and s ∈ S,

12(1) student i ∈ I points to school s ∈ S if i = T ops (Dsµ ) and i is acceptable to s, and(2) school s ∈ S points to student i ∈ I if either(a) µi = s, or(b) |µs | < qs and, [i ∈ r(s) and µi = ∅] or µi ∈ r(s).
A fair improvement graph cycle (FIG cycle) on µ is a cycle in the FIG for µ.
A student i points to a school s when she finds s to be better than her current outcomeµi , and if she is acceptable to s and the best student for s among those who find s to be
an improvement (so, under our assumption of strict priorities, each school can be pointed
to by at most one student). In this sense, the students point to the schools in the mostfair manner, and this is why we call the graph the “fair improvement graph.”
On the other hand, a school s can point to a student i in two different cases. The firstcase is as in other algorithms based on cycles in the literature such as the Top Trading
Cycles (TTC) algorithm (Shapley and Scarf, 1974) and the stable improvement cycles
algorithm (Erdil and Ergin, 2008). This is when i is currently matched to s, and it
is described by part (2a) in Definition 3. The second case, described by part (2b) in
Definition 3, depends on the notion of regions. School s can point to i if s has a vacancy
and either i lives in the region of s and is unmatched, or i is matched to a school in theregion. The need for this second case and the logic behind this particular pointing rule
will become clear in a later example (Example 5 in Section 4).
Given a matching µ and a cycle of the form F = (i1 , s1 , i2 , s2 , . . . , im , sm ), call µ0 thematching generated by (µ, F) ifµ0ik = sk for each k ∈ {1, . . . , m}, and µ0j = µj for all j ∈ I \ {i1 , . . . , im }.
Given a matching µ and a cycle F, we say that we implement F on µ when we create
the matching generated by (µ, F).
As we will show in Section 4, whether there exists a FIG cycle is crucial to the characterization of efficient iBF. Also, in the algorithm we define in Section 5, we repeatedly
implement FIG cycles. But before stating the formal results that use the notion of FIG
cycles, let us illustrate the concept of FIG cycle through a series of examples in the next
subsection.
Remark 1. Erdil and Ergin (2017) consider a model with weak student preferences (andschool priorities) and propose to improve students’ welfare by using chains in addition
to cycles. A chain can start from a matched or unmatched student and ends at a schoolthat has a vacant seat. We could define a chain in our model too, while restricting thepointing from schools to students to the one described in part (2a) of Definition 3.

13

Figure 4. Example 2, Continued. The arrows represent the FIG. There
are two FIG cycles.

Let us be forthcoming about the similarity and difference between their chains and our
FIG cycles. First, in our model, implementing all chains and cycles under such a pointing
rule would violate balancedness (there is no such issue in Erdil and Ergin (2017) as they
have no balancedness constraint). For example, in Example 2, there would be one chain
going out of r (i1 → s3 ) while there would be two chains going into r (i2 → s1 andi3 → s2 ). As we will see in Theorem 1, balancedness is respected if we implement any
FIG cycle. Second, one might argue that “connecting” chains might work. That is, wewould start from a chain, and at the end of the chain (which is a school), we would findan unmatched student in the same region and see if there was a chain originating fromthat student. If there was such an arrow, then we would follow the arrows. Continuing
this way, if an arrow eventually pointed to a school that had already appeared, then wewould call the closed set of arrows a cycle. Cycles constructed in this way turns out tobe the same as our FIG cycles. One can view that our pointing rule from schools tostudents, especially the part described in part (2b) of Definition 3, correctly captures how
this “connecting” should be done. Third, the reasons behind why there are chains aredifferent. In Erdil and Ergin (2017), a chain is implemented on a stable matching. For
the existence of chains it is necessary that the student preferences are weak: if instead
the students’ preferences are strict, then the last student on the chain would have strictlypreferred to be matched to a vacant position in the last school in the chain under theoriginal matching, so the original matching was not stable. In our model, there can exista chain (defined in the absence of the pointing rule described in part (2b) of Definition 3)
because of the balancedness constraint.
3.2. Examples of FIG Cycle.

14

Figure 5.

Example 3. The thick and thin arrows represent the FIG

while the thick arrows represent a FIG cycle. School s2 ∈ r points to an
unmatched student i4 ∈ r because s2 ’s capacity is currently not full.
Example 2, Continued. Consider the same environment as in Example 2. The FIG
for µ00 is drawn in Figure 4. Note that there are two FIG cycles:
F := (i1 , s3 , i2 , s1 ) and F 0 := (i1 , s3 , i3 , s2 ).
Implementing the former cycle results in µ, and implementing the latter cycle results inµ0 . Note that, in this example, it is important that the pointing rule for FIG lets a school
point to a student matched to another school in the same region.12



Example 3 (Capacity matters for FIG cycle). Let I = {i1 , i2 , i3 , i4 }, S = {s1 , s2 , s3 },R = {r, r0 } where r = {i1 , i2 , i4 , s1 , s2 } and r0 = {i3 , s3 }. Schools s1 and s3 have thecapacity of one each while s2 has the capacity of two. Student preferences and school
priorities are given as follows:i1 : s1 ,

s1 : i1 , i2 , i3 , i4 ,

i2 : s2 , s1 ,

s2 : i2 , i3 ,

i3 : s1 , s2 ,

s3 : i 4 .

i4 : s1 , s3 ,Consider the following matching:µ=s1 s2 s3∅∅

i3 , i4

i1

i2

!
,

which, by inspection, one can show to be fair. This matching as well as the FIG for µ is
drawn in Figure 5. We note two features of this FIG. First, s2 points to an unmatched
12This is the point alluded to in footnote 9.

15

student i4 even though it is already matched with student i2 . This is because s2 ’s capacity
is not filled under µ: the capacity is 2 while it is matched to only one student (student
i2 ). Second, there are multiple arrows from student i3 . Although the rule for pointing
in a FIG implies that each school is pointed to by at most one student, one student canpoint to multiple schools if she is the “number one” choice from multiple schools. In thisexample, i3 ranks at the top among all students who prefer s1 to their current match (i.e.,among {i3 , i4 }), and she also ranks at the top among all students who prefer s2 to theircurrent match (i.e., among {i3 }). Note that there is a single FIG cycle:
F := (i3 , s2 , i4 , s3 ).
Implementing this cycle, we obtain the following matching:
!
s
s
s
∅
1
2
3
µ0 =
,
i1 i2 , i3 i4 ∅which is an improvement over µ and is fair. One can show by inspection that µ0 is also
an efficient iBF.


4. Characterization of Efficient iBF

This is the main section of this paper, and we are going to formalize the following
claims:(1) If we implement a FIG cycle on a given iBF µ, then it results in an iBF that
Pareto dominates µ (Theorem 1).
(2) If there is no FIG cycle on a given iBF µ, then µ is an efficient iBF (Theorem 2).
These results in particular imply the following characterization of efficient iBF: Given aniBF, it is an efficient iBF if and only if there is no FIG cycle on it (Corollary 1). In what
follows, we will examine each claim and explain their intuition in detail.
Theorem 1. Let µ be an iBF. If there exists a FIG cycle F on µ, then a matching
generated by (µ, F) is an iBF and Pareto dominates µ.
An implication of this theorem is that, if we can find a FIG cycle on a given iBF,then that matching cannot be an efficient iBF. Thus, one can think of this theorem asproviding a necessary condition for an iBF to be an efficient iBF.
We note that the proof shows a stronger result: Implementing a FIG cycle on anarbitrary matching µ (which is not necessarily an iBF) results in a matching that is (i)Pareto superior to µ, (ii) individually rational if µ is individually rational, (iii) fair if µ is
fair, and (iv) balanced if µ is balanced.

16

Figure 6. Why balancedness is maintained when a FIG cycle is implemented (proof intuition for Theorem 1).
Let us explain the intuition for the proof (of the stronger result above). For this, letµ be the original matching and µ0 be the matching generated by (µ, F) where F is a
FIG cycle on µ. The proof shows Pareto dominance, individual rationality, fairness andbalancedness one by one. First, it is straightforward that µ0 Pareto dominates µ by ourpointing rule for students. Second, this observation also implies that µ0 is individually
rational if µ is individually rational.
Third, fairness of µ0 is due to the pointing rule used in the FIG. A crucial step is toshow that no student has justified envy to student ik who is newly matched to sk underµ0 , where ik and sk appear in the FIG cycle (i.e., ik points to sk under the FIG).13 If
some student i finds sk to be better than her match under µ0 , then she should have also
found sk to be better than her match under µ (because µ0 Pareto dominates µ). But the
pointing rule for FIG implies that ik is the best student (according to sk ’s priority) among
those who found sk to be better than the match under µ. So, in particular, i is not higher
than ik under sk ’s priority. This implies that i cannot have justified envy to ik under µ0 .
Finally, balancedness of µ0 holds because the FIG cycle is “closed,” that is, for any
given region r, if an arrow from a student goes outside of r along the cycle, then anotherarrow from a student must come back to r and vice versa, which implies that the numberof times the arrows go outside must be equal to the number of times the arrows come backto r. Whether balancedness is maintained by implementing a cycle may not be obvious
13Justified envy to other students matched to s

k or those that involve other schools can be shown not0

to exist by using fairness of µ and the fact that µ Pareto dominates µ.

17Figure 7. Example 4. The thick and thin arrows represent the FIG. µ is aunique efficient iBF, and there is no FIG cycle such that implementing it onµ0 results in µ. Meanwhile, implementing a FIG cycle on µ0 (indicated bythick arrows in the left panel of the figure) results in µ0 , and implementinga FIG cycle on µ0 (indicated by thick arrows in the middle panel of the
figure) results in µ.

due to the fact that an outgoing arrow may carry a student who lives in r or one whodoes not live in r, and similarly an incoming arrow may carry either type of a student.
Figure 6 shows that in every possible case, balancedness is maintained when a cycle is
implemented.14 Feasibility would also be violated if an arrow that goes across regions
can originate from a school, a possibility that the definition of FIG prohibits. Example 5
illustrates this point.
Two remarks are in order. First, we note that Theorem 1 does not assert that implementing a FIG cycle on a balanced and fair matching necessarily results in an efficientiBF. Indeed, the following example presents a case in which one needs to implement FIG
cycles more than once to reach an efficient iBF.
Example 4 (Multiple rounds of FIG cycles). Let I = {i1 , i2 }, S = {s1 , s2 }, R = {r} .
Each school has the capacity of one. Student preferences and school priorities are given
14Hafalir, Kojima and Yenmez (2022) study TTC under a variety of constraints, one of which is thebalancedness constraints of the present paper. They verify that the balancedness constraints satisfy acondition called M-concavity, which Suzuki et al. (2023) showed is sufficient for the outcome of a certain
version of TTC to satisfy balancedness. Although their TTC algorithm is substantially different fromours, one might also be able to use a similar indirect approach to establish balancedness of the outcomeof our algorithm.

18

as follows:i1 : s2 , s1 ,

s1 : i1 , i2 ,

i2 : s1 , s2 ,

s2 : i2 , i1 .

Let µ0 be the empty matching. Starting from µ0 , there are three FIG cycles:
F := (i1 , s1 ), F 0 := (i2 , s2 ), and F 00 := (i1 , s1 , i2 , s2 ).
It is straightforward to see that there is a unique efficient iBF, which is!
s1 s2 ∅µ=.
i2 i1 ∅
However, µ is not a matching generated by (µ0 , F̃) where F̃ is either F, F 0 or F 00 . The
reason is that, for example, student i1 does not point to s2 in the FIG for µ0 because she
is not the top choice of s2 among those who point to s2 (s2 ’s top choice is i2 ).
The efficient iBF can be obtained by “two rounds of FIG cycles” starting from µ0 :First, implementing the FIG cycle F 00 on µ0 , we obtain:
!
s
s
∅
1
2
µ0 =
.
i1 i2 ∅
Second, implementing
F 000 := (i1 , s2 , i2 , s1 )on µ0 results in µ.

The second remark is about the pointing rule for FIG. Note that Theorem 1 asserts
that, among other things, implementing a FIG cycle on an iBF results in a balanced
matching. This property depends on a somewhat subtle manner in which we define theFIG, as the following example illustrates.
Example 5 (Pointing rule for FIG). Let I = {i1 , i2 }, S = {s1 , s2 , s3 }, R = {r, r0 } wherer = {i1 , s1 , s2 } and r0 = {i2 , s3 }. Each school has the capacity of one. Student preferences
and school priorities are given as follows:i1 : s2 , s3 , s1 ,

s1 : i1 , i2 ,

i2 : s1 , s2 ,

s2 : i2 , i1 ,
s3 : i 1 .

19Figure 8. Example 5. The solid arrows represent the FIG. Student i1 lives
in r and student i2 lives in r0 . If we allowed s1 to point to i1 (the dashedarrow) in the FIG and implemented the resulting cycle (i2 , s1 , i1 , s2 ), thebalancedness constraint would be violated.

Consider the following matching:µ=s1 s2 s3 ∅
∅

i2

i1 ∅

!
.

Note that this matching is a matching generated by (µ0 , F) where µ0 denotes the empty
matching and we let F := (i1 , s3 , i2 , s2 ). The cycle F is a FIG cycle and µ is fair.
Now, consider the FIG on µ, which is depicted in Figure 8 by solid arrows. Suppose that
we modify case (2b) of the definition of FIG (Definition 3) and hypothetically allow eachschool with a vacancy to point to any student that lives in the same region, irrespectiveof where that student is currently matched. This means that s1 points to i1 , although it is
not allowed in the FIG according to its pointing rule. This additional pointing is depictedby a dotted arrow in Figure 8. With this arrow, there is a cycle F 0 := (i1 , s2 , i2 , s1 ).
However, the matching generated by (µ, F 0 ) violates the balancedness constraint. The
reason is that implementing this cycle on µ would result in one less outflow for region r
while the inflow does not change. This happens because the arrow going out of regionr starts from a school, not a student. In the definition of the FIG, all arrows going outof regions are from students. As we explained when providing the intuition for the proofof balancedness in Theorem 1 (see Figure 6), this feature ensures that implementing any
FIG cycle on any balanced matching results in a balanced matching.

Theorem 2. Let µ be an iBF. µ is an efficient iBF if there exists no FIG cycle on µ.

20

Recall that Theorem 1 identifies a necessary condition for a given iBF to be an efficientiBF. Theorem 2 establishes that the same condition is in fact sufficient as well. Therefore, as we will formally state later in Corollary 1, combining those results provides acharacterization of an efficient iBF.
The proof is by contraposition. That is, we take µ that is an iBF and assume that
there is another iBF µ0 that Pareto dominates µ. Then we show that there exists a FIG
cycle on µ.
To find a FIG cycle, we construct a graph. In this graph, the students who are associatedwith arrows are those whose outcomes are different between µ and µ0 . We denote by I 0 theset of those students. Meanwhile, the schools with arrows are the ones that are matchedto students in I 0 under µ0 (which means that these are the schools that are matched tosome new students under µ0 relative to µ). We denote by S(µ0 ) the set of those schools.
Also, let S(µ) be the set of schools that students in I 0 are matched with under µ.
To understand the complication in the proof, consider first a simple case: there is asingle region r (i.e., a standard environment without a balancedness constraint), and µ isa stable matching (in the standard sense). Then, since stability implies non-wastefulness
and µ0 Pareto dominates µ, it follows that S(µ0 ) = S(µ). We can have each school s point
to students in µs ∩ I 0 , and allow a student in I 0 point to s if she is the top student among
I 0 who regard s to be an improvement relative to µ. This way, each school is pointed toby one student, and each student is pointed to by one school. Thus, there is a cycle, andwith some work, one can prove that such a cycle must be a FIG cycle. This is essentiallythe same method as what is used in Erdil and Ergin (2008).15
In our problem, complication arises for two reasons. First, fairness alone does not
imply non-wastefulness, so µ may have some waste (for example, consider the empty
matching µ0 in Example 4). This means that S(µ0 ) may not be equal to S(µ), so a graphconstructed in the above manner might not have a cycle (schools in S(µ0 ) \ S(µ) would
have no outgoing arrow, and those in S(µ) \ S(µ0 ) would have no incoming arrow). Thissuggests we need an alternative way of forming a graph. Second, arrows might go in andout of any region, hence in defining the alternative graph, we must make sure that thebalancedness constraint would be respected when implementing a cycle in the graph.
We overcome these difficulties by constructing a graph, denoted G(µ, µ0 ), in the following
manner. First, each school in S(µ0 ) is pointed to by the top student among those in I 0 who
15We note that Erdil and Ergin (2008) allow school priorities to be weak, while we assume strict

preferences here. However, as explained in Section 6.4, our analysis extends to the case with weakpriorities without any significant change.

21

Figure 9. Example 6. Given an iBF µ and a Pareto dominating iBF µ0 ,the proof of Theorem 2 constructs a cycle (represented by the thick arrows)
and shows that the constructed cycle is in fact a FIG cycle.
regard the school to be an improvement relative to µ, just as in the “simple case” above.
Second, each student i in I 0 is pointed to by a school in the following three different ways
depending on i’s outcome under µ:(1) If µi ∈ S(µ0 ), then we let µi point to i. This is the case that is analogous to the“simple case” explained above.
(2) If µi ∈ S \ S(µ0 ), then we can show, using individual rationality and balancedness,that we can find a school that resides in µi ’s region and belongs to S(µ0 ) whose
capacity is not filled under µ.16 We let such a school point to i.
(3) If µi = ∅, then we can show, again using individual rationality and balancedness,that we can find a school that resides in i’s region and belongs to S(µ0 ) whose
capacity is not filled under µ. We let such a school point to i.
Since each school is pointed to by one student, and each student is pointed to by one
school, G(µ, µ0 ) has a cycle. The proof shows that any cycle in this graph is a FIG cycle.
The next example illustrates how our construction works in a specific environment.

16Showing the existence of such a school is nontrivial.

The proof constructs an additional graph foreach region and uses that graph to establish the existence. See the Appendix for detail.

22

Example 6 (Construction of a FIG cycle). Let I = {i1 , i2 , i3 , i4 }, S = {s1 , s2 , s3 , s4 },R = {r, r0 } where r = {i1 , i2 , i3 , s1 , s2 , s3 } and r0 = {i4 , s4 }. School s2 has the capacityof two while all other schools have the capacity of one. Student preferences and school
priorities are given as follows:i1 : s2 , s1 ,

s1 : i1 ,

i2 : s4 , s2 ,

s2 : i2 , i3 , i1 , i4 ,

i3 : s2 ,

s3 : i4 ,

i4 : s2 , s3 ,

s4 : i2 .

Consider the following matchings:
µ=

s1

s2

i1 i2 , i3

s3 s4 ∅
∅

∅

i4

!
,

µ0 =

s3 s4 ∅s1s2∅

i1 , i3 i4

!

i2 ∅

.

They are both an iBF, and µ0 Pareto dominates µ.
Let us explain how to obtain the graph G(µ, µ0 ) and a FIG cycle in this environment(see Figure 9 for a graphical illustration). First, note that I 0 = {i1 , i2 , i4 }, S(µ) = {s1 , s2 },and S(µ0 ) = {s2 , s3 , s4 }. Recall that a student in I 0 points to a school in S(µ0 ) if and only
if she is the top student according to the school’s priority among those who prefer theschool to their current match. Hence, the edges originating at a student in G(µ, µ0 ) are(i1 , s2 ), (i2 , s4 ), and (i4 , s3 ). Next, we illustrate how a student is pointed to by a school.
(1) µi1 = s1 ∈ S \ S(µ0 ). This is case 2 of the aforementioned pointing rule from aschool to a student. School s3 is the only school that resides in µi1 ’s region r andbelongs to S(µ0 ) whose capacity is not filled under µ. Thus, (only) s3 points to i1 .
(2) µi2 = s2 ∈ S(µ0 ). This is case 1 of the pointing rule, and thus s2 points to i2 .
(3) µi4 = ∅. This is case 3 of the pointing rule. School s4 is the only school that
resides in i4 ’s region r0 and belongs to S(µ0 ) whose capacity is not filled under µ.
Thus, (only) s4 points to i4 .
Overall, the graph G(µ, µ0 ) can be drawn as in Figure 9. There is a unique cycle on
G(µ, µ0 ), which is (i1 , s2 , i2 , s4 , i4 , s3 ). One can check that this is a FIG cycle as well.
We note a special feature of this example: Given an iBF µ and a Pareto dominating
iBF µ0 , implementing a FIG cycle on µ constructed in the proof results in µ0 . This featureturns out not to hold generally. This fact can be seen in Example 4, where two steps of
FIG cycle implementations may be necessary to move between two iBFs.



Theorem 1 and Theorem 2 together imply the following characterization of efficient iBF23

Corollary 1. Let µ be an iBF. µ is an efficient iBF if and only if there exists no FIG
cycle on µ.
5. FIG Cycles Algorithm
Let µ̃ be an arbitrary iBF, e.g., the empty matching. Building on Corollary 1, we definea FIG cycles algorithm on µ̃ as follows.
FIG Cycles Algorithm on µ̃:
Step 0: Let µ0 = µ̃ and move to Step 1.
Step l (l ≥ 1): If there is no FIG cycle on µl−1 , terminate the algorithm and outputµl−1 . Otherwise, choose a FIG cycle F on µl−1 arbitrarily and let µl be the matching
generated by (µl−1 , F), and go to Step l + 1.
Corollary 2. Let µ̃ be an arbitrary iBF. The FIG cycles algorithm on µ̃ runs in polynomial time, and its output is an efficient iBF.
Proof. Take an arbitrary iBF and denote it by µ̃. Theorems 1 and 2 together show thatthe output of the FIG cycles algorithm on µ̃ is an efficient iBF. To show that the algorithm
runs in polynomial time, first note that each student can only become better off whilerunning the algorithm, and at least one student must be made strictly better off at eachstep as long as the algorithm does not terminate in that step. Therefore, at most |I| × |S|
steps are necessary for terminating the algorithm. Second, within each step, finding a FIG
cycle can be done in polynomial time.17 These two observations show that the algorithm
runs in polynomial time, as desired.



In some applications, a school may give a higher priority to residents of that school’s
region than non-residents. Let us now consider such a case. Formally, assume that i s jfor each r ∈ R, s ∈ r, i ∈ r, and j 6∈ r.
We consider a special fair matching, namely the matching that is produced by running
the standard deferred acceptance algorithm of Gale and Shapley (1962), separately ineach region. Formally, it is defined as follows.
Definition 4. A region-wise student-optimal stable matching µRW is a matchingthat satisfies the following:(1) For each r ∈ R and each i ∈ r, we have µRW∈ r ∪ {∅}.
i(2) µRW is individually rational.
17There are well-known polynomial-time algorithms that identify a cycle if one exists and otherwise

show that there is no cycle. The “depth-first search” algorithm, for example, has the running time ofO(|I| × |S|) (Cormen et al., 2001).

24(3) For each r ∈ R, there is no pair of a student and a school i, s ∈ r such thats i µRW, i s ∅, and |µRW
| < qs .
is(4) For each r ∈ R, there is no pair of students i, i0 ∈ r such that i has justified envy
to i0 under µRW .
(5) µRW weakly Pareto dominates all matchings that satisfy conditions (1), (2), (3)and (4).
Intuitively, a region-wise student-optimal stable matching requires that a matching
restricted to each region (i.e., consider the students and schools that reside in that region)
is a student-optimal stable matching in the standard sense (Conditions (2), (3), and (4)correspond to individual rationality, non-wastefulness, and fairness within each region).
By Gale and Shapley (1962), a region-wise student-optimal stable matching always exists,
and it can be obtained by their deferred acceptance algorithm in polynomial time.
We note that µRW is an iBF. To see this, first note that µRW is individually rational(Condition (2)). Second, it is balanced because no student is matched to a school outsideof her region (Condition (1)), and thus both the inflow and outflow for any given region
is equal to zero. Third, µRW is fair by Condition (4) and the assumption in this sectionthat schools rank students from the same region higher than those from other regions (soa student living in r cannot have justified envy to another student living in r0 if the latterstudent is matched to a school in r0 ).18
The next corollary considers the case when we run a FIG cycles algorithm starting fromthis matching.
Corollary 3. The output of a FIG cycles algorithm starting from the region-wise studentoptimal stable matching µRW is an efficient iBF and weakly Pareto dominates µRW .
Proof. Let µRW be the region-wise student-optimal stable matching. Note that it is an
iBF as we have explained after providing the statement of Definition 4. Hence, Corollary 2
implies that the output of a FIG cycles algorithm starting from µRW is an efficient iBF.
Finally, Theorem 1 and the definition of FIG cycles algorithm imply that the output
Pareto dominates µRW .



18We wrote Definition 4 following the most standard way, but some conditions and qualifiers are

redundant because condition (5) holds and, as we explained, µRW is fair. A simplified (equivalent)
definition requires the following three conditions:(1) For each r ∈ R and each i ∈ r, we have µRW∈ r ∪ {∅}.
i(4’) µRW is fair.
(5’) µRW weakly Pareto dominates all matchings that satisfy conditions (1) and (4’).

25

6. Discussions
This section provides a number of discussions. In Section 6.1, we characterize whenbalancedness and stability are compatible with each other. Section 6.2 examines thestrategic properties. In Section 6.3, we provide comparative statics to evaluate the effectof merging and splitting regions. Section 6.4 considers the case with weak priority, which
often arises in school choice applications. In Section 6.5, we review the related literature.
6.1. Balancedness and Stability. As discussed in Section 2.2, Example 2 demonstrates
that the balancedness condition is not necessarily compatible with stability. This observation leads to the question of when those properties are compatible with each other.
The following result provides a characterization and establishes, in particular, that thosecases exactly coincides with cases in which the unique efficient iBF is the student-optimal
stable matching.
Theorem 3. The following statements are equivalent.
(1) There exists a unique efficient iBF, and it coincides with the student-optimal stablematching.
(2) There exists a stable and balanced matching.
(3) Every stable matching is balanced.
Proof. (1) → (2): Obvious.
(2) → (3): Let µ and µ0 be two stable matchings. Define a graph as follows. The set ofnodes are I and S. We let each s ∈ S point to i ∈ I if µi = s and let each i ∈ I points ∈ S if µ0i = s. By the rural hospital theorem (Roth, 1986), for each school s, the numberof arrows that point to s is equal to the number of arrows that point from s and, for each
student i, the number of arrows that point to i is equal to the number of arrows thatpoint from i. Therefore, the graph is partitioned into sets of edges that correspond to a
finite number of disjoint cycles such that µ0 is generated by implementing all those cycles
on µ.19 Thus, by an argument analogous to the proof of Theorem 1, if µ is balanced, thenµ0 is balanced as well.
(3) → (1): Suppose that every stable matching is balanced. We first observe that thestudent-optimal stable matching µ∗ is stable and hence balanced. By Wu and Roth
19Formally, let F , . . . F
1

0
`
`−1
, F` ) for eachk be the set of cycles. Let µ := µ and µ be generated by (µ0k` = 1, . . . , k. Then it follows that µ = µ .

26(2018), for any matching µ that is individually rational and fair, µ∗i i µi for all i ∈ I.
Therefore, µ∗ is a unique efficient iBF.

6.2. Strategic Property. In this section, we investigate strategic properties. It turns
out that our mechanism based on the FIG cycles algorithm is not strategy-proof. In fact,
we show that there is no strategy-proof mechanism that always outputs an efficient iBF.
Formally, a mechanism ϕ is a function from the set of student preference profiles to theset of matchings. Mechanism ϕ is strategy-proof if
ϕi () i ϕi (0i , −i ),for every student preference profile , i ∈ I, and student preference 0i .
Theorem 4. There exists no strategy-proof mechanism that outputs an efficient iBF for
all preference profiles.
Proof. We prove the result by presenting an example. Let I = {i1 , i2 , i3 } and S ={s1 , s2 , s3 }. Let there be two regions, r = {i1 , i2 , s1 } and r0 = {i3 , s2 , s3 }. Each school has
the capacity of one. Student preferences and school priorities are given as follows:i1 : s2 ,

s1 : i1 , i2 , i3 ,

i2 : s3 ,

s2 : i3 , i2 , i1 ,

i3 : s1 ,

s3 : i3 , i1 , i2 .

In this environment, there are two efficient iBFs:!
s1 s2 s3 ∅
µ=
,
µ0 =
i3 i1 ∅ i2

s1 s2 s3 ∅
i3

∅

i2 i1

!
.

Fix a mechanism ϕ that outputs an efficient iBF for all preference profiles. It must beeither ϕ() = µ or ϕ() = µ0 .
Suppose ϕ() = µ. Then, consider 0i2 : s3 , s2 . The unique efficient iBF at 0 := (0i2, −i2 ) is µ0 , so ϕ(0 ) = µ0 . Noting that µ0i2 = s3 i2 ∅ = µi2 , we have obtained that
ϕi2 () 6i2 ϕi2 (0i2 , −i2 ), violating strategy-proofness.
Next, suppose ϕ() = µ0 . Then, by considering 0i1 : s2 , s3 and following a symmetricargument, we conclude that ϕ is not strategy-proof. This completes the proof.



Theorem 4 shows a sense in which the lack of strategy-proofness is not a drawback of
the FIG cycles algorithm. Rather, it is inevitable in that any mechanism that outputs anefficient iBF necessarily fails to be strategy-proof.

27

6.3. Comparative Statics. Intuition suggests that merging regions will lead to a more
efficient matching while splitting regions will have the opposite effect. To explore thisintuition, first consider the case where all regions were merged, that is, the union of all
regions in the original model is regarded as a single region after the mergers. In thiscase, there would be a unique efficient iBF, which coincides with the student-optimal
stable matching. This matching weakly Pareto dominates any individually rational andfair matching, and hence any efficient iBF under any structure of regions. However, as
we have argued in the Introduction, merging all regions may be impractical. A questionof interest is whether mergers generally result in a more efficient matching even if there
remain multiple regions after the mergers.
We say that an environment E = (I, S, (a )a∈I∪S , (qs )s∈S , R) is a result of mergers
from another environment E 0 = (I 0 , S 0 , (0a )a∈I 0 ∪S 0 , (qs0 )s∈S 0 , R0 ) if I = I 0 , S = S 0 , a =0a
for every a ∈ I ∪ S, qs = qs0 for every s ∈ S and, for each r ∈ R, r is a union of (possiblyone) regions of R0 . That is, some regions in E 0 merge to form a region in E, but otherwise
all the primitives are unchanged between the two environments.
In the following simple example, merging regions Pareto-improves the outcomes forstudents.
Example 7 (An instance in which merging regions makes every student better off). Let
I = {i} and S = {s}. Let there be two regions, r = {i}, and r0 = {s}.20 School s has thecapacity of one. Student i finds school s to be acceptable and school s finds student i tobe acceptable. In this environment, there is a unique efficient iBF:
!
s ∅
µ=
.
∅ i
If regions r1 and r2 are merged, then there is a unique efficient iBF:
!
s
∅
µ0 =
.
i ∅
Since µ0i i µi and i is the only student in the market, this means that merging the regions
made every student strictly better off in this example. The intuition is simple: The merge
reduced the constraint of balanced exchange between regions r and r0 , so after the merger,
the student i can go to school s.
It turns out that the finding of this example is not a coincidence. Indeed, the next
proposition establishes a comparative statics regarding any mergers.
20In this example, region r does not have a school and region r 0 does not have a student.

features are not necessary to make our point.

These

28

Proposition 1. Suppose that E is a result of mergers from E 0 . Then, for any matchingµ0 that is an efficient iBF at E 0 , there exists a matching µ that is an efficient iBF at E
such that µ weakly Pareto dominates µ0 .
Proof. We first show that µ0 is an iBF at E. Individual rationality and fairness are obvious.
The following claim is proved in Appendix A.3:
Claim 1. µ0 is balanced at E.
The preceding arguments have established that µ0 is an iBF at E. Therefore, by definition of an efficient iBF, there exists a matching µ that is an efficient iBF at E such that
µ weakly Pareto dominates µ0 .

We note that a kind of converse of Proposition 1 does not hold. Specifically, Example 8
in Appendix A.4 presents an instance in which, starting at a certain efficient iBF, somestudent is made strictly better off in any efficient iBF after splitting a region.
To summarize, the analysis in this section confirmed the intuition that merging regions
improves student welfare. We also found that, however, a precise sense in which thisintuition goes through is somewhat subtle.
6.4. Weak Priorities. In applications such as daycare allocations and school choice,schools are sometimes endowed with weak priorities. Erdil and Ergin (2008) consider
weak priorities and propose an algorithm based on cycles to improve upon the deferred
acceptance algorithm with tie-breaking, albeit in a setting without our balancedness constraints. Accordingly, a natural question would be whether our analysis extends to cases
where priorities are allowed to be weak in the presence of balancedness constraints. As
it turns out, all of our results go through. In particular, the conclusions of Theorems 1
and 2 hold without any change.21
Here we illustrate how the proofs of Theorems 1 and 2 change with weak priorities. The
only difference from the case of strict priorities is the following. In the FIG or G(µ, µ0 )(a graph which appears in the proof of Theorem 2), each school can be pointed to by atmost one student. This was because a student can point to a school only if she is the top
student among those who regard the school as an improvement. Under strict priorities,
there is a unique “top” student, which was why each school can be pointed to by at mostone student. Under weak priorities, however, there can be multiple “top” students, so
21Under weak priority, we say that a student is acceptable to a school if she is ranked weakly higher thanthe outside option, and modify the definitions of individual rationality, efficient iBF and FIG by adopting
this definition of acceptability in the relevant parts of those concepts. The proofs change accordingly ina straightforward manner.

29

a school can be pointed to by multiple students. But this change does not affect theremainder of the proof.
6.5. Related Literature. The aim of our study is to improve efficiency in situations
in which matching is organized at a small local level. Sharing this interest with thepresent paper, Hafalir, Kojima and Yenmez (2022) study a variety of constraints in thecontext of interdistrict school choice, and one of the constraints studied there is thebalancedness constraint. Differently from our analysis, they study conditions under which
the outcome of the standard deferred acceptance algorithm satisfies the constraint, whichturns out to be very restrictive. The present paper offers a way to improve upon matchingmechanisms organized separately in each district even if the deferred acceptance algorithm
does not produce a balanced matching. To our knowledge, the balancedness condition
was introduced and studied first by Dur and Ünver (2019), although the setting of tuition
exchange they study is different from ours or Hafalir, Kojima and Yenmez (2022) in several
important respects, making their analysis and ours logically unrelated.
Our algorithm is based on a number of Pareto-improving cycles among students andschools. At a high level, this is a common idea and is shared by many other algorithms,
including Gale’s celebrated TTC algorithm in Shapley and Scarf (1974). The difference of
our algorithm from TTC is that we construct cycles in a more subtle and nuanced manner,
taking school priorities into account in particular, so that implementing the cycles willkeep fairness of the original matching. Closer to our algorithm are those due to Erdiland Ergin (2008, 2017) who, like us, provide iterative algorithms that improve efficiency
while retaining fairness.22 Similarities and differences between those studies and ours areillustrated in detail in Section 1.1, Remark 1 in Section 3.1, and Section 4.
This paper can be regarded as part of the literature in matching with constraints.
Research in this literature include Abdulkadiroğlu (2005), Ergin and Sönmez (2006), andHafalir, Yenmez and Yildirim (2013) for school choice, Abraham, Irving and Manlove(2007) for project allocation, Westkamp (2013) and Aygün and Turhan (2020) for college
admission, Pathak et al. (2021) on pandemic resource allocation, and Kamada and Kojima(2015, 2017, 2018, 2023), Goto et al. (2014), and Biro et al. (2010) on labor markets.23 The
main departure of the present paper is that we consider integration of multiple markets,
while those earlier contributions treat the relevant market as given.
22Algorithms based on analogous ideas have been adapted to other settings by, for example, Combe,

Tercieux and Terrier (2022), Combe et al. (2022), and Erdil and Kumano (2019).
23See also Kojima, Tamura and Yokoo (2018) who explore connection between matching with constraints and convexity and concavity notions in discrete mathematics.

30

The main applications of the present paper is allocation of daycare seats. Researchin daycare allocation in the matching literature include Kennes, Monte and Tumennasan(2014), Veski et al. (2017), Herzog and Klein (2018), Okumura (2019), Delacrétaz (2019),
and Kamada and Kojima (2023). While those papers and ours share interest in daycare,the overlap is rather limited, as none of those papers analyzes models with multiple regions
as we do.

7. Conclusion
This paper studied a school-choice matching model that allows for ekkyo admission(inter-regional transfer of students). To accommodate practical concerns, we provided
solutions for partial integration, namely a mechanism that satisfies the balancedness constraint. Given any matching, we defined a directed bipartite graph (the “FIG”) in which
the nodes represent students and schools while the edges are constructed using student
preferences, school priorities, and the information about the current matching. Using thisgraph, we characterized the set of efficient iBFs (individually rational, balanced, and fair
matchings) by non-existence of a cycle that would improve the welfare of the students
involved in the cycle. This led us to define the FIG cycles algorithm that computes anefficient iBF in polynomial time. In terms of application, our analysis provided a way to
improve upon mechanisms organized in a fragmented manner.
Market fragmentation is prevalent in real markets: for example, in the City of Tokyo,
each of the 23 municipalities independently organizes a daycare matching market. We
started discussions with some of those municipalities about possible implementation of
our FIG cycles algorithm. One of the appealing features of our method is that it does not
require the 23 municipalities to fully integrate with one another: It would be impracticalto require that transfer of students be allowed between different municipalities without
restrictions. We, by contrast, only require partial integration where transfer can be madeto the extent that the balancedness condition is respected. Given our experience withpractitioners in daycare policies, we view such partial integration to be a practical solution.

References
Abdulkadiroğlu, A. 2005. “College admissions with affirmative action.” International
Journal of Game Theory, 33(4): 535–549.
Abdulkadiroğlu, Atila, and Tayfun Sönmez. 2003. “School Choice: A Mechanism
Design Approach.” American Economic Review, 93: 729–747.

31

Abraham, D. J., R.W. Irving, and D.F. Manlove. 2007. “Two algorithms for the
student-project allocation problem.” Journal of Discrete Algorithms, 5: 73–90.
Agarwal, Nikhil, Itai Ashlagi, Eduardo Azevedo, Clayton R Featherstone, andÖmer Karaduman. 2019. “Market failure in kidney exchange.” American Economic
Review, 109(11): 4026–70.
Aygün, Orhan, and Bertan Turhan. 2020. “Dynamic reserves in matching markets.”
Journal of Economic Theory, 188: 105069.
Balinski, Michel, and Tayfun Sönmez. 1999. “A tale of two mechanisms: student
placement.” Journal of Economic theory, 84(1): 73–94.
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(34-36): 3136–3153.
Combe, Julien, Olivier Tercieux, and Camille Terrier. 2022. “The design of teacher
assignment: Theory and evidence.” The Review of Economic Studies, 89(6): 3154–3222.
Combe, Julien, Umut Mert Dur, Olivier Tercieux, Camille Terrier, andM Utku Ünver. 2022. Market Design for Distributional Objectives in (Re) assignment:
An Application to Improve the Distribution of Teachers in Schools. MIT Departmentof Economics.
Cormen, Thomas H, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.
2001. Introduction to Algorithms. MIT Press and McGraw-Hill.
Delacrétaz, David. 2019. “Stability in matching markets with sizes.” Working paper.
Dur, Umut Mert, and M Utku Ünver. 2019. “Two-sided matching via balanced
exchange.” Journal of Political Economy, 127(3): 1156–1177.
Erdil, Aytek, and Haluk Ergin. 2008. “What’s the Matter with Tie-Breaking? Improving Efficiency in School Choice.” American Economic Review, 98: 669–689.
Erdil, Aytek, and Haluk Ergin. 2017. “Two-sided matching with indifferences.” Journal of Economic Theory, 171: 268–292.
Erdil, Aytek, and Taro Kumano. 2019. “Efficiency and stability under substitutablepriorities with ties.” Journal of Economic Theory, 184: 104950.
Ergin, Haluk, and Tayfun Sönmez. 2006. “Games of School Choice under the Boston
Mechanism.” Journal of Public Economics, 90: 215–237.
Gale, David, and Lloyd S. Shapley. 1962. “College Admissions and the Stability of
Marriage.” American Mathematical Monthly, 69: 9–15.
Goto, Masahiro, Atsushi Iwasaki, Yujiro Kawasaki, Yosuke Yasuda, and32

Makoto Yokoo. 2014. “Improving Fairness and Efficiency in Matching with Distributional Constraints: An Alternative Solution for the Japanese Medical Residency
Match.” https://mpra.ub.uni-muenchen.de/53409/1/MPRA paper 53409.pdf, last accessed on October 13, 2023.
Hafalir, Isa E, Fuhito Kojima, and M Bumin Yenmez. 2022. “Interdistrict school
choice: A theory of student assignment.” Journal of Economic Theory, 201: 105441.
Hafalir, Isa E, M Bumin Yenmez, and Muhammed A Yildirim. 2013. “Effective
affirmative action in school choice.” Theoretical Economics, 8(2): 325–363.
Herzog, Sabrina, and Thilo Klein. 2018. “Matching Practices for Childcare–
Germany.”

http://www.matching-in-practice.eu/matching-practices-for-childcare-germany/.
Kamada, Yuichiro, and Fuhito Kojima. 2015. “Efficient Matching under Distributional Constraints: Theory and Applications.” American Economic Review, 105(1): 67–
99.
Kamada, Yuichiro, and Fuhito Kojima. 2017. “Stability concepts in matching with
distributional constraints.” Journal of Economic Theory, 168: 107–142.
Kamada, Yuichiro, and Fuhito Kojima. 2018. “Stability and Strategy-Proofnessfor Matching with Constraints: A Necessary and Sufficient Condition.” Theoretical
Economics, 13: 761–793.
Kamada, Yuichiro, and Fuhito Kojima. 2023. “Fair Matching under Constraints:
Theory and Applications.” Forthcoming, The Review of Economic Studies.
Kennes, John, Daniel Monte, and Norovsambuu Tumennasan. 2014. “The day
care assignment: A dynamic matching problem.” American Economic Journal: Microeconomics, 6(4): 362–406.
Kojima, Fuhito, Akihisa Tamura, and Makoto Yokoo. 2018. “Designing Matching
Mechanisms under Constraints: An Approach from Discrete Convex Analysis.” Journalof Economic Theory, 176: 803–833.
Okumura, Yasunori. 2019. “School choice with general constraints: a market design
approach for the nursery school waiting list problem in Japan.” The Japanese Economic
Review, 70: 497–516.
Pathak, Parag A, Tayfun Sönmez, M Utku Ünver, and M Bumin Yenmez. 2021.
“Fair allocation of vaccines, ventilators and antiviral treatments: leaving no ethicalvalue behind in health care rationing.” Forthcoming, Management Science.
Roth, Alvin E. 1986. “On the allocation of residents to rural hospitals: a general property of two-sided matching markets.” Econometrica, 54(2): 425–427.

33

Shapley, Lloyd, and Herbert Scarf. 1974. “On cores and indivisibility.” Journal ofmathematical economics, 1(1): 23–37.
Suzuki, Takamasa, Akihisa Tamura, Kentaro Yahiro, Makoto Yokoo, andYuzhe Zhang. 2023. “Strategyproof allocation mechanisms with endowments and Mconvex distributional constraints.” Artificial Intelligence, 315: 103825.
Veski, André, Péter Biró, Kaire Pöder, and Triin Lauri. 2017. “Efficiency andfair access in kindergarten allocation policy design.” The Journal of Mechanism andInstitution Design, 2(1): 57–104.
Westkamp, Alexander. 2013. “An Analysis of the German University Admissions System.” Economic Theory, 53(3): 561–589.
Wu, Qingyun, and Alvin E Roth. 2018. “The lattice of envy-free matchings.” Gamesand Economic Behavior, 109: 201–211.

34

Appendix A. Proofs
A.1. Proof of Theorem 1.
Proof. Fix µ and a FIG cycle F = (i1 , s1 , i2 , s2 , . . . , im , sm ) on µ. Let µ0 be the matchingthat is generated by (µ, F). Clearly, µ0 Pareto dominates µ.
To show that µ0 is fair, notice that µ0i i µi for all i ∈ I by the definition of FIG
cycle. This implies that, for every i 6∈ {i1 , . . . , im }, no one has justified envy to i underµ0 because µ is fair. Thus, it remains to show that for each k ∈ {1, . . . , m}, no one hasjustified envy to ik under µ0 . To see this, note that, again by µ0i i µi for all i ∈ I, s i µ0i0implies s i µi . Hence, Dsµ ⊆ Dsµ for any s ∈ S (and thus in particular for s = sk ).24
0

Since ik = T opsk (Dsµk ) for each k by definition, this implies i 6sk ik for every i ∈ Dsµk .
Hence, no one has justified envy to ik under µ0 .
To show that µ0 is balanced, consider a sequence (r1 , . . . , rm ) such that sk ∈ rk for eachk. Fix r ∈ R and let K(r) = {k ∈ {1, . . . , m}|rk = r}. If K(r) = ∅, then (2.1) is satisfied
for r under µ0 because it is satisfied for r under µ. So suppose K(r) 6= ∅. Let
Inr = {k ∈ K(r)|rk−1 6= r} and Outr = {k ∈ K(r)|rk+1 6= r}.
Clearly we must have |Inr | = |Outr |. Define In0r ⊆ Inr and Out0r ⊆ Outr by
In0r = {k ∈ K(r)|rk−1 6= r and ik ∈ r} and Out0r = {k ∈ K(r)|rk+1 6= r and ik+1 ∈ r}.
On the one hand, the inflow to r has changed from µ to µ0 by(|Inr | − |In0r |)|{z}(|Outr | − |Out0r |)
|
{z
}

−

the number of non-r students
coming to r.

the number of non-r students
going out of r

On the other hand, the outflow from r has changed from µ to µ0 by|Out0r || {z }

the number of r students
going out of r

|In0 || {zr}−.

the number of r students
coming to r

Note that these two values are equal because |Inr | = |Outr |. Finally, since (2.1) holds forr under µ, this implies that (2.1) holds for r under µ0 .
To show that individual rationality of µ implies individual rationality of µ0 , note firstthat µ0i  ∅ for each i ∈ I because µ is individually rational and µ0 Pareto dominates µ.
Moreover, i s ∅ for every s ∈ S and i ∈ µ0s because (i) i s ∅ for every i ∈ µ0s ∩ µs by
the assumption that µ is individually rational, while (ii) i s ∅ for every i ∈ µ0s \ µs by
the definition of FIG (more specifically, part (1) of Definition 3).
24Recall that, for any matching µ̃ and school s, D µ̃ = {j ∈ I|s sj µ̃j }.



35

A.2. Proof of Theorem 2.
Proof. We prove the contraposition, so fix an iBF µ and assume that there exists an iBFµ0 that Pareto dominates µ.
Lemma 1. For any r ∈ R, |{i ∈ I|µi ∈ r, µ0i 6∈ r}∪{i ∈ r|µi = ∅, µ0i ∈ r0 for some r0 6= r}|is equal to |{i ∈ I|µi ∈ r0 for some r0 6= r, µ0i ∈ r} ∪ {i ∈ I \ r|µi = ∅, µ0i ∈ r}|.
Proof. Since µ and µ0 are both balanced, the change (from µ to µ0 ) of the inflow of students
to r and the change of the outflow are the same as each other. The change of the inflow
is:|{i ∈ I \ r|µi ∈ r0 for some r0 6= r, µ0i ∈ r}| + |{i ∈ I \ r|µi = ∅, µ0i ∈ r}| − |{i ∈ I \ r|µi ∈ r, µ0i 6∈ r}| .
|
{z
} |
{z
} |
{z
}
the number of non-r students
coming from an outside school to r

the number of non-r students
coming from being unmatched to r

the number of non-r students
going out of r

The change of the outflow is:|{i ∈ r|µi ∈ r, µ0i ∈ r0 for some r0 6= r}| + |{i ∈ r|µi = ∅, µ0i ∈ r0 for some r0 6= r}|
{z
}
{z
}
|
|
the number of r students
going out of r

the number of r students
who was unmatched but is now matched to a non-r school− |{i ∈ r|µi ∈ r0 for some r0 6= r, µ0i 6∈ r0 for all r0 6= r}| .
|{z}the number of r students
who was matched to a non-r school but now is notThus, we have:(A.1)|{i ∈ r|µi ∈ r, µ0i ∈ r0 for some r0 6= r}| + |{i ∈ r|µi = ∅, µ0i ∈ r0 for some r0 6= r}|
{z
}
{z
}
|
|
the number of r students
going out of r

the number of r students
who was unmatched but is now matched to a non-r school+ |{i ∈ I \ r|µi ∈ r, µ0i 6∈ r}| ={z}|the number of non-r students
going out of r|{i ∈ I \ r|µi ∈ r0 for some r0 6= r, µ0i ∈ r}| + |{i ∈ I \ r|µi = ∅, µ0i ∈ r}|
|
{z
} |
{z
}
the number of non-r students
coming from an outside school to r

the number of non-r students
coming from being unmatched to r

+ |{i ∈ r|µi ∈ r0 for some r0 6= r, µ0i 6∈ r0 for all r0 6= r}| .
|{z}the number of r students
who was matched to a non-r school but now is not
Now, recall that µ is individually rational. Hence, µ0i i µi i ∅ for every i, and thus wehave that µi ∈ r implies µ0i 6= ∅. Therefore,{i ∈ r|µi ∈ r, µ0i ∈ r0 for some r0 6= r} = {i ∈ r|µi ∈ r, µ0i 6∈ r}
Also, for the same reason, we have{i ∈ r|µi ∈ r0 for some r0 6= r, µ0i 6∈ r0 for all r0 6= r} = {i ∈ r|µi ∈ r0 for some r0 6= r, µ0i ∈ r}.

36

Hence, (A.1) is equivalent to|{i ∈ r|µi ∈ r, µ0i 6∈ r}|+|{i ∈ r|µi = ∅, µ0i ∈ r0 for some r0 6= r}|+|{i ∈ I\r|µi ∈ r, µ0i 6∈ r}| =|{i ∈ I \ r|µi ∈ r0 for some r0 6= r, µ0i ∈ r}| + |{i ∈ I \ r|µi = ∅, µ0i ∈ r}|+|{i ∈ r|µi ∈ r0 for some r0 6= r, µ0i ∈ r}|,or|{i ∈ I|µi ∈ r, µ0i 6∈ r}| + |{i ∈ r|µi = ∅, µ0i ∈ r0 for some r0 6= r}| =|{i ∈ I|µi ∈ r0 for some r0 6= r, µ0i ∈ r}| + |{i ∈ I \ r|µi = ∅, µ0i ∈ r}|.
Since the two terms in each side of the above equation are disjoint from each other, wehave|{i ∈ I|µi ∈ r, µ0i 6∈ r} ∪ {i ∈ r|µi = ∅, µ0i ∈ r0 for some r0 6= r}| =|{i ∈ I|µi ∈ r0 for some r0 6= r, µ0i ∈ r} ∪ {i ∈ I \ r|µi = ∅, µ0i ∈ r}|.
This completes the proof.

Consider the following graph, in which the only agents associated with arrows are theschools in r and students who are matched to a school in r under µ and students living inr who are unmatched under µ. First, each s ∈ r points to each student i ∈ µs \ µ0s . Then,for each student who was pointed to by some school in r and each student living in r who
are unmatched under µ, let her point to the school µ0i if µ0i ∈ r. Moreover, by Lemma 1,
there is a one-to-one and onto mapping from {i ∈ I|µi ∈ r, µ0i 6∈ r} ∪ {i ∈ r|µi = ∅, µ0i ∈r0 for some r0 6= r} to {i ∈ I|µi ∈ r0 for some r0 6= r, µ0i ∈ r} ∪ {i ∈ I \ r|µi = ∅, µ0i ∈ r}.
Take one such mapping φ. Then, for each i ∈ {i ∈ I|µi ∈ r, µ0i 6∈ r} ∪ {i ∈ r|µi = ∅, µ0i ∈r0 for some r0 6= r}, let i point to µ0φ(i) . This defines a directed graph, denoted G(µ, µ0 , r).
By construction, only schools in r, students matched to a school in r under µ, and thestudents of r who are unmatched under µ may be associated with arrows in this graph.
Let I 0 := {i ∈ I|µ0i i µi }. By the assumption that µ0 Pareto dominates µ, we haveI 0 6= ∅. For any matching µ̃, let S(µ̃) := {s ∈ S|s = µ̃i for some i ∈ I 0 }.
Lemma 2. Suppose s ∈ S(µ) \ S(µ0 ). Then there exists a school s0 ∈ r(s) ∩ S(µ0 ) suchthat |µs0 | < qs0 .
Proof. Take an arbitrary s such that s ∈ S(µ) \ S(µ0 ) (If there is no such school, we aredone). Starting from this school, follow the arrows in G(µ, µ0 , r(s)) in an arbitrary mannerwithout passing the same student twice (note that there is an outgoing arrow from s).
Since there are a finite number of students, there is s0 such that there is no more outgoingarrow from s0 to a student who has not appeared in the path (note that, by definition,

37

this path cannot end at any student). Because s 6∈ S(µ0 ) and hence s0 6= s, the numberof incoming arrows to s0 is greater than that of outgoing arrows from s0 along this path.
This implies that the number of students who are in µ0s0 \ µs0 is larger than the numberof students who are in µs0 \ µ0s0 by at least one. Hence, we have qs0 ≥ |µ0s0 | > |µs0 |. Sinces0 ∈ r(s) and s0 ∈ S(µ0 ) by the definition of the graph, this completes the proof.

Lemma 3. Suppose µi = ∅ and i ∈ I 0 . Then there exists a school s0 ∈ r(i) ∩ S(µ0 ) suchthat |µs0 | < qs0 .
Proof. Suppose there is i such that µi = ∅ and i ∈ I 0 . Starting from this student i, follow
the arrows in G(µ, µ0 , r) in an arbitrary manner without passing the same student twice(note that there is an outgoing arrow from i). Since there are a finite number of students,
there is s0 such that there is no more outgoing arrow from s0 to a student who has notappeared in the path (note that, by definition, this path cannot end at any student).
This implies that the number of students who are in µ0s0 \ µs0 is larger than the numberof students who are in µs0 \ µ0s0 by at least one. Hence, we have qs0 ≥ |µ0s0 | > |µs0 |. Sinces0 ∈ r(i) and s0 ∈ S(µ0 ) by the definition of the graph G(µ, µ0 , r(i)), this completes theproof.



Next, we define a graph, denoted G(µ, µ0 ), as follows. In this graph, only students in I 0
and schools in S(µ0 ) may be associated with arrows. Formally, for any s ∈ S(µ0 ), consider
the set of students in I 0 who strictly prefer s to their match at µ, i.e., Dsµ (I 0 ) := Dsµ ∩ I 0(or, equivalently, Dsµ (I 0 ) := {i ∈ I 0 |s i µi }), and let T ops (Dsµ (I 0 )) point to s. Note thatDsµ (I 0 ) is nonempty by the definitions of I 0 , µ and µ0 , and thus for any s ∈ S(µ0 ), there
exists some i ∈ I 0 who points to s. Next, consider any i ∈ I 0 .
(1) If µi ∈ S(µ0 ), then let µi point to i.
(2) If µi ∈ S \ S(µ0 ), then µi ∈ S(µ) \ S(µ0 ) by the definition of S(µ) and hence byLemma 2, there exists a school s0 ∈ r(µi ) ∩ S(µ0 ) such that |µs0 | < qs0 . Let any
such school s0 point to i.
(3) If µi = ∅, then by Lemma 3, there exists s ∈ r(i) ∩ S(µ0 ) such that |µs | < qs . Let
any such school s point to i.
The graph must have a cycle because each school is pointed to by a single student, andeach student is pointed to by at least one school.25 Pick an arbitrary cycle and call it F ∗ .
25To find a cycle, take an arbitrary school and find the student pointing to that school. Then find theschool pointing to that student. Then find the student pointing to that school, etc., until we find a schoolor a student that has already been visited. Since there are only finitely many students, this procedureends in finite steps.

38

Lemma 4. F ∗ is a FIG cycle.

Proof. Let F ∗ = (i1 , s1 , . . . , im , sm ).
It is straightforward to check that the last two conditions of a cycle are satisfied: By
construction, each student appears only once in F ∗ . Given this, since the pointing rulefor G(µ, µ0 ) implies that each school is pointed to only by a single student, each school
appears at most once in F ∗ .
To complete the proof, it suffices to show that G(µ, µ0 ) is a subset of the FIG on µ. To
show this, first we establish that, for any k ∈ {1, . . . , m}, ik points to sk according to thedefinition of pointing used for FIG. To do so, it suffices to show that ik = T opsk (Dsµk )and ik sk ∅ (part (1) of Definition 3). The latter holds for the following reason: we havei ∈ Dsµk (I 0 ) for some i ∈ µ0sk because of the definitions of S(µ0 ) and I 0 and the fact thatsk ∈ S(µ0 ). Hence, by individual rationality of µ0 , it follows that ik = T opsk (Dsµk (I 0 )) sk
i sk ∅. To show the former, note first that, by construction, ik = T opsk (Dsµk (I 0 )) andhence ik sk i for any i ∈ (Dsµk ∩ I 0 ) \ {ik }. Next, consider any i ∈ Dsµk \ I 0 . Because0µ0i0 = µi0 for any i0 ∈ I \ I 0 by the definition of I 0 , it follows that i ∈ Dsµk . This and theassumption that µ0 is fair imply j sk i for every j ∈ µ0sk . By the construction of thecycle, ik sk j for every j ∈ µ0sk \ µsk 6= ∅ (the nonemptiness holds because sk ∈ S(µ0 )).
Thus, we have ik sk i. Therefore, we have ik sk i for any i ∈ Dsµk \ {ik }, which implies
ik = T opsk (Dsµk ).
Second, we consider three cases of the definition of G(µ, µ0 ) to show that, for anyk ∈ {1, . . . , m}, sk points to ik+1 according to the definition of pointing used for FIG,
where im+1 = i1 . Suppose first that ik+1 and sk satisfy the condition described in Case
1 of the definition of G(µ, µ0 ). This implies that ik+1 and sk satisfy the assumption inpart (2a) of Definition 3. Next, consider Case 2 of the definition of G(µ, µ0 ). In this case,|µsk | < qsk and µik+1 ∈ r(sk ) hold, which satisfies the condition in part (2b) of Definition 3.
Finally, consider Case 3 of the definition of G(µ, µ0 ). In this case, |µsk | < qsk , ik+1 ∈ r(sk ),and µik+1 = ∅ hold, which again satisfies the condition in part (2b) of Definition 3. This
completes the proof.

Lemma 4 completes the proof.

A.3. Proof of Claim 1.





39

Proof. We first observe that the balancedness of µ0 at E 0 is equivalent to the property
that, for each r ∈ R0 ,X

X|{i|i ∈ µ0s , i 6∈ r}| −|{i|i ∈ µ0s , i ∈ r}| = 0.

s6∈r

s∈r

|

{z

}

inflow to r

{z

|

}

outflow from r

Consider any r∗ ∈ R. Then,




X

X


0
0

 = 0.
,
i
∈
6
r}|
|{i|i
∈
µ
−
,
i
∈
r}|
|{i|i
∈
µ
s
s



s6∈r
r∈R0 ,r⊆r∗  s∈r
|
{z
} |
{z
}
X

(A.2)

inflow to r

outflow from r

The left-hand side of (A.2) is equal to







X

X
X
X



0
∗
0
∗
0
0

|{i|i ∈ µs , i 6∈ r }| + |{i|i ∈ µs , i ∈ r \ r}| −|{i|i ∈ µs , i ∈ r}| +|{i|i ∈ µs , i ∈ r}|
s6∈r ∗s∈r ∗ \rr∈R0 ,r⊆r ∗ s∈r

|
{z
} |
{z
}
inflow to r

outflow from r


X

=


X


r∈R0 ,r⊆r ∗|{i|i ∈ µ0s , i 6∈ r∗ }| −

X


=

X

|{i|i ∈ µ0s , i 6∈ r∗ }| −

s∈r ∗

X

|{i|i ∈ µ0s , i ∈ r∗ }| +s6∈r ∗

X



X|{i|i ∈ µ0s , i ∈ r∗ \ r}| −|{i|i ∈ µ0s , i ∈ r}|r∈R0 ,r⊆r ∗

s∈r

X



X
X

|{i|i ∈ µ0s , i ∈ r0 }| −|{i|i ∈ µ0s , i ∈ r}|


r,r 0 ∈R0 ,r,r 0 ⊆r ∗ ,r6=r 0s∈r ∗ \r

s∈r 0

s∈r




=

X

|{i|i ∈ µ0s , i ∈ r}| +s6∈r ∗s∈rX|{i|i ∈ µ0s , i 6∈ r∗ }| −

s∈r ∗

X

|{i|i ∈ µ0s , i ∈ r∗ }|s6∈r ∗










 


 X

X
X
X
 X
 

0
0
0
0
|{i|i ∈ µs , i ∈ r` }| −|{i|i ∈ µs , i ∈ rk }| + |{i|i ∈ µs , i ∈ rk }| −|{i|i ∈ µs , i ∈ r` }|
+


 

s∈r`
s∈rk
k<` s∈rk
 s∈r`

|
|
{z
} |
{z
}
{z
} |
{z
}
flow from r` to rk

=

X
s∈r ∗

|

X

|{i|i ∈ µ0s , i 6∈ r∗ }| −flow from rk to r`

flow from rk to r`

flow from r` to rk|{i|i ∈ µ0s , i ∈ r∗ }|,s6∈r ∗{zinflow to r

∗

}

|

{z

outflow from r ∗}where we let {r1 , r2 , . . . } be a partition of r∗ by regions in R0 .
By (A.2), this implies thatX|{i|i ∈ µ0s , i 6∈ r∗ }| −

s∈r∗

|

X

|{i|i ∈ µ0s , i ∈ r∗ }| = 0.

s6∈r∗

{z

inflow to r∗

}

|

{z

outflow from r∗}

Hence the inflow and outflow for region r∗ are equal to each other. Since this relation
holds for every r∗ ∈ R, µ0 is balanced at E.

40

A.4. Comparative Statics: An Example. The following example shows that the converse of Proposition 1 does not hold. That is, starting at a certain efficient iBF, somestudent can be made strictly better off in any efficient iBF after splitting a region.
Example 8 (An instance in which splitting a region inevitably makes some student
better off). Let I = {i1 , i2 } and S = {s1 , s2 , s3 }. Let there be two regions, r = {i1 , s1 , s2 }and r0 = {i2 , s3 }. Each school has the capacity of one. Student preferences and school
priorities are given as follows:i1 : s2 , s3 ,

s1 : i 2 ,i2 : s1 ,

s2 : i 1 ,s3 : i 1 .

In this environment, there is an efficient iBF:µ=s1 s2 s3 ∅
∅

i1

∅

!

i2

.

If region r is split into two regions, r1 = {i1 , s1 } and r2 = {s2 }, then there is a uniqueefficient iBF:
0

µ =

!
s1 s2 s3 ∅
i2

∅

i1 ∅

.

Note that i2 is better off as a result of the split. The intuition is the following: Before thesplit, i2 in r0 was unable to match with s1 in r as there was no student who wanted tocome from r to his region r0 . However, the split made it impossible for i1 in r1 (which waspart of r) to go to s2 , and she is now interested in coming to r0 . This made it possible toimplement a swap between r1 and r0 .
Notice that, in the above example, both µ and µ0 are an efficient iBF before region r was
split. In fact, multiplicity of efficient iBFs is necessary for the failure of the converse of
Proposition 1: Indeed, Proposition 1 implies its converse if there exists a unique efficientiBF before the split of a region.