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
More intriguing information
1. The Impact of Minimum Wages on Wage Inequality and Employment in the Formal and Informal Sector in Costa Rica2. Concerns for Equity and the Optimal Co-Payments for Publicly Provided Health Care
3. 09-01 "Resources, Rules and International Political Economy: The Politics of Development in the WTO"
4. The name is absent
5. Bargaining Power and Equilibrium Consumption
6. Macro-regional evaluation of the Structural Funds using the HERMIN modelling framework
7. The name is absent
8. 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
9. BUSINESS SUCCESS: WHAT FACTORS REALLY MATTER?
10. Om Økonomi, matematik og videnskabelighed - et bud på provokation