quota-games have a common feature: the equilibria are nested with respect to the quota.
More precisely, given a quota, any Nash equilibrium is also a Nash equilibrium under
any less stringent quota. This leads to the following important observation: If a Nash
equilibrium outcome in a quota-game has an undesirable property then this is not simply
due to the presence of a constraint on the size of submittable lists. Regarding BOS and
TTC we obtain a much stronger result: Nash equilibrium outcomes are independent of
the quota. This is a powerful result, since it allows us to reduce the analysis to games of
quota 1.
The core of this paper is devoted to the analysis of equilibrium outcomes, focusing on
stability and efficiency. Abdulkadiroglu and Sonmez (2003) discuss in detail the impor-
tance and desirability of these two properties in school choice. In this paper, we explore
under which conditions the mechanisms implement stable and efficient matchings in Nash
equilibria. Most of our analysis will concentrate on SOSM and TTC. The results for BOS
either are already known or come as byproducts of the characterizations for SOSM.7
Stability is the central concept in the two-sided matching literature and does not
lose its importance in the closely related model of school choice.8 Loosely speaking,
stability of an assignment obtains when, for any student, all the schools he prefers to
the one he is assigned to have exhausted their capacity with students that have higher
priority. Romero-Medina (1998) claims that any Nash equilibrium outcome under SOSM
is stable. We provide an example that shows that this is not true.9 Furthermore, the
unstable equilibrium outcome we present cannot be Pareto ranked with respect to the
set of stable assignments, thereby leaving us with little hope for hitting on a closed form
characterization of equilibrium outcomes under SOSM. We therefore turn to the problem
of implementing stable matchings under SOSM. This turns out to be possible if, and
only if, schools’ priorities satisfy Ergin’s (2002) acyclicity condition. However, we may
understand this as a negative result, for Ergin’s acyclicity is a condition that is likely not
to be met in real-life school choice problems. As for BOS, it is easy to show that the
correspondence of stable matchings is implemented in Nash equilibria. Finally, and for
the sake of completeness, we also consider the stability of equilibrium outcomes under
7Alcalde (1996), Ergin and Sonmez (2006) and Pathak and Sonmez (2008) provide an extensive analysis
of the equilibria under BOS.
8In many centralized labor markets, clearinghouses are most often successful if they produce stable
matchings —see Roth (2002) and the references therein.
9See also Example 3 in Sotomayor (1998), which even applies to a larger class of mechanisms than
SOSM.