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. The name is absent
2. Optimal Private and Public Harvesting under Spatial and Temporal Interdependence
3. The Role of Immigration in Sustaining the Social Security System: A Political Economy Approach
4. Optimal Tax Policy when Firms are Internationally Mobile
5. Neighborhood Effects, Public Housing and Unemployment in France
6. Housing Market in Malaga: An Application of the Hedonic Methodology
7. A Rational Analysis of Alternating Search and Reflection Strategies in Problem Solving
8. Stakeholder Activism, Managerial Entrenchment, and the Congruence of Interests between Shareholders and Stakeholders
9. The name is absent
10. Computational Batik Motif Generation Innovation of Traditi onal Heritage by Fracta l Computation