Constrained School Choice

Recall Q = (Qi , Qj , Q_-ij ). Define Q := (Q_i , Qj , Q_-ij ) and Q := (Q_i, Qj , Q_-ij ) . We
can rewrite (6) as

T (Q‘) = T (Q_x,(Qj ,Q-ij )Р_гт (Qi,Qj ,Q-ij ) = τ (Q).                   (7)

From Q ∈ E^τ(P, k), Lemma B.2 (O^τ(P, k) ⊆ IR(P)), and Proposition B.5, τ(QQ) =
T(Q) ∈ IR(P). By (7), τ(Q')(i) =: s ∈ S. Since Q = Qi ∈Q(1), Qi = s.

Suppose τ(Q')(j) = τ(Q)(j). Recall (Qj = τ(Q)(j). So, QQj = τ(Q')(j). Hence, Propo-
sition B.5 implies τ(Qi, (Qj, Q-j) = τ(Qi, Qj, Q-j) and τ(Q_i, Qj,Q-_ij) = τ(Q_i, Qj,Q-_ij).
Then (7) can be rewritten as τ (Qi, Qj ,Q_-ij )P_iτ (Q_i,Qj ,Q_-ij ). So, Q ∈ E^τ (P, k), a con-
tradiction. Hence, τ(Q')(j) = τ(Q)(j).

Next, we prove that τ(Q')(i) = τ(Q')(i). Suppose τ(Q')(i) = τ(Q')(i). Since τ(QQ) =
τ(Q), (7) boils down to τ(Q')P_iτ(Q), which implies that Q ∈ E^τ(P, k), a contradiction.
So, τ(Q')(i) = τ(<Q')(i).

Note that for any student h = i, Qh = Q_h. So, by Lemma B.8, σ(Q',i) ≤ σ(Q',j).
Note also that for any student h = j, (Qh = Qh So, by Lemma B.8, σ(Q', j) ≤ σ(Q',i).
So, σ(Q',i) = σ(Q', j). From Lemma B.8 it follows that i and j are in the same cycle
in TTC(Q'). So, i is not in a self-cycle. Hence, i is assigned to a school in TTC(Q').
Since Qi = s, τ(Q')(i) = s. By definition, s = τ(Q)')(i).  So, τ(Q')(i) = τ(Q)^z)(i), a

contradiction. Hence, Q ∈ E^τ(P, k), which completes the proof of the Claim.         ■

Proof of Theorem 5.4 Follows from Propositions B.5 and B.9.                 ■

In order to prove Theorem 6.8 we need the following two lemmas.

Lemma B.10 Let f be a Kesten-cyclic priority structure. Let 1 ≤ 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), T(Q) ∈ S(P).

Proof By Theorem 1 of Kesten (2006), there is a school choice problem P such that
T(P) is unstable. Since T is strategy-proof, P ∈ E^τ (P, m). Hence, by Theorem 5.4,
T(P) ∈ O^τ (P, m) = O^τ (P, k). So, there is a profile Q ∈ Q(k)^I such that Q ∈ E^τ(P, k)
and τ(Q) = τ(P) ∈ S(P).                                                           ■

Lemma B.11 Let f be a Kesten-acyclic priority structure. Let 1 ≤ k ≤ m. Then, for
any school choice problem P all equilibrium outcomes in the game Γ^τ(P, k) are stable, i.e.,
for all Q ∈ E^τ (P, k), T(Q) ∈ S(P). In fact, S(P) = O^τ (P, k).

39

<<   36   37   38   39   40   41   42   >>

More intriguing information