Deferred acceptance algorithms: history, theory, practice, and open questions (Q2482681): Difference between revisions

\textit{D. Gale} and \textit{L. S.\ Shapley}'s 1962 paper [Am. Math. Monthly 69, 9--15 (1962; Zbl 0109.24403)] introduced a two-sided matching model in which men and women (or students and colleges) hold preferences over members of the other set, to whom they might be matched. Gale and Shapley introduced the ``deferred acceptance algorithm'' to prove that the set of stable matchings in this model is nonempty. Because of the theoretical interest and wide applicability of this theory, Gale and Shapley's foundational paper has led to an extraordinarily active body of research on the design of matching markets. This literature spans several fields, with contributions from theoretical mathematics, economics, operations research, and computer science. In this article, Alvin E.\ Roth, a frequent and distinguished contributor to the study of matching markets, discusses both the theoretical and applied branches of the research on matching markets. Roth's account is thorough and well-paced. His article assumes only minimal background and is appropriate for both mathematicians and economists. Roth first reviews Gale and Shapley's original paper, presenting both the ``marriage'' and ``college admissions'' models of two-sided matching. Roth then surveys the subsequent theoretical work on the marriage model, touching on several key possibility characterizations (such as Conway's ``Lattice Theorem'' [see \textit{D. E. Knuth}, Mariages stables et leurs rélations avec d'autres problèmes combinatoires. Introduction á l'analyse mathématique des algorithmes (1976; Zbl 0358.68057)]) and impossibility results (including \textit{A. E. Roth}'s ``Impossibility theorem'' [Math. Oper. Res. 7, 617--628 (1982; Zbl 0496.90008)]). He then addresses more general models, including models with price-setting and those (such as the college admissions model) with ``many-to-one matching.'' Next, Roth surveys the applied and empirical literature on matching markets. Here, he focuses on how matching algorithms have been used (and misused) in practice. This section includes an appendix drawn from [\textit{A. E. Roth}, J. Polit. Econ. 92, 991--1016 (1984)] and a list of the labor markets that have adopted the Roth-Peranson [\textit{A. E. Roth} and \textit{E. Peranson}, The redesign of the matching market for American physicians: some engineering aspects of economic design. Am. Econ. Rev. 89, 748--780 (1999)] clearinghouse design. The article closes with an exposition of contemporary matching research. This includes a survey of the past few years of literature on matching market stability, brief remarks on the interactions between matching and market design, and a loose conjecture on the presence of stable matchings in realistic markets.