Course allocation
 | This article is actively undergoing a major edit for a little while. To help avoid edit conflicts, please do not edit this page while this message is displayed. This page was last edited at 13:19, 13 November 2020 (UTC) (4 years ago) – this estimate is cached, . Please remove this template if this page hasn't been edited for a significant time. If you are the editor who added this template, please be sure to remove it or replace it with {{Under construction}} between editing sessions. |
Course allocation is the problem of allocating seats in university courses among students. Many universities impose an upper bound on the number of students allowed to register to each course, in order to ensure that the teachers can give sufficient attention to each individual student. Since the demand for some courses is higher than the upper bound, a natural question is which students should be allowed to register to each course.
Many institutions allow students to register on a first come, first served basis. However, this may lead to unfair outcomes: a student who happens to be near his/her computer when registration starts can manage to register to all the most wanted courses, while a student who comes too late might find that all wanted courses are already full and be able to register only to less-wanted courses. To mitigate this unfairness, many institutions use more sophisticated allocation mechanisms.[1]
Draft mechanisms
In a draft mechanism (also called round-robin), students take turns in picking courses from the set of courses with available seats. The choosing order is random at the first round, and then reverses in subsequent rounds. In practice, students do not have to pick by rounds: they can just report their preferences over individual courses to a computer, and the computer chooses courses for them one at a time. This procedure has been used, for example, in the Harvard Business School since the mid-1990s.[2]: 3
One problem with the draft procedure is that it is not strategyproof: students may potentially get better courses by manipulating their reported preferences. Moreover, the draft is easy to manipulate: students should overreport how much they like the more wanted courses, and underreport how much they like the less wanted courses. Results from a field study at Harvard show that students indeed manipulate their preferences, and this manipulation leads to allocations that are not Pareto efficient and have a low social welfare.[2]: 4
A variant of draft that can potentially reduce the inefficiencies due to manipulation is the proxy draft. In this mechanism, the students still report their preferences to a computer, but this time, the computer manipulates the preferences for them in an optimal way, and then plays the original draft. This procedure reduces the welfare loss due to mistakes in manipulation and lack of knowledge of the position in the choosing sequence.[2]: 5
Auction based mechanisms
[4][5][6][7][8][9][10][11][12][13][14][15]
References
- ^ Kominers, Scott Duke; Ruberry, Mike; Ullman, Jonathan (2010). Saberi, Amin (ed.). "Course Allocation by Proxy Auction". Internet and Network Economics. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 551–558. doi:10.1007/978-3-642-17572-5_49. ISBN 978-3-642-17572-5.
- ^ a b c Budish, Eric; Cantillon, Estelle (2012-08-01). "The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard". American Economic Review. 102 (5): 2237–2271. doi:10.1257/aer.102.5.2237. ISSN 0002-8282.
- ^ Othman, Abraham; Sandholm, Tuomas; Budish, Eric (2010-05-10). "Finding approximate competitive equilibria: efficient and fair course allocation". Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1. AAMAS '10. Toronto, Canada: International Foundation for Autonomous Agents and Multiagent Systems: 873–880. doi:10.5555/1838206.1838323. ISBN 978-0-9826571-1-9.
{{cite journal}}: Check|doi=value (help) - ^ Budish, Eric; Cachon, Gérard P.; Kessler, Judd B.; Othman, Abraham (2016-10-28). "Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation". Operations Research. 65 (2): 314–336. doi:10.1287/opre.2016.1544. ISSN 0030-364X.
- ^ Budish, Eric; Che, Yeon-Koo; Kojima, Fuhito; Milgrom, Paul (2013-04-01). "Designing Random Allocation Mechanisms: Theory and Applications". American Economic Review. 103 (2): 585–623. doi:10.1257/aer.103.2.585. ISSN 0002-8282.
- ^ Budish, Eric; Kessler, Judd B. (2016-07-25). "Can Market Participants Report their Preferences Accurately (Enough)?".
{{cite journal}}: Cite journal requires|journal=(help) - ^ Budish, Eric (2011-12-01). "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes". Journal of Political Economy. 119 (6): 1061–1103. doi:10.1086/664613. ISSN 0022-3808.
- ^ Budish, Eric; Cantillon, Estelle (2007). Cramton, Peter; Müller, Rudolf; Tardos, Eva; Tennenholtz, Moshe (eds.). "Strategic Behavior in Multi-unit Assignment Problems: Theory and Evidence from Course Allocations". Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings. Dagstuhl, Germany: Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany.
- ^ Budish, Eric B.; Kessler, Judd B. (2017-11-12). "Can Agents 'Report Their Types'? An Experiment that Changed the Course Allocation Mechanism at Wharton". Rochester, NY.
{{cite journal}}: Cite journal requires|journal=(help) - ^ Budish, Eric (2012-12-01). "Matching "versus" mechanism design". ACM SIGecom Exchanges. 11 (2): 4–15. doi:10.1145/2509002.2509005.
- ^ Hoshino, Richard; Raible-Clark, Caleb (2014-07-27). "The quest draft: an automated course allocation algorithm". Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. AAAI'14. Québec City, Québec, Canada: AAAI Press: 2906–2913. doi:10.5555/2892753.2892954.
{{cite journal}}: Check|doi=value (help) - ^ Diebold, Franz; Aziz, Haris; Bichler, Martin; Matthes, Florian; Schneider, Alexander (2014-04-01). "Course Allocation via Stable Matching". Business & Information Systems Engineering. 6 (2): 97–110. doi:10.1007/s12599-014-0316-6. ISSN 1867-0202.
- ^ Diebold, Franz; Bichler, Martin (2017-07-01). "Matching with indifferences: A comparison of algorithms in the context of course allocation". European Journal of Operational Research. 260 (1): 268–282. doi:10.1016/j.ejor.2016.12.011. ISSN 0377-2217.
- ^ Atef Yekta, Hoda; Day, Robert (2020-01-13). "Optimization-based Mechanisms for the Course Allocation Problem". INFORMS Journal on Computing. 32 (3): 641–660. doi:10.1287/ijoc.2018.0849. ISSN 1091-9856.
- ^ Li, Mengling (2020-10-01). "Ties matter: Improving efficiency in course allocation by allowing ties". Journal of Economic Behavior & Organization. 178: 354–384. doi:10.1016/j.jebo.2020.07.030. ISSN 0167-2681.