Constrained School Choice



e(Q,p,v) = e(Q',p,v) for each agent v V (Q,p)i, C * is also a cycle in G(Q',p). In
particular, τ(Q)(j) = τ(Q
')(j), a contradiction. This completes the proof of (a).

We now prove (b). We distinguish between two cases.

Case 1: j P(Q',p, i).

Then, (b) follows directly from Lemma B.6 with Q = Q, v' = j, and v = i.

Case 2: j P(Q',p,i).

Assume that (b) is not true. In other words, assume that σ(Q', i) > σ(Q', j) or [σ(Q', i) =
σ(Q
', j) and i and j are assigned in different cycles in TTC(Q,)]∙ Then, σ(Q,i) = p
r= σ(Q, j) σ(Q',i)∙

Note that by definition of r', j V(Q', r). Suppose j (P(Q', r, i) i). Since j = i,
j
P(Q',r',i). By Lemma B.6, σ(Q',i) σ(Q,j) and [σ(Q',i) = σ(Q',j) only if i and
j are removed in the same cycle in
TTC(Q)]. This contradicts the assumption that (b)
is not true. So, j
(P(Q',r',i) i). In other words, j V(Q',r')(P(Q',r',i) i).
Hence, by Lemma B.7, j
V(Q, r) and F(Q,r',j) = F(Q',r',j). Since σ(Q',j) = r,
student j forms part of a cycle, say C
', in G(Q',r'). Hence, C' = F(Q',r',j). So, also
C
= F(Q, r, j). Hence, student j is assigned to the same school (or himself) in TTC(Q)
and TTC(Q
'), contradicting τ(Q)(j) = τ(Q')(j). This completes the proof of (b).     

Proposition B.9 Let P be a school choice problem. Let 2 k m. Let Q Eτ (P, k).
Define Qi := τ(Q)(i) for all i I. Then, Q Eτ (P, 1) and τ(Q) = τ(Q). In particular,
Oτ(P, k) Oτ (P, 1).

Proof It is sufficient to prove the following claim.

Claim: Let P be a school choice problem. Let 2 k m, Q Eτ (P, k), and j I. Let
Q
j := τ(Q)(j). Then, Q := (Qj,Q-j) Eτ(P,k).

Indeed, if the Claim is true then we can pick students one after another and each time
apply both the Claim and Proposition B.5 to eventually obtain a profile Q
Eτ(P, k)
with τ(Q) = τ(Q) and where for all j
I, Qj = τ(Q)(j). By construction, Q Q(1)I.
So, Q
Eτ(P, 1).

To prove the Claim, suppose Q / Eτ(P, k). Then, there is a student i with a profitable
deviation at Q in Γ
τ (P, k). In fact, by Proposition B.5 there is a strategy Qi Q(1) with

τ (Qi,Q)-i)PiT (Qi,Q-i).                                   (6)

We claim i = j . Suppose i = j . Then, Q-i = Q-j = Q-j . So, (6) becomes τ (Qj , Q-j )Pj
τ(Qj , Q-j ), contradicting Q Eτ (P, k). So, i = j .

38



More intriguing information

1. Return Predictability and Stock Market Crashes in a Simple Rational Expectations Model
2. Income Mobility of Owners of Small Businesses when Boundaries between Occupations are Vague
3. Imputing Dairy Producers' Quota Discount Rate Using the Individual Export Milk Program in Quebec
4. ROBUST CLASSIFICATION WITH CONTEXT-SENSITIVE FEATURES
5. Lumpy Investment, Sectoral Propagation, and Business Cycles
6. Tastes, castes, and culture: The influence of society on preferences
7. Analyzing the Agricultural Trade Impacts of the Canada-Chile Free Trade Agreement
8. Olfactory Neuroblastoma: Diagnostic Difficulty
9. Education as a Moral Concept
10. SLA RESEARCH ON SELF-DIRECTION: THEORETICAL AND PRACTICAL ISSUES
11. The name is absent
12. Evolutionary Clustering in Indonesian Ethnic Textile Motifs
13. SOCIOECONOMIC TRENDS CHANGING RURAL AMERICA
14. Experimental Evidence of Risk Aversion in Consumer Markets: The Case of Beef Tenderness
15. Regional science policy and the growth of knowledge megacentres in bioscience clusters
16. Towards a Strategy for Improving Agricultural Inputs Markets in Africa
17. DETERMINANTS OF FOOD AWAY FROM HOME AMONG AFRICAN-AMERICANS
18. The name is absent
19. Keynesian Dynamics and the Wage-Price Spiral:Estimating a Baseline Disequilibrium Approach
20. The name is absent