Constrained School Choice

the empty list. Let Q := (Q_i, Q_-i). By a result of Gale and Sotomayor (1985b, Theorem
2) extended to the college admissions model (Roth and Sotomayor, 1990, Theorem 5.34),
for each j ∈ I\i, either γ(Q)(j) = γ(Q)(j) or γ(Q^)(j)QjY(Q)(j). Hence, the set of
schools to which each j ∈ I\i proposes in DA(Q) is a subset of the schools to which
he proposes in DA(Q). Since moreover Q_i is the empty list, each school receives in
DA(Q) only a subset of the proposals of DA(Q). For school s this immediately implies
that ∣γ(dQ)(s)∣ ≤ ∣γ(Q)(s)∣ < q_s. So, if we take Qi = s then γ(Qi,Q_-i)(i) = s. Since
sP_iγ(Q)(i), Qi is a profitable deviation for i at Q in Γ^γ(P, k). So, Q ∈ E^γ(P, k), a
contradiction. Hence, γ(Q) ∈ NW(P).                                            ■

Proof of Theorem 5.3 It suffices to prove the theorem for k^′ = k+ 1. Let Q ∈ E^γ(P, k)
and suppose that Q ∈ E^γ(P, k +1). Then, there is a student i and a strategy Qi ∈ Q(k + 1)
with γ(Qi,Q-i)Piγ(Qi,Q-i). By Lemma A.2, γ(Q) ∈ IR(P). Hence, γ(Qi,Q-i)(i) ∈ S.
Note also that Qi must be a list containing exactly k + 1 schools, for otherwise it would
also be a profitable deviation in Γ^γ(P, k), contradicting Q ∈ E^γ(P, k).

Let s be the last school listed in Q'_i. We claim that γ(Qi,Q_-i)(i) = s. Suppose
Y(Qi,Q_-i)(i) = s. Consider the truncation of Qi after γ(Qi,Q_-i)(i) and denote this list
by Qi’. In other words, Qi’ is the list obtained from Qi by making all schools listed after
Y (Qi, Q_-i)(i) unacceptable. By assumption, Qi’ ∈ Q(k). It follows from the DA algorithm
that Y(Q^’_i^’, Q-i) = Y(Q^’_i, Q-i). Hence, Q^’_i^’ is a profitable deviation for i at Q in Γ^γ(P, k),
a contradiction. So, Y(Q^’_i, Q-i)(i) = s.

Let Q_i := s. Note Q_i ∈ Q(k). By Lemma A.1, γ((Q_i,Q_-i)(i') = s. Hence, Q_i is a
profitable deviation for i at Q in Γ^γ(P, k), a contradiction. Hence, Q ∈ E^γ(P, k + 1). ■

We need the following three lemmas to prove Theorem 6.5.

Lemma A.3 Let f be an Ergin-cyclic priority structure. Let 2 ≤ k ≤ m. Then, there
is a school choice problem P with an unstable equilibrium outcome in the game Γ^γ (P, k),
i.e., for some Q ∈ E^γ(P,k), Y(Q) ∈ S(P).

Proof Since f is Ergin-cyclic, we may assume, without loss of generality, that

(a) fs₁(i1) < fs₁ (i2) < fs₁(i3) and fs₂(i3) < fs₂(i1),

(b) fs₁ (ij) < fs₁ (i2) for each j ∈ I1 := {4, . . . , qs₁ + 2}, and

(c) fs₂ (ij) < fs₂ (i1) for each j ∈ I2 := {qs₁ + 3, . . . , qs₁ + qs₂ + 1}.

Consider students’ preferences P defined by Pi₁ := s2, s1 , Pi₂ := s1 , Pi₃ := s1, s2,

Pi_j := si for j ∈ Iι, Pi_j := s2 for j ∈ I₂, and Pi_j := 0 for all j ∈ {q₃₁ + q_β2 + 2,..., n}.

29

<<   26   27   28   29   30   31   32   >>

More intriguing information