nism is used. However, little is known about the properties of the these two mechanisms
(i.e., the structure of equilibrium profiles and equilibrium outcomes) when individuals
do not necessarily submit their true preferences. In this paper we aim at filling this
gap by exploring the effects of imposing a quota (i.e., a maximal length) on the submit-
table preference lists of students. Thereby we revive an issue that was initially raised by
Romero-Medina (1998), who shows that any stable matching can be sustained at some
Nash equilibrium under the Student-Optimal Stable mechanism.4 In this paper we con-
sider and compare three matching mechanisms that are or have been employed or proposed
in many US school districts: the Boston (BOS), the Student Optimal Stable Matching
(SOSM) and the Top Trading Cycles (TTC) mechanisms.
The model considered in this paper is the school choice problem (Abdulkadiroglu and
Sonmez, 2003) where a number of students has to be assigned to a number of schools,
each of which has a limited seat capacity. Students have preferences over schools and
remaining unassigned and schools have exogenously given priority rankings over students.5
We introduce a preference revelation game where students can only declare up to a fixed
number (the quota) of schools to be acceptable. Each possible quota, from 1 up to the
total number of schools, together with a student assignment mechanism induces a strategic
“quota-game.” Since the presence of the quota eliminates the existence of a dominant
strategy when the mechanism at hand is the SOSM or TTC, we focus our analysis on the
Nash equilibria of the quota-games. Regarding SOSM, our approach complements the
work of Roth (1984), Gale and Sotomayor (1985a), and Alcalde (1996) who characterized
the set of Nash equilibrium outcomes when the schools are strategic.6 As for TTC, so far
little has been known about its Nash equilibria.
Our preliminary results concern the existence and the structure of the Nash equilibria
under BOS, SOSM, and TTC. For all three mechanisms and for any quota, there are Nash
equilibria in pure strategies. We establish that for the three mechanisms the associated
4Kojima and Pathak (2007) consider the game played by schools when for each student only a small
set of schools is acceptable.
5Priorities are the counterpart of schools’ preferences over students in the college admissions problem
(Gale and Shapley, 1962).
6Roth (1984) and Gale and Sotomayor (1985a) characterized the set of Nash equilibrium outcomes
when schools are strategic agents in a college admissions problem, assuming that students truthfully
reveal their (whole) preferences. In particular, they showed that Nash equilibria yield stable matchings
and that any stable matching can be obtained as a Nash equilibrium outcome. Alcalde (1996) went one
step further assuming that students may not necessarily use their weakly dominant strategy. He showed
that the set of Nash equilibrium outcomes coincides with the set of individually rational matchings.