The Secure Boston Mechanism

Abstract

It is well known in the school assignment literature that it is impossible for a strategyproof mechanism to Pareto improve the assignment made be the Deferred Acceptance algorithm (DA). However, we show that it is possible for an algorithm to Pareto dominate DA in equilibrium. We do this by introduce a new algorithm, the Secure Boston Mechanism (sBM), that is a hybrid between the Boston Mechanism (BM) and DA. Our algorithm protects students that are initially guaranteed a school a but otherwise adjusts priorities at a based on how students rank a. We demonstrate that sBM always has an equilibrium that weakly dominates the DA assignment. We show that in equilibria that survive iterated elimination of dominated strategies that no student receives a school worse than a school she receives in a fair assignment. Finally, we show that whenever DA is inefficient, there exists a larger economy in which DA makes the same assignment but an equilibrium of sBM makes the Pareto dominating reassignment.

Keywords

• boston mechanism
• school choice
• matching