schools, and (b) for any two schools s and s’ listed in Qi (or Qi), sQ'is' implies sPist.
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.13
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
13An 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