What’s the Matter with Tie-breaking? Improving Efficiency with

In several school choice districts in the United States, the student proposing deferred acceptance algorithm is applied after indifferences in priority orders are broken in some exogenous way. Although such a tie-breaking procedure preserves stability, it adversely affects the welfare of the students since it introduces arti-ficial stability constraints. Our main finding is a polynomial-time algorithm for the computation of a student-optimal stable matching when priorities are weak. The idea behind our construction relies on a new notion which we call a stable improvement cycle. We also investigate the strategic properties of the student optimal stable mechanism. (JEL C78, D61, D78, I20) Until about a decade ago, children in the U.S. were assigned to public schools by the district they live in, without taking into account the preferences of their families. Such systems overlooked reallocations of seats which could Pareto improve welfare. Motivated by such concerns, several cities in the U.S., including New York City, Boston, Cam