Constrained School Choice

We distinguish among three cases for the priority ordering fs₂ of school s2 with respect
to students i1, i2, and i3: (i) fs₂ (i2) < fs₂ (i3) < fs₂ (i1), (ii) fs₂ (i3) < fs₂ (i2) < fs₂ (i1),
and (iii) f_s2 (i₃) < f_s2 (i₁) < f_s2 (i₂). One easily verifies that in each of the cases (i), (ii),
and (iii), the unique stable matching for P is μ* = γ(P) with μ*(i₁) = s₁, μ*(i₃) = s₂,
and μ*(i₂) = i₂.

Consider Q ∈ Q(k)I defined by Qi₂ := 0 and Qi := Pi for all i ∈ I∖i₂. One easily
verifies that in each of the cases (i), (ii), and (iii), γ(Q)(i₁) = s₂ and γ(Q)(i₃) = s₁. 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

<<   <   27   28   29   30   31   32   33   >   >>