Social:Course allocation

From HandWiki
Revision as of 09:15, 11 January 2022 by imported>Gametune (fixing)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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]

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]

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.[3]:5

Other variants are the quest draft[4] and Pareto-improving draft.[5]

Random serial dictatorship

Economic theorists have proved that random serial dictatorship (RSD) is the only strategyproof mechanism that is ex-post Pareto-efficient and satisfies some other natural properties. Based on this theoretical fact, they suggested to use it in practice for course allocation.[6][7][8]

However, field experiments have shown that RSD performs worse than the manipulable draft mechanism in natural measures such as the number of students who get their first choice, the average rank of courses per student.[3]:5

Bidding mechanisms

In a bidding mechanism, each student is given a fixed amount of some unreal money, and can allocate this "money" among courses he/she wishes to take. The bids of all students on all courses are ordered from high to low and processed one at a time. Each bid in turn is honored if and only if the student has not filled his/her schedule and the course has available seats. Similar mechanisms are used in the Ross School of Business, Columbia Business School, Haas School of Business, Kellogg School of Management, Princeton University, Yale School of Management[9] and Tel-Aviv University.[10]

Equilibrium mechanisms

In an equilibrium mechanism, each student is allowed to rank all the feasible schedules of courses (i.e., all subsets of courses in which no two courses overlap in time, no two courses teach the same material in different times, etc.) Then, a computer finds a competitive equilibrium from equal incomes in this market. Since an exact competitive equilibrium may not exist, a mechanism often used in practice is the Approximate Competitive Equilibrium from Equal Incomes (A-CEEI). Eric Budish developed the theory;[11] Othman and Sandholm[12] provided efficient computer implementations. The mechanism has been implemented in the Wharton Business School, replacing the previous bidding-based mechanism.[13]

The need to report a ranking over schedules is a major challenge in implementing such algorithms, since the number of feasible schedules might be very large.[14][15] Overcoming this challenge requires to design a simple language that allows students to describe their preferences in a reasonable time. The language developed at Wharton allows students to specify a utility for each individual course, and an "adjustment value" for each pair of courses. The utility of each pair is the sum of utilities of the individual courses, plus the adjustment value. Zero / positive / negative adjustment values correspond to courses that are independent goods / complementary goods / substitute goods respectively. In addition, some specific combinations of courses (e.g. those that are given at the same time or have the same content) are specifically disallowed. While this language does not allow to express every possible ranking on schedules, it is sufficient in practice.[13]

Other mechanisms

Other mechanisms for course allocation include fair random assignment,[16] stable matching,[17][18][19] and optimization based mechanisms.[20]

