**School Choice and Gale-Shapley Model Bibliography**

Prepared by:

Joseph Malkevitch

Department of Mathematics

York College (CUNY)

Jamaica, New York 11451

email:

__malkevitch@york.cuny.edu__

web page:

__http://york.cuny.edu/~malk/__

School choice models, ideas about how to assign students to schools for the benefit of the students, the school system and all of society, owes much to a a delightful and important paper by the American game theorists David Gale (1921-2008) and Lloyd Shapley (1923- ). In the section about school choice I have included some papers about the Gale-Shapley model in general as well as some dealing with mechanism design.

**The Source** (the paper that started it all!)

Gale, D., and L. Shapley, College admissions and the stability of marriage, Amer. Math. Monthly, 69 (1962) 9-15.

**Books**

Gusfield, D., and R. Irving, The Stable Marriage Problem, MIT Press, Cambridge, 1989.

Knuth, D., Mariages Stables, Les Presses de l’Université de Montreal, Montréal, 1976.

Knuth, D. Stable Marriage and Its Relation to other Combinatorial Problems, American Mathematical Society, Providence, 1997.

Roth, A., and M. Sotomayor, Two-Sided Matching, Cambridge U. Press, New York, 1990.

**School Choice**

(Many of these papers can be found in various versions on the web.)

Abdulkadiroglu, A., College admissions with affirmative action, Int. J. Game Theory, 33 (2005) 535-549.

Abdulkadiroglu, A. and Y. Che, Y. Yasuda, "Expanding Choice" in School Choice, Duke University, (Unpublished manuscript.)

Abdulkadiroglu, A. and P. Pathak, A. Roth, The New York City high school match, Amer. Econ. Review, Papers and Proceedings, 95 (2005) 368-371.

Abdulkadiroglu, A. and P. Pathak, A. Roth, T. Sönmex, The Boston public school match, American Econ. Review, Papers and Proceedings, May, 2005.

Abdulkadirogu, A. and T. Sönmez, House allocation with existing tenants, J. Econ. Theory, 88 (1999) 233-260.

Abdulkadirogu, A. and T. Sönmez, School choice: A mechanism approach, American Econ. Rev., 93 (2003) 729-747.

Balinski, M. and T. Sönmez, A tale of two mechanisms: Student placement, J. of Econ. Theory, 84 (1999) 73-94.

Barberà,S. and B. Dutta, Protective behavior in matching models, Games Econ. Behavior, 8 (1995) 281-296.

Chen, Y. and T. Sönmez, Improving the efficiency of on-campus housing: an experimental study, Amer. Econ. Rev., 92 (2002) 1669-1686.

Chen, Y. and T. Sönmez, School choice: an experimental study, J. Econ. Theory, 127 (2006) 202-231.

Demange, G. and D. Gale, M. Sotomayor, A further note on the stable matching problem, Discrete Applied Math., 16 (1987) 217-222.

Dubins, L. and D. Freedman, Machiavelli and the Gale-Shapley Algorithm, Amer. Math. Monthly, 88 (1981) 485-494.

Ehlers, L., Respecting priorities when assigning students to schools, CIREQ, Feb., 2006.

Erdil, A., Two-side Matching with Ties, Doctoral Thesis, Department of Mathematics, U. of Chicago, 2006.

Erdil, A. and H. Ergin, What's the matter with tie breaking? Improving efficiency in school choice, Amer. Econ. Review, 98 (2008) 669-689.

Ergin, H. and T. Sönmez, Games of school choice under the Boston mechanism, J. of Public Economics, 90 (2006) 215-237.

Featherstone, C. and M. Niederle, Manipulation in school choice mechanisms, Working paper, Stanford U., 2008.

Featherstone, C. and M. Niederle, Ex ante efficiency in school choice mechanisms: an experimental investigation, (to appear).

Gale, D. and M. Sotomayor, Some remarks on the stable matching problem, Discrete Applied Math., 11 (1985) 223-232.

Gale, D. and M. Sotomayor, Ms. Machiavelli and the stable matching problme, Amer. Math. Monthly, 69 (1985) 261-268.

Gusfield, D., Three fast algorithms for four problems in stable marriage, SIAM J. on Computing, 16 (1987) 111-128.

Gusfield, D., The structure of the stable roommate problem: efficient representation and enumeration of all stable assignments, SIAM J. on Computing, 17 (1988) 742-769.

Gusfield, D. and R. Irving, The parametric stable marriage problem, Information Processing Letters, 30 (1987) 255-259.

Gusfield, D. and R. Irving, P. Leather, M. Sakes, Every finite distributive lattice is a set of stable matchings for a small stable marriage instance, J. of Comb. Theory A, 44 (1987) 304-309.

Haeringer, G. and F. Klijn, Constrained school choice, J. Economic Theory, 144 (2009) 1921-1947.

Huang, C., Cheating by men in the Gale-Shapley matching algorithm. (Preprint)

Huange, C., How hard is it to cheat in the Gale-Shapley stable matching algorithm, (Preprint).

