CROWDING IN SCHOOL CHOICE
WILLIAM PHAN, RYAN TIERNEY, AND YU ZHOU
Abstract. We consider the market design problem of matching students to schools in thepresence of crowding effects. These effects are salient in parents’ decision making andthe empirical literature; however, they cause major difficulties in the design of satisfac­
tory mechanisms and, as such, are not currently considered. We propose a new framework
and an equilibrium notion that accommodates crowding, no­envy, and respect for priori­ties. The equilibrium has a student­optimal element that induces an incentive compatible
mechanism and is implementable via a novel algorithm. Moreover, analogs of fundamental
structural results of the matching literature—the Rural Hospitals Theorem, welfare lattice,
etc.—survive.
Keywords: School choice with crowding; Rationing crowding equilibrium; Student opti­
mality; Strategy­proofness
JEL Classification: C78, D47, D62, I20(William Phan) Department of Economics, North Carolina State University, USA(Ryan Tierney) Department of Economics, University of Southern Denmark, Denmark(Yu Zhou) Graduate School of Economics, Kyoto University, JapanE­mail addresses: wphan@ncsu.edu, ryanetierney@gmail.com, zhouyu_0105@hotmail.com.
Date: This version 25th May, 2022, first version 22nd October, 2021.
We thank Açelya Altuntaş, Tommy Andersson, Inácio Bó, Umut Dur, Aram Grigoryan, Melinda Mor­rill, Thayer Morrill, Arunava Sen, Ning Sun, Qianfeng Tang, Alex Teytelboym, Rakesh Vohra, Thomas Wise­man, Aytek Erdil, and conference/seminar participants at the European Winter Meeting of the EconometricSociety 2021, Kyoto University, Indian Statistical Institute, Delhi Winter School 2021, Easter Workshop on
School Choice 2022, and NC State Equity Research Symposium 2022 for helpful comments. Yu Zhou grate­
fully acknowledges financial support from the Joint Usage/Research Center at ISER, Osaka University, and
the Grant­in­aid for Research Activity, Japan Society for the Promotion of Science (19K13653, 20H05631,
20KK0027, 22K13364, 22H00062).
1

2

W. PHAN, R. TIERNEY, AND Y. ZHOU

1. Introduction
Parents believe that if a school is overcrowded, then the quality of their children’s ed­
ucation will suffer. This is supported by empirical literature. Card and Krueger [1992],
Krueger and Whitmore [2001], Chetty et al. [2011], and Jackson et al. [2016] all show that
decreasing crowding, as measured by per capita expenditure or teacher­student ratios, etc.,
has positive effects on measures such as test scores, students’ lifetime expected income,and career development. Policymakers also share parents’ concerns. From 1999­2001, theUnited States’ federal government allotted over $4 billion to the Class­Size Reduction Pro­
gram with the goal of smaller class sizes in grades K­3.1 Similar programs exist in othercountries.2
Matching theory has been astonishingly successful in practice, reforming the way stu­
dents are assigned to schools in many municipalities worldwide. However, despite thesalience of crowding effects, the theoretical school choice literature has largely avoided
the issue. This is because whenever externalities are introduced into the standard model,
its appealing features—like the existence of fair (in terms of respect for priorities) or stablematchings, the ordered structure of the set of such matchings, and the existence of incentive
compatible mechanisms—vanish (see Example 1 and Section 1.2). As such, while students’preferences take into account crowding, the design of school choice mechanisms currently
fails to do so.
The contribution of this paper is a novel framework to analyse the school choice problem
with crowding. Our framework generalizes the now­standard model of Abdulkadiroğlu andSönmez [2003] and restores its core features. There, each student has a preference over thefinite set of schools. In our model, each student has a preference over the two dimensionsof school identity and the total amount of educational resources that they consume at eachschool. The more crowded a school is, the less resource each student enjoys, and so the valueof this second dimension at each school will emerge endogenously. The feature that allows
us to cut the proverbial Gordian knot is modelling the level of educational resources as acontinuous variable. This is of course an abstraction; however, the return on this abstraction
is high—recovering existence of an ordered set of fair matchings, and a class of fair andstrategy­proof rules. Our techniques also connect the school choice literature with research
1
U.S. Department of Education, Office of the Deputy Secretary, Policy and Program Studies Service, “A
Descriptive Evaluation of the Federal Class­Size Reduction Program: Final Report,” Washington, D.C., 2004.
2
For example, the “Plus de Maîtres que de Classes” program in France in 2013 aimed to reduce classsizes in socioeconomically depressed areas (Réseaux d’Éducation Prioritare).

CROWDING IN SCHOOL CHOICE

3

on Walrasian equilibria in the presence of price rigidities (see Section 1.2). Finally, ourframework naturally opens up new avenues for policy analysts: Eliciting preferences overcrowding would provide powerful data for welfare analysis, and the model very naturallyaccommodates novel comparative statics like shifting resources between schools.

Case Study: Crowding in the Wake County Public School System. Wake County is the mostpopulous county in North Carolina and, in the last decade, was the third fastest­growing
in the United States among those with over a million residents.3 The Wake County Public
School System (WCPSS) currently serves over 150,000 K­12 students. In 2016, WCPSS
projected the arrival of 32,000 new students, which indeed materialized into student pop­
ulation growth that has outpaced that of physical infrastructure. For example, in Abbotts
Creek Elementary School for the 2019­2020 year, 870 students enrolled, or 141.2% of theschool’s total building capacity.4 This is not an uncommon phenomenon; Figure 1 lists
crowding statistics for several other schools in the WCPSS, with some enrollments at al­most twice the original building capacity. Student populations also fluctuate significantly
from year to year. In Abbotts Creek, for the 2016­2017 year, there were 796 enrolled stu­
dents, increasing to 870 for the 2019­2020 year, and dropping to 854 in the following year.
The National Center for Education Statistics (NCES) also provides a wide range of data
relevant to crowding, including enrollments, financial expenditure, number of teachers,
and basic demographics on all public schools in the United States. The recently initiatedNCES School­Level Finance Survey program collects and releases data on faculty and staff
salaries, spending on supplies, spending on technology related equipment, etc. For example,
in 2016­2017 (latest available), Abbotts Creek had financial expenditures of $3.5 million(or $4,100 per student).5

This case study immediately points to several items outside of the purview of the stan­
dard model. First, parents have access to data relevant to crowding and can condition theirpreferences over schools in this dimension. The figures above are publicly available via the3

U.S. Census Bureau.
Figures regarding Abbotts Creek accessed Nov 10, 2021 at https://www.wcpss.net/domain/100.
5https://nces.ed.gov/ccd/.
4

4

W. PHAN, R. TIERNEY, AND Y. ZHOU

2019­20202020­21
Crowding
Crowding
Trailers
Population Building Cap%% w/ Trailers
Abbotts Creek
Alston Ridge
Beaverdam
Cedar Fork
Combs
Highcroft Drive
Holly Grove
Hortons Creek
Lead Mine
Mills Park
Oakview
Olive Chapel
Rogers Lane
Scotts Ridge
Sycamore Creek
Weatherstone
White Oak

870
1,053
790
848
767
921
940
911
500
828
901
978
730
857
1,082
850
747

616
914
616
508
410
508
814
716
410
716
716
612
616
616
914
508
616

0
0
4
8
13
15
3
0
1
3
6
14
4
6
0
11
0

141.2%
115.2%
128.2%
166.9%
187.1%
181.3%
115.5%
127.2%
122%
115.6%
125.8%
159.8%
118.5%
139.1%
118.4%
167.3%
121.3%

141.2%
115.2%
116.9%
126.9%
118%
114%
107.6%
127.2%
122%
106.7%
110.4%
112.2%
104.9%
116.4%
118.4%
116.8%
121.3%

Figure 1. Crowding statistics for elementary schools in WCPSS that enacted
enrollment caps for the 2020­2021 school year.6 These amounted to 17 outof 120 elementary schools.
WCPSS and NCES websites, as well as regularly reported on by the local media.7 Second,
the fact that student enrollments frequently and grossly exceed building capacity challenges
the standard assumption that enrollment capacity is ex ante exogenously fixed. A school
may almost always accommodate some extra students by adding seats in a classroom or a
trailer. In the Feb. 4, 2020 WCPSS Board of Education meeting, the Assistant Superinten­
dent for School Choice, Planning, and Assignment proposed enrollment caps for each of
the schools in Figure 1 (among others)—after years of overcrowding.8 Many of the schools
6

Statistics from Feb. 4, 2020 WCPSS Board of Education Meeting Minutes section “Capping Recom­
mendations.” Accessed April 9, 2022 at https://www.wcpss.net/Page/3728.
7
See,
for
example:Editorial
Board,“More
GrowthChallenges
Wake
Schools,” News and Observer,
March 26,2016,
accessed November 7,2021,
https://www.newsobserver.com/opinion/editorials/article68451967.html.
8
See Footnote 6. See also: T. Keung Hui, “Wake County Puts Enrollment Caps On 19 Schools For
2020. One More May Be Added,” News and Observer, February 5, 2020, accessed November 7, 2021,
https://www.newsobserver.com/news/local/education/article239808038.html.

CROWDING IN SCHOOL CHOICE

5

in Figure 1 are therefore now considered at capacity. This implies, however, that manyothers are below capacity, with the potential for fluctuations year to year.9
Our model addresses all of these points. We accommodate inviolable caps while provid­
ing a framework for analyzing the still­salient crowding levels at all schools, and in particu­
lar those below capacity. Parents are able to explicitly express preferences over such levels.
Moreover, the strategy­proof and fair rules we propose make crowding levels a publicly
announced quantity in the manner of an auctioneer, eliminating the need for parents to infer
future crowding from the lagged data available.
The remainder of this section provides a sketch of the model and an overview of theformal results. Each student consumes a bundle consisting of a school and a level of ed­
ucational resources. We require that all the students at a given school consume the samelevel, an important benchmark representing the ideal that all students are equally entitled to
the resources of their school.10 An aggregate allocation is thus composed of a matching ofstudents to schools and a vector of resource levels, one level for each school.
We propose a new equilibrium concept—the Rationing Crowding Equilibrium (RCE).
The core of our innovation is in realizing that the vector of resource levels can function likea price. Consider a competitive solution applied in our context. We may imagine that an
auctioneer announces a resource vector, which then determines a (finite) list of school andresource­level pairs. Each student will then demand (generically) one of these pairs, andwe can ask the usual market clearing question: Does there exist a resource vector at which,for each school, the demand for educational resources is equal to its supply? We show thatthe answer is yes, if we allow for an error of one seat.11,12 Since each student faced thesame budget set, the resulting allocation satisfies no­envy, at least for schools that have notreached their enrollment cap.
9

Apart from such proposals for enrollment caps, many states also have laws specifying a minimum
teacher­student ratio and therefore implying such caps. For example, North Carolina requires at least one
teacher per 18 students in grades K­3 (G.S. 115C­301 on “Allocation of teachers; class size”). Districts may
also “manually” adjust capacities to accommodate unmatched students with specific requirements only avail­able at certain schools e.g. disabilities, large number of siblings.
10This is a restriction, and yet we have found an appealing solution to the problem. It follows that finding
an appealing solution for the unrestricted case should be easier.
11
More precisely, if a school at an RCE admits k students, each student is guaranteed to consume morethan 1/k+1 fraction of the school’s total resources (see Remark 1).
12
Excluding several specialized schools, the smallest (Wake STEM Early College) and largest (Apex
Friendship) schools in Wake County in 2020­2021 had 256 and 2,733 students, respectively. In practice,then, the presence or not of a single seat at either school is negligible.

6

W. PHAN, R. TIERNEY, AND Y. ZHOUFor schools constrained by their caps, our equilibrium incorporates fairness via respect
for priorities: If student i prefers school s at an RCE, then school s has exhausted its capacity
and all students in that school have higher priority than student i. To continue the Walrasiananalogy, a school exhausting capacity is tantamount to the auctioneer no longer being able
to lower the announced resource level of a school, and thereby reduce demand—akin toa price ceiling.13 If schools are below capacity, then assignments will be decided by ourmarket­like mechanism without price rigidities.
Our main results are as follows. Fix a school choice problem with crowding. We showthat an RCE exists for this problem so long as it satisfies a regularity condition that holds
true generically (Theorem 1). We then establish a version of the Rural Hospitals Theorem
for our environment, i.e. in each RCE, each school is matched with the same number ofstudents (Theorem 2). We show that the set of RCEs constitute a closed upper semi­latticeunder the Pareto dominance partial order (Theorem 3), and so there exists a student­optimal
RCE (Proposition 3). These are analogs of fundamental results in the literature, but thepresence of crowding necessitates substantial difference in technique.
A maximal RCE mechanism recommends, for each problem in our domain, a maximal
RCE (all in this set are welfare­equivalent and student­optimal). We show that these mecha­
nisms are strategy­proof (Theorem 4), and we further find an algorithm to calculate them ona natural subdomain (Theorem 5).14 It is in general hard to propose an algorithm for equilib­
rium computation when students’ preferences are not quasi­linear (see the discussion after
Theorem 1). This algorithm uses tools from both the multi­item auction [Demange et al.,1986], with rationing constraints on students’ demands, and the Deferred­Acceptance algo­rithm [Gale and Shapley, 1962]. The latter adjusts the matching for schools whose capacity
constraint have been met, and the former adjusts the distribution for unconstrained schools.
1.1. Discrete Versus Continuous Crowding: Our Methodological Novelty. We model
crowding via the consumption of a continuous good that comes in fixed supply. We havetouted the benefits of this approach, weighed against the negligible “within­one­seat” relax­
ation of the market clearing condition. Thus, one might wonder if we could have achieved
the same without such abstraction, by simply saying that if n students arrive at a school,
13

If the school admits further students, then crowding increases and the resource level each student enjoys
would decrease. So an upper bound on student enrollment is equivalent to a lower bound on the resource
level.
14
The general domain is infinite dimensional. We show the algorithm works on a finite­dimensional sub­domain.

CROWDING IN SCHOOL CHOICE

7

then its aggregate resources are split n ways. We immediately face difficulties: two key
solution concepts in the school choice literature, no justified envy and non­wastefulness,
are incompatible. Recall, that if student i envies student j, who is attending school s, thenthis envy is justified if school s prioritizes i over j. An allocation is wasteful if a student
would want to switch to a school at which there is currently unfilled capacity.
Example 1 (Incompatibility of No Justified Envy and Non­Wastefulness). Consider a simple
problem with only two schools, s1 and s2 , and three students, 1, 2, and 3. Assume that s1 ands2 each have capacity three; each school also prioritizes student 3 over the others. Suppose
student 1 has such strong preferences for s1 that they prefer to attend s1 regardless of thenumber of students there. Assume 2 has similarly strong preferences for s2 . Then at any
non­wasteful allocation we have 1 at s1 and 2 at s2 . Finally, suppose student 3 would rather
be alone than share either s1 or s2 with another student. If we put 3 at s1 , then since they
have highest priority at s2 , they have justified envy of student 2. A symmetric statement
holds if we put 3 at s2 .
In work independent of ours, Copland [2021] studies exactly this model. They propose
a natural relaxation of the standard solution concept: the envy that 3 had for 2 above is notyet justified unless student 3 is also willing to attend school s2 , keeping all other students,
including 2, at their place.15 Given this definition, a solution always exists. They provide analgorithm to compute a solution, but it does not yield a strategy­proof mechanism. Unfor­
tunately, other key properties are also lost: the Rural Hospitals Theorem and upper­lattice
structure on the set of satisfactory matchings do not hold.
We review prior work in discrete models below in Section 1.2. The model just discussed
is even more tightly structured than what had come before, allowing only crowding ex­
ternalities as opposed to preferences over the identity of one’s cohort or even the entire
matching. Thus, it will not surprise the reader that those more general models also yield
similarly negative results. Thus, so far, no discrete model yields structured solutions andstrategy­proof rules as in the standard model without externalities.
1.2. Related Literature.
15

