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. Deletion of a mycobacterial gene encoding a reductase leads to an altered cell wall containing β-oxo-mycolic acid analogues, and the accumulation of long-chain ketones related to mycolic acids
2. ESTIMATION OF EFFICIENT REGRESSION MODELS FOR APPLIED AGRICULTURAL ECONOMICS RESEARCH
3. Protocol for Past BP: a randomised controlled trial of different blood pressure targets for people with a history of stroke of transient ischaemic attack (TIA) in primary care
4. Managing Human Resources in Higher Education: The Implications of a Diversifying Workforce
5. Publication of Foreign Exchange Statistics by the Central Bank of Chile
6. Stillbirth in a Tertiary Care Referral Hospital in North Bengal - A Review of Causes, Risk Factors and Prevention Strategies
7. The name is absent
8. Before and After the Hartz Reforms: The Performance of Active Labour Market Policy in Germany
9. Cancer-related electronic support groups as navigation-aids: Overcoming geographic barriers
10. The name is absent