Measuring the External Stability of the One-to-One Matching Generated by the Deferred Acceptance Algorithm

Saglam, Ismail (2019): Measuring the External Stability of the One-to-One Matching Generated by the Deferred Acceptance Algorithm.

Abstract

In this paper, we consider a one-to-one matching model where the population expands with the arrival of a man and a woman. Individuals in this population are matched, before and after the expansion, according to a version of the deferred acceptance algorithm (Gale and Shapley, 1962) where men propose and women reject or (tentatively or permanently) accept. Using computer simulations of this model, we study how the percentage of matches disrupted (undisrupted) with the expansion of the population is affected when the initial size of the population and the size of correlation in the preferences of individuals change.

• Item Type: MPRA Paper
• Language: English
• Keywords: One-to-one matching; deferred acceptance; stability; external stability
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C63 - Computational Techniques ; Simulation Modeling; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C78 - Bargaining Theory ; Matching Theory

References

Abdulkadiroglu, A., Pathak, P. A. & Roth, A. E. (2005) The New York City high school match. American Economic Review, Papers and Proceedings, 95(2), 364-367.

Aptech Systems. (1998) GAUSS version 3.2.34. Maple Valley, WA: Aptech Systems, Inc.

Balinski, M. & Sonmez, T. (1999) A tale of two mechanisms: Student Placement. Journal of Economic Theory, 84, 73-94.

Blum, Y., Roth A. E. & Rothblum, U. G. (1997) Vacancy chains and equilibration in senior-level labor markets. Journal of Economic Theory, 76, 362-411.

Cantala, D. (2004) Restabilizing matching markets at senior level. Games and Economic Behavior, 48(1), 1-17.

Gabszewicz, J. J., Garcia, F., Pais, J. & Resende, J. (2012) On Gale and Shapley ``College admissions and the stability of marriage''. Theoretical Economics Letters, 2, 291-293.

Gale, D. & Shapley, L. S. (1962) College admissions and the stability of marriage. American Mathematical Monthly, 69, 9-15.

Pathak, P. A. & Sonmez, T. (2008) Leveling the playing field: Sincere and sophisticated players in the Boston mechanism. American Economic Review, 98(4), 1636-1652.

Roth, A. E. (2008) Deferred acceptance algorithms: History, theory, practice, and open questions. A collection of papers dedicated to David Gale on the occasion of his 85th birthday, special issue. International Journal of Game Theory, 36(3-4), 537-569.

Roth, A. E. (2002) The economist as engineer: Game theory, experimental economics and computation as tools of design economics. Econometrica, 70(4), 1341-1378.

Roth, A. E. (1984) The evolution of the labor market for medical interns and residents: A case study in game theory. Journal of Political Economy, 92, 991-1016.

Saglam, I. (2019a) The success of the deferred acceptance algorithm under heterogenous preferences with endogenous aspirations, mimeo.

Saglam, I. (2019b) The mutual sequential mate search model under non-homogenous preferences. Marriage & Family Review, accepted for publication.

Todd, P. M. & Miller, G. F. (1999) From pride and prejudice to persuasion: Satisficing in mate search. In G. Gigerenzer, P. M. Todd & the ABC Research Group (Eds.), Simple Heuristics That Make Us Smart (pp. 287-308). New York: Oxford University Press.