The usual no justified envy embodies a “replacement” principle: if i has justified envy of j, then i cansimply take the place of j. Copland’s solution is subtly different—one student “joins” another school without
replacing anyone else.

8

W. PHAN, R. TIERNEY, AND Y. ZHOUMatching with Externalities. Our problem is one of matching with externalities. In princi­
ple, an agent may have preferences over where all the other agents are matched. Sasaki andToda [1996], Hafalir [2008], Bando [2012], and Bando [2014] propose and study various
notions of stability in such an environment. For the case when there are general exter­
nalities and several ways for each pair of agents to match—the matching with contracts
problem—Rostek and Yoder [2020] and Pycia and Yenmez [2021] identify general condi­
tions on preferences under which stability is possible. In most applications, there is a natural
structure on possible externalities. For example, agents may care only about who their peers
are, not about those matched to other schools/firms [Dutta and Massó, 1997, Echenique andYenmez, 2007, Leshno, 2021]. Narrowing down even further, a large literature considers
matching with couples, siblings, or neighbors [Roth, 1984, Roth and Peranson, 1999, Klaus
and Klijn, 2005, Kojima et al., 2013, Ashlagi et al., 2014, Nguyen and Vohra, 2018, Dur andWiseman, 2019, Dur et al., 2022]. These studies find that externalities eliminate the struc­tures that have been found in the classical literature. Preference over crowding introduces
yet more structure to the problem, but that alone is not sufficient to yield all the standard
results from the classical problem.
Tierney [2019] also studies crowding, but in an environmental resource allocation prob­
lem. In principle, we could treat school resources like environmental resources; however,adapting their equilibrium to our model is not appropriate for several reasons, chief among
them being that the concept assumes agents can be allotted arbitrarily small quantities.
This is unacceptable for school choice, as it implies that a single school can accommodate
all the students in the entire system. Additionally, their equilibrium concept also satisfies
anonymity. Here, respecting priorities necessitates retaining student identities.
Walrasian Approaches. Our RCE follows, in spirit, price­based equilibrium notions inmatching with the possibility of monetary transfers. Shapley and Shubik [1971] first proved
the existence and structural properties of the core and competitive equilibrium allocations
for these models. These properties imply that, for each side of the market, there is a unique
undominated utility vector it can achieve in the core. Mechanisms that realize one of these
vectors are efficient for all and strategy­proof [Demange and Gale, 1985] for the side of themarket whose utility is maximized. In matching models where prices are not fully flexible,
e.g. restricted between price floors and ceilings, Drèze Equilibrium and Rationing Price
Equilibrium were proposed as alternative notions [Drèze, 1975, Talman and Yang, 2008,
Andersson and Svensson, 2014, Herings, 2018]. Under some mild domain restrictions,

CROWDING IN SCHOOL CHOICE

9

there are constrained efficient and group strategy­proof rules [Andersson and Svensson,2014].
In several matching models without continuous transfers, the usual fairness properties arenaturally expressed with an endogenously determined cutoff vector [Balinski and Sönmez,
1999, Sönmez and Ünver, 2010, Azevedo and Leshno, 2016, Dur and Morrill, 2018, Leshno
and Lo, 2021]. In the case of school choice, the vector specifies for each school the lowest
priority student able to attend. This is thus a competitive approach—cutoffs determine
budget sets for agents, agents maximize therein, and markets clear. Note that the cutoffs inthese models play a different role to that of our resource vector. The former control accessto schools, while the latter modulates the character of what students eventually consume.
1.3. Organization. In Section 2, we define the school choice with crowding problem. In
Section 3, we define the Rationing Crowding Equilibrium. Section 4 shows that RCE exist,
and Section 5 investigates some properties of them, like the Rural Hospitals Theorem andthe welfare upper lattice. In Section 6, we identify a fair and strategy­proof mechanism, andin Section 7, we find an algorithm that implements this mechanism on a restricted domainof preferences. In Section 8, we discuss the robustness of our results and some applications
beyond school choice. Section 9 concludes with open questions.
2. ModelLet S be the finite set of schools, and N be the finite set of students. Each schools ∈ S has resources in the form of teachers, buildings, money, etc. We aggregate this to asingle measure and for each school normalize this to one. When a student attends a school,
the number of other students and the policy of the school together determine what fractionof those resources, that is, what resource ratio, they consume. Formally, each student’s
consumption space is [0, 1] × S, where the first component is a resource ratio ρs and thesecond is the school s that they attend. Inclusion of an outside option in our model would
not change the results and only add complication to the proofs.16 This abstraction of theconsumption space drives our theoretical innovations. For some applications, it may beessential that the resource ratio be restricted to simple fractions of the form 1/k. This would
be the case when crowding really depends only on the number of students at a school. Ourmodel is still useful in these cases, since we shall recommend, for each school, a resource16

We show, however, in Section 3.1, that the richness of our preference space subsumes the outside option
in the classical sense.

10

W. PHAN, R. TIERNEY, AND Y. ZHOU

ratio that is within one student of being the simple fraction implied by the cohort they admit(see Remark 1).
Each student i ∈ N has a complete and transitive preference relation Ri over [0, 1] × S.
We assume that each is monotonic in the resource ratio: for each ρs , ρ′s ∈ [0, 1] with ρ′s > ρs ,and each s ∈ S, (ρ′s , s) Pi (ρs , s). Let R be the set of monotonic preference relations, andR = (Ri )i∈N ∈ R N denote a profile of preferences for students.
Each school s ∈ S has a maximum natural number capacity. Let bs ∈ [0, 1] be such that−1
bs is equal to this capacity; we can then interpret bs as a lower bound on the resource ratio
it can provide. Let b = (bs )s∈S denote the profile of bounds for schools. We assume that∑−1s∈S bs ≥ |N |, so all students can be admitted to some school. Each school s ∈ S has apriority order s over the set of students, where i s j indicates that i has higher priority
than j at s. Let ≻= (s )s∈S denote the profile of priorities for schools.
A school choice problem with crowding (hereafter just a problem) is a tuple(S, N, R, b, ≻). The canonical school choice problem of Abdulkadiroğlu and Sönmez
[2003] is a special case (see Section 3.1 for details). A distribution is a vector ρ ∈ [0, 1]Sof resource ratios. A matching σ : N → S places each student at a school. Let M be theset of matchings, and for each σ ∈ M write σ[s] as the set of students matched to s at σ.17
An allocation is a pair (ρ, σ) ∈ [0, 1]S × M such that for each s ∈ S,(1) (Distribution Feasibility) ρs · |σ[s]| ≤ 1 and(2) (Respects Capacity) ρs ≥ bs .
Given a distribution ρ ∈ [0, 1]S and a school s ∈ S, we also write (ρ, s) to indicate
bundle (ρs , s). Thus, for an allocation (ρ, σ), each i ∈ N receives (ρ, σ(i)). We refer tothis as i’s component when the allocation at hand is clear.
A mechanism φ recommends, for each profile R in a domain D ⊆ R N , an allocation.
Denote by φi (R) student i’s component of the allocation recommended at problem R. We
formalize some senses in which these recommendations might either be good or achievable.
We consider fairness amongst the students. A student should be able to attend any schoolthat is not yet at capacity. If a school is at capacity, then the student may be turned away
if all others have higher priority. This embodies the classic no­envy condition of Foley[1966] as well as the standard notion of no justified envy in school choice. We combine
these two ideas formally. Fix a problem (S, N, R, b, ≻). The allocation (ρ, σ) is fair if
17

Generally, for any function f and any element or set y, we let f [y] denote the pre­image of y under f .

CROWDING IN SCHOOL CHOICE

11(ρ, s) Pi (ρ, σ(i)) implies that ρs = bs (s is at capacity) and, for each j ∈ σ[s], j s i. We
repeat this terminology for the associated property of mechanisms.
Fairness: For each problem, the allocation recommended by φ is fair.
There may be several fair allocations, and we distinguish those most preferred by thestudents. Allocation (ρ, σ) Pareto­dominates (ρ′ , σ ′ ) if for each i ∈ N , (ρ, σ(i)) Ri(ρ′ , σ ′ (i)), and for some j ∈ N , (ρ, σ(i)) Pi (ρ′ , σ ′ (i)). A student­optimal fair allocation
is fair and not Pareto­dominated by any other fair allocation.18
Student­optimal fairness: For each problem, the allocation recommended by φ is student­
optimal fair.
Next, we consider the direct revelation incentive compatibility condition.
Strategy­proofness: For each problem (S, N, R, b, ≻), each i ∈ N , and each preference
relation Ri′ ∈ R such that (Ri′ , R−i ) ∈ D,
φi (S, N, R, b, ≻) Ri φi (S, N, (Ri′ , R−i ), b, ≻).

One might worry about the potential for a single agent i to report Ri′ and induce/ D. However, in all of the problems that we study, this event is negligible,(Ri′ , R−i ) ∈either topologically or probabilistically. We provide a more detailed discussion in Section
4.
3. Solution Concept
Our solution concept is fundamentally Walrasian in spirit. There is a publicly announced
vector (a distribution) that induces, for each student, a menu of options (a list of ratio­school
pairs), and students select their most preferred. Two main points, though, distinguish ourconcept from price equilibrium. If too many students select one school, then rationing oc­
curs as opposed to a price increase. Exogenously given priority information (≻) determines
which students are matched. Next, once a distribution is announced, they must consume
the object at that distribution quantity (i.e. teacher­student ratio). They cannot “purchase”
more or less of the object.
18

There may be allocations that are efficient (Pareto­undominated by any allocation) but not fair. As weare in the context of school choice, we focus on respect for priorities.

12

W. PHAN, R. TIERNEY, AND Y. ZHOUFormally, a Rationing Crowding Equilibrium (RCE) is an allocation (ρ, σ) that satis­
fies three conditions:(1) (Fairness) (ρ, σ) is fair.
(2) (Exhaustive Given ρ) For each school s with σ[s] 6= ∅,bρ−1
s c = |σ[s]|.
(3) (Inferior Empty Schools) For each school s with σ[s] = ∅, ρs = 1, and for eachi ∈ N,(ρ, σ(i)) Pi (ρ, s).
Note that our notion begins by offering each student the menu {(ρ, s) : s ∈ S}. If
ρs > bs , then “demand” for s is just as one expects. Anticipating, however, that ρs cannot
be reduced if it equals bs , “demand” is first rationed via priorities in this case. Thus, fair­ness is the analog to consumer maximization. The second condition is the key to adapting
our notion to the crowding environment and operationalizes the interpretation of ρs as aresource ratio. The amount of resources the school provides to each student is, up to round­ing error, the total amount of resource (one) divided by the number of students matched tothe school. Together with the definition of an allocation (feasibility), this is the analog ofmarket clearing. The third condition states that each student finds any empty school strictly
worse than their component of the allocation, and is therefore the analog of the requirement
that, at equilibrium, unconsumed commodities should be available for free. Section 3.2 re­lates RCE to other notions in the literature encompassing competitive equilibria with pricerigidities.
Example 2 (An RCE). Let S = {s1 , s2 } and N = {1, 2, 3}. Agents’ preferences are givenby the following utility functions:3+ ρs1 and u1 (ρ, s2 ) = ρs2
227+ ρs1 and u2 (ρ, s2 ) = ρs2
u2 (ρ, s1 ) =123
u3 (ρ, s1 ) =+ ρs1 and u3 (ρ, s2 ) = ρs2
11
u1 (ρ, s1 ) =Each school s has minimum ratio bs = 12 (and thus capacity b−1
s = 2). School s1 has thepriority order 1 s1 2 s1 3. School s2 has the priority order 3 s2 1 s2 2.

CROWDING IN SCHOOL CHOICE

13

Allocation (ρ, σ) = ((ρs1 , ρs2 ), (σ(1), σ(2), σ(3))) = (1/2, 7/11, s1 , s1 , s2 ) is an RCE.
Fairness: Both students 1 and 2 find their component at least as good as others’.19 Agent 3
prefers both 1 and 2’s component to her own: u3 (ρ, σ(3)) = 7/11 < 3/11 + 1/2 = u3 (ρ, s1 ).
Since ρs1 = bs1 = 1/2 and 1 s1 2 s1 3, however, fairness is still satisfied. Exhaustive­−1
ness: We have bρ−1
s1 c = |σ[s1 ]| = 2 and bρs2 c = |σ[s2 ]| = 1. Inferior Empty Schools is istrivially satisfied, as there is no empty school.
This example is also among the most extreme cases of mismatch between the number ofstudents matched to a school and the reciprocal of the resource ratio. Since there is only one
student at s2 , we should hope that ρs2 = 1. Let ρ′s2 = ρs2 + ϵ and consider ρ′ = (ρs1 , ρ′s2 ).
7
7
For student 1, u1 (ρ′ , σ(1)) = 11< 11
+ ϵ = u1 (ρ′ , s2 ). Since ρ′s2 > bs2 = 1/2, 1 prefers(ρ′ , s2 ) to their own component, in violation of fairness.
In this problem, the entire set of RCEs is7
1 1{(ρ, σ) : ρs1 = , < ρs2 ≤ , σ(1) = s1 , σ(2) = s1 , σ(3) = s2 }
2 2
11
1 7
17
∪{(ρ′ , σ ′ ) : ρ′s1 = ,≤ ρ′s2 ≤ , σ ′ (1) = s2 , σ ′ (2) = s1 , σ ′ (3) = s1 }.
2 11
22
Note that we can have ρs2 > 7/11 when the matching is changed, but that in all cases,
school 2 will have only 1 student and ρs2 < 1.
Remark 1 (Discrepancy between ρs and a simple ratio of the form k1 ). The magnitude of thediscrepancy at any RCE is
1
1
1
1
1
1
1
− ρs =− −1 ≤− −1=−.
|σ[s]||σ[s]| ρs|σ[s]| bρs c + 1|σ[s]| |σ[s]| + 1
Thus, the difference between our modeled ratio and a strictly interpreted resource­to­student
ratio is at most the addition of one more student. This is a negligible difference for the
overwhelming majority of real world applications including school choice.
3.1. Connection to the Standard School Choice Model. Consider the canonical school
choice model of Abdulkadiroğlu and Sönmez [2003]. We show how to embed this problem
into school choice with crowding, then relate solution concepts across models.
Let schools S, students N , and priorities ≻ be defined as before. For each student i ∈ N ,let Pi∗ be a strict preference relation over schools and P ∗ = (Pi∗ )i∈N be the profile ofsuch preferences. For each school s ∈ S, let c∗s ∈ N be its capacity and c∗ = (c∗s )s∈S
19

7
7
7
3
+ 12 = 11= u1 (ρ, s2 ), and u2 (ρ, σ(2)) = 12
+ 12 > 11= u2 (ρ, s2 ).
u1 (ρ, σ(1)) = 22

