Constrained School Choice



Pil

P
i i2

p.

i i3

Pi4

fsι

fs2

fs3                         ______________________________

s1

s2

s3

s1

i3

i1

i2

Qii

Qi2

Qi3

Qi4

s2

s3

s1

s2

i1

i2

i4

s1

s2

s3

s1

s3

s1

s2

s3

i2

i3

i3

S2

S3

S1

S2

i4

i4

iι

One easily verifies that γ(Q) = {{i1, s1}, {i2, s2}, {i3, s3}, {i4}}. Since student i4 has
justified envy for school s
3, γ(Q) S(P). It remains to show that Q Eγ(P, 2). Since
students i
1 , i2 , and i3 are assigned a seat at their favorite school, it is sufficient to check
that student i
4 has no profitable deviation. Notice that the only possibility for student i4
to change the outcome of the mechanism is by listing school s3 . So, the only strategies that
we have to check are given by Q(2) =
{Qa,Qb,Qc,Qd,Qe}, where Qa = s3, Qb = s1,s3,
Qc = s2, s3, Qd = s3, s1, and Qe = s3, s2. Routine computations show that none of these
strategies is a profitable deviation. So,
Q Eγ(P, 2).21

Furthermore, since students i1 , i2 , and i3 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},
{i2 , s2 }, {i3 , s3}, {i4}}. For the same reason as b efore, it is sufficient to check that student
i4 has no profitable deviation. This, however, is immediate since student i4 cannot “break”
the cycle (
i1, s1, i3, s3, i2, s2) 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.
22 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

21Note 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.

22A 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



More intriguing information

1. The Role of Land Retirement Programs for Management of Water Resources
2. Reputations, Market Structure, and the Choice of Quality Assurance Systems in the Food Industry
3. Gianluigi Zenti, President, Academia Barilla SpA - The Changing Consumer: Demanding but Predictable
4. A Review of Kuhnian and Lakatosian “Explanations” in Economics
5. ANTI-COMPETITIVE FINANCIAL CONTRACTING: THE DESIGN OF FINANCIAL CLAIMS.
6. The name is absent
7. The name is absent
8. ¿Por qué se privatizan servicios en los municipios (pequeños)? Evidencia empírica sobre residuos sólidos y agua.
9. Impact of Ethanol Production on U.S. and Regional Gasoline Prices and On the Profitability of U.S. Oil Refinery Industry
10. EMU's Decentralized System of Fiscal Policy