Title: First Choice-Maximizing and First Choice-Stable School Choice Mechanisms
Abstract: We investigate the class of school choice mechanisms that are first choice-maximizing (i.e., they assign a maximum number of first choices) and first choice-stable (i.e., no student forms a blocking pair with her first choice). Typical members of this class include most variants of the popular Boston mechanism. We show that such mechanisms are exactly the ones that consist of a first round of the Boston mechanism, followed by a second round in which the unassigned students are matched with the remaining seats in some arbitrary fashion. We compare these mechanisms by their vulnerability to strategic manipulation and we characterize their Nash equilibria, both, when all students act strategically or when a subset of the students reports truthfully. Our results imply a novel approach to the design of school choice markets: under any mechanism in this class, strategic students will self-select into grabbing their school in the first round; since only non-strategic students enter the second round, their assignment may be chosen independent of the usual incentive constraints, e.g., by optimizing the rank distribution.
