NATIONAL BUREAU OF ECONOMIC RESEARCH
NATIONAL BUREAU OF ECONOMIC RESEARCH

Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions

Alvin E. Roth

NBER Working Paper No. 13225
Issued in July 2007
NBER Program(s):   LS   ED

The deferred acceptance algorithm proposed by Gale and Shapley (1962) has had a profound influence on market design, both directly, by being adapted into practical matching mechanisms, and, indirectly, by raising new theoretical questions. Deferred acceptance algorithms are at the basis of a number of labor market clearinghouses around the world, and have recently been implemented in school choice systems in Boston and New York City. In addition, the study of markets that have failed in ways that can be fixed with centralized mechanisms has led to a deeper understanding of some of the tasks a marketplace needs to accomplish to perform well. In particular, marketplaces work well when they provide thickness to the market, help it deal with the congestion that thickness can bring, and make it safe for participants to act effectively on their preferences. Centralized clearinghouses organized around the deferred acceptance algorithm can have these properties, and this has sometimes allowed failed markets to be reorganized.

download in pdf format
   (801 K)

email paper

This paper is available as PDF (801 K) or via email.

Acknowledgments

Machine-readable bibliographic record - MARC, RIS, BibTeX

Document Object Identifier (DOI): 10.3386/w13225

Published: Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer, vol. 36(3), pages 537-569, March.

Users who downloaded this paper also downloaded these:
Roth w13530 What Have We Learned From Market Design?
Figlio w11195 Names, Expectations and the Black-White Test Score Gap
Roth w12702 Repugnance as a Constraint on Markets
Abdulkadiro─člu, Pathak, and Roth w14864 Strategy-proofness versus Efficiency in Matching with Indifferences: Redesigning the New York City High School Match
Bullock, Gerber, Hill, and Huber w19080 Partisan Bias in Factual Beliefs about Politics
 
Publications
Activities
Meetings
Data
People
About

Support
National Bureau of Economic Research, 1050 Massachusetts Ave., Cambridge, MA 02138; 617-868-3900; email: info@nber.org

Contact Us