Constrained School Choice

Suppose fs₁ (i2) < fs₁ (i1). Since i1 ∈ γ(Q)(s2), setting i = i2, i^′ = i1 , s = s1, s^′ = s2,
Is = γ(Q)(s₁)∖ip, and Is’ = γ(Q)(s2)∖i1 yields a weak X-cycle.

Suppose now f_s1 (i₁) < f_s1 (i₂). If f_s1 (i₃) < f_s1 (i₂), then we obtain again a weak X-
cycle by setting i = i3, i' = i₂, s = sɪ, s’ = S3, Is = γ(Q)(sι)∖ip, and Is’ = γ(Q)(s3)∖i2.
So, suppose fs₁ (i2) < fs₁ (i3). By repeating this reasoning with students i4, i5, . . . , ip-1 we
either obtain a weak X -cycle or establish that the priority ordering of school sɪ has the
following form:

^fsι : ∙ ∙ ∙ Y(Q) (sɪ) ∙ ∙ ∙ iɪ ∙ ∙ ∙ ⁱ2 ∙ ∙ ∙ ip-2 ∙ ∙ ∙ ip-ɪ ∙ ∙ ∙

To deal with the latter case, recall that by construction, i_p ∈ γ(Q)(s₁) and ip-ɪ ∈ γ(Q)(s_p).
So, we obtain a weak X-cycle by setting i = i_p, i' = i_p-1, s = sɪ, s’ = s_p, Is = γ(Q)(s₁)∖i_p,
and Is’ = γ(Q)(Sp)∖ip-b
(ii) ⇒ (i): Without loss of generality, let students i_ɪ = i and i₂ = i^’ and schools s_ɪ = s
and s₂ = s^’ be the agents involved in a weak X -cycle. Without loss of generality we may
assume that Is₁ = {i₃,..., iq_s1 ₊₁} and Is₂ = {iq_s1 ₊₂,..., iq_s1 ₊q_s2}. Consider the students’
preferences P given below. (Unacceptable schools are not depicted.)

Note that for j = q_s1 + q_s2 + 1, . . . , n, student ij finds all schools unacceptable. One easily
verifies that the distinct matchings
are stable. So, |S(P)| ≥ 2.

(i) ⇒ (iii): Let P be a school choice problem with Q ∈ E^γ(P, k) such that γ(Q) ∈/ PE(P).
Suppose first that |S(P)| ≥ 2. Then, by (i) ⇒ (ii), f admits a weak X -cycle. So, suppose
|S(P)| = 1. By Lemma A.8, there exists Q ∈ E^γ(P, 1) with γ(Q) = γ(P) =: μ₁. If
μ₁ ∈ PE(P) then by Theorem 1 of Ergin (2002) f admits an Ergin-cycle, which by

32

<<   <   29   30   31   32   33   34   35   >   >>