Constrained School Choice

schools, and (b) for any two schools s and s’ listed in Qi (or Qi), sQ'_is' implies sP_is^t.
Then, Qi is weakly к-dominated by Qi in the games Γ^γ(P, k) and Γ^τ(P, k).

Proof Let φ := γ, τ. The result follows directly from the strategy-proofness of γ (Dubins
and Freedman, 1981; Roth, 1982b) and τ (Abdulkadiroglu and Sonmez, 2003) by using
Qi as student i’s “true preferences:” φ(Q'i, Q_-i)(i) is ranked higher than φ(Qi, Q_-i)(i) by
Qi, hence φ(Q'i,Q_-i)(i) is ranked higher than φ(Qi,Q_-i)(i') by Pi.                      ■

The message of Lemma 4.2 is clear: a student cannot lose (and may possibly gain) by
submitting the same set of schools in the true order.

5 Existence and Nestedness of Equilibria

Our main interest in this section is to analyze the extent to which Nash equilibria are
affected by the value of the quota. To avoid vacuously true statements, we first establish
the existence of (pure) Nash equilibria in any constrained school choice problem for all
three mechanisms, for any value of the quota.¹³

Proposition 5.1 For any school choice problem P and quota k, E^ψ(P,k) = 0, for φ =
β, γ, τ .

Understanding whether the presence of a quota affects the set of equilibria and equi-
librium outcomes is crucial in our analysis of constrained school choice games. The next
results describe how the equilibria vary when the quota changes. Fortuitously, Proposi-
tion 5.1 is a direct corollary to these results.

For BOS it turns out that the equilibrium outcomes do not depend on the quota.

Proposition 5.2 For any school choice problem P and quota k, O^β (P, k) = O^β(P, 1).

The existence of equilibria under BOS is therefore a straightforward implication of Propo-
sition 5.2 and O^β(P,m) = 0 (implied by Ergin and Sonmez, 2006, Theorem 1 or a slight
adaptation of Alcalde, 1996, Theorem 4.6), where m is the number of schools. We do

¹³An adaptation of the arguments in the proofs of Alcalde (1996, Theorem 4.6) or Ergin and
Sonmez (2006, Theorem 1) establishes Theorem 5.1 for the case of β (any k) and γ (with k = 1). Also
notice that when k = m, the result for γ and τ follows from the strategy-proofness of the unconstrained
mechanisms.

14

<<   11   12   13   14   15   16   17   >>

More intriguing information