the other school. If one of the schools, say school s1, had a capacity greater than 1, say
c + 1, then we would still be able to sustain a Pareto-inefficient equilibrium provided we
can find a set of students not including i2 that (1) can fill c seats at school s1 and (2)
have a higher priority at school s1 than student i2 . The condition we introduce below,
X -acyclicity,18 formalizes this intuition.
Definition 7.1 X-Cycles and X-Acyclicity
Given a priority structure f , an X-cycle is constituted of distinct s, s′ ∈ S and i, i′ ∈ I
such that the following two conditions are satisfied:
X-cycle condition: fs (i) < fs(i′) and fs′ (i′) < fs′ (i) and
xc-scarcity condition: there exist (possibly empty and) disjoint sets Is ⊆ I\i, Is' ⊆ I∖i'
such that Is ⊆ Uf(i), Is’ ⊆ Uf(i'), |Is| = qs - 1, and |Is’| = qs’ - 1.
A priority structure is X-acyclic if no X -cycles exist. △
The next result establishes that X -acyclicity is a necessary and sufficient condition to
guarantee that all equilibrium outcomes under TTC are Pareto-efficient.
Theorem 7.2 Let 1 ≤ k ≤ m. Then, f is an X -acyclic priority structure if and only
if for any school choice problem P, all Nash equilibria of the game Γτ (P, k) are Pareto-
efficient, i.e., Oτ (P, k) ⊆ PE(P).
We now consider the question of the efficiency of equilibrium outcomes under BOS
and SOSM. First of all, note that under either mechanism any stable matching can be
sustained at some equilibrium (see the discussion after Proposition 6.1). Hence, by the
lattice structure of the set of stable matchings, BOS and SOSM typically induce Pareto-
inefficient equilibrium outcomes. We now provide a necessary and sufficient condition
that ensures that all equilibrium outcomes under BOS and SOSM are Pareto-efficient.
Note that although the set of equilibrium outcomes under BOS is a subset of the set of
equilibrium outcomes under SOSM, the condition is the same for both mechanisms. This
does not come as a big surprise since for both mechanisms we have to make sure that the
set of stable matchings is a singleton (otherwise there is a Pareto-inefficient equilibrium
outcome).
The relevant condition is a slight variant of X -acyclicity.
18The X represents the cross in the priority structure that results from connecting the two entries of
i1 and the two entries of i2.
20