Ties matter: improving efficiency in course allocation by introducing ties

Chen, Ning and Li, Mengling (2013): Ties matter: improving efficiency in course allocation by introducing ties.

Abstract

We study the course allocation system at Nanyang Technological University, where students submit strict preferences for courses and courses have implicit preferences for students. This formulates a many-to-many matching problem. We show the inefficiencies of the current mechanism and propose new competing mechanisms called Pareto-improving draft and dictatorship mechanisms, which introduce ties into students' preferences. Our mechanisms generate (group) stable and Pareto-efficient allocations, and the dictatorship mechanism can be implemented truthfully. Simulations on real data show that introducing ties into students' preferences can significantly improve efficiency, and the draft mechanism outperforms the dictatorship mechanism despite that the former is non-strategyproof.

• Item Type: MPRA Paper
• Language: English
• Keywords: matching, many-to-many, Pareto efficiency, stability, strategyproof
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C78 - Bargaining Theory ; Matching Theory; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D82 - Asymmetric and Private Information ; Mechanism Design; I - Health, Education, and Welfare > I2 - Education and Research Institutions > I23 - Higher Education ; Research Institutions

References

Abdulkadiroglu, Atila, Parag A. Pathak, and Alvin E. Roth. 2009. “Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match.” American Economic Review 99 (5): 1954-78.

Abdulkadiroglu, Atila, and Tayfun Sonmez. 2003. “School Choice: A Mechanism Design Approach.” American Economic Review 93 (3): 729-47.

Alkan, Ahmet. 2001. “On Preferences over Subsets and the Lattice Structure of Stable Matchings.” Review of Economic Design 6 (1): 99-111.

Alkan, Ahmet. 2002. “A Class of Multipartner Matching Models with a Strong Lattice Structure.” Economic Theory 19 (4): 737-46.

Blair, Charles. 1988. “The Lattice Structure of the Set of Stable Matchings with Multiple Partners.” Mathematics of Operations Research: 13(4), 619-28.

Budish, Eric. 2012. “Matching ‘versus’ Mechanism Design.” ACM SIGecom Exchanges 11 (2): 4-15.

Budish, Eric, and Estelle Cantillon. 2012. “The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard.” American Economic Review 102 (5): 2237-71.

Chen, Ning, and Arpita Ghosh. 2011. “A Market Clearing Solution for Social Lending.” In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, 152-57.

Cripps, Martin W., and Jeroen M. Swinkels. 2006. “Efficiency of Large Double Auctions.” Econometrica: 74 (1), 47-92.

Echenique, Federico, and Jorge Oviedo. 2006. “A Theory of Stability in Many-to-Many Matching Markets.” Theoretical Economics: 1 (2), 233-73.

Erdil, Aytek, and Haluk Ergin. 2006. “Two-Sided Matching with Indifferences.” Manuscript.

Erdil, Aytek, and Haluk Ergin. 2008. “What’s the Matter with Tie-breaking? Improving Efficiency in School Choice.” American Economic Review: 98 (3), 669-89.

Gale, David, and Lloyd S. Shapley. 1962. “College Admissions and the Stability of Marriage.” American Mathematical Monthly: 69 (1), 9-15.

Fudenberg, Drew, Markus M. Mobius, and Adam Szeidl. 2007. “Existence of Equilibria in Large Double Auctions.” Journal of Economic Theory: 133 (1), 550-67.

Immorlica, Nicole, and Mohammad Mahdian. 2005. “Marriage, Honesty, and Stability.” In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 53-62.

Kominers, Scott D., Mike Ruberry, and Jonathan Ullman. 2010. “Course Allocation by Proxy Auction.” In Proceedings of the 6th International Conference on Internet and Network Economics, 551-58.

Kojima, Fuhito, and Mihai Manea. 2010. “Incentives in the Probablistic Serial Mechanism.” Journal of Economic Theory: 145 (1), 106-23.

Kojima, Fuhito, and Parag A. Pathak. 2009. “Incentives and Stability in Large Two-Sided Matching Markets.” American Economic Review: 99 (3), 608-27.

Krishna, Aradhna, and M. Utku Unver. 2008. “Improving the Efficiency of Course Bidding at Business Schools: Field and Laboratory Studies.” Marketing Science: 27 (2), 262-82.

Martinez, Ruth, Jordi Masso, Alejandro Neme, and Jorge Oviedo. 2004. “An Algorithm to Compute the Full Set of Many-to-Many Stable Matchings.” Mathematical Social Sciences 47 (2): 187-210.

Roberts, Donald J., and Andrew Postlewaite. 1976. “The Incentives for Price-Taking Behavior in Large Exchange Economies.” Econometirca 44 (1): 115-27.

Roth, Alvin E.. 1984. “Stability and Polarization of Interests in Job Matching.” Econometrica 52 (1): 47-57.

Roth, Alvin E., and Elliott Peranson. 1999. “The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design.” American Economic Review 89 (4): 748-80.

Roth, Alvin E., and Marilda A. Oliveira Sotomayor. 1990. “Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis.” New York: Cambridge University Press.

Roth, Alvin E., and John H Vande Vate. 1990. “Random Paths to Stability in Two-Sided Matching.” Econometrica 58 (6): 1475-80.

Sonmez, Tayfun, and M. Utku Unver. 2010. “Course Bidding at Business Schools.” International Economic Review 51 (1): 99-123.

Sonmez, Tayfun, and M. Utku Unver. 2011. “Matching, Allocation, and Exchange of Discrete Resources.” In Handbook of Social Economics, edited by J. Benhabib, A. Bisin, and M. Jackson, 1A: 781-852. North-Holland.

Sotomayor, Marilda A. Oliveira. 1999. “Three Remarks on the Many-to-Many Stable Matching Problem.” Mathematical Social Sciences 38 (1): 55-70.

Sotomayor, Marilda A. Oliveira. 2011. “The Pareto-Stability Concept is a Natural Solution Concept for Discrete Matching Markets with Indifferences.” International Journal of Game Theory 40 (3): 631-44.