Constrained School Choice

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: f_s (i) < f_s(i^′) and f_s′ (i^′) < f_s′ (i) and

wxc-scarcity condition: there exist (possibly empty and) disjoint sets I_s ⊆ 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.¹⁹ Each node indicates the existence of a priority
structure that satisfies the associated requirements.

21

<<   18   19   20   21   22   23   24   >>

More intriguing information