TTC. Like for SOSM, under TTC unstable matchings may obtain in equilibrium. We
show that Kesten’s (2006) acyclicity condition is necessary and sufficient to implement
stable matchings under TTC.
In a school choice problem, efficiency is defined with respect to the preferences of stu-
dents only. It is known that in this case SOSM may not be efficient —see Ergin (2002).
TTC then becomes the most natural mechanism to obtain efficient matchings provided
students do submit their true preferences. However, notice that since TTC is no longer
strategy-proof when choice is constrained it is not clear whether it performs better than
BOS, which is also efficient with respect to submitted preference lists. The efficiency of
TTC turns out to be not robust to the Nash equilibrium operator. In fact, it is easy
to see that an inefficient matching can be sustained by an Nash equilibrium, even if we
restrict to undominated strategies. This negative result motivates then the search for
conditions that ensure efficiency. We show that efficient Nash equilibrium outcomes can
be guaranteed if, and only if, schools’ priorities satisfy a new acyclicity condition called
X -acyclicity. This condition roughly states that two schools cannot prioritize differently
two students that compete for the last available seat in both schools. A similar but slightly
stronger condition, strong X -acyclicity, is necessary and sufficient to guarantee efficient
Nash equilibrium outcomes under both SOSM and BOS. It may come as a surprise that
we find the same necessary and condition for SOSM and BOS. However, since any stable
matching can be obtained as a Nash equilibrium outcome under both SOSM and BOS,
strong X -acyclicity needs to guarantee that there is a unique stable matching (otherwise
the lattice structure of the set of stable matchings implies that not all equilibrium out-
comes are efficient). In fact, nothing more is needed: X -acyclicity is a necessary and
sufficient condition for the set of stable matchings to be a singleton.
The remainder of the paper is organized as follows. In Section 2, we recall the model of
school choice. In Section 3, we describe the three mechanisms. In Section 4, we introduce
the strategic game induced by the imposition of a quota on the revealed preferences. In
Section 5 we provi de existence results and establish the nestedness of equilibrium out-
comes. In Sections 6 and 7 we investigate the implementability of stable and efficient
matchings, respectively. In Section 8, we study Nash equilibria in undominated trunca-
tion strategies for the Student-Optimal Stable mechanism and the Top Trading Cycles
mechanism. Finally, in Section 9, we discuss the policy implications of our results and
our contribution to the literature on school choice. Almost all proofs are relegated to the
Appendices.