Smart Lotteries in School Choice

In a typical school choice application, the students have strict preferences over the schools while the schools have coarse priorities over the students based on their distance and their enrolled siblings. The outcome of a centralized admission mechanism is then usually obtained by the Deferred Acceptance (DA) algorithm with random tie-breaking. Therefore, every possible outcome of this mechanism is a stable solution for the coarse priorities that will arise with certain probability. This implies a probabilistic assignment, where the admission probability for each student-school pair is specified. In the paper presented in this ZEW Research Seminar, the authors propose a new efficiency-improving stable `smart lottery' mechanism. The authors aim to improve the probabilistic assignment ex-ante in a stochastic dominance sense, while ensuring that the improved random matching is still ex-post stable, meaning that it can be decomposed into stable matchings regarding the original coarse priorities. Therefore, this smart lottery mechanism can provide a clear Pareto-improvement in expectation for any cardinal utilities compared to the standard DA with lottery solution, without sacrificing the stability of the final outcome. The authors show that although the underlying computational problem is NP-hard, the problem can be solved by using advanced optimization techniques such as integer programming with column generation. The authors conduct computational experiments on generated and real instances. The results show that the welfare gains by the used mechanism are substantially larger than the expected gains by standard methods that realize efficiency improvements after ties have already been broken.