14

W. PHAN, R. TIERNEY, AND Y. ZHOU

be the capacity profile for S. A school choice problem is a tuple (S, N, P ∗ , c∗ , ≻). An
allocation is a matching σ : N → S such that for each s ∈ S, |σ[s]| ≤ c∗s . We recall
two central properties in this model. A matching σ satisfies no justified envy if for eachi ∈ N , there is no j ∈ N \ i such that σ(j) Pi∗ σ(i) and i σ(j) j. A matching σ satisfies
non­wastefulness if for each i ∈ N , and s ∈ S, s Pi∗ σ(i) implies |σ[s]| = c∗s .
We now construct an associated school choice problem with crowding (S, N, R, b, ≻).
Let S, N , and ≻ be as in the school choice problem; only R and b need adjustment. For
each i ∈ N , let Ri be such that for each s, s′ ∈ S, s Pi∗ s′ if and only if (0, s) Pi (1, s′ ). Thatis, at any distribution level, i prefers s to s′ in Ri . For each s ∈ S, let bs = c1∗ . Thus, thesclassical model embeds in ours as a preference restriction. The externality is still present:
students are worse off when they have more classmates. However, on the restricted domainof classical preferences, there is no way for students to reveal this fact through their choices.
If we wish, we may include a special school, ϕ, in our model with bϕ < 1/|N |. When the
canonical school choice model is embedded in ours, this school may function as an outside
option in the standard sense, since it can accept all students. This is despite the fact that in
our model, we have elected not to consider the outside option.
Proposition 1. Fix a school choice problem. The following statements are equivalent:(1) σ satisfies no justified envy and non­wastefulness, and(2) There is a distribution ρ such that (ρ, σ) is an RCE for the associated school choiceproblem with crowding.
Proof. Fix a school choice problem (S, N, P ∗ , c∗ , ≻). Let (S, N, R, b, ≻) be an associatedschool choice problem with crowding.
Let σ be a matching. Let ρ ∈ [0, 1]S be such that for each empty school s ∈ S, ρs = 1 andfor each non­empty school s ∈ S, ρ−1
s = |σ[s]|. Thus (ρ, σ) is an allocation and exhaustive.
Matching σ is non­wasteful at empty schools if and only if, for each empty s ∈ S andeach i ∈ N , σ(i) Ri∗ s. Since Ri∗ is strict, this is true if and only if σ(i) Pi∗ s. Then(ρ, σ(i)) Pi (ρ, s). Therefore, non­wastefulness for empty schools in (S, N, P ∗ , c∗ , ≻) isequivalent to inferior empty schools in (S, N, R, b, ≻).
Now (ρ, s) Pi (ρ, σ(i)) if and only if s Pi∗ σ(i). So σ is non­wasteful for non­empty
schools if and only if |σ[s]| = c∗s = b−1
s if and only if ρs = bs . Moreover, σ satisfies no∗ ∗justified envy for (S, N, P , c , ≻) if and only if, for each j ∈ σ[s], j s i. Conclude

CROWDING IN SCHOOL CHOICE

15

that non­wastefulness for non­empty schools and no justified envy in (S, N, P ∗ , c∗ , ≻) areequivalent to fairness in (S, N, R, b, ≻).
■3.2. Competitive Foundations of RCE. Our RCE concept is related to notions of com­
petitive equilibria when prices exhibit rigidities. In the classical exchange problem, a priceceiling may cause demand to outstrip supply, resulting in the failure of market clearing andthus non­existence of equilibria. Drèze [1975] proposed and showed existence for a notion
where prices are constrained by ceilings or floors and rationing occurs at such boundaries.
In addition to prices, the notion includes a rationing scheme that specifies limits for the
net trades of agents. Likewise, in matching models with price controls, Talman and Yang
[2008], Andersson and Svensson [2014], and Herings [2018] introduce similar Drèze­styleequilibrium concepts. None of these models consider consumption externalities. Our RCE
can be seen as a conceptual parallel to their notions, but for the environment where agents
have preferences over crowding.
To explore this relationship, we define several Drèze­style equilibrium notions for aschool choice with crowding problem (S, N, R, b, ≻), then compare them to those above.
A rationing scheme provides each agent with a set of objects that is available for that agent
to consume. For each agent i ∈ N , let Qi ⊆ S be the set of objects available to them. Let
Q = (Qi )i∈N be the rationing scheme. A special case (defined below) is when rationing
relies on priorities associated with the objects.
The rationed demand set of agent i at distribution ρ and rationing scheme Q is
Di (ρ, Qi ) = {s ∈ Qi : (ρ, s) Ri (ρ, s′ ), ∀s′ ∈ Qi }.
Consider a tuple (ρ, σ, Q) consisting of an allocation and a rationing scheme. Each equi­
librium notion is defined by subsets of the conditions below:(1) Each agent is matched to a school in their rationed demand set.
(2) For each school s with σ[s] 6= ∅, bρ−1s c = |σ[s]|.
(3) For each pair of agent i and school s such that s ∈/ Qi , ρs = bs .
(4) For each agent i, j ∈ N , and school s ∈ S such that s ∈/ Qi and j ∈ σ[s], j s i.
A Crowding Drèze Equilibrium (CDE) is a tuple (ρ, σ, Q) that satisfies conditions (1)­(3).
Note that Q is a general rationing scheme and does not depend on ≻. When Q is consistent
with the priority profile ≻ (Condition 4), then we say that it is a Priority­Compatible
Drèze Equilibrium (PCDE). Our RCE is a further refinement of PCDE by additionallyimposing the inferior empty schools condition.

16

W. PHAN, R. TIERNEY, AND Y. ZHOU

Without crowding, these notions coincide with several of those in the literature. Con­
dition 2 is the key difference—the number of students matched to a school is nearly the
distribution associated with the school. Without this coupling, we revert back to the in­terpretation of the distribution as the price. Formally, without Condition 2, CDE coincides
with the notion in Talman and Yang [2008], and if priorities are used, then PCDE, with addi­
tional requirement of constrained efficiency, coincides with that in Andersson and Svensson[2014]. Finally, notice that when agents’ preferences satisfy the standard monotonicity andcontinuity assumptions, the existence for each of the aforementioned equilibrium notions
is guaranteed. This is not true when there is crowding, as Example 3 demonstrates. With amild domain restriction, however, we can recover existence (Theorem 1).

4. Existence of RCEs
There are profiles in R N that do not admit an RCE. Such profiles are rare; profiles thatdo admit an RCE are generic. We first present an example and then introduce a domain
restriction that excludes these cases and ensures existence.
Example 3 (The non­existence of RCE). Let S = {s1 , s2 , s3 } and N = {1, 2, 3}. Agents
have the following utility functions:1u1 (ρ, s3 ) = − + ρs322
u2 (ρ, s1 ) = ρs1 , u2 (ρ, s2 ) = ρs2 , u2 (ρ, s3 ) = − + ρs333
u3 (ρ, s1 ) = ρs1 , u3 (ρ, s2 ) = ρs2 , u3 (ρ, s3 ) = − + ρs3
4Each school is allowed to have any priority order, and bs1 = 1/2, bs2 = 1/2, and bs3 = 0.
We show that there is no RCE. By contradiction, suppose that there is. First we claim thatno student is matched with school s3 . If there were, then by exhaustiveness, at least one ofthe other two schools, i.e., s1 and s2 , should have a ratio greater than 1/2. Thus the student
matched with s3 prefers the school with a ratio greater than 1/2, contradicting fairness.
Since bs1 = bs2 = 1/2, in the case where s1 takes two students, the ratio at s1 is 1/2
while s2 only takes one student, and by exhaustiveness, has a ratio greater than 1/2. Thus,
any student matched with s1 prefers s2 , contradicting fairness. The same reasoning works
for the case where s2 takes two students.
u1 (ρ, s1 ) = ρs1 ,

u1 (ρ, s2 ) = ρs2 ,CROWDING IN SCHOOL CHOICE

17

We now introduce our domain restriction. Given a preference profile R ∈ R N , twoschools s1 and sk+1 are connected by indifference if there is a distribution ρ, a sequenceof distinct students {i1 , . . . , ik }, and a sequence of schools {s1 , . . . , sk+1 } such that(1) ρs1 = n1 and ρsk+1 = m1 for some m, n ∈ {1, . . . , |N |} and(2) (ρ, si ) Ii (ρ, si+1 ) for each student 1 ≤ i ≤ kNote that ρ in this case need not be part of an RCE, nor even be compatible with any
feasible alloction; it is an arbitrary vector. A preference domain satisfies no connection
by indifference (NCBI), if it contains no profile that is connected by indifference. Denoteby D ⊆ R N the subdomain of all profiles that are not connected by indifference.20 Callthis the NCBI domain. The preference profile presented in Example 3 is not in the NCBI
domain as as all three students are indifferent between (1/2, s1 ) and (1/2, s2 ). On the other
hand, the preference profile presented in Example 2 is not connected by indifference.
The NCBI domain D is not rectangular, but is open and dense in the full domain. Thus,
we may invoke the Kuratowski­Ulam theorem to say that for a generic profile of the others,
R−i , and a generic manipulation Ri′ of i, the resulting profile (Ri′ , R−i ) ∈ D.21 We are notpermitted to say anything about the probability of landing outside D; since R N is infinite
dimensional, there is no non­trivial, translation­invariant measure, and therefore no obvious
extension of the concept measure zero. For our algorithm, however, we consider a natural
finite­dimensional preference domain. Restricting to this domain, it is easy to see that theLebesgue measure of the event that an agent forces the problem outside the domain is zero(see Remark 2 in Section 7).
Theorem 1. Each preference profile in the NCBI domain admits an RCE.
The proof of Theorem 1 is in Appendix A.4. We provide a sketch of the argument here.
Start from a fair allocation. That is, we allow for the discrepancy between ρ−1s and theactual number of matched students to be arbitrarily large. The existence of fair allocations
is trivial: set the distribution equal to vector b and run the Deferred Acceptance mechanism.
20

NCBI is similar to the identically named condition in Andersson and Svensson [2014], although the twoare applied to different environments. Our condition is stronger than theirs, and the latter is not sufficient toshow existence of RCE in our model.
21
A set is generic if it is the countable intersection of open­and­dense sets. When a particular generic set isfixed (e.g., a subdomain) its elements are called generic. Endow R with the topology of closed convergence[Hildenbrand, 2015]. Thus, R is metrizable and hence second­countable. Assume D is open and dense, which
implies that it is both generic (also called comeager) in R N and has the Baire property. Given R−i ∈ R N \i ,let DR−i = {Ri′ ∈ R : (Ri′ , R−i ) ∈ D}. Then the Kuratowski­Ulam theorem implies that the set {R−i ∈R N \i : DR−i is generic in R} is generic in R N \i .

18

W. PHAN, R. TIERNEY, AND Y. ZHOUThe set of distributions that generate RCE, if non­empty, lie in the upper envelope of theset of distributions that generate a fair allocation. So, given that a fair allocation always
exists, our argument begins with one of these, and seeks to increase the distribution vector
while maintaining fairness. We do this with some graph theoretic tools.
With a distribution fixed, we study a graph with vertices S and such that an arc represents
a student at a given school who finds another school at least as good. A source set is a set ofvertices such that no arcs enter the set (there may be arcs among vertices in the set, so thatno vertex is a source on its own). Lemma 1 tells us that if we can find a set of schools that isa source set in our graph, and for which all schools fail our exhaustiveness condition, thenwe can perturb upwards the ratios for these schools and arrive at another fair allocation.
Thus, our goal is to move students among schools such that we do not violate fairness
and that we find a source set. This is the only part of the argument that requires NCBI,
and is achieved in Lemma 2. In sum, beginning with a fair allocation, if it is not an RCE,
then we can increase the ratio of some school and find another fair allocation. Along theway, we eliminate the problem of empty schools by simply putting students in them; NCBI
ensures they will not hinder us in finding a source set.
Having established that we can perturb upwards any fair allocation that is not an RCE, itremains only to make a limit argument. This is done in Theorem 6 in the Appendix, which
actually proves Theorem 1 and Proposition 3 below.
It is known that the exact auction of Demange et al. [1986] and its variants crucially de­pend on the quasi­linear assumption, and when agents have non­quasi­linear preferences,
they are not appropriate methods to show the existence of equilibrium [Zhou and Serizawa,2021]. Instead, the salary adjustment process of Crawford and Knoer [1981] and Kelso Jr
and Crawford [1982], and its variants are frequently used to establish the existence of equi­
librium [Herings, 2018, Fleiner et al., 2019]. In general, this method requires that agentsalways choose their favorite schools among those who have not rejected them yet, and an
agent’s welfare is independent of the number of tentatively matched agents. This is not truein our model, thus the method fails. Another well­known method is via Scarf’s Lemma[Quinzii, 1984]: One first shows existence when agents have piece­wise quasi­linear utility
functions and then takes the limit, approximating the original continuous utility functions. It
is unclear how to establish the existence of RCEs even when agents have piece­wise quasi­
linear utility functions, and the main challenges still come from showing exhaustiveness.

CROWDING IN SCHOOL CHOICE

19

5. Structural Properties of RCEs
In the classical model, the set of no justified envy and non­wasteful allocations has anumber of remarkable structural properties. Among them, the welfare lattice and the so­called Rural Hospitals Theorem stand out as particularly important [Roth and Sotomayor,
1990, Roth, 1986]. On the NCBI domain, we find analogous, sometimes identical prop­
erties. RCEs form a welfare upper lattice, which further implies the classical upper lattice
result via the embedding. We also show that the number of students matched to any school
remains constant across all RCE, which establishes a Rural Hospitals Theorem for our en­
vironment.
Along the way, we find a decomposition result that also has analogues in earlier literature,
but was previously unknown. We require, first, a definition. A sequence of distinct students(i1 , ..., ik ) constitutes a trading cycle from a matching σ to a matching τ if τ (il ) = σ(il+1 )for each 1 ≤ l ≤ k − 1 and τ (ik ) = σ(i1 ).
Proposition 2. Consider two arbitrary RCEs, (ρ, σ) and (γ, τ ), for a given preference
profile from the NCBI domain.
(1) When moving from (ρ, σ) to (γ, τ ), if student i experiences a strict welfare­improvement (welfare­reduction), then students in the same trading cycle as student
i experience a non­decreasing welfare change (non­increasing welfare change).
(2) If τ (i) 6= σ(i), then i is involved in a trading cycle from σ to τ .
The proof of Proposition 2 is in Appendix A.2. What follows is a sketch of the argument.
Schools whose ratio either increases or remains the same cannot take on more students(exhaustiveness). Students attending a school whose ratio increases must be better off, as its
increase causes it to rise above its lower bound and thereby be available for all. Then, using
Walrasian­type reasoning, we find that these better­off students must go to a school whose
ratio must not have decreased. This of course “closes off” the set of such schools and yields
the proposition for them. The proposition for the other students comes from feasibility, since
the schools whose ratios have decreased must take in the rest of the students, and from theproperties of RCE—these schools must also have “high enough” ratios by exhaustiveness.
The full argument is complicated by several technical details, most difficult among them
being: what if (γ, τ (i)) Ii (ρ, σ(i)), γσ(i) = ρσ(i) > bσ(i) and γτ (i) = ρτ (i) = bτ (i) ? Student
i may displace j at τ (i) who has i τ (i) j, since i’s indifference means that j’s presenceat τ (i), under allocation (σ, ρ), was not a priority violation. Student j’s welfare may drop,

