schools are mere “objects” to be consumed by students, whereas in the college admissions
model (or more generally, in two-sided matching) both sides of the market are agents with
preferences over the other side. In other words, a college admissions problem is given by
1-4 above and 5’. a profile of strict school preferences PS = (Ps1 ,...,Psm), where Ps
denotes the strict preference relation of school s ∈ S over the students.
Priority orderings in school choice can be reinterpreted as school preferences in the
college admissions model. Therefore, many results or concepts for the college admissions
model have their natural counterpart for school choice.10 In particular, an outcome of a
school choice or college admissions problem is a matching μ : I ∪ S → 2i ∪ S such that
for any i ∈ I and any s ∈ S ,
• μ(i) ∈ S ∪ i,
• μ(s) ∈ 2I,
• μ(i) = s if and only if i ∈ μ(s), and
• ∣μ(s)∣ ≤ qs.
For v ∈ V, we call μ(v) agent v’s allotment. For i ∈ I ,if μ(i) = s ∈ S then student
i is assigned a seat at school s under μ. If μ(i) = i then student i is unassigned under
μ. For convenience we often write a matching as a collection of sets. For instance,
μ = {{i1, i2, s1}, {i3}, {i4, s2}} denotes the matching in which students i1 and i2 each are
assigned a seat at school s1 , student i3 is unassigned, and student i4 is assigned a seat at
school s2.
A key property of matchings in the two-sided matching literature is stability. In-
formally, a matching is stable if, for any student, all the schools he prefers to the one
he is assigned to have exhausted their capacity with students that have higher priority.
Formally, let P be a school choice problem. A matching μ is stable if
• it is individually rational, i.e., for all i ∈ I, μ(i)Ri i,
• it is non wasteful (Balinski and Sonmez, 1999), i.e., for all i ∈ I and all s ∈ S,
sPiμ(i) implies ∣μ(s)∣ = qs, and
• there is no justified envy, i.e., for all i, j ∈ I with μ(j) = s ∈ S, sPiμ(i) implies
fs(j) < fs(i).
We denote the set of individually rational matchings by IR(P), the set of non wasteful
matchings by NW (P), and the set of stable matchings by S(P).
10See, for instance, Balinski and Sonmez (1999).