Theorem 6.8 Let 1 ≤ k ≤ m. Then, f is a Kesten-acyclic priority structure if and only
if for any school choice problem P, the game Γτ (P, k) implements S(P) in Nash equilibria,
i.e., Oτ (P, k) =S(P).
Kesten’s (2006) result and Theorem 6.8 have in common that Kesten-acyclicity is both
necessary and sufficient for the stability of the Top Trading Cycle mechanism. Yet, it is
important to note that, contrary to Kesten (2006), in our game students typically cannot
reveal their true preferences.
Theorem 6.8 is easily proved. If f is Kesten-cyclic then for some school choice problem
P , τ(P) is not stable (Kesten, 2006, Theorem 1). Yet P is an m-Nash equilibrium (τ
is strategy-proof), so by Theorem 5.4 for any k there is a k-Nash equilibrium Q with
τ(Q) = τ(P) ∈/ S(P). Conversely, if f is Kesten-acyclic then it is also Ergin-acyclic
(Kesten, 2006, Lemma 1) and γ and τ coincide (Kesten, 2006, Theorem 1), so the stability
of equilibrium outcomes under TTC follows from Theorem 6.5.
Since Kesten-acyclicity implies Ergin-acyclicity we can compare in a straightforward
way the three mechanisms regarding the stability of equilibrium outcomes. If our criterion
is determined by the domain of “problem-free” priority structures, then BOS outperforms
SOSM, and SOSM in turn outperforms TTC.
7 Implementation of Pareto-Efficient Matchings
In this section we address the implementation of Pareto-efficient matchings. The main
candidate in this case is TTC since it was designed to produce Pareto-efficient match-
ings —provided agents are truthful. To obtain a full comparison as in the previous section
we shall also consider the other two mechanisms.
If we do not impose any restriction on the priority structure then equilibrium outcomes
under TTC may not be Pareto-efficient. To see this, consider the following situation
with 2 students and 2 schools, each with 1 seat. Let P (i1) = s1, s2, P (i2) = s2, s1,
fs1 (i2) < fs1 (i1), and fs2 (i1) < fs2 (i2). Then, Q = (s2, s1) is a Nash equilibrium, but
τ(Q) = {{i1, s2}, {i2, s1}} is not Pareto-efficient.17 The key element in this example is
that student i1 has higher priority at one school and student i2 has higher priority at
Cycles mechanism to be resource monotonic and population monotonic. In addition, he also proved that
the Top Trading Cycles mechanism coincides with the Student-Optimal Stable mechanism if and only if
the priority structure is Kesten-acyclic.
17Note that neither Qi1 = s2 nor Qi2 = s1 are dominated strategies.
19