20

W. PHAN, R. TIERNEY, AND Y. ZHOU

and she may envy i at (γ, τ ), without priority violation. The problem is that seemingly
nothing prevents i from being part of a trading path along which some previous student
has increasing welfare and all other previous students have non­decreasing welfare. For
this case we invoke NCBI, and the earlier Walrasian­type reasoning, as we find that sucha student i must actually be the end of an indifference chain originating at a school u ∈ Swith ρu = bu . Thus, it appears that NCBI is essential for this decomposition to hold.
Note the significance of claim 2 in the proposition. In general, if γs−1 > ρ−1s , then s might
be able to take on more students under (γ, τ ), and so may be the endpoint of a trading pathrather than a member of a trading cycle. In fact, this occurs among the fair allocations, andso our decomposition does not hold on that larger set of allocations.
Proposition 2 is reminiscent of the classical decomposition property of the marriage mar­ket [Roth and Sotomayor, 1990]: Moving from one stable outcome to another, there is a
one to one correspondence between agents on the one side who have strictly increased wel­fare (resp. strictly reduced welfare) and those one the other side whose welfare is strictly
reduced (resp. strictly increased). This property holds for competitive equilibrium/core out­
comes in the two­sided matching models with transfers as well [Demange and Gale, 1985].
Nevertheless, such a decomposition does not hold in our model. Instead, we provide a gen­eralized decomposition by associating welfare changes with trading cycles of components
in an allocation. In our language, the existing decomposition results can be read as follows:
if an agent experiences a strict welfare improvement, all the other agents in the same trading
cycle will also experience strict welfare improvement. In contrast, claim 1 of Proposition
2 admits the possibility of unchanged welfare in a trading cycle.
We state our version of the Rural Hospitals Theorem—a clear corollary of Proposition 2:
Theorem 2. Fix a preference profile from the NCBI domain and let (ρ, σ) and (γ, τ ) be
two RCEs for this profile. Then for each school s ∈ S, the number of students matched tos under σ is equal to the number of students matched to s under τ .
Consider the set of RCEs in Example 2. There are two RCE matchings. The first oneis σ = (σ(1), σ(2), σ(3)) = (s1 , s1 , s2 ). The second one is σ ′ = (σ ′ (1), σ ′ (2), σ ′ (3)) =(s2 , s1 , s1 ). In either matching, school s1 is always matched with two students and schools2 is matched with one student. The standard Rural Hospitals Theorem also states that if aschool has unfilled seats at a stable matching, then it matches to the same set of students inevery stable matching. Example 2 also demonstrates that this fact is not true under crowd­
ing.

CROWDING IN SCHOOL CHOICE

21

Given two distributions, ρ and γ, let ρ∨γ ∈ [0, 1]S denote the vector whose s component,
for each s ∈ S, is max{ρs , γs }.
Theorem 3. Assume that (ρ, σ) and (γ, τ ) are RCEs for a preference profile from the NCBI
domain. There is a matching µ such that (ρ ∨ γ, µ) is an RCE, and for each i ∈ N ,(ρ ∨ γ, µ(i)) Ri max{(ρ, σ(i)), (γ, τ (i)).}Ri

The theorem states that the set of RCE’s has an upper­lattice structure in welfare space.
It does not always have a lower­lattice.
The full proof of Theorem 3 is in Appendix A.2. Similar to extant results of similar
character, a decomposition result, in our case Proposition 2, is the main tool. We simply
begin with one of the two RCEs, say (ρ, σ), and to arrive at a candidate matching, µ, executeall the welfare­non­decreasing trading cycles from σ to τ . Then we show that (ρ ∨ γ, µ)is an RCE. If (ρ ∨ γ)s = γs > ρs , then any student i ∈ σ[s] must have increased welfare,as otherwise they would prefer s at (γ, τ ) and the previous inequality gives γs > bs . Then
Proposition 2 and some supporting results in the appendix allow us to conclude that i is partof a cycle among schools whose resource ratio is at least as high under γ as it is under ρ.
This further allows us to use the feasibility of (γ, τ ) to conclude the feasibility of (ρ∨γ, µ).
Since all students are partitioned by Proposition 2, the execution of these cycles will notinterfere with each other. The foregoing argument studied the case when ρ 6= γ. However,the decomposition holds equally well when ρ = γ and so demonstrates that RCE induce
an upper­lattice in welfare space.
It is in general not true that the existence of an upper lattice in distributions implies theexistence of an upper lattice in welfare (see Example 4 below). Here again the NCBI domain
seems crucial.
Since we have an upper lattice in welfare space, a limit argument is sufficient to show
the existence of a greatest RCE welfare vector. Several RCEs may induce this vector, all ofwhich have the same distribution. Any RCE that induces this vector is called maximal. For
Example 2, one such maximal RCE is given by distribution (1/2, 17/22) paired with matching(s2 , s1 , s1 ). We formalize the foregoing observations as follows.
Proposition 3. Given a preference profile R from the NCBI domain,(1) there is a greatest RCE distribution ρ∗ (R),(2) there is a maximal RCE, with distribution ρ∗ (R), and all students are indifferent
between all maximal RCEs, and22

W. PHAN, R. TIERNEY, AND Y. ZHOU

(3) among all RCEs, only the maximal RCEs satisfy student­optimal fairness.
The proof of Proposition 3 is in Appendix A.4. It is not true that an RCE compatible withρ∗ (R) always maximizes students’ welfare; maximal RCEs are a strict subset of the RCEs
that are compatible with ρ∗ (R).
We conclude this section with two remarks. First, in Section 3.1 we showed that thestandard school choice model can be embedded in our model. Recalling that the embedded,
standard model may have an outside option, even though our more general model does
not, it follows that the standard Rural Hospitals Theorem of Roth [1986] is a corollary ofTheorem 2. Theorem 3 and Proposition 3 mirror the standard welfare lattice results in Rothand Sotomayor [1990], but here we only consider the student side of the market and its
corresponding direction in the lattice. Second, even when RCEs exist for profiles outside
the NCBI domain, the structural results above may fail to hold.
Example 4 (Lack of structure on the general domain.). The reader will observe that thestructures above fail for the same reason they do in the standard school choice model when
students’ preferences may have indifferences.
Let S = {s1 , s2 , s3 , s4 } and N = {1, 2, 3}. Agents have the following preferences: Foreach ρ ∈ [0, 1]S ,(ρ, s1 ) I1 (ρ, s2 ) P1 (ρ, s3 ) P1 (ρ, s4 )(ρ, s1 ) P2 (ρ, s4 ) P2 (ρ, s3 ) I2 (ρ, s2 )(ρ, s2 ) P3 (ρ, s3 ) P3 (ρ, s1 ) I3 (ρ, s4 )Each school has unit capacity, i.e., bs1 = bs2 = bs3 = bs4 = 1. Schools have the following
priority rankings: 1 s1 2 s1 3; 1 s2 3 s2 2; 3 s3 2 s3 1; and 2 s4 3 s4 1.
Let ρ = (1, 1, 1, 1). There are two RCEs compatible with ρ, clearly making ρ∗ (R) = ρ.
The first one is (ρ, σ) such that (σ(1), σ(2), σ(3)) = (s1 , s4 , s2 ). The second one is (ρ, τ )such that (τ (1), τ (2), τ (3)) = (s2 , s1 , s3 ). It is not hard to see that there is no trading cyclefrom σ to τ , and so Proposition 2 fails to hold. Also at (ρ, σ) school s3 is empty and at (ρ, τ )school s4 is empty school. Therefore, Theorem 2 fails to hold. Note that in both of the
RCEs mentioned, two students get their favorite possible bundle, and one gets their second
favorite. Thus, the only way to improve upon this is with matching (µ(1), µ(2), µ(3)) =(s1 , s1 , s2 ) or matching (µ′ (1), µ′ (2), µ′ (3)) = (s2 , s1 , s2 ), both of which are infeasible.

CROWDING IN SCHOOL CHOICE

23

However, student 2 prefers (ρ, τ (2)) to (ρ, σ(2)). Thus Theorem 3 fails to hold. Since
there are no maximal RCEs, Proposition 3 fails to hold as well.
Examples 3 and 4 highlight the role of our domain restriction, NCBI. However, it is worth
noting that the structural properties hold under a weaker restriction. In particular, we may
relax the first condition in the definition of connected by indifference, requiring only that
ρs1 = bs1 and ρsk+1 = bsk+1 . However, this domain restriction is not sufficient for our proofof the existence of RCE. See Appendix section A.1 for details.
6. Maximal RCE Mechanisms
Fixing an environment of schools, students, and lower­bounds, for each profile in the
NCBI domain, there is a non­empty set of maximal RCE allocations, between which all
students are indifferent (Proposition 3). A maximal RCE mechanism is a function that
selects, for each profile in the NCBI domain, a maximal RCE allocation; we do not define
these mechanisms on the full domain. Thus, all maximal RCE mechanisms are welfare
equivalent.
Theorem 4. Any maximal RCE mechanism on the NCBI domain is strategy­proof.
The full proof of Theorem 4 is in Appendix B. For some intuition as to how it works,
consider first the properties of ρ∗ (·), the greatest RCE distribution. Consider a student i
who is not even weakly envied by a student at a different school. That is to say, all students
not attending i’s school strictly prefer their outcome to i’s. Then it better not be feasible toraise the ratio at i’s school, because if it were, then we could do so by a very small amount,make i and her classmates happier, and not induce any envy from other students. Thus, foreach student i one of the following is true: 1) some student j from another school finds
i’s outcome at least as good as her own or 2) the ratio at i’s school exactly correspondswith the number of students there. For case (2), this means that the ratio at i’s school isof the form 1/k, where k is the number of students at i’s school. We say such a school iscompletely exhausted. The above reasoning then implies that, for each student for whom
(1) is true, we must be able to find a chain of students {j, k, . . . , l} such that j finds i’s
outcome at least as good as her own, k finds j’s outcome at least as good as her own, etc.,
and l’s school is completely exhausted. This is the so­called connectedness property, seenin similar environments.

24

W. PHAN, R. TIERNEY, AND Y. ZHOUNow let i declare a Ri′ such that her preference for her outcome is strictly stronger than
before. That is, Ri′ is a strict Maskin monotonic transform of Ri at her initial outcome.
Ignoring complications, if she stays at her original school, then the connectedness property
prevents the ratio at her school from rising. If she goes to another school, the connectedness
property prevents the ratios of these schools from rising as well, so the only way her new
outcome can be Ri better than the original is if she goes to a school that has hit its lower
bound. Then we use our decomposition and the connectedness property to find that wecannot displace these students and make them happier, so i induces violation of fairness at
this new school. In the appendix we show that, if the rule were manipulable, then it would
be manipulable via a Maskin monotonic transform, and thus our argument is complete.
7. An Algorithm for Maximal RCE
As discussed after Theorem 1, it is non­trivial to find an algorithm that calculates an RCE
in a finite number of steps, in particular, when students have general preferences as studied
here. We can, however, on a restricted domain. Say a preference relation R ∈ R is linear
if there is a vector v ∈ RS++ such that the utility function (r, s) 7→ rv(s) represents R. For
the remainder of this section, we fix a profile of linear preferences R ∈ D.
Remark 2 (NCBI in Linear Preferences). In the domain of linear preferences, a violationof NCBI is a sequence {1, . . . , J} of students, a sequence {1, . . . , J + 1} of schools, and a
distribution ρ ∈ RS such that, for each j on the sequence, ρj vj (j) = ρj+1 vj (j + 1), and for−1
the two end points, ρ−1
1 ∈ N and ρJ+1 ∈ N. By recursion on this sequence, we find there
are p and q ∈ N such thatq ∏ vj (j + 1)
vk (k + 1)=.
vk (k)
p j̸=k vj (j)Note that without loss of generality we may restrict attention to representations such thatvi (1) = 1, and therefore, given R−k , k has at­most­countably many reports that would
induce a failure of NCBI. Thus, by Fubini’s theorem, students almost surely report a profilethat is within our domain.
The algorithm we introduce uses tools from the multi­item auction [Demange et al.,1986], and the Deferred­Acceptance algorithm [Gale and Shapley, 1962], presented in theframework of Drèze equilibrium (Section 3.2). In brief, starting from an initialized distri­bution, the algorithm will decrement it continuously, pausing occasionally to “reject” some

CROWDING IN SCHOOL CHOICE

25

students from some schools; the rejected students cannot thereafter demand these schools.
In such cases, time is advanced discretely and, if possible, decrementing is re­initialized.
At each moment z ∈ R in time, each student i is permitted to demand a set Qiz of objects,
and so their rationed demand set is Di (ρz , Qiz ), shortened to Diz for simplicity. Say thati requires S ′ if Diz ⊆ S ′ . A set S ′ ⊆ S is in excess demand if (1) the number of students∑′′′
i who require S ′ exceeds s∈S ′ bρ−1s c, and (2) for each S ⊊ S , the number of students∑
whose demand intersects S ′′ , among those requiring S ′ , is larger than s′ ∈S ′′ bρ−1s′ c. There∗is a unique set Ez in the collection of sets in excess demand with maximal cardinality, which
can be found in a computationally efficient way [Andersson et al., 2013].
The following decrementing process will be used in the algorithm. Let z be a time atwhich decrementing starts, or restarts. There is a set Ωz ⊆ S whose ratios are continuously
decreasing while Qz = (Qiz )i∈N remains constant. Each s ∈/ Ωz maintains a constant ratio.
′
Then, for z ≥ z in the same decrementing phase as z, let ρsz z s ∈ Ωzz′ρsz′ =
0s∈/ Ωz
The reader may verify that the resulting distribution path ρz has the following property,
given linear preferences: if Diz ⊆ Ωz , then Di,z′ remains constant throughout the decre­
menting phase.
The Algorithm. Time begins at z = 0, the distribution is initialized at ρ0 = (1, . . . , 1),
and each Qiz = S. The algorithm consists of three subroutines, described below. In eachcase, assume for notational simplicity that the subroutine is entered at time z. The algorithm
begins in the subroutine pause.
Pause: Calculate Ez∗ .
If Ez∗ is empty, the algorithm is terminated.
If all schools in Ez∗ can be decremented, i.e., if each s ∈ Ez∗ has ρsz > bs , then go to
subroutine decrementing.
∗If Ez contains a school that cannot be decremented, go to subroutine rejection.
Regardless of the condition under which the algorithm exits this subroutine, the time at exit
equals the time at entry.
Rejection: Let s ∈ Ez∗ have ρsz = bs . Find the i ∈ N who is s ­lowest priority among
those students j with s ∈ Djz . Advance time 1 unit to z +1 and exit with Qjz+1 = Qjz \{s}for all j with i s j and for j = i. Go to subroutine pause. Note that s will reject at most26

W. PHAN, R. TIERNEY, AND Y. ZHOU

