We investigate the class of school choice mechanisms that are first-choice maximal (FCM) (i.e., they match a maximal number of students to their reported first choices) and first-choice stable (FCS) (i.e., no students form blocking pairs with their reported first choices). FCM is a ubiquitous desideratum in school choice, and we show that FCS is the only rank-based relaxation of stability that is compatible with FCM. The class of FCM and FCS mechanisms includes variants of the well-known Boston mechanism as well as certain Asymmetric Chinese Parallel mechanisms. Regarding incentives, we show that while no mechanism in this class is strategyproof, the Pareto efficient ones are least susceptible to manipulation. Regarding student welfare, we show that the Nash equilibrium outcomes of these mechanisms correspond precisely to the set of stable matchings. By contrast, when some students are sincere, we show that more students may be matched to their true first choices in equilibrium than under any stable matching. Finally, we show how our results can be used to obtain a new characterization of the Boston mechanism (i.e., the most widely used FCM and FCS mechanism). On a technical level, this paper provides new insights about an influential class of school choice mechanisms. For practical market design, our results yield a potential rationale for the popularity of FCM and FCS mechanisms in practice.

In many situations, a group of individuals (called "agents") must collectively decide on one of several alternatives, e.g., elect the next president. "Ordinal mechanisms" are systematic procedures to make such decisions based on the agents' preference orders over the alternatives. A mechanism is "strategyproof" if it makes truthful reporting of preferences a dominant strategy. Strategyproofness is therefore the gold standard among the incentive concepts. However, the seminal impossibility result of Gibbard [1977] showed that strategyproofness also greatly restricts the design space of ordinal mechanisms even if they can use randomization. In particular, it is incompatible with many other common desiderata, such as Condorcet consistency, stability, or egalitarian fairness. Thus, trade-offs between strategyproofness and other desiderata are necessary. In this paper, we study these trade-offs. We use approximate strategyproofness to define "manipulability," a measure to quantify the incentive properties of non-strategyproof mechanisms, and we introduce "deficit," a measure to quantify the performance of mechanisms with respect to another desideratum. A mechanism that minimizes the deficit subject to a particular bound on manipulability is called "optimal" at this bound; and the mechanisms that are optimal at some bound form the "Pareto frontier." Our main contribution is a structural characterization of this Pareto frontier: we show that there exists a finite set of "supporting manipulability bounds," such that it suffices to identify optimal mechanisms at each of them. Other mechanisms along the Pareto frontier can then be constructed as "hybrids" (i.e., convex combinations) of these optimal mechanisms.

No abstract available.