Definition 7.3 Weak X -Cycles and Strong X-Acyclicity
Given a priority structure f , a weak X-cycle is constituted of distinct s, s′ ∈ S and i, i′ ∈ I
such that the following two conditions are satisfied:
X-cycle condition: fs (i) < fs(i′) and fs′ (i′) < fs′ (i) and
wxc-scarcity condition: there exist (possibly empty and) disjoint sets Is ⊆ I\i, Is ⊆ I∖i'
such that Is ⊆ Uf(i'), Is’ ⊆ Uf(i), ∣Is∣ = qs - 1, and ∣Is'∣ = qs’ - 1.
A priority structure is strongly X-acyclic if no weak X -cycles exist. △
Remark 7.4 Note that if ((s, s′), (i, j, l)) constitutes an Ergin-cycle, then ((s, s′), (i, l))
constitutes a weak X -cycle. Hence, strong X -acyclicity implies Ergin-acyclicity.
Clearly, strong X -acyclicity is very restrictive. In fact, it is easy to see that strong
X -acyclicity implies both X -acyclicity and Ergin-acyclicity. Nevertheless it is a necessary
(and sufficient) condition to guarantee the Pareto-efficiency of all equilibrium outcomes
under SOSM as well as BOS.
Theorem 7.5 Let f be a priority structure. Let 1 ≤ k ≤ m. Then, the following are
equivalent:
(i) f is strongly X -acyclic.
(ii) For any school choice problem P , S(P) is a singleton.
(iii) For any school choice problem P, all Nash equilibria of the game Γγ(P, k) are Pareto-
efficient, i.e., Oγ(P,k) ⊆ PE(P).
(iv) For any school choice problem P, all Nash equilibria of the game Γβ (P, k) are Pareto-
efficient, i.e., Oβ(P, k) ⊆ PE(P).
Since strong X -acyclicity implies X -acyclicity we can also compare the three mecha-
nisms regarding the Pareto-efficiency of equilibrium outcomes. If our criterion is deter-
mined by the domain of “problem-free” priority structures, then TTC outperforms both
SOSM and BOS, and SOSM performs equally well as BOS.
Remark 7.6 Below we show that apart from [Kesten-acyclicity ⇒ Ergin-acyclicity],
[strong X -acyclicity ⇒ Ergin-acyclicity], and [strong X -acyclicity ⇒ X -acyclicity], there
are no other logical implications regarding pairs of acyclicity conditions. The Venn dia-
gram in Figure 1 summarizes these facts.19 Each node indicates the existence of a priority
structure that satisfies the associated requirements.
21