|N | − b−1
s times before it is no longer in excess demand, so this subroutine will be invokedat most |S| (|N | − b−1s ) times.
Decrementing: Advance time continuously and decrement ρz according to the path given
above, with Ωz = Ez∗ . Exit at time z ′ > z, when either(1) there is s ∈ Ez∗ with ρsz′ = 1/k for k ∈ N or(2) there is i who requires Ez∗ at z for whom Diz′ 6= Diz .
Since the rationed demands of students who require Ez∗ are locally constant, decrementing
will run at least for an open set of time. Upon exit, go to subroutine pause.
When the algorithm terminates, say at time z, Hall’s theorem (Hall [1935]) guarantees
the existence of an equilibrium assignment σ, which of course corresponds to the existenceof a feasible allocation (ρz , σ). In Appendix C we finish the proof of
Theorem 5. For linear preference profiles from the NCBI domain, the algorithm terminatesin finite time with finitely many elicitations of demand, and results in a maximal RCE.
8. Discussion
8.1. Dropping Inferior Empty Schools. Let an allocation be a weak RCE if it satisfies
all the conditions of RCE except for the inferior empty schools condition. There exists a
weak RCE in the NCBI domain. A parallel result to Proposition 2 for weak RCEs would
decompose changes into trading cycles of positive or negative welfare value, and indiffer­ence chains. The Rural Hospitals Theorem (Theorem 2) no longer holds for weak RCEs.
Fortunately, all of the other remaining results can be established. The proofs of the above
statements are analogous to those in the main text so we omit them.
8.2. Applications beyond School Choice. The first application is to the problem of labormarkets with financially constrained start­ups. Consider the labor market where there
is a finite set of start­ups F and a finite set of workers W . Each start­up f ∈ F is subject tosome (hard) financial constraints so that expenditure for labor employment κf > 0 is fixed
for the modelled time period. Given this, the start­up selects employees following a priority
order f . The labor market is protected by a minimum wage w such that 0 < w ≤ κf foreach f ∈ F . Each worker w ∈ W has a complete and transitive preference relation Rw
over {(t, f ) ∈ R × F : 0 ≤ t ≤ κf } such that for each f ∈ F and t, t′ ∈ [0, κf ] with t > t′ ,(t, f ) Pw (t′ , f ). The tuple (F, W, R, κ, ≻, w) summarizes primitives of the problem.

CROWDING IN SCHOOL CHOICE

27

We reformulate the problem to apply our results. Let F , W , and ≻ be as defined above.
For each f ∈ F , let bf = κwf . Each worker w ∈ W has a complete and transitive preference∗∗
relation Rw
over [0, 1] × F such that for each f, f ′ ∈ F and each t, t′ ∈ [0, 1], (t, f ) Rw
(t′ , f ′ ) if and only if (tκf , f ) Rw (t′ κ′f , f ′ ). It is easy to see that all our results hold in
the problem (F, W, R∗ , b, ≻) and therefore the insights can be carried over to the original
problem (F, W, R, κ, ≻, w).
The second application is to the problem of allocating polluting firms. Instead of stu­
dents and schools, consider polluting firms and subnations. Each firm is willing to invest in
at one most one subnation. Each subnation s is endowed with an amount of the same envi­
ronmental resource, and the priority for selecting polluting firms is based on their industrial
development policy. Let b−1
s be the maximum number of polluting firms that the subnation
is willing to admit. Each firm prefers to locate to a subnation where they are allowed ahigher level of pollution. As this is simply a re­interpretation of the model, we are able todirectly apply our results for this application.
9. Conclusion
We provide a new framework to model school choice with crowding and establish analogsof key results in the school choice and matching literature. Many issues of perennial
interest—diversity considerations, efficiency improvements, sibling guarantees, etc.—canbe reconsidered in this model. We also align with the empirical literature’s explicit consid­
eration of per capita crowding metrics.
The model also opens up completely new avenues of exploration not suited to the stan­
dard one. Most interesting is the question of redistributing resources between schools. We
have assumed that each school has a fixed endowment of resources, but in practice theresources of all schools in a given district are usually controlled centrally by that district.
For example, money or physical infrastructure (such as a trailer) can be shifted from one
school to another; counselors routinely serve multiple schools. Thus, we can design new
mechanisms encompassing such distribution between schools. We can also ask if there areways to redistribute resources so that, ex post, our mis­match between supply and demand iscompletely eliminated. More generally, we can study comparative statics in this dimension
and build a more dynamic model of educational resource allocation.
It is worth noting, in conclusion, that the model implicitly covers a wide variety of dif­ferent crowding effects. We have modeled crowding in a hyperbolic way: n students share

28

W. PHAN, R. TIERNEY, AND Y. ZHOU

resources at (approximately) 1/n per­capita. However, our relatively unrestricted domainof preferences contains within it many subdomains that each embody different notions of1−ηscrowding. For example, the reader may verify that a function of the form (ρs , s) 7→ vs ρ1−ηexhibits decreasing marginal disutility for crowding if η > 2.22

Appendix A. Existence of RCE and maximal RCE
We proceed in four subsections. In Section A.1 we study the set of fair allocations, whichcontains the set of RCE, and which can be trivially shown to be non­empty on our domain.
In Section A.2 we show that RCE, if they exist, induce an upper lattice in welfare space,which then leads to Theorem 3. Proposition 2 is necessary for this argument, so we give its
proof here as well. In Section A.3, we uncover some Pareto dominance relations in the setof fair allocations (“the fair set” for short). These imply that RCE will lie in the welfare­upper­envelope of the fair set, and so will exist if the fair set induces a closed set in welfare
space. Finally, we conclude in Section A.4 with the (simple) topological arguments that are
required for this upper­envelope to exist.
A.1. Existence of Fair Allocations. A preference domain D ′ ⊆ R N satisfies no bound­ary indifference (NBI), if for each pair of schools s and t and each R ∈ D ′ , there is no
chain of indifference connecting (bs , s) and (bt , t). Note that if R satisfies NCBI, then it
satisfies NBI.
Proposition 4. A fair allocation exists on any NBI domain.
Proof. Consider ρ ∈ [0, 1]S such that ρs = bs . Then we have a standard school­choiceproblem where the capacity of school s ∈ S is b−1
s . NBI implies that student preferences
are strict, so the set of stable matchings is non­empty [Roth and Sotomayor, 1990]. Let σ
be a stable matching for this problem. Clearly, it satisfies no­blocking, in the sense of ourmodel. Thus, (ρ, σ) is a fair allocation.
■
A.2. The upper­lattice property. Given two allocations, (ρ, σ) and (γ, τ ), construct theilabeled, directed transfer graph T on vertices S so that s → t ∈ T if σ(i) = s, τ (i) = t,
22

2

d
1
Calculate dn
2 u( /n, s).

CROWDING IN SCHOOL CHOICE

29

and s 6= t. Define the sets
S + = {s ∈ S : γs > ρs }N + = {i ∈ N : (γ, τ (i)) Pi (ρ, σ(i))}

S = = {s ∈ S : γs = ρs > bs }N = = {i ∈ N : (γ, τ (i)) Ii (ρ, σ(i))}

S ∗ = {s ∈ S : γs = ρs = bs }.
We denote by s⇝t ⊆ T (σ, τ ) a simple path in the transfer graph, which is to say, a pathwith no repeated arcs. Note that since our graph may contain several arcs, with the sameorientation, between a given pair of vertices, there may be many distinct paths from s to t,even on the same ordered list of vertices. We distinguish between different paths either bydecoration, so that s⇝′ t 6= s⇝t, or superscript index, so that s⇝m t 6= s⇝n t when n 6= m.
A path is positive if it contains an N + ­labeled arc. A positive path is totally­positive if it
contains only labels from N + ∪ N = .
The in­degree of a set of vertices V ⊆ S is the number of edges s → t ∈ T with s ∈/Vand t ∈ V . Symmetrically, the out­degree is the number of such edges where s ∈ V andt∈/ V.
Given the language just introduced, we rephrase Proposition 2.
Proposition 5. Let (ρ, σ) and (γ, τ ) be two RCEs for a profile R satisfying NBI. Let T
be the transfer graph from (ρ, σ) to (γ, τ ), and let the sets S + , S = , S ∗ , N + , N = be defined
as above. Then any path s⇝t ⊆ T touching a S + school is positive. Any positive path
is a totally­positive cycle, confined to S = S + ∪ S = ∪ S ∗ . Moreover, these cycles can beconstructed so that they are all mutually disjoint.
Proof. We first establish several claims.
Claim 1. For each s ∈ S with σ[s] 6= ∅, the out­degree of s in T is at least as large as its
in­degree.
Proof of claim. For each s ∈ S, with σ −1 [s] non­empty,−1bγs−1 c ≤ bρ−1s c = |σ [s]|,and so there cannot be more students at s under (γ, τ ) then under (ρ, σ), and so for any arc
entering s, there must be at least one exiting.
iClaim 2. If s → t ∈ T has s ∈ S and i ∈ N + ∪ N = , then t ∈ S.

30

W. PHAN, R. TIERNEY, AND Y. ZHOUProof of claim. If t ∈/ S, then γt < ρt , and furthermore, ρt > bt . Since (ρ, σ) is an RCE andσ(i) = s, (ρ, s) Ri (ρ, t). Since, γt < ρt , (ρ, s) Pi (γ, t), and since τ (i) = t, i ∈/ N + ∪N = .
Claim 3. σ[S + ] ⊆ N + and τ (N + ) ⊆ S + ∪ S ∗ .
Proof of claim. For s ∈ S + , γs > bs . Therefore, for each i ∈ N , (γ, τ (i)) Ri (γ, s). In
particular, for i ∈ σ[s], preference monotonicity gives(γ, τ (i)) Ri (γ, s) Pi (ρ, s) = (ρ, σ(i)) .
Thus, i ∈ N + .
Let i ∈ N + . If τ (i) ∈/ S + , then by preference monotonicity(ρ, τ (i)) Ri (γ, τ (i)) Pi (ρ, σ(i)) ,and so bτ (i) = ρτ (i) ≥ γτ (i) ≥ bτ (i) . This yields τ (i) ∈ S ∗ .

Claim 4. Consider a path in T of the following form:
i

j

t→u→v
with i ∈ N + and j ∈/ N + . Then j ∈ N = , u ∈ S ∗ , v ∈ S + ∪ S = , and σ[v] 6= ∅.
Proof of claim. By Claim 3, u ∈ S + implies j ∈ N + , and so γu ≤ ρu . Since i ∈ N + ,(ρ, u) Ri (γ, u) = (γ, τ (i)) Pi (ρ, σ(i)) .
It follows that u ∈ S ∗ and, since σ(j) = u, j u i. Thus if j is made worse off going to(γ, τ ), we have(γ, u) = (ρ, u) = (ρ, σ(j)) Pj (γ, τ (j)) ,implying, since τ (i) = u, that i u j. In sum, we have j u i and i u j, a contradiction.
Therefore, j ∈ N = . Since u ∈ S ∗ , if γv = bv , then j is indifferent between (bu , u) and(bv , v), contradicting NBI. Moreover, if ρv > γv , then ρv > bv and(ρ, v) Pj (γ, v) = (γ, τ (j)) Ij (ρ, σ(j)) ,contradicting that (ρ, σ) is an RCE. Conclude that v ∈ S + ∪ S = . Finally, if σ[v] = ∅, then(ρ, u) = (ρ, σ(j)) Pj (ρ, v) = (1, v) Rj (γ, v) = (γ, τ (j)) ,where the strict relation is by inferior empty schools, contradicting that j ∈ N = .

CROWDING IN SCHOOL CHOICE

31

1

Let s → u ∈ T have 1 ∈ N + . We shall extend this to a path s⇝t. By Claim 3, u ∈ S. If
it were the case that σ[u] = ∅, then since (ρ, σ) is an RCE, inferior empty schools implies,(ρ, s) P1 (ρ, u) = (1, u) = (γ, u) ,2

contradicting that 1 ∈ N + . By Claim 1, there is u → v ∈ T . If 2 ∈ N + , we could then startwith this edge instead. Continuing inductively, let j be the first student on the path who is
not in N + (if such an student does not exist, the argument yields a totally positive cycle, as
desired). We have that s⇝t decomposes toj1

s → u⇝v → σ(j) → w,
where u⇝v, if it exists, is labeled by N + students. By Claim 4, j ∈ N = , σ(j) ∈ S ∗ ,kw ∈ S + ∪ S = , and σ[w] 6= ∅. If w ∈ S + , then the path is extended by an arc w → w′
with k ∈ N + (Claims 1 and 3). Our argument has returned to its starting point; our goal
is simply to show that a path initiated by a positive arc cannot have a terminal arc, remains
within S, and is labeled only by N + ∪ N = students. Thus, we proceed constructively, andwhen we arrive at an arc with an N + label, call this the escape condition of our proof.
k
Assume, therefore, that w ∈ S = . Claim 1 implies there is w → w′ ∈ T . Note thatk ∈ N + ∪ N = , as otherwise,(γ, w) = (ρ, w) = (ρ, σ(k)) Pk (γ, τ (k)) ,violating that (γ, τ ) is an RCE. If k ∈ N + , we have encountered the escape condition again,so assume k ∈ N = . By Claim 2, w′ ∈ S. If w′ ∈ S + , then ρw′ < 1 so σ[w′ ] 6= ∅, and there
must be an outgoing N + arc from w′ (Claims 1 and 3); again we have the escape condition.
Thus, to continue the argument, assume w′ ∈ S ∗ ∪ S = . Now if w′ ∈ S ∗ , we havejσ(j) → w → w′kwith σ(j), w′ ∈ S ∗ , and j, k ∈ N = . This is an indifference chain connecting two S ∗ schools,
contradicting NBI. Conclude that w′ ∈ S = , so
(ρ, w) Ik (γ, w′ ) = (ρ, w′ ) ,where the indifference is because k ∈ N = . Since (ρ, σ) is an RCE, by inferior empty
schools, σ[w′ ] 6= ∅. We can then repeat the foregoing arguments and continue the path. Ink′particular, w′ must have an outgoing arc w′ → w′′ , and k ′ ∈ N + ∪ N = . If k ′ ∈ N + , we getthe escape condition, and if k ′ ∈ N = , we again conclude that w′′ ∈ S = and σ[w′′ ] 6= ∅.

32

W. PHAN, R. TIERNEY, AND Y. ZHOU

Conclude that we can further decompose s⇝t to
1

