The Large and Likely Inefficiency of Stable Matching Mechanisms

Josue Ortega, Gabriel Ziegler, R. Pablo Arribillaga and Geng Zhao

Papers from arXiv.org

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.

Date: 2024-07, Revised 2026-07
New Economics Papers: this item is included in nep-des and nep-ure
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://arxiv.org/pdf/2407.19831 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:2407.19831

Access Statistics for this paper

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