What`s the Matter with Tie-breaking? Improving Efficiency in School Choice
AbstractVery little is known about the student-optimal stable mechanism when school priorities are weak. In current practice, the student proposing deferred acceptance algorithm is applied after indifferences in priority orders are broken with a lottery. Although such a tie-breaking procedure preserves stability, it adversely affects the welfare of the students since it introduces artificial stability constraints. We propose a simple procedure to compute a student-optimal stable matching when priorities are weak. The idea behind our construction relies on a new notion which we call a stable improvement cycle. Abdulkadiroglu, Pathak, and Roth (2006) report that had our algorithm been applied to the preference data of the 2003-2004 New York City High School Match, 6,854 students (10.5% of the 63,795 matched students) would have been matched with schools higher on their preference lists without hurting the others. We run simulations to understand the qualitative effects of correlation in preferences and of locational preference on the size of the efficiency gain. We also investigate the strategic properties of the class of student-optimal stable mechanisms.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by University of Oxford, Department of Economics in its series Economics Series Working Papers with number 349.
Date of creation: 01 Sep 2007
Date of revision:
School Choice; Student-Optimal Stable Mechanism; Weak Priorities; Stable Improvement Cycles;
Other versions of this item:
- Aytek Erdil & Haluk Ergin, 2008. "What's the Matter with Tie-Breaking? Improving Efficiency in School Choice," American Economic Review, American Economic Association, vol. 98(3), pages 669-89, June.
- I28 - Health, Education, and Welfare - - Education - - - Government Policy
- H75 - Public Economics - - State and Local Government; Intergovernmental Relations - - - State and Local Government: Health, Education, and Welfare
- I21 - Health, Education, and Welfare - - Education - - - Analysis of Education
This paper has been announced in the following NEP Reports:
- NEP-ALL-2007-09-16 (All new papers)
- NEP-DCM-2007-09-16 (Discrete Choice Models)
- NEP-EDU-2007-09-16 (Education)
- NEP-URE-2007-09-16 (Urban & Real Estate Economics)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth, 2009. "Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match," American Economic Review, American Economic Association, vol. 99(5), pages 1954-78, December.
- Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2006.
"Changing the Boston School Choice Mechanism,"
Boston College Working Papers in Economics
639, Boston College Department of Economics.
- Atila Abdulkadiroglu & Parag Pathak & Alvin E. Roth & Tayfun Sonmez, 2006. "Changing the Boston School Choice Mechanism," NBER Working Papers 11965, National Bureau of Economic Research, Inc.
- Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2006. "Changing the Boston School Choice Mechanism," Levine's Bibliography 122247000000001022, UCLA Department of Economics.
- EHLERS, Lars, 2006.
"Respecting Priorities when Assigning Students to Schools,"
Cahiers de recherche
2006-04, Universite de Montreal, Departement de sciences economiques.
- EHLERS, Lars, 2006. "Respecting Priorities when Assigning Students to Schools," Cahiers de recherche 04-2006, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
- Atila Abdulkadiroğlu & Parag A. Pathak & Alvin E. Roth & Tayfun S�nmez, 2005.
"The Boston Public School Match,"
American Economic Review,
American Economic Association, vol. 95(2), pages 368-371, May.
- Atila Abdulkadiroglu & Tayfun Smez, 2003.
"School Choice: A Mechanism Design Approach,"
0203-18, Columbia University, Department of Economics.
- Roth,Alvin E. & Sotomayor,Marilda A. Oliveira, 1992.
Cambridge University Press, number 9780521437882, April.
- Roth, Alvin E. & Sotomayor, Marilda, 1992. "Two-sided matching," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 1, chapter 16, pages 485-541 Elsevier.
- Alvin E. Roth & Uriel G. Rothblum, 1999. "Truncation Strategies in Matching Markets--In Search of Advice for Participants," Econometrica, Econometric Society, vol. 67(1), pages 21-44, January.
- Alvin E. Roth & Elliott Peranson, 1999.
"The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design,"
NBER Working Papers
6963, National Bureau of Economic Research, Inc.
- Elliott Peranson & Alvin E. Roth, 1999. "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design," American Economic Review, American Economic Association, vol. 89(4), pages 748-780, September.
- Szilvia Papai, 2000. "Strategyproof Assignment by Hierarchical Exchange," Econometrica, Econometric Society, vol. 68(6), pages 1403-1434, November.
- Roth, Alvin E, 1984. "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory," Journal of Political Economy, University of Chicago Press, vol. 92(6), pages 991-1016, December.
- Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
- Pathak, Parag A. & Abdulkadiroglu, Atila & Roth, Alvin, 2005.
"The New York City High School Match,"
2562765, Harvard University Department of Economics.
- Kesten, Onur, 2006. "On two competing mechanisms for priority-based allocation problems," Journal of Economic Theory, Elsevier, vol. 127(1), pages 155-171, March.
- Alvin E. Roth, 2002. "The Economist as Engineer: Game Theory, Experimentation, and Computation as Tools for Design Economics," Econometrica, Econometric Society, vol. 70(4), pages 1341-1378, July.
This item has more than 25 citations. To prevent cluttering this page, these citations are listed on a separate page. reading list or among the top items on IDEAS.Access and download statisticsgeneral information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Caroline Wise).
If references are entirely missing, you can add them using this form.