2 School Choice
Following Abdulkadiroglu and Sonmez (2003) we define a school choice problem by a set
of schools and a set of students, each of which has to be assigned a seat at not more than
one of the schools. Each student is assumed to have strict preferences over the schools
and the option of remaining unassigned. Each school is endowed with a strict priority
ordering over the students and a fixed capacity of seats. Formally, a school choice problem
is a 5-tuple (I, S, q, P, f) that consists of
1. a set of students I = {i1, . . . , in},
2. a set of schools S = {s1, . . . , sm},
3. a capacity vector q = (qs1 , . . . , qsm),
4. a profile of strict student preferences P = (Pi1 , . . . , Pin), and
5. a strict priority structure of the schools over the students f = (fs1 , . . . , fsm).
We denote by i and s a generic student and a generic school, respectively. An agent
is an element of V := I ∪ S . A generic agent is denoted by v . With a slight abuse of
notation we write v for singletons {v} ⊆ V .
The preference relation Pi of student i is a linear order over S ∪ i, where i denotes
his outside option (e.g., going to a private school). Student i prefers school s to school
s’ if sPis’. School s is acceptable to i if sPii. Henceforth, when describing a particular
preference relation of a student we will only represent acceptable schools. For instance,
Pi = s, s′ means that student i’s most preferred school is s, his second best s′, and any
other school is unacceptable. For the sake of convenience, if all schools are unacceptable
for i then we sometimes write Pi = i instead of Pi = 0. Let Ri denote the weak preference
relation associated with the preference relation Pi .
The priority ordering fs of school s assigns ranks to students according to their priority
for school s. The rank of student i for school s is fs(i). Then, fs(i) < fs(j) means that
student i has higher priority (or lower rank) for school s than student j . For s ∈ S and
i ∈ I, we denote by Usf (i) the set of students that have higher priority than student i for
school s, i.e., Usf (i) = {j ∈ I : fs(j) < fs(i)}.
Throughout the paper we fix the set of students I and the set of schools S . Hence, a
school choice problem is given by a triple (P, f, q), and simply by P when no confusion is
possible.
School choice is closely related to the college admissions model (Gale and Shap-
ley, 1962). The only but key difference between the two models is that in school choice