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. Text of a letter2. MATHEMATICS AS AN EXACT AND PRECISE LANGUAGE OF NATURE
3. The name is absent
4. Reputations, Market Structure, and the Choice of Quality Assurance Systems in the Food Industry
5. ANTI-COMPETITIVE FINANCIAL CONTRACTING: THE DESIGN OF FINANCIAL CLAIMS.
6. The Impact of EU Accession in Romania: An Analysis of Regional Development Policy Effects by a Multiregional I-O Model
7. Contribution of Economics to Design of Sustainable Cattle Breeding Programs in Eastern Africa: A Choice Experiment Approach
8. Foreign Direct Investment and the Single Market
9. The name is absent
10. Labour Market Flexibility and Regional Unemployment Rate Dynamics: Spain (1980-1995)