The large and likely inefficiency of stable matching mechanisms

Josue Ortega (), Gabriel Ziegler (), R. Pablo Arribillaga () and Geng Zhao ()
Additional contact information
Josue Ortega: Department of Economics, Queen's University Belfast
Gabriel Ziegler: Department of Economics, Free University Berlin
R. Pablo Arribillaga: Instituto de Matemática Aplicada San Luis, Universidad Nacional de San Luis and CONICET
Geng Zhao: Department of Electrical Engineering and Computer Science, University of California Berkeley

Theoretical Economics, Forthcoming

Abstract: 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.

Keywords: Unimprovable students; school choice; random markets (search for similar items in EconPapers)
JEL-codes: C78 D47 (search for similar items in EconPapers)
Date: 2026-08-04
References: Add references at CitEc
Citations:

Downloads: (external link)
http://econtheory.org/ojs/index.php/te/article/viewForthcomingFile/6699/45799/1 Working paper version. Paper will be copyedited and typeset before publication. (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:the:publsh:6699

Access Statistics for this article

Theoretical Economics is currently edited by Federico Echenique, Mira Frick, Pablo Kurlat, Juuso Toikka, Rakesh Vohra

More articles in Theoretical Economics from Econometric Society
Bibliographic data for series maintained by Editor Theoretical Economics ( this e-mail address is bad, please contact ).