Constrained School Choice



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 (i
1) = s1, s2, P (i2) = s2, s1,
f
s1 (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 i
1 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



More intriguing information

1. Running head: CHILDREN'S ATTRIBUTIONS OF BELIEFS
2. L'organisation en réseau comme forme « indéterminée »
3. The name is absent
4. Word searches: on the use of verbal and non-verbal resources during classroom talk
5. The Dynamic Cost of the Draft
6. The name is absent
7. ANTI-COMPETITIVE FINANCIAL CONTRACTING: THE DESIGN OF FINANCIAL CLAIMS.
8. Change in firm population and spatial variations: The case of Turkey
9. Implementation of Rule Based Algorithm for Sandhi-Vicheda Of Compound Hindi Words
10. What should educational research do, and how should it do it? A response to “Will a clinical approach make educational research more relevant to practice” by Jacquelien Bulterman-Bos