js → u⇝v → σ(j) → w⇝x → t
where(1) u⇝v, is labeled by N + students, and is contained in S by Claim 3,(2) j ∈ N = and σ(j) ∈ S ∗ ,(3) w⇝x, is within S = and labeled by N = students,(4) t ∈ S + .
These segments need not all exist. If the last segment exists, then we are back where we
started and repeat the argument. In any case, we have shown that any N + labeled arc
s → u induces a path that is always labeled by N + ∪ N = students, is always within S(except possibly for the very first vertex, s), and can always be extended. It follows that we
can find a cyclic sub­path, not necessarily including s. However, by deleting the cycle fromT (viewing the graph as a set of labeled edges), we preserve the vertex degree inequalityof Claim 1, and none of the other claims are affected. Thus, we may repeat the argument.
Eventually, we must find a cycle involving s, implying s ∈ S.
Note, finally, that if s → t ∈ T and t ∈ S + , then since ρt < γt ≤ 1, σ[t] 6= ∅, and byi
Claim 1, there is t → u ∈ T , and i ∈ N + . Invoking the argument above, we find that any
path that touches a S + school is a totally positive cycle.
■
Now we apply Proposition 5 to the NCBI domain and complete the proofs of Proposition
2 and Theorem 3.
Proof of Proposition 2. Note that Proposition 5 can be applied in reverse, from (γ, τ ) to(ρ, σ) to get the first claim of this proposition. Thus, to complete the decomposition, it
remains to show that there are no paths in T that are not cycles. We have already shown
this for signed paths, so suppose s⇝t ⊆ T is labeled only by N = students. Then eachivertex on the path belongs to S ∗ ∪ S = . If u → v ∈ s⇝t has σ[v] = ∅, then by inferior
empty schools, (ρ, u) Pi (1, v) = (γ, v), contradicting that i ∈ N = . If τ [u] = ∅ thenreverse the argument. Clearly only s or t could be empty in one of the two RCEs, and oneof the two arguments just made applies to each, so no vertex touched by the path is empty
at either RCE. Then, since (ρ, σ) and (γ, τ ) are both exhaustive, for each vertex u touched−1∗=by the path, bρ−1
u c = |σ[u]| and bγu c = |τ [u]|. Since u ∈ S ∪ S , ρu = γu and so|σ[u]| = |τ [u]|. Thus, s⇝t can be extended to u → s⇝t → v. If u⇝v is labeled only by

CROWDING IN SCHOOL CHOICE

33

N = students, then we may repeat the argument. Since there are finitely many vertices, we
can eventually extend to a cycle, either by exhaustion of the argument in this paragraph, orby extending to a signed path.
■
Proof of Theorem 3. Let T be the transfer graph from (ρ, σ) to (γ, τ ). Let µ be the matchingthat results from executing all the positive paths in T on σ. That is, if i labels an arc on a
positive path, then µ(i) = τ (i), and otherwise µ(i) = σ(i). Let ζ = ρ ∨ γ. We show that(ζ, µ) is an RCE. Since positive paths are totally positive cycles, the number of students
at each school is unchanged from σ to µ, so (ζ, µ) satisfies exhaustiveness. To check that(ζ, µ) is an allocation, it is sufficient to check the schools whose distribution has increased.
That is, pick s ∈ S + , where S + is defined as above. Since |τ −1 [s]| = |σ −1 [s]|, and ζs = γs ,distribution feasibility at school s then follows from the distribution feasibility of (γ, τ ).
Let N ′ be the set of students on a totally positive cycle. By Proposition 5, totally positive
cycles are confined to S, so each i ∈ N ′ gets (ζ, µ(i)) = (γ, τ (i)). The total­positivity ofthese paths also yields∀i ∈ N ′ , (ζ, µ(i)) = (γ, τ (i)) Ri (ρ, σ(i)) .

(1)

Each i not on a totally positive cycle gets µ(i) = σ(i). Let σ(i) = s. There are twocases, s ∈ S + or not. If s ∈ S + , then Proposition 5 implies that i cannot label any arc in
T , as any such arc is then part of a totally positive cycle. Thus, τ (i) = σ(i) and we have(ζ, µ(i)) = (γ, τ (i)). Then by preference monotonicity we have(2)∀i ∈ σ[S + ] \ N ′ , (ζ, µ(i)) = (γ, τ (i)) Pi (ρ, σ(i))

If s ∈/ S + , then ζs = ρs and so (ζ, µ(i)) = (ρ, σ(i)). If i ∈ N + , then since γs ≤ ρs , it must
be that τ (i) 6= σ(i) = s. Then i would be on a totally positive cycle. Therefore, i ∈/ N+
and again we conclude(3)∀i ∈ σ[S \ S + ] \ N ′ , (ζ, µ(i)) = (ρ, σ(i)) Ri (γ, τ (i)) .

In all cases, we have found that, at (ζ, µ), students are consuming either their bundle under(ρ, σ) or their bundle under (γ, τ ). Moreover, since
(
) (
) (
)
σ[S + ] \ N ′ ∪ σ[S \ S + ] \ N ′ = σ[S + ] ∪ σ[S \ S + ] \ N ′ = N \ N ′ ,lines 1, 2, and 3 yield(4)∀i ∈ N, (ζ, µ(i)) Ri max{(ρ, σ(i)) , (γ, τ (i))}
Ri

34

W. PHAN, R. TIERNEY, AND Y. ZHOU

Suppose (ζ, s) Pi (ζ, µ(i)), which by line 4 implies(ζ, s) Pi max{(ρ, σ(i)) , (γ, τ (i))}.
Ri

Assume there is j ∈ µ[s], so (ζ, µ(j)) = (ζ, s). Then since (ζ, µ(j)) ∈{(ρ, σ(j)) , (γ, τ (j))}, plugging the appropriate case into the previous line yieldsj s i.
Assume, therefore, that s is empty under µ. Then it is empty under σ, and so ζs = ρs = 1.
Thus, again invoking line 4,(1, s) = (ρ, s) Pi (ζ, µ(i)) Ri (ρ, σ(i)) ,contradicting that (ρ, σ) is an RCE. Therefore, (ζ, µ) satisfies fairness.
Finally, by Theorem 2, the set of empty schools remains the same in (ρ, σ) and (γ, τ ),and so also in (ζ, µ). Thus, by line 4, (ζ, µ) satisfies inferior empty schools.
■iA.3. Domination lemmas. Given an allocation (ρ, σ), let s → t ∈ Γ if σ(i) = s 6= t, and(ρ, t) Ri (ρ, s). We say that Γ is the weak envy graph of (ρ, σ).
Recall that a source set in a directed graph is a set of vertices that no edge enters. For­
mally, it is a set S ′ ⊆ S such that if s → t ∈ Γ and s ∈/ S ′ , then t ∈/ S ′.
Say a school s ∈ S is totally exhausted at (ρ, σ) if |σ −1 [s]|ρs = 1.
Lemma 1. Let (ρ, σ) be a fair allocation with weak­envy graph Γ. Suppose S ′ ⊆ S \ S ∗ ,not empty, is a source set in Γ and that no school in S ′ is totally exhausted. Then there isan RCE (γ, τ ), Pareto­dominating (ρ, σ) and with γ ⪈ ρ.
Proof. Let N ′ = σ −1 [S ′ ]. For each s ∈ S ′ , let ns = |σ −1 [s]|. We shall construct anassignment market isomorphic to the problem we currently face when restricted to N ′ andS ′ . To aid comparison of our current model with the assignment market we employ, we use
the terms stability and blocking. For our model, clearly s and i block (ρ, σ) if σ(i) 6= s andeither σ[s] = ∅ or i has (justified) envy at s. An allocation is stable if there are no blocks.
∑
Let S be a set of s∈S ′ ns elements. Let f : S → S ′ have |f [s]| = ns . We view S as theset of copies of the elements of S ′ .
Each s ∈ S consumes a point (l, i) ∈ R × N ′ and has simple preferences represented
by utility function Ws (l, i) = l; copies of schools care only about resources. Each copy has
an outside option denoted ws , so that s will withdraw from the matching (now an option)
before accepting a bundle giving utility less than ws . With abuse of notation, we retain thesame notation for the students. Each i ∈ N ′ consumes a point (r, s) ∈ R × S and has

CROWDING IN SCHOOL CHOICE

35

preferences so that(r, s) Ri (r′ , s′ ) ⇐⇒ (r, f (s)) Ri (r′ , f (s′ )).
Let Ui be a continuous utility function representation of Ri . Assume that the outside option
utility for students is −∞. When an student and a school match, one unit of divisible re­source is produced, independent of their identities. We now have a one­to­one assignment
market, matching the sets N ′ and S together, and each matched pair having a unit of di­visible resource to divide. Demange and Gale [1985] show that, in this model, there is aunique student­optimal stable utility profile (u, w), with at least one and possibly several
matchings that yield these utilities. Moreover, there is at least one s ∈ S with ws = ws .
Let σ̂ : N ′ → S be a bijection such that each σ̂(i) ∈ f [σ(i)]. The RCE (ρ, σ) induces
the following allocation on the constructed assignment market: Each i ∈ N ′ gets (ρf (s) , s)
and s ∈ S gets (1 − ρf (s) , σ̂ −1 (s)).23
We show in this paragraph that, so long as ws ≤ 1 − ρf (s) , the allocation (ρ, σ̂) in theconstructed assignment market is stable. Clearly, no individual rationality constraints are
violated. Since (ρf (s) , f (s)) Ri (ρf (s′ ) , f (s′ )) when f (s) = σ(i), i and s′ could only form ablocking pair by giving i at least ρf (s′ ) , leaving only 1 − ρf (s′ ) for s′ .
Fix ε > 0 and set each ws = 1 − ρf (s) − ε. Let (u, w) be the student­optimal utility
profile for this problem, and let µ̂ be a matching that supports it. Since (ρ, σ̂) is stable,
Demange and Gale [1985] also show that, for each s ∈ S, ws ≤ 1 − ρf (s) .
Suppose there are s, s′ ∈ f [s] with ws < ws′ . Let j = µ̂−1 (s′ ). By feasibility, j is getting
no more than rj = 1 − ws′ units of resource at s′ . By monotonicity of j’s preferences, andsince she cannot distinguish s and s′ , Uj (rj , s) ≥ uj . However,Ws (1 − rj , j) = 1 − rj = ws′ > ws ,and so j and s form a blocking pair. Conclude then that copies of the same school all get
the same level of utility.
For each s ∈ S ′ , let γs = 1 − wf [s] , where this latter is an abuse of notation but iswell­defined by our previous observation. For each s ∈/ S ′ , let γs = ρs . For s ∈ S ′ we have
γs = 1 − wf [s] ≥ 1 − (1 − ρs ) = ρs ,We use f −1 (x) to denote the unique inverse of a bijection and f [x] to denote the set­valued pre­image.

23

36

W. PHAN, R. TIERNEY, AND Y. ZHOU

and since ws = ws for some copy of some school, the above inequality is strict for at least
one s ∈ S ′ . Next, define µ so that, for each s ∈ S ′ , µ[s] = {i ∈ N : µ̂(i) ∈ f [s]}, and fors∈/ S ′ , µ[s] = σ[s].
Recall that for each s ∈ S ′ , ρs > bs , so there is a block of (γ, µ) involving s ∈ S ′ ifand only if there is i ∈ N with (γ, s) Pi (γ, µ(i)). Since S ′ is a source set in Γ, for εsmall enough, it remains a source set in the weak­envy graph for (γ, µ). Thus, there is noblock with students outside N ′ . Since (u, w) is stable, for each i ∈ N ′ and each s ∈ S ′ ,(γ, µ(i)) Ri (γ, s). Thus the only remaining possible block is between i ∈ N ′ and s ∈/ S ′.
Suppose such a block exists. Then(ρ, s) = (γ, s) Pi (γ, µ(i)) Ri (ρ, σ(i)) ,where the last relation is because the stable match in the one­to­one problem Pareto domi­nates (ρ, σ) for the N ′ students. Thus, i would also like to block with s at (ρ, σ). However,since γs = ρs and µ[s] = σ[s], if school s is party to the block at (γ, µ) then it is at (ρ, σ)as well, contradicting that the latter is a fair allocation.
It remains to check that (γ, µ) is feasible, which requires only checking feasibility for
the S ′ schools. Since each s ∈ S ′ has ns ρs < 1, for ε small enough,ns γs = ns (1 − wf [s] ) ≤ ns (1 − wf [s] ) = ns (ρs + ε) < 1,■

as desired.

Let Γ be the weak­envy graph of allocation (ρ, σ), and let t⇝s ⊆ Γ. Construct τ so thatifor each i ∈ N with u → v ∈ t⇝s, τ (i) = v, and otherwise τ (i) = σ(i). We allow fors = t, so that the path may be a cycle. If (ρ, τ ) is an allocation, then we say that t⇝s is
feasible. We say that τ is the matching that results from executing the path on matching σ.
Given allocation (ρ, σ) with weak envy graph Γ, the set of vertices upstream of s is
Us = {t ∈ S : ∃t⇝s ⊆ Γ}.
Lemma 2. Given profile R from the NCBI domain, let (ρ, σ) be a fair allocation that is not
an RCE. Then there is another fair allocation for R that Pareto dominates (ρ, σ).
Proof. Observe that if the set of upstream vertices Us is empty for some s ∈ S, and if ρs isless than 1, then we can set γs = ρs + ϵ and all else equal, and (γ, σ) is a fair allocation if
ϵ is small enough. If σ[s] is non­empty, we are done.

CROWDING IN SCHOOL CHOICE

37

As usual, let S ∗ = {s ∈ S : ρs = bs }. Execute the following procedure as many times−1
as possible, starting with σ0 = σ: choose s ∈ S \ S ∗ with |σm[s]| ≤ bρ−1
s c − 1. Letting
Γm be the weak­envy graph of (ρ, σm ), find a (minimal) path t⇝s ⊆ Γm with t ∈ S ∗ .
That is, by taking sub­paths, t⇝s touches S ∗ only at t. Execute the path to arrive at a newallocation (ρ, σm+1 ). Observe that (ρ, σm+1 ) is a fair allocation, as no student has entereda S ∗ ­school, so no violations of fairness can be introduced. Of course, we now have a
failure of exhaustiveness at t, if not before. Nonetheless, by the definition of the weak­
envy graph, (ρ, σm+1 ) Pareto weakly dominates (ρ, σm ).24 We have therefore proven thefollowing claim:
Claim. Let Γ be the weak­envy graph of a fair allocation (ρ, σ). Assume t⇝s ⊆ Γ touches
the set of constrained vertices, S ∗ , only at t. Then the allocation (ρ, τ ) that results fromexecuting t⇝s on (ρ, σ) is a fair allocation that Pareto weakly dominates the original.
If any (ρ, σm+1 ) Pareto dominates (ρ, σm ), we are done. Thus, we may assume (ρ, σm+1 )is welfare equivalent to (ρ, σ). This process can be repeated at most finitely many times.
Let (ρ, µ) be the result and Γµ the associated weak­envy graph.
Case 1: There is s ∈ S \ S ∗ with |µ−1 [s]| ≤ bρ−1
s c − 1.
Our procedure above moves students out of S ∗ vertices along chains of weak­envy (ac­tually, chains of indifference). Thus, since the procedure was executed to exhaustion, there
are no S ∗ vertices in the set Us of upstream vertices of s in graph Γµ .
By definition, Us is a source in Γµ . If no school in Us is totally exhausted under (ρ, µ)then we may invoke Lemma 1 to arrive at our desired conclusion. Suppose, then, that
there is t ∈ Us that is totally exhausted. Since {s} ∪ Us ⊆ S \ S ∗ , and since (ρ, µ) is
an RCE, all the arcs between these vertices in Γµ represent indifferences. Suppose there ist′ ∈ Us , t′ 6= t, that is also totally exhausted. Then there are two chains of indifference, t⇝sand t′ ⇝′ s, in Γµ . The concatenation of these, t⇝s⇝′ t′ , represents a chain of indifference
connecting t and t′ . This violates NCBI as both of these vertices are totally exhausted and−1so ρ−1t , ρt′ ∈ N. Therefore, t is the only member of Us that is totally exhausted.
Execute t⇝s on (ρ, µ) to arrive at a fair allocation (ρ, τ ) with associated weak­envy
graph Γτ . As above, if we have found a Pareto improvement, we are done, so we may
assume it is welfare equivalent to (ρ, µ). Our next task is to show that {s} ∪ Us is a sourcein Γτ , recalling that Us is the set of upstream vertices in Γµ .
Allocation (ρ, σ) Pareto weakly dominates (ρ′ , σ ′ ) if for each i ∈ N , (ρ, σ(i)) Ri (ρ′ , σ ′ (i)).

