The Naive versus the Adaptive Boston Mechanism.

Abstract

The Boston mechanism is often criticized for its manipulability and the resulting negative implications for welfare and fairness. Nonetheless, it is one of the most popular school choice mechanisms used in practice. In this paper, we first study the traditional (naive) Boston mechanism (NBM) in a setting with no priority structure and single uniform tie-breaking. We show that it imperfectly rank dominates the strategyproof Random Serial Dictatorship (RSD). We then formalize an adaptive variant of the Boston mechanism (ABM), which is also sometimes used in practice. We show that ABM has significantly better incentive properties than NBM (it is partially strategyproof), while it shares most of NBM's efficiency advantages over RSD as markets get large. However, while a direct efficiency comparison of NBM and ABM via imperfect dominance is inconclusive, numerical simulations suggest that NBM is still somewhat more efficient than ABM, which can be interpreted as the cost of partial strategyproofness one pays when choosing ABM over NBM. Our results highlight the subtle trade-off between efficiency and strategyproofness a market designer must make when choosing between the two Boston mechanisms and RSD.