Constrained School Choice

Ergin-acyclic

Kesten-acyclic

X -acyclic

strongly X -acyclic

Figure 1: Venn diagram of the acyclicity conditions

We have made use of four different acyclicity conditions. Below we indicate the absence
or existence of each of the 12 possible logical implications between pairs of acyclicity
conditions.

• [Kesten-acyclicity ⇒ Ergin-acyclicity]: Kesten (2006, Lemma 1);

• - [Kesten-acyclicity ⇒ Ergin-acyclicity]: Example 2 in Kesten (2006) which is given
by fs₁ = i1, i2, i3 and fs₂ = i3, i1, i2, qs₁ = 1 and qs₂ = 2;

• [strong X -acyclicity ⇒ X -acyclicity]: immediate from definition;

• - [X -acyclicity ⇒ strong X -acyclicity]: Example 2 in Kesten (2006) which is given
by fs₁ = i1, i2, i3 and fs₂ = i3, i1, i2, qs₁ = 1 and qs₂ = 2;

• [strong X -acyclicity ⇒ Ergin-acyclicity]:

if ((s, s^′), (i, j, l)) constitutes an Ergin-cycle, then ((s, s^′), (i, l)) constitutes a weak
X -cycle;

• - [strong X -acyclicity ⇒ Kesten-acyclicity]:

f_s1 = i1, i2 , i3 and f_s2 = i3 , i1 , i2 , q_s1 = 1 and q_s2 = 3;

• - [X -acyclicity ⇒ Kesten-acyclicity]: follows from [strong X -acyclicity ⇒ X -acyclicity]
and - [strong X -acyclicity ⇒ Kesten-acyclicity];

¹⁹A proof that [Kesten-acyclicity and X -acyclicity ⇒ strong X -acyclicity] is as follows. Suppose that
the priority structure is Kesten-acyclic, X -acyclic, but not strongly X -acyclic. By Theorem 7.5(ii)⇒(i),
there is a school choice problem P with |S(P)| ≥ 2. By Theorem 6.8, S(P) = O^τ (P, k). By Theorem
7.2, O^τ (P, k) ⊆ PE(P). Hence, S(P) ⊆ PE(P) and |S(P)| ≥ 2, which contradicts the optimality of the
Student-Optimal Stable matching.

22

<<   19   20   21   22   23   24   25   >>

More intriguing information