24

38

W. PHAN, R. TIERNEY, AND Y. ZHOUii

Let u → v ∈ Γτ have u ∈/ Us . If τ (i) = µ(i) then clearly u → v ∈ Γµ , and since Us isa source set in Γµ , v ∈/ Us . If τ (i) 6= µ(i), then i labels some arc on the path t⇝s ⊆ Γµi
we just executed. Stated formally, there is u′ → u ∈ t⇝s, µ(i) = u′ , and τ (i) = u. Byiconstruction, the only school not in Us that is touched by this path is s, so in fact u′ → u isithe last arc of the path, and so u = s. Thus, we have shown that if u → v ∈ Γτ has u ∈/ Us
but v ∈ Us , then u = s; the only arcs in Γτ (if there are any at all) that enter Us are thosecoming from s.
Suppose there is a path w⇝s ⊆ Γτ that is not a path in Γµ . By taking sub­paths, assume
we have the shortest such path, so thatw⇝s = w → w′ ⇝s,kwith w′ ⇝s ⊆ Γµ . This latter inclusion, however, implies that w′ ∈ Us , along with all theother vertices touched by w′ ⇝s, and so by the previous paragraph, w = s. Conclude thatthe only paths to s in Γτ that are not in Γµ are of the form s → t⇝s, where t⇝s ⊆ Γµ . It
follows that {s} ∪ Us is a source set in Γτ .
Recall that our original path t⇝s ⊆ Γµ represented only indifferences. Since t is totally−1exhausted at (ρ, µ), ρ−1t ∈ N. By NCBI, it follows that ρs is not an integer, implying that−1
ρ−1s > bρs c. This further implies that s remains not totally exhausted if another student is
added to it, and so is not totally exhausted at (ρ, τ ). The schools in the middle of the pathhave not changed the number of students they admit from µ to τ , so they remain not totally
exhausted. Clearly,|τ −1 [t]| = |µ−1 [t]| − 1 = bρ−1
t c − 1,
so t is not totally exhausted at (ρ, τ ). Since t was the only totally exhausted site in Us under(ρ, µ), we now have that {s} ∪ Us is a source set in Γτ with no exhausted schools, and wetherefore invoke Lemma 1.
∗−1−1
Case 2: Each s ∈ S with |µ−1 [s]| ≤ bρ−1
s c − 1 has s ∈ S , so ρs = bs ∈ N.
Assume N ′ = {j ∈ N : (ρ, s) Pj (ρ, µ(j))} is non­empty, and let j = min≻s N ′ .
Define matching τ so that τ (j) = s and otherwise τ (i) = µ(i). Then (ρ, τ ) is clearly a fair
allocation that Pareto dominates (ρ, µ), and therefore (ρ, σ). We proceed, therefore, underithe assumption that each arc t → s ∈ Γµ represents indifference.
If there is t ∈ Us with ρ−1t ∈ N, then by taking sub­paths, assume t⇝s is a minimal pathstarting from such a t. That is, for every s′ ∈ S touched by the path except t and s, ρs′ > bs′ .
Decompose t⇝s as t → u⇝v → s. Then u⇝v touches no S ∗ vertices and so, since (ρ, µ)CROWDING IN SCHOOL CHOICE

39

is a fair allocation, the edge t → u and all edges in u⇝v represent indifference. We showedin the previous paragraph that v → s represents indifference. Thus, since ρ−1t ∈ N, this path
is a contradiction to NCBI. Conclude that Us contains neither a totally exhausted vertex, nora S ∗ vertex, and so we invoke Lemma 1.
■
A.4. Topological argument to complete the proof.
Theorem 6. Given R ∈ R N satisfying NCBI, let E be the set of RCE for R. Then
(1) E is not empty,(2) E induces a closed upper­lattice in welfare space, and(3) the set of distributions supporting the elements of E has a ≤­greatest element,ρ∗ (R), which itself supports the welfare­greatest elements of E.
Proof. For each i ∈ N , let ui be a continuous utility function representation for Ri . FixingUa matching σ, the function ρ ∈ [0, 1]S 7→ (ui (ρ, σ))i∈N is continuous. Closed subsets of[0, 1]S are compact and so map to compact sets under this function. The set D σ ⊆ [0, 1]Sof distributions ρ such that (ρ, σ) is a fair allocation is closed: To see this, recall simply
that a violation of fairness requires strict preference, and no new strict preference can be
introduced in the limit of a sequence of distributions of fair allocations. Let D = ∪σ D σ .
Since there are only finitely many possible matchings, D is compact.
Let U = U (D), which is compact. Let u ∈ U be ≤­maximal. By Lemma 2, there is an
RCE that induces u. Thus, the ≤­upper envelope of U corresponds to RCE. By Theorem
3, the ≤­upper envelope of U is a lattice. Therefore, U has a ≤­greatest element.
■
Proof of Theorem 1. It follows directly from Part (1) of Theorem 6.

■

Proof of Proposition 3. By Lemma 2 and Theorem 6, it follows that the correspondence of
welfare­greatest RCE, i.e., the maximal RCE, on the NCBI domain is non­empty, essentiallysingle­valued, and satisfies student­optimal fairness.
■
Appendix B. Proof of Theorem 4: Strategy­proofness
First, we establish the following lemma, which is an immediate consequence of lemmas
in Section A.3, but highlights a structural feature that will be important in the proof ofstrategy­proofness below.
Lemma 3. Assume that R ∈ R N satisfies NCBI. Suppose (ρ, σ) is a fair allocation for
R at which either s ∈ S is not totally exhausted, or s ∈ S ∗ . Let Us be the set of vertices

40

W. PHAN, R. TIERNEY, AND Y. ZHOU

upstream of s under the weak­envy graph of (ρ, σ). If Us contains no totally exhausted
schools, there is another fair allocation that Pareto dominates (ρ, σ).
Proof. Observe that if Us is empty, then we can set γs = ρs +ϵ and all else equal, and (γ, σ)
is an RCE if ϵ is small enough. Thus, we may assume that Us is non­empty for all s ∈ S.
By Case 2 of Lemma 2, we may assume each S ∗ school is totally exhausted. Thus ifsome s ∈ S has Us containing no totally exhausted schools, then it contains no S ∗ schools
either. That is, Us ⊆ S \ S ∗ , and is non­empty. We now invoke Lemma 1 to get the desired
result.
■Recall that preference relation R′ is a Maskin Monotonic transform of preference relation
R at bundle (x, m) if (y, t) R′ (x, m) implies that (y, t) R (x, m). Let T(R, (x, m)) be theset of Maskin monotonic transforms of R at (x, m). It is obvious that the correspondenceof RCE is Maskin monotonic, which is to say that if (ρ, σ) is a RCE for R, and R′ has, foreach i ∈ N , Ri′ ∈ T(Ri , (ρ, σ(i))), then (ρ, σ) is a RCE for R′ . We first uncover somestructural properties of φ with respect to Maskin Monotonic Transforms.
An undirected graph is a tree if there is exactly one path in the graph between any pairof vertices. In particular, a tree is simple—there is at most one edge between any pair ofvertices. With abuse of terminology, we shall call a directed graph a tree if its underlying
undirected graph is a tree and there is a special vertex r, called the root, from which allpaths emerge. That is, for all non­root vertices s, there is a path r⇝s in the graph. Finally,a directed graph is a forest if it is comprised of disjoint directed trees, having no edge orvertex in common. Let Γ be the weak­envy graph for allocation φ(R) with preferences R.
By Lemma 3, we can find a subgraph Γ′ ⊆ Γ that is a directed forest and such that eachtotally exhausted s ∈ S with ρ∗s (R) > bs is a root vertex. Call such Γ′ a minimal forest
for R. The following observations imply that, for generic profiles, the minimal forest is
unique. In any case, these structures lead to the following theorem:
Theorem 7 (The Locality Theorem). Let R′ ∈ D be a preference profile such that, foreach i ∈ N , (ρ∗ (R), s) Ii φi (R) implies (ρ∗ (R), s) Ii′ φi (R). Then ρ∗ (R′ ) = ρ∗ (R).
Proof. Let Γ′ be a minimal forest for R. First consider R′′ ∈ D such that, for each i ∈ N ,Ri′′ ∈ T(Ri , φi (R)) and such that the weak­envy graph of R′′ at φ(R) is precisely Γ′ .
By Maskin monotonicity, φ(R) is an RCE for R′′ , so ρ∗ (R′′ ) ≥ ρ∗ (R). By the latticeproperty, R′′ welfare can only increase from φ(R) to φ(R′′ ). By Theorem 2, the change inschool­assignment between these two consists entirely of trading cycles. By Proposition 2,

CROWDING IN SCHOOL CHOICE

41

all trading cycles between these two allocations must be welfare non­negative, and therefore
must be cycles in Γ′ . However, Γ′ has no cycles, and therefore the matching under φ(R′ ),say σ, is the same as that under φ(R). Now if ρ∗s (R′ ) > ρ∗s (R), then clearly s is not totallyiexhausted at φ(R). Thus there is a path t⇝s ⊆ Γ′ . In particular, there is u → s ∈ Γ′ .
However, we then have ρ∗s (R′′ ) > bs and(ρ∗ s (R′′ ), s) Pi′′ (ρ∗ s (R), s) Ri′′ (ρ∗ s (R), u) ,implying, since φ(R′′ ) is an RCE, that ρ∗u (R′′ ) > ρ∗u (R). It follows that u is not totally
exhausted at φ(R) and so we may repeat the argument. In fact, we may repeat the argu­
ment all the way up the path t⇝s to vertex t, getting a contradiction to feasibility since|σ[t]| ρ∗t (R) = 1. We conclude, therefore, that ρ∗ (R′′ ) = ρ∗ (R).
Now let R′ ∈ D have, for each i ∈ N , Ri′ ∈ T(Ri , φ(R)) and that Γ′ is a subgraphof the weak­envy graph of R′ at φ(R). As above, ρ∗ (R′ ) ≥ ρ∗ (R). However, note that
we may choose R′′ above so that, for each i ∈ N , Ri′′ ∈ T(Ri′ , φ(R)). Thus, ρ∗ (R) =ρ∗ (R′′ ) ≥ ρ∗ (R′ ) and so ρ∗ (R′ ) = ρ∗ (R).
■We are now prepared to prove the incentive compatibility of φ.
Proof of Theorem 4. Let R′ = (Ri′ , R−i ) ∈ D. Suppose φi (R′ ) Pi φi (R). Let
Ri′′ ∈ T(Ri′ , φi (R′ )) ∩ T(Ri , φi (R))
have the following properties. For each s ∈ S, if (ρ∗ (R′ ), s) 6= φi (R′ ) then φi (R′ ) Pi′′(1, s). Also, let Ri′′ have the same indifference set through φi (R) as Ri does. Note that
this assumption implies φi (R′ ) P ′′ φi (R). Let R′′ = (Ri′′ , Ri ). By the Locality Theo­rem, ρ∗ (R′′ ) = ρ∗ (R). By Maskin monotonicity, φ(R′ ) is an RCE for R′′ . Therefore
φi (Ri′′ , R−i ) Ri′′ φi (R′ ) Pi′′ φi (R). It follows that φi (Ri′′ , R−i ) Pi φi (R). Therefore, if i
can manipulate φ at R, then i can manipulate via a preference such as Ri′′ . Without loss ofgenerality, we assume henceforth that R′ = R′′ .
We are considering two allocations, φ(R) and φ(R′ ) with the same distribution vectorρ = ρ∗ (R) = ρ∗ (R′ ). We shall construct a classical school choice problem from these andderive a contradiction to the strategy­proofness of the student­optimal stable rule [Roth andSotomayor, 1990] in this context.
The set of classical schools is denoted S. As usual, let S ∗ = {s ∈ S : ρs = bs } and callthese (crowded) schools constrained. We collapse all the unconstrained schools into oneclassical school, s̀. School priorities in the classical model will be denoted ◁. For s ∈ S ∗ ,42

W. PHAN, R. TIERNEY, AND Y. ZHOU

which maps to s ∈ S, set ◁s =s . Set k ◁s̀ j if k ∈ τ [S \ S ∗ ] and j ∈ τ [S ∗ ]. We shall notneed to further specify ◁s̀ .
Next we break ties in student preferences. We begin with an intermediate step, decidingthat s̀ shall inherit the rank of the highest ranked unconstrained school. That is, let s ∈ S \S ∗have, for each t ∈ S \ S ∗ , (ρ, s) Rj (ρ, t). Then, for u ∈ S, u Rj s̀ only if (ρ, u) Rj (ρ, s).
With this step, we have defined the weak preference Rj on S. It remains to break ties on
this relation. Note that by NCBI, Rj is in fact strict when restricted to S \ {s̀}, so there is
at most one non­singleton indifference class, and it has the form {t, s̀}. Before completing
our tie­breaking specification, let us first make the following observation:
Claim 5. Let (ρ, s) Ij (ρ, σ(j)) or (ρ, s) Ij′ (ρ, τ (j)). Then s ∈ S \ S ∗ .
Proof of claim. Recall Lemma 3. First, if σ(j) is exhausted at (ρ, σ), then the claim follows
directly from NCBI. Otherwise, there is t⇝σ(j) ⊆ Γ, where Γ is the weak­envy graph of R
at (ρ, σ), with t totally exhausted. By taking subpaths we may find assume this is a shortest(by length) path with this property. Thus, at most one school touched by the path is in S ∗ ,and it must be t, as otherwise we could shorten the path further. Therefore, the path must
consist entirely of indifferences, and so t⇝σ(j) → s, with s ∈ S ∗ , contradicts NCBI.
Note that the symmetric proof holds for (ρ, s) Ij′ (ρ, τ (j)).
We now break the tie in the indifference set {t, s̀}. Here are the rules:(1) If σ(j) maps to s̀, then s̀ Pj t.
(2) Otherwise t Pj s̀.
We now show that σ̄ is stable for the classical school­choice problem with preferences
R. Suppose s Pj σ̄(j). There is s ∈ S such that (ρ, s) Rj (ρ, σ(j)). If this relation is strict,then s ∈ S ∗ , since (ρ, σ) is an RCE. This further implies that ◁s =s and that, for eachk ∈ σ[s], k s j. If the relation is an indifference, then by the claim, s = s̀. However,s̀ Pj σ̄(j) could only have happened via Rule (1), which could only happen if σ̄(j) = s̀, acontradiction. In sum, all envy is justified by the priorities.
We now show that τ is stable for R′ . Observe that, by construction, P′i top ranks τ̄ (i), so
we may restrict attention to j 6= i. In this case, R′j = Rj . Suppose s Pj τ̄ (j). Given theargument of the previous paragraph, it is clear we can skip to the case that (ρ, s) Ij (ρ, τ (j)).
The claim then implies that s = s̀ and so τ̄ (j) 6= s̀ and j ∈ τ [S ∗ ]. Thus for each k ∈ τ̄ [s̀],k ∈ τ [S \ S ∗ ], and so k ◁s̀ j. Again, all envy is justified by the priorities.

CROWDING IN SCHOOL CHOICE