References

  1. ↑ Kominers, Scott Duke; Ruberry, Mike; Ullman, Jonathan (2010). Saberi, Amin. ed. "Course Allocation by Proxy Auction" (in en). Internet and Network Economics. Lecture Notes in Computer Science (Berlin, Heidelberg: Springer) 6484: 551–558. doi:10.1007/978-3-642-17572-5_49. ISBN 978-3-642-17572-5. https://link.springer.com/chapter/10.1007/978-3-642-17572-5_49. 
  2. ↑ 2.0 2.1 Budish, Eric; Cantillon, Estelle (2007). Cramton, Peter; Müller, Rudolf; Tardos, Eva et al.. 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). http://drops.dagstuhl.de/opus/volltexte/2007/1154. 
  3. ↑ 3.0 3.1 Budish, Eric; Cantillon, Estelle (2012-08-01). "The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard" (in en). American Economic Review 102 (5): 2237–2271. doi:10.1257/aer.102.5.2237. ISSN 0002-8282. https://www.aeaweb.org/articles?id=10.1257/aer.102.5.2237. 
  4. ↑ 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. https://dl.acm.org/doi/abs/10.5555/2892753.2892954. 
  5. ↑ Li, Mengling (2020-10-01). "Ties matter: Improving efficiency in course allocation by allowing ties" (in en). Journal of Economic Behavior & Organization 178: 354–384. doi:10.1016/j.jebo.2020.07.030. ISSN 0167-2681. http://www.sciencedirect.com/science/article/pii/S0167268120302523. 
  6. ↑ Pápai, Szilvia (2001). "Strategyproof and Nonbossy Multiple Assignments" (in en). Journal of Public Economic Theory 3 (3): 257–271. doi:10.1111/1097-3923.00066. ISSN 1467-9779. https://www.onlinelibrary.wiley.com/doi/abs/10.1111/1097-3923.00066. 
  7. ↑ Ehlers, Lars; Klaus, Bettina (2003). "Coalitional strategy-proof and resource-monotonic solutions for multiple assignment problems". Social Choice and Welfare 21 (2): 265–280. doi:10.1007/s00355-003-0259-1. ISSN 0176-1714. https://www.jstor.org/stable/41106560. 
  8. ↑ Hatfield, John William (2009-09-01). "Strategy-proof, efficient, and nonbossy quota allocations" (in en). Social Choice and Welfare 33 (3): 505–515. doi:10.1007/s00355-009-0376-6. ISSN 1432-217X. https://doi.org/10.1007/s00355-009-0376-6. 
  9. ↑ Sönmez, Tayfun; Ünver, M. Utku (2010). "Course Bidding at Business Schools*" (in en). International Economic Review 51 (1): 99–123. doi:10.1111/j.1468-2354.2009.00572.x. ISSN 1468-2354. https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1468-2354.2009.00572.x. 
  10. ↑ "Tel-Aviv University registration instructions (in Hebrew)". 2020-06-15. https://education.tau.ac.il/rishum_toar_rishon. 
  11. ↑ 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. https://www.journals.uchicago.edu/doi/full/10.1086/664613. 
  12. ↑ 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. ISBN 978-0-9826571-1-9. https://dl.acm.org/doi/abs/10.5555/1838206.1838323. 
  13. ↑ 13.0 13.1 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. https://pubsonline.informs.org/doi/abs/10.1287/opre.2016.1544. 
  14. ↑ Budish, Eric; Kessler, Judd B. (2016-07-25) (in en). Can Market Participants Report their Preferences Accurately (Enough)?. https://www.nber.org/papers/w22448. 
  15. ↑ Budish, Eric B.; Kessler, Judd B. (2017-11-12) (in en). Can Agents 'Report Their Types'? An Experiment that Changed the Course Allocation Mechanism at Wharton. Rochester, NY. https://papers.ssrn.com/abstract=2579107. 
  16. ↑ Budish, Eric; Che, Yeon-Koo; Kojima, Fuhito; Milgrom, Paul (2013-04-01). "Designing Random Allocation Mechanisms: Theory and Applications" (in en). American Economic Review 103 (2): 585–623. doi:10.1257/aer.103.2.585. ISSN 0002-8282. https://www.aeaweb.org/articles?id=10.1257/aer.103.2.585. 
  17. ↑ Diebold, Franz; Aziz, Haris; Bichler, Martin; Matthes, Florian; Schneider, Alexander (2014-04-01). "Course Allocation via Stable Matching" (in en). Business & Information Systems Engineering 6 (2): 97–110. doi:10.1007/s12599-014-0316-6. ISSN 1867-0202. https://doi.org/10.1007/s12599-014-0316-6. 
  18. ↑ Budish, Eric (2012-12-01). "Matching "versus" mechanism design". ACM SIGecom Exchanges 11 (2): 4–15. doi:10.1145/2509002.2509005. https://doi.org/10.1145/2509002.2509005. 
  19. ↑ Diebold, Franz; Bichler, Martin (2017-07-01). "Matching with indifferences: A comparison of algorithms in the context of course allocation" (in en). European Journal of Operational Research 260 (1): 268–282. doi:10.1016/j.ejor.2016.12.011. ISSN 0377-2217. http://www.sciencedirect.com/science/article/pii/S037722171631030X. 
  20. ↑ 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. https://pubsonline.informs.org/doi/abs/10.1287/ijoc.2018.0849. 




Retrieved from "https://handwiki.org/wiki/index.php?title=Social:Course_allocation&oldid=893880"