Constrained School Choice

Obviously, TTC was not introduced to produce stable matchings. It is easy to con-
struct an example for which not every equilibrium outcome is stable.

Example 6.6 A School Choice Problem P with S (P ) ∩ O^τ (P, 1) = 0

Let I = {i₁, i₂, i₃} be the set of students, S = {s₁, s₂} be the set of schools, and q = (1, 1)
be the capacity vector. The students’ preferences P and the priority structure f are given
in the table below.

Pil Pi2 Pi3      fsi fs2

s2     s1     s1         i1     i3

i2     i2

i3     iɪ

It is easy to check that the unique stable matching is μ = {{i₁,s₂}, {i₂,s₁}, {i₃}}. We
show that μ cannot be sustained at any Nash equilibrium of the game Γ^τ(P, 1). Suppose
to the contrary that μ can be sustained at some Nash equilibrium. In other words, there is
a profile Q ∈ Q(1)I such that τ(Q) = μ and Q ∈ E^τ(P, 1). Since τ(Q) = μ, Qi₁ = s₂ and
Qi₂ = sι∙ If Qi₃ = si, then τ(Q)(i3) = sɪ = μ(i3)∙ So, Qi₃ = sι∙ But then τ(Q)Pi₃τ(Q)
for Q' := (Q_i1 ,Q_i2,s₁). Hence, Q ∈ E^τ(P, 1), a contradiction.                            ^

However, if we are to compare the three mechanisms we need to find a sufficient and
necessary condition on the priority structure that guarantees stability, in very much the
same way as we have done for SOSM. In the case of TTC the crucial necessary and
sufficient condition for the stability of equilibrium outcomes is Kesten-acyclicity (2006).

Definition 6.7 Kesten-Acyclicity (Kesten, 2006)

Given a priority structure f, a Kesten-cycle is constituted of distinct s, s^′ ∈ S and i, j, l ∈ I
such that the following two conditions are satisfied:

Kesten-cycle condition  f_s (i) < f_s (j) < f_s (l) and f_s′ (l) < f_s′ (i), f_s′ (j) and

kc-scarcity condition there exists a (possibly empty) set Is ⊆ I \{i, j, l} with Is ⊆ U_s^f (i)∪

Uf(f)∖Uf^{(l) and} IIsI = qs^- 1.

A priority structure is Kesten-acyclic if no Kesten-cycles exist.                         △

Kesten (2006) showed that Kesten-acyclicity of the priority structure is necessary and
sufficient for the stability of the Top Trading Cycles mechanism when students report their
true preferences.¹⁶ Kesten-acyclicity implies Ergin-acyclicity (Lemma 1, Kesten, 2006).
It is easy to check that the reverse holds if all schools have capacity 1.

¹⁶Kesten (2006) also showed that Kesten-acyclicity is necessary and sufficient for the Top Trading

18

<<   15   16   17   18   19   20   21   >>

More intriguing information