Constrained School Choice

not give a proof of Proposition 5.2 as it is a direct consequence of Theorem 6.1, which
provides a characterization of the equilibrium outcomes under BOS.

As for SOSM, an equilibrium (outcome) for a given value of the quota is also an
equilibrium (outcome) for any higher value of the quota, i.e., equilibria are nested.

Theorem 5.3 For any school choice problem P and quotas k < k^′, E^γ (P, k) ⊆ E^γ (P, k^′).

Notice that when k = 1 there is only one round in the Boston and the DA algorithm, and
this round is the same for both algorithms. So, the existence of equilibria for SOSM for
any value of the quota follows directly from the existence of equilibria for BOS.

Finally, the set of equilibrium outcomes under TTC is invariant with respect to the
quota.

Theorem 5.4 For any school choice problem P and quota k, O^τ (P, k) = O^τ (P, 1).

Notice that the true strategy profile P is an equilibrium for k = m (because TTC is
strategy-proof). Hence, Theorem 5.4 implies the existence of Nash equilibria for any
value of the quota under TTC.

The fact that under BOS and TTC the set of equilibrium outcomes does not depend
on the value of the quota will simplify to a great extent our analysis. Indeed, for these
two mechanisms it will be enough to consider strategy profiles in which students submit
a list containing at most one school. As for SOSM, the implications of Theorem 5.3 are
not as sharp.

6 Implementation of Stable Matchings

We address in the section the question of the stability of equilibrium outcomes. Among
the three mechanisms we consider, only SOSM is designed to produce stable matchings —
provided agents are truthful. However, when agents are constrained it is not clear whether
a particular mechanism, including SOSM, yields stable matching in equilibrium. While
SOSM is the most natural candidate when studying the stability of equilibrium outcomes
we also consider BOS and TTC.

We first start with BOS. Quite surprisingly, it turns out that any equilibrium outcome
is stable.

15

<<   12   13   14   15   16   17   18   >>

More intriguing information