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. Non Linear Contracting and Endogenous Buyer Power between Manufacturers and Retailers: Empirical Evidence on Food Retailing in France
2. Multi-Agent System Interaction in Integrated SCM
3. Towards Teaching a Robot to Count Objects
4. Stable Distributions
5. ISSUES AND PROBLEMS OF IMMEDIATE CONCERN
6. The name is absent
7. Survey of Literature on Covered and Uncovered Interest Parities
8. Placentophagia in Nonpregnant Nulliparous Mice: A Genetic Investigation1
9. A Rare Case Of Fallopian Tube Cancer
10. On Evolution of God-Seeking Mind