We distinguish among three cases for the priority ordering fs2 of school s2 with respect
to students i1, i2, and i3: (i) fs2 (i2) < fs2 (i3) < fs2 (i1), (ii) fs2 (i3) < fs2 (i2) < fs2 (i1),
and (iii) fs2 (i3) < fs2 (i1) < fs2 (i2). One easily verifies that in each of the cases (i), (ii),
and (iii), the unique stable matching for P is μ* = γ(P) with μ*(i1) = s1, μ*(i3) = s2,
and μ*(i2) = i2.
Consider Q ∈ Q(k)I defined by Qi2 := 0 and Qi := Pi for all i ∈ I∖i2. One easily
verifies that in each of the cases (i), (ii), and (iii), γ(Q)(i1) = s2 and γ(Q)(i3) = s1. So,
γ (Q) = μ*, and hence γ(Q) ∈ S (P ). Finally, one easily verifies that Q ∈ Eγ (P, k). ■
A mechanism is non bossy if no student can maintain his allotment and cause a change
in the other students’ allotments by reporting different preferences.
Definition A.4 Non Bossy Mechanism (Satterthwaite and Sonnenschein, 1981)
A mechanism φ is non bossy if for all i ∈ I, Qi, Qi ∈ Q, and Q-i ∈ QI\i, φ(Q'i, Q-i)(i) =
φ(Qi,Q-i)(i) implies φ(Q'i,Q-i) = φ(Qi,Q-i). △
Lemma A.5 Let f be an Ergin-acyclic priority structure. Then, γ is non bossy.
Proof Follows from Ergin’s (2002) Theorem 1, (iv) ⇒ (iii) and proof of (iii) ⇒ (ii). ■
Lemma A.6 Let f be an Ergin-acyclic priority structure. Let 2 ≤ 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), γ(Q) ∈ S(P).
Proof Suppose to the contrary that Q ∈ Eγ(P, k) but γ(Q) ∈ S(P). So, by Lemma A.2,
there are i, j ∈ I, i = j and s ∈ S with γ(Q)(j) = s, sPiγ(Q)(i), and fs(i) < fs(j).
Since γ is strategy-proof in the unconstrained setting (i.e., when the quota equals m,
the number of schools), γ(Pi,Q-i)Riγ(Qi, Q-i). Let Qi := γ(Pi,Q-i)(i). Clearly, Qi ∈
Q(k). By Lemma A.1, γ(Qi,Q-i)(i) = γ(Pi,Q-i)(i). Hence, γ(Qi, Q-i)Riγ(Qi, Q-i).
If γ(Qi,Q-i)Piγ(Qi,Q-i), then Q ∈ Eγ(P, k), a contradiction. Hence, γ(Qi,Q-i)(i) =
γ(Qi,Q-i)(i).
By Lemma A.5, γ is non bossy. Hence, γ(Pi, Q-i) = γ(Qi, Q-i) = γ(Q). In particular,
γ(Pi, Q-i)(j) = γ(Q)(j) = s. Since sPiγ(Q)(i) = γ(Pi, Q-i)(i), student i has justified
envy at γ (Pi, Q-i), contradicting γ (Pi, Q-i) ∈ S (Pi, Q-i). Hence, γ(Q) ∈ S (P ). ■
Proof of Theorem 6.5 Proposition 6.1 implies that the game Γγ(P, 1) = Γβ(P, 1)
implements S(P) in Nash equilibria, i.e., S(P) = Oγ(P, 1). Theorem 5.3 implies that
S (P ) = Oγ (P, 1) ⊆ Oγ (P, k). Now Lemmas A.3 and A.6 complete the proof. ■
30
More intriguing information
1. Bird’s Eye View to Indonesian Mass Conflict Revisiting the Fact of Self-Organized Criticality2. The geography of collaborative knowledge production: entropy techniques and results for the European Union
3. The name is absent
4. Does adult education at upper secondary level influence annual wage earnings?
5. Menarchial Age of Secondary School Girls in Urban and Rural Areas of Rivers State, Nigeria
6. Evidence of coevolution in multi-objective evolutionary algorithms
7. XML PUBLISHING SOLUTIONS FOR A COMPANY
8. The name is absent
9. A Theoretical Growth Model for Ireland
10. The name is absent