Irving, R., An efficient algorithm for the stable room-mates problem, Journal of Algorithms, 6 (1985) 577-595.

Irving, R. and P. Leather, The complexity of counting stable marriages, SIAM J. on Computing, 15 (1986) 655-667.

Irving, R. and P. Leather, and D. Gusfield, An efficient algorithm for the "optimal" stable marriage, Journal of the A.C.M., 34 (1987) 532-543.

Kesten, O., Coalitional strategy-proofness and resource monotonicity for house allocation problems, International J. Game Theory, 38 (2009) 17-21.

Knuth, D., Marriages stable, Les Presses de l"Universite de Montreal, Montreal, 1976.

Kojima, F., Games of school choice under the Boston mechanism with general priority structures, Soc. Choice Welfare, 31 (2008) 357-365.

Kojima, F. and P. Pathak, Incentives and stability in large two-sided markets. (Preprint)

McVittie, D. and L. Wilson, Stable marriage assignments for unequal sets, BIT, 10 (1970) 295-309.

McVittie, D. and L. Wilson, The applications of the stable marriage assignment in university admissions, Operational Research Quarterly, 21 (1970) 425-433.

McVittie, D. and L. Wilson, The stable marriage problem, Communications of the ACM, 14 (1971) 486-492.

Mongell, S., Sorority rush as a two-sided matching mechanism: A Game Theoretic Analysis, Doctoral Dissertation, Department of Economics, University of Pittsburgh, 1987.

Mongell, S. and A. Roth, A note on job matching with budget constraints, Economics Letters, 21 (1986) 135-138.

Niederle, M. and A. Roth, T. Sönmez, Matching, The New Palgrave Dictionary of Economics, (Second edition).

Pais, J. and A. Pinter, School choice and information: an experimental study on matching mechanisms, Games and Econ. Behavior, 64 (2008) 303-328.

Romero-Medina, A., Equitable selection in bilateral matching markets, Theory and Decision, 58 (2005) 305-324.

Roth, A., The economics of matchings: stability and incentives, Math. of Operations Research, 7 (1982) 617-628.

Roth, A., The evolution of the labor market for medical interns and residents: A case study in Game theory, J. of Pol. Econ., 92 (1984) 991-1016.

Roth, A., The college admissions problem is not equivalent to the marriage problem, J. of Economic Theory, 36 (1985) 277-288.

Roth, A. A natural experiment in the organization of entry level labor markets: regional markets for new physicians and surgeons in the U.K., Amer. Economic Review, 81 (1991) 415-440.

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

Roth, A., What have we learned from market design?, Economic Journal, 118 (2008) 285-310.

Roth, A. and E. Peranson, The redesign of the matching market for American physicians: some engineering aspects of economic design, American Econ. Rev., 89 (1999) 748-780.

Roth, A. and T. Sönmez, M. Ünver, Pairwise kidney exchange, J. Economic Theory, 125 (2005) 151-188.

Roth, A. and M. Sotomayor, Interior points in the core of two-sided matching markets, J. of Economic Theory, 45 (1988) 85-101.

Roth, A. and M. Sotomayor, The college admissions problem revisited, Econometrica, 57 (1989)559-570.

Roth, A. and M. Sotomayor, Two-Sided Matching, Chapter 16, in Handbook of Game Theory, R. Aumann and S. Hart (eds.), Elsevier, 1992, pp. 459-541.

Roth, A. and X. Xing, Turnaround time and bottlenecks in market clearing: Decentralized matching in the market for clinical psychologists, J. of Pol. Econ., 105 (1997) 284-329.

Shapley, L. and H. Scarf, On cores and indivisibility, J. Math. Economics, 1 (1974) 23-37.

Shapley, L. and M. Shubik, The assignment game I: The Core, International J. of Game Theory, 1 (1971) 111-130.

Sönmez, T., Manipulation via capacities in two-sided matching markets, J. Economic Theory, 77 (1997) 197-204.

Sönmez, T., Can prearranged matches be avoided in two-sided matching markets? J. of Economic Theory, 86 (1999) 148-156.

Sotomayor, M., A non-constructive elementary proof of the existence of stable marriages, Games and Econ. Behavior, 13 (1996) 135-137.

Sotomayor, M. Reaching the core of the marriage market through a non-revelation matching mechanism, International J. Game Theory, 32 (2003) 241-251.

Sotomayor, M., The stability of the equilibrium outcomes in the admissions games induced by stable matching rules, International J. Game Theory, 36 (2008) 621-640.

Sotomayor, M., My encounters with David Gale, Games and Economic Behavior, 66 (2009) 643-646.

Teo, C. and J. Sethuraman, W. Tan, Gale-Shapley stable marriage problem revisited: strategic issues and applications, Management Science, 47 (2001) 1252-1267.

Ünver, M., Backward unraveling over time: the evolution of strategic behavior in the entry-level British medical labor market, J. Econ. Dyn. Control, 25 (2001) 1039-1080.

Ünver, M., On the survival of some unstable two-sided matching mechanims, International J. of Game Theory, 33 (2005) 239-254.

Back to list of bibliographies