Constrained School Choice

One easily verifies that γ(Q) = {{i₁, s₁}, {i₂, s₂}, {i₃, s₃}, {i₄}}. Since student i₄ has
justified envy for school s3, γ(Q) ∈ S(P). It remains to show that Q ∈ E^γ(P, 2). Since
students i1 , i2 , and i3 are assigned a seat at their favorite school, it is sufficient to check
that student i4 has no profitable deviation. Notice that the only possibility for student i4
to change the outcome of the mechanism is by listing school s₃ . So, the only strategies that
we have to check are given by Q(2) = {Q^a,Q^b,Q^c,Q^d,Q^e}, where Q^a = s₃, Q^b = s₁,s₃,
Q^c = s2, s3, Q^d = s3, s1, and Q^e = s3, s2. Routine computations show that none of these
strategies is a profitable deviation. So, Q ∈ E^γ(P, 2).²¹

Furthermore, since students i₁ , i₂ , and i₃ are assigned a seat at their favorite school at
γ(Q) and Q ∈ E^γ (P, 2), it follows that Q is a strong Nash equilibrium (cf. Aumann, 1959)
in Γ^γ(P, 2).

As for the Top Trading Cycles mechanism, one easily verifies that also τ(Q) = {{i1 , s1},
{i₂ , s₂ }, {i₃ , s₃}, {i₄}}. For the same reason as b efore, it is sufficient to check that student
i₄ has no profitable deviation. This, however, is immediate since student i₄ cannot “break”
the cycle (i₁, s₁, i₃, s₃, i₂, s₂) that forms in the first step of the TTC algorithm. Hence, Q
is also a strong Nash equilibrium in Γ^τ (P, 2).                                           ^

The results of McVitie and Wilson (1970) and Roth (1984b) for college admissions imply
that for any school choice problem the set of unassigned students is the same for all stable
matchings.²² In other words, for μ,μ' ∈ S (P ), μ(i) = i implies μ'(i) = i. Given the re-
strictiveness of the acyclicity conditions to guarantee stable Nash equilibrium outcomes,
one may wonder whether at least always the set of unassigned students at equilibrium
coincides with the set of unassigned students in stable matchings. In fact, a less ambitious

²¹Note that it is not necessary to set the quota equal to 2. Strategy profile Q is also a Nash equilibrium
in the unconstrained setting, i.e., when the quota is k = 3. Finally, one can straightforwardly extend
the example for m > 3 and/or n > 4 by making existing schools unacceptable for new students and new
schools unacceptable for existing students.

²²A generalization of this result is known in the two-sided matching literature as the “Rural Hospital
Theorem” (Roth, 1986) and says that the degree of occupation and quality of interns at typically less
demanded rural hospitals in the US is not due to the choice of a specific stable matching.

25

<<   <   22   23   24   25   26   27   28   >   >>