43

Now we claim that σ̄ is the student optimal stable match for R. Suppose that µ̄ is a stablematch that weakly dominates σ̄. By our tie­breaking construction, if (ρ, σ(j)) Rj (ρ, t),then σ̄(j) Pj t. In particular, since (ρ, σ) is an RCE for R, either σ̄(j) = s̀ or σ̄(j) Pj s̀.
Thus, going from σ̄ to µ̄ cannot involve moving students into s̀ who are not already there.
Then by feasibility, no students can move out of s̀. Thus, µ̄[s̀] = σ̄[s̀]. In other words, µ̄ isa reassignment of the students at constrained schools. Let µ be a matching in the crowded
school model that coincides with µ̄ on S ∗ and with σ otherwise. Suppose there is j ∈ Nwith µ̄(j) Pj σ̄(j). Then j ∈ σ[S ∗ ] and µ(j) ∈ S ∗ . Since (ρ, σ) is maximal for R, there isk ∈ N with k µ(j) j and (ρ, µ(j)) Pk (ρ, µ(k)). By construction, k ◁µ̄(j) j. If µ(k) ∈ S ∗ ,then µ̄(k) 6= s̀ and µ̄ is blocked in the classical model, as preferences over S ∗ map directly
to preferences over S \ s̀. Thus, µ(k) = σ(k) ∈ S \ S ∗ . Since (ρ, σ) is an RCE, foreach t ∈ S \ S ∗ , (ρ, σ(k)) Rk (ρ, t), so recalling that s̀ inherits the rank of the highest
unconstrained school, we have µ̄(j) Pk µ̄(k) = s̀. Again we conclude that µ̄ is blocked in
the classical model.
Now observe that τ̄ (i) is the top­ranked school for R′i , so µ̄(i) = τ̄ (i) for any stable µ̄ that
dominates τ̄ for R′ . By assumption, (ρ, τ (i)) Pi (ρ, σ(i)), so by construction τ̄ (i) Pi σ̄(i),contradicting that i is not able to manipulate the student optimal stable rule.
■

Appendix C. Proof of Theorem 5: The Algorithm
We first introduce threshold equilibrium, which is a way of generalizing price equilibrium
so that more abstract objects can play the role of the price. Then by providing an equivalentmodification of the original algorithm via threshold equilibrium, the convergence result of
the modified algorithm establishes Theorem 5.
Augment N with a null element ϕ having the property that, for each s ∈ S and eachi ∈ N , i s ϕ. For each s ∈ S, let
Ts = {(r, i) ∈ [bs , 1] × N : i 6= ϕ =⇒ r = bs }.
Define linear order ⊐s on Ts so that (r, i) ⊐s (q, j) if either r < q or
(r = q = bs and i s j). Let ws denote the reflexive enlargement of ⊐s . With abuse ofnotation, write (ρ, a) to indicate the list ((ρs , as ))s∈S . Let (ρ, a) w (γ, b) if, for eachs ∈ S, (ρs , as ) ws (γs , bs ).

44

W. PHAN, R. TIERNEY, AND Y. ZHOU

Given a list of thresholds, student i’s constrained demand is their favorite school fromamong those whose threshold they can cross:Ci (ρ, a) = {s ∈ S : i s as and (i t at =⇒ (ρ, s) Ri (ρ, t))} .
A threshold equilibrium (ρ, a, σ) is a list of thresholds (ρ, a) and a matching σ such that(ρ, σ) is an allocation and, for each i ∈ N , σ(i) ∈ Ci (ρ, a).
Clearly, there is an equivalence between fair allocations and threshold equilibrium al­
locations. A maximal RCE is therefore also a student­optimal threshold equilibrium al­
location. Whereas the distribution that supports maximal RCE is unique, this is not trueof the threshold list. However, setting as equal to the highest­s ­ranked student who has(ρ∗ (R), s) Pj (ρ∗ (R), σ(j)) will ⊐s ­minimize this threshold. Since the welfare at maxi­
mal RCE is well­defined, this is independent of any particular maximal RCE matching, andthus, the minimal threshold (ρ∗ (R), a ∗ (R)) is well­defined.
Given these concepts, we make a slight modification of the algorithm in the main text.
Rather than decrementing the distribution, we shall increment the threshold list. Initialize
the modified algorithm at (ρ0 , a0 ) = ((1, . . . , 1), (ϕ, . . . , ϕ)). The decrementing subrou­tine remains the same. Rejection, however, is modified so that, with each iteration, asz isincremented one step. Thus, as,z+1 = min≻s {i ∈ N : i s asz }. To see the equivalence ofthe two algorithms, let i be the student identified in the rejection subroutine at time z. Then
excluding s from Qjz+1 for j = i and all lower ranked students is the same as repeating
the modified rejection subroutine until as,z+k = i. Moreover, nothing in the state of theeconomy changes until as,z+k = i as, by definition, none of the j with i s j have s ∈ Djz .
Let Z ⊆ R be the set of times at which the algorithm is defined. It is the disjoint union ofclosed intervals (closures of decrementing subroutines) and isolated points (rejection fol­
lowed by rejection). Clearly, (ρ∗ (R), a ∗ (R)) w (ρ0 , a0 ). Let (ρ∗ (R), a ∗ (R)) w (ρz , az )and, for some s ∈ S, (ρsz , asz ) = (ρ∗s , as∗ ). We show that (ρsz , asz ) will remain unchanged.
By contradiction, suppose s ∈ Ez∗ . Let Ω′z ⊆ Ez∗ contain s and be such that any two
schools in Ω′z are connected by chains of indifference. Let N ′ be the set of students
who require Ω′z at (ρz , az ). Let S ′ ⊆ Ω′z be the set of schools such that (ρtz , atz ) =(ρ∗t (R), at∗ (R)). By construction, an student’s demand intersects Ω′z only if they require∑Ω′z . Thus, |N ′ | > s∈Ω′z bρ−1
tz c, so by Hall’s Theorem (Hall [1935]) there is no equilibrium′′
matching of N to Ωz . Let µ instead be a maximal feasible matching such that each student
gets something in their conditional demand. By NCBI, there is at most one t ∈ Ω′z with

CROWDING IN SCHOOL CHOICE45

ρtz = bt . Suppose such a t exists and t ∈/ S ′ . Then the algorithm will increment atz before
decrementing ρsz . Thus, it is without loss of generality to assume that t ∈ S ′ . Then, for eachu ∈ Ω′z \ S ′ , ρ∗u (R) < ρuz . It follows that any j ∈ N ′ with Cj (ρz , az ) ∩ S ′ 6= ∅ requires S ′at (ρ∗ (R), a ∗ (R)). In particular, this is true for each j ∈ µ[S ′ ]. Recalling condition (2) inthe definition of excess demand, Hall’s theorem then implies there is a student i ∈ N ′ \µ[S ′ ]with Ci (ρz , az ) ∩ S ′ 6= ∅. Then the students who require S ′ at (ρ∗ (R), a ∗ (R)) are at least
the set {i} ∪ µ[S ′ ]. However,∑∑|{i} ∪ µ[S ′ ]| = 1 + |µ[S ′ ]| = 1 +
bρ−1
c
=
1
+
bρ∗−1
sz
s c,
s∈S ′

s∈S ′

where the second equality is because µ is a maximal matching and so covers S ′ . Thisequation implies that S ′ is overdemanded at (ρ∗ (R), a ∗ (R)), a contradiction.
By construction, the path z 7→ ρz is continuous. Since our rejection procedure incre­
ments a one component, one step at a time, no s can cross its minimal threshold without
first equaling its minimum equilibrium threshold. The foregoing argument shows that whena school first reaches its minimum equilibrium threshold, it is not incremented again. Thus,
for all z ∈ Z, (ρ∗ (R), a ∗ (R)) w (ρz , az ). The modified algorithm must terminate: as
mentioned, the number of rejection subroutines is bounded and the distribution is decre­
mented at constant speed. However, the modified algorithm only terminates at a threshold
equilibrium. In conclusion, the algorithm terminates at (ρ∗ (R), a ∗ (R)). Thus, by letting
σ be any matching satisfying demands, we have a maximal RCE (ρ∗ (R), σ).
References
Atila Abdulkadiroğlu and Tayfun Sönmez. School choice: A mechanism design approach.
American Economic Review, 93(3):729–747, 2003.
Tommy Andersson and Lars­Gunnar Svensson. Non­manipulable house allocation withrent control. Econometrica, 82(2):507–539, 2014.
Tommy Andersson, Christer Andersson, and Dolf Talman. Sets in excess demand in simple
ascending auctions with unit­demand bidders. Annals of Operations Research, 211:27–
36, 2013.
Itai Ashlagi, Mark Braverman, and Avinatan Hassidim. Stability in large matching markets
with complementarities. Operations Research, 62(4):713–732, 2014.
Eduardo M Azevedo and Jacob D Leshno. A supply and demand framework for two­sided
matching markets. Journal of Political Economy, 124(5):1235–1268, 2016.

46

W. PHAN, R. TIERNEY, AND Y. ZHOU

Michel Balinski and Tayfun Sönmez. A tale of two mechanisms: student placement. Jour­nal of Economic Theory, 84(1):73–94, 1999.
Keisuke Bando. Many­to­one matching markets with externalities among firms. Journalof Mathematical Economics, 48(1):14–20, 2012.
Keisuke Bando. A modified deferred acceptance algorithm for many­to­one matching mar­kets with externalities among firms. Journal of Mathematical Economics, 52:173–181,
2014.
David Card and Alan B Krueger. Does school quality matter? returns to education and thecharacteristics of public schools in the united states. Journal of Political Economy, 100(1):1–40, 1992.
Raj Chetty, John N Friedman, Nathaniel Hilger, Emmanuel Saez, Diane Whitmore
Schanzenbach, and Danny Yagan. How does your kindergarten classroom affect yourearnings? evidence from project star. The Quarterly Journal of Economics, 126(4):1593–1660, 2011.
Andrew Copland. School choice and class size externalities. Working Paper, 2021.
Vincent P Crawford and Elsie Marie Knoer. Job matching with heterogeneous firms andworkers. Econometrica, 49:437–450, 1981.
Gabrielle Demange and David Gale. The strategy structure of two­sided matching markets.
Econometrica, 53:873–888, 1985.
Gabrielle Demange, David Gale, and Marilda Sotomayor. Multi­item auctions. Journal of
Political Economy, 94(4):863–872, 1986.
Jacques H Drèze. Existence of an exchange equilibrium under price rigidities. International
Economic Review, 16:301–320, 1975.
Umut Dur and Thayer Morrill. Competitive equilibria in school assignment. Games andEconomic Behavior, 108:269–274, 2018.
Umut Dur and Thomas Wiseman. School choice with neighbors. Journal of Mathematical
Economics, 83:101–109, 2019.
Umut Dur, Thayer Morrill, and William Phan. Family ties: School assignment with siblings.
Theoretical Economics, 17(1):89–120, 2022.
Bhaskar Dutta and Jordi Massó. Stability of matchings when individuals have preferences
over colleagues. Journal of Economic Theory, 75(2):464–475, 1997.
Federico Echenique and M Bumin Yenmez. A solution to matching with preferences overcolleagues. Games and Economic Behavior, 59(1):46–71, 2007.

CROWDING IN SCHOOL CHOICE

47

Tamás Fleiner, Ravi Jagadeesan, Zsuzsanna Jankó, and Alexander Teytelboym. Trading
networks with frictions. Econometrica, 87(5):1633–1661, 2019.
Duncan Karl Foley. Resource allocation and the public sector. Yale University, 1966.
David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The
American Mathematical Monthly, 69(1):9–15, 1962.
Isa E Hafalir. Stability of marriage with externalities. International Journal of Game The­
ory, 37(3):353–369, 2008.
Philip Hall. On representatives of subsets. Journal of the London Mathematical Society,s1­10:26–30, 1935.
P Jean­Jacques Herings. Equilibrium and matching under price controls. Journal of Eco­nomic Theory, 177:222–244, 2018.
Werner Hildenbrand. Core and Equilibria of a Large Economy. (PSME­5):. Princeton
University Press, 2015. ISBN 9781400869473.
C Kirabo Jackson, Rucker C Johnson, and Claudia Persico. The effects of school spending
on educational and economic outcomes: Evidence from school finance reforms. The
Quarterly Journal of Economics, 131(1):157–218, 2016.
Alexander S Kelso Jr and Vincent P Crawford. Job matching, coalition formation, and grosssubstitutes. Econometrica, 50:1483–1504, 1982.
Bettina Klaus and Flip Klijn. Stable matchings and preferences of couples. Journal of
Economic Theory, 121(1):75–106, 2005.
Fuhito Kojima, Parag A Pathak, and Alvin E Roth. Matching with couples: Stability andincentives in large markets. The Quarterly Journal of Economics, 128(4):1585–1632,
2013.
Alan B Krueger and Diane M Whitmore. The effect of attending a small class in the early
grades on college­test taking and middle school test results: Evidence from project star.
The Economic Journal, 111(468):1–28, 2001.
Jacob Leshno. Stable matching with peer­dependent preferences in large markets: Exis­
tence and cutoff characterization. Working Paper, 2021.
Jacob D Leshno and Irene Lo. The cutoff structure of top trading cycles in school choice.
The Review of Economic Studies, 88(4):1582–1623, 2021.
Thanh Nguyen and Rakesh Vohra. Near­feasible stable matchings with couples. American
Economic Review, 108(11):3154–69, 2018.

48

W. PHAN, R. TIERNEY, AND Y. ZHOU

Marek Pycia and M Bumin Yenmez. Matching with externalities. University of Zurich,Department of Economics, Working Paper, (392), 2021.
Martine Quinzii. Core and competitive equilibria with indivisibilities. International Journalof Game Theory, 13(1):41–60, 1984.
Marzena Rostek and Nathan Yoder. Matching with complementary contracts. Economet­
rica, 88(5):1793–1827, 2020.
Alvin E Roth. The evolution of the labor market for medical interns and residents: a casestudy in game theory. Journal of Political Economy, 92(6):991–1016, 1984.
Alvin E Roth. On the allocation of residents to rural hospitals: a general property of two­sided matching markets. Econometrica, 54:425–427, 1986.
Alvin E Roth and Elliott Peranson. The redesign of the matching market for american
physicians: Some engineering aspects of economic design. American Economic Review,
89(4):748–780, 1999.
Alvin E Roth and Marilda Sotomayor. a study in game­theoretic modeling and analysis.
Econometric Society Monographs, 18, 1990.
Hiroo Sasaki and Manabu Toda. Two­sided matching problems with externalities. Journalof Economic Theory, 70(1):93–108, 1996.
Lloyd S Shapley and Martin Shubik. The assignment game i: The core. International
Journal of Game Theory, 1(1):111–130, 1971.
Tayfun Sönmez and M Utku Ünver. Course bidding at business schools. International
Economic Review, 51(1):99–123, 2010.
Dolf Talman and Zaifu Yang. A dynamic auction for differentiated items under price rigidi­
ties. Economics Letters, 99(2):278–281, 2008.
Ryan Tierney. The problem of multiple commons: A market design approach. Games andEconomic Behavior, 114:1–27, 2019.
Yu Zhou and Shigehiro Serizawa. Multi­object auction design beyond quasi­linearity:
Leading examples. Working Paper, 2021.