The DOI matches its Crossref record; 72 of the 72 references it cites were found in a registry or an index.
Deferred acceptance algorithms: history, theory, practice, and open questions
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
College Admissions and the Stability of Marriage
Gale, D., & Shapley, L. S. (1962) · The American Mathematical Monthly · doi:10.1080/00029890.1962.11989827 · Cited by 5,985
A lattice-theoretical fixpoint theorem and its applications
Tarski, A. (1955) · Pacific Journal of Mathematics · doi:10.2140/pjm.1955.5.285 · Cited by 2,704
The assignment game I: The core
Shapley, L. S., & Shubik, M. (1971) · International Journal of Game Theory · doi:10.1007/bf01753437 · Cited by 1,682
Putting Auction Theory to Work
Milgrom, P. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511813825 · Cited by 1,642
School Choice: A Mechanism Design Approach
Abdulkadiroğlu, A., & Sönmez, T. (2003) · American Economic Review · doi:10.1257/000282803322157061 · Cited by 1,568
Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis
Roth, A. E., & Sotomayor, M. A. O. (1990) · Cambridge University Press eBooks · doi:10.1017/ccol052139015x · Cited by 1,340
Self-citationJob Matching, Coalition Formation, and Gross Substitutes
Kelso, A. S., & Crawford, V. P. (1982) · Econometrica · doi:10.2307/1913392 · Cited by 1,307
The evolution of the labor market for medical interns and residents: A case study in game theory
Roth, A. E. (1984) · Journal of Political Economy · doi:10.1086/261272 · Cited by 1,219
Self-citationShapley, L. S., & Scarf, H. E. (1974) · Journal of Mathematical Economics · doi:10.1016/0304-4068(74)90033-0 · Cited by 1,158
Roth, A. E. (2002) · Econometrica · doi:10.1111/1468-0262.00335 · Cited by 1,004
Self-citationThe Economics of Matching: Stability and Incentives
Roth, A. E. (1982) · Mathematics of Operations Research · doi:10.1287/moor.7.4.617 · Cited by 895
Self-citationHatfield, J. W., & Milgrom, P. R. (2005) · American Economic Review · doi:10.1257/0002828054825466 · Cited by 788
Roth, A. E., & Peranson, E. (1999) · American Economic Review · doi:10.1257/aer.89.4.748 · Cited by 756
Self-citationMachiavelli and the Gale-Shapley Algorithm
Dubins, L. E., & Freedman, D. A. (1981) · The American Mathematical Monthly · doi:10.1080/00029890.1981.11995301 · Cited by 654
The New York City High School Match
Abdulkadiroğlu, A., Pathak, P. A., & Roth, A. E. (2005) · American Economic Review · doi:10.1257/000282805774670167 · Cited by 654
Self-citationRandom Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
Abdulkadiroğlu, A., & Sönmez, T. (1998) · Econometrica · doi:10.2307/2998580 · Cited by 611
Demange, G., Gale, D., & Sotomayor, J. (1986) · Journal of Political Economy · doi:10.1086/261411 · Cited by 586
A Tale of Two Mechanisms: Student Placement
Balinski, M., & Sönmez, T. (1999) · Journal of Economic Theory · doi:10.1006/jeth.1998.2469 · Cited by 565
The Boston Public School Match
Abdulkadiroğlu, A., Pathak, P. A., Roth, A. E., & Sönmez, T. (2005) · American Economic Review · doi:10.1257/000282805774669637 · Cited by 530
Self-citationJob Matching with Heterogeneous Firms and Workers
Crawford, V. P., & Knoer, E. M. (1981) · Econometrica · doi:10.2307/1913320 · Cited by 484
The college admissions problem is not equivalent to the marriage problem
Roth, A. E. (1985) · Journal of Economic Theory · doi:10.1016/0022-0531(85)90106-1 · Cited by 466
Self-citationHouse Allocation with Existing Tenants
Abdulkadiroğlu, A., & Sönmez, T. (1999) · Journal of Economic Theory · doi:10.1006/jeth.1999.2553 · Cited by 448
An efficient algorithm for the “stable roommates” problem
Irving, R. W. (1985) · Journal of Algorithms · doi:10.1016/0196-6774(85)90033-1 · Cited by 431
Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences
Roth, A. E., Sönmez, T., & Ünver, M. U. (2007) · American Economic Review · doi:10.1257/aer.97.3.828 · Cited by 392
Self-citationMcVitie, D. G., & Wilson, L. B. (1971) · Communications of the ACM · doi:10.1145/362619.362631 · Cited by 386
Random Paths to Stability in Two-Sided Matching
Roth, A. E., & Vate, J. H. V. (1990) · Econometrica · doi:10.2307/2938326 · Cited by 353
Self-citationOn the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets
Roth, A. E. (1986) · Econometrica · doi:10.2307/1913160 · Cited by 347
Self-citationLeveling the Playing Field: Sincere and Sophisticated Players in the Boston Mechanism
Pathak, P. A., & Sönmez, T. (2008) · American Economic Review · doi:10.1257/aer.98.4.1636 · Cited by 346
Jumping the Gun: Imperfections and Institutions Related to the Timing of Market Transactions
Roth, A. E., & Xing, X. (1994) · Digital Access to Scholarship at Harvard (DASH) (Harvard University) · Cited by 343
Self-citationThe Strategy Structure of Two-Sided Matching Markets
Demange, G., & Gale, D. (1985) · Econometrica · doi:10.2307/1912658 · Cited by 315
What's the Matter with Tie-Breaking? Improving Efficiency in School Choice
Erdil, A., & Ergin, H. (2008) · American Economic Review · doi:10.1257/aer.98.3.669 · Cited by 314
Hard variants of stable marriage
Manlove, D. F., Irving, R. W., Iwama, K., Miyazaki, S., & Morita, Y. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00206-7 · Cited by 311
Games of school choice under the Boston mechanism
Ergin, H., & Sönmez, T. (2006) · Journal of Public Economics · doi:10.1016/j.jpubeco.2005.02.002 · Cited by 305
A Fixed-Point Approach to Stable Matchings and Some Applications
Fleiner, T. (2003) · Mathematics of Operations Research · doi:10.1287/moor.28.1.103.14256 · Cited by 291
Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges
Abraham, D. J., Blum, A., & Sandholm, T. (2007) · Proceedings of the 8th ACM conference on Electronic commerce · doi:10.1145/1250910.1250954 · Cited by 280
Incentive compatibility in a market with indivisible goods
Roth, A. E. (1982) · Economics Letters · doi:10.1016/0165-1765(82)90003-9 · Cited by 279
Self-citationA Kidney Exchange Clearinghouse in New England
Roth, A. E., Sönmez, T., & Ünver, M. U. (2005) · American Economic Review · doi:10.1257/000282805774669989 · Cited by 279
Self-citationEfficient Resource Allocation on the Basis of Priorities
Ergin, H. I. (2002) · Econometrica · doi:10.1111/1468-0262.00383 · Cited by 275
Stable marriage assignment for unequal sets
McVitie, D. G., & Wilson, L. B. (1970) · BIT · doi:10.1007/bf01934199 · Cited by 225
Kagel, J. H., & Roth, A. E. (2000) · Quarterly Journal of Economics · doi:10.1162/003355300554719 · Cited by 220
Self-citationChanging the Boston School Choice Mechanism
Abdulkadiroglu, A., Pathak, P., Roth, A., & Sonmez, T. (2006) · National Bureau of Economic Research · doi:10.3386/w11965 · Cited by 219
Self-citationThe Lattice Structure of the Set of Stable Matchings with Multiple Partners
Blair, C. (1988) · Mathematics of Operations Research · doi:10.1287/moor.13.4.619 · Cited by 217
Roth, A. E., & Xing, X. (1997) · Journal of Political Economy · doi:10.1086/262074 · Cited by 204
Self-citationNP-complete stable matching problems
Ronn, E. (1990) · Journal of Algorithms · doi:10.1016/0196-6774(90)90007-2 · Cited by 188
The Origins, History, and Design of the Resident Match
Roth, A. E. (2003) · JAMA · doi:10.1001/jama.289.7.909 · Cited by 186
Self-citationA necessary and sufficient condition for the existence of a complete stable matching
Tan, J. J. M. (1991) · Journal of Algorithms · doi:10.1016/0196-6774(91)90028-w · Cited by 179
On the Existence of Stable Roommate Matchings
Chung, K.-S. (2000) · Games and Economic Behavior · doi:10.1006/game.1999.0779 · Cited by 163
Unraveling Reduces Mobility in a Labor Market: Gastroenterology with and without a Centralized Match
Niederle, M., & Roth, A. E. (2003) · Journal of Political Economy · doi:10.1086/378530 · Cited by 161
Self-citationOn two competing mechanisms for priority-based allocation problems
Kesten, O. (2005) · Journal of Economic Theory · doi:10.1016/j.jet.2004.11.001 · Cited by 157
Manipulation via Capacities in Two-Sided Matching Markets
Sönmez, T. (1997) · Journal of Economic Theory · doi:10.1006/jeth.1997.2316 · Cited by 154
The College Admissions Problem Revisited
Roth, A. E., & Sotomayor, J. (1989) · Econometrica · doi:10.2307/1911052 · Cited by 153
Self-citationMatching and Price Competition
Bulow, J. I., & Levin, J. (2006) · American Economic Review · doi:10.1257/aer.96.3.652 · Cited by 150
New physicians: A natural experiment in market organization
Roth, A. E. (1990) · Science · doi:10.1126/science.2274783 · Cited by 141
Self-citationStable matchings and preferences of couples
Klaus, B., & Klijn, F. (2004) · Journal of Economic Theory · doi:10.1016/j.jet.2004.04.006 · Cited by 131
The Hospitals/Residents Problem with Ties
Irving, R. W., Manlove, D. F., & Scott, S. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44985-x_24 · Cited by 122
On a characterization of stable matchings
Adachi, H. (2000) · Economics Letters · doi:10.1016/s0165-1765(99)00241-4 · Cited by 120
A further note on the stable matching problem
Demange, G., Gale, D., & Sotomayor, J. (1987) · Discrete Applied Mathematics · doi:10.1016/0166-218x(87)90059-x · Cited by 82
The gastroenterology fellowship Match: How it failed and why it could succeed once again
Niederle, M., & Roth, A. E. (2004) · Gastroenterology · doi:10.1053/j.gastro.2004.05.034 · Cited by 77
Self-citationCan Pre-arranged Matches Be Avoided in Two-Sided Matching Markets?
Sönmez, T. (1999) · Journal of Economic Theory · doi:10.1006/jeth.1999.2507 · Cited by 71
Risk Sharing, Sorting, and Early Contracting
Li, H., & Suen, W. C. (2000) · Journal of Political Economy · doi:10.1086/317675 · Cited by 68
A Non-constructive Elementary Proof of the Existence of Stable Marriages
Sotomayor, J. (1996) · Games and Economic Behavior · doi:10.1006/game.1996.0029 · Cited by 64
Crawford, V. P. (2006) · Journal of Economic Behavior & Organization · doi:10.1016/j.jebo.2006.09.001 · Cited by 62
An algorithm to compute the full set of many-to-many stable matchings
Martı́nez, R., Jordi Massó, A., Neme, A., & Oviedo, J. A. (2003) · Mathematical Social Sciences · doi:10.1016/j.mathsocsci.2003.07.002 · Cited by 52
Connecting the cooperative and competitive structures of the multiple-partners assignment game
Sotomayor, J. (2006) · Journal of Economic Theory · doi:10.1016/j.jet.2006.02.005 · Cited by 52
The Gastroenterology Fellowship Market: Should There Be a Match?
Niederle, M., & Roth, A. E. (2005) · American Economic Review · doi:10.1257/000282805774669691 · Cited by 51
Self-citationOn the lattice structure of the set of stable matchings for a many-to-one model∗
nez, R. M., Jordi Massó, A., Neme, A., & Oviedo, J. A. (2001) · Optimization · doi:10.1080/02331930108844574 · Cited by 47
Ünver, M. U. (2001) · Journal of Economic Dynamics and Control · doi:10.1016/s0165-1889(00)00067-1 · Cited by 42
Ehlers, L., & Klaus, B. (2005) · Games and Economic Behavior · doi:10.1016/j.geb.2005.02.009 · Cited by 42
Matching and Price Competition: Comment
Kojima, F. (2007) · American Economic Review · doi:10.1257/aer.97.3.1027 · Cited by 41
Interior points in the core of two-sided matching markets
Roth, A. E., & Sotomayor, J. (1988) · Journal of Economic Theory · doi:10.1016/0022-0531(88)90255-4 · Cited by 40
Self-citationAldershof, B. K., & Carducci, O. M. (1996) · Discrete Applied Mathematics · doi:10.1016/0166-218x(96)89151-7 · Cited by 34
The Effects of a Centralized Clearinghouse on Job Placement, Wages, and Hiring Practices
Niederle, M., & Roth, A. E. (2007) · National Bureau of Economic Research · doi:10.3386/w13529 · Cited by 7
Self-citation
Cited by
Gender Identity and Relative Income within Households *
Bertrand, M., Kamenica, E., & Pan, J. (2015) · The Quarterly Journal of Economics · doi:10.1093/qje/qjv001 · Cited by 1,164
Incentives and Stability in Large Two-Sided Matching Markets
Kojima, F., & Pathak, P. A. (2009) · American Economic Review · doi:10.1257/aer.99.3.608 · Cited by 362
Stable Matching-Based Selection in Evolutionary Multiobjective Optimization
Li, K., Zhang, Q., Kwong, S., Li, M., & Wang, R. (2014) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2013.2293776 · Cited by 357
Pathak, P. A., & Sönmez, T. (2013) · American Economic Review · doi:10.1257/aer.103.1.80 · Cited by 312
Effective affirmative action in school choice
Hafalir, I. E., Yenmez, M. B., & Yildirim, M. A. (2013) · Theoretical Economics · doi:10.3982/te1135 · Cited by 278
Metadata
- Authors
- Roth, A. E.
- Venue
- International Journal of Game Theory
- Published
- 2008-01-29
- Volume
- 36
- Issue
- 3-4
- Pages
- 537-569
- ISSN
- 0020-7276 (ISSN-L)
- 1432-1270
- OpenAlex
- W2261048370
- Cited by
- 372
- References
- 72
- FWCI
- 21.23
- Type
- journal article
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.