Course Allocation via Stable Matching
Tóm tắt
The allocation of students to courses is a wide-spread and repeated task in higher education, often accomplished by a simple first-come first-served (FCFS) procedure. FCFS is neither stable nor strategy-proof, however. The Nobel Prize in Economic Sciences was awarded to Al Roth and Lloyd Shapley for their work on the theory of stable allocations. This theory was influential in many areas, but found surprisingly little application in course allocation as of yet. In this paper, different approaches for course allocation with a focus on appropriate stable matching mechanisms are surveyed. Two such mechanisms are discussed in more detail, the Gale-Shapley student optimal stable mechanism (SOSM) and the efficiency adjusted deferred acceptance mechanism (EADAM). EADAM can be seen as a fundamental recent contribution which recovers efficiency losses from SOSM at the expense of strategy-proofness. In addition to these two important mechanisms, a survey of recent extensions with respect to the assignment of schedules of courses rather than individual courses is provided. The survey of the theoretical literature is complemented with results of a field experiment, which help understand the benefits of stable matching mechanisms in course allocation applications.
Tài liệu tham khảo
Abdulkadiroğlu A, Sönmez T (2003) School choice: a mechanism design approach. American Economic Review 93(3):729–747
Abdulkadiroğlu A, Pathak P, Roth AE, Sonmez T (2006) Changing the Boston school choice mechanism. National Bureau of Economic Research, Cambridge
Abdulkadiroğlu A, Pathak P, Roth AE (2009) Strategy-proofness versus efficiency in matching with indifferences: redesigning the NYC high school match. American Economic Review 99(5):1954–1978
Abraham DJ, Irving RW, Kavitha T, Mehlhorn K (2007) Popular matchings. SIAM Journal on Computing 37(4):1030–1045
Bapna R, Goes P, Gupta A, Jin Y (2004) User heterogeneity and its impact on electronic auction market design: an empirical exploration. MIS Quarterly 28(1):21–43
Bichler M, Pikovsky A, Setzer T (2009) An analysis of design problems in combinatorial procurement auctions. Business & Information Systems Engineering 51(1):111–117
Braun S, Dwenger N, Kübler D (2007) Telling the truth may not pay off: an empirical study of centralised university admissions in Germany. IZA
Budish E (2011) The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. Journal of Political Economy 119(6):1061–1103
Budish E, Cantillon E (2012) The multi-unit assignment problem: theory and evidence from course allocation at Harvard. American Economic Review 102(5):2237–2271
Chen Y, Sönmez T (2006) School choice: an experimental study. Journal of Economic Theory 127(1):202–231
Ehlers L, Klaus B (2003) Coalitional strategy-proof and resource-monotonic solutions for multiple assignment problems. Social Choice and Welfare 21(2):265–280
Erdil A, Ergin H (2008) What’s the matter with tie-breaking? Improving efficiency in school choice. American Economic Review 98(3):669–689
Featherstone C, Niederle M (2008) Ex ante efficiency in school choice mechanisms: an experimental investigation. National Bureau of Economic Research, Cambridge
Gale D, Shapley LS (1962) College admissions and the stability of marriage. The American Mathematical Monthly 69(1):9–15
Gusfield D, Irving RW (1989) The stable marriage problem: structure and algorithms. MIT Press, Cambridge
Halldórsson MM, Irving RW, Iwama K, Manlove DF, Miyazaki S, Morita Y, Scott S (2003) Approximability results for stable marriage problems with ties. Theoretical Computer Science 306(1):431–447
Hamada K, Iwama K, Miyazaki S (2011) The hospitals/residents problem with quota lower bounds. In: Algorithms – ESA 2011 – 19th annual European symposium. Springer, Heidelberg, pp 180–191
Kesten O (2010) School choice with consent. The Quarterly Journal of Economics 125(3):1297–1348
Krishna A, Ünver MU (2005). A field experiment on course bidding at business schools. EconWPA
Krishna A, Ünver MU (2008) Research note: improving the efficiency of course bidding at business schools: field and laboratory studies. Marketing Science 27(2):262–282
Manlove D (2013) Algorithmics of matching under preferences. World Scientific, Singapore
Manlove DF, Irving RW, Iwama K, Miyazaki S, Morita Y (2002) Hard variants of stable marriage. Theoretical Computer Science 276(1):261–279
Milgrom P (2011) Critical issues in the practice of market design. Economic Inquiry 49(2):311–320
Othman A, Sandholm T, Budish E (2010) Finding approximate competitive equilibria: efficient and fair course allocation. In: Proc of 9th international conference on autonomous agents and multiagent systems, Toronto, vol 1, pp 873–880
Pápai S (2001) Strategyproof and nonbossy multiple assignments. Journal of Public Economic Theory 3(3):257–271
Roth AE (1982) The economics of matching: stability and incentives. Mathematics of Operations Research 7(4):617–628
Roth AE (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
Roth AE (2002) The economist as engineer: game theory, experimentation, and computation as tools for design economics. Econometrica 70(4):1341–1378
Shapley L, Scarf H (1974) On cores and indivisibility. Journal of Mathematical Economics 1(1):23–37
Sönmez T, Ünver MU (2010) Course bidding at business schools. International Economic Review 51(1):99–123
Ueda S, Fragiadakis D, Iwasaki A, Troyan P, Yokoo M (2012) Strategy-proof mechanisms for two-sided matching with minimum and maximum quotas. In: Proc of 11th international conference on autonomous agents and multiagent systems, Valencia, vol 3, pp 1327–1328
Varian HR (1976) Two problems in the theory of fairness. Journal of Public Economics 5(3):249–260
Weinhardt C, Holtmann C, Neumann D (2003) Market Engineering. WIRTSCHAFTSINFORMATIK 45(6):635–640
Westkamp A (2013) An analysis of the German university admissions system. Economic Theory 53(3):561–589