2024/07/29 by Josué Ortega, Ortega, Josue, Gabriel Ziegler +4 · 1 citation
Social Sciences · #FOS: Economics and business #Global Educational Reforms and Inequalities #Intergenerational and Educational Inequality Studies #School Choice and Performance #Theoretical Economics (econ.TH)
paper · pdf · doi:10.48550/arxiv.2407.19831
openalex publication_date 2024/07/29 · openalex created_date 2024/08/01 · openalex updated_date 2026/07/28
We prove that any stable matching mechanism suffers from systematic inefficiency of striking magnitude: in large random markets, any stable allocation is Pareto-inefficient with high probability, and almost all students can simultaneously improve their placements without harming anyone else. We establish this result by showing that the envy digraph generated by the student-proposing Deferred Acceptance mechanism contains a unique giant strongly connected component, implying that nearly all students are improvable via trading cycles. Finally, we show that every maximal cycle packing covers almost all students, revealing a surprising asymptotic equivalence among all efficient mechanisms that Pareto-dominate DA.