Constrained School Choice



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

T (Q) = T (Qx,(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 τ(Q
i, (Qj, Q-j) = τ(Qi, Qj, Q-j) and τ(Qi, Qj,Q-ij) = τ(Qi, Qj,Q-ij).
Then (7) can be rewritten as τ (Q
i, Qj ,Q-ij )Piτ (Qi,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
')Piτ(Q), which implies that Q Eτ(P, k), a contradiction.
So, τ(Q
')(i) = τ(<Q')(i).

Note that for any student h = i, Qh = Qh. 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 Q
i = 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



More intriguing information

1. An Investigation of transience upon mothers of primary-aged children and their school
2. Palvelujen vienti ja kansainvälistyminen
3. Labour Market Institutions and the Personal Distribution of Income in the OECD
4. Locke's theory of perception
5. A Dynamic Model of Conflict and Cooperation
6. Comparison of Optimal Control Solutions in a Labor Market Model
7. The name is absent
8. The name is absent
9. Influence of Mucilage Viscosity On The Globule Structure And Stability Of Certain Starch Emulsions
10. A Hybrid Neural Network and Virtual Reality System for Spatial Language Processing