Smart Lotteries in School Choice: Ex-ante Pareto-Improvement with Ex-post Stability

Haris Aziz, P\'eter Bir\'o, Gergely Cs\'aji and Tom Demeulemeester

Papers from arXiv.org

Abstract: In school choice, students typically 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 outcome of this mechanism that occurs with a positive probability is a stable solution for the coarse priorities. This implies a probabilistic assignment, specifying the admission probability for each student-school pair. In this paper, we propose a new efficiency-improving stable 'smart lottery' mechanism. We 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. We show that although the underlying computational problem is NP-hard, we can solve the problem in practice by using column generation. Our computational results show that the welfare gains by our mechanism are substantially larger than the expected gains by standard methods that realize efficiency improvements after ties have already been broken. Additionally, we illustrate for real-world school choice data of Ghent (Belgium) that, while not theoretically guaranteed, our mechanism can Pareto-improve upon methods that improve upon DA but violate ex-post stability, such as Efficiency-Adjusted Deferred Acceptance.

Date: 2026-02, Revised 2026-10
New Economics Papers: this item is included in nep-des and nep-upt
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://arxiv.org/pdf/2602.10679 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2602.10679

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().