Course allocation

From Wikipedia, the free encyclopedia

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". 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.
  2. ^ a b 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.
  3. ^ a b 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.
  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.
  5. ^ 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.
  6. ^ Pápai, Szilvia (2001). "Strategyproof and Nonbossy Multiple Assignments". Journal of Public Economic Theory. 3 (3): 257–271. doi:10.1111/1097-3923.00066. ISSN 1467-9779.
  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. JSTOR 41106560.
  8. ^ Hatfield, John William (2009-09-01). "Strategy-proof, efficient, and nonbossy quota allocations". Social Choice and Welfare. 33 (3): 505–515. doi:10.1007/s00355-009-0376-6. ISSN 1432-217X.
  9. ^ Sönmez, Tayfun; Ünver, M. Utku (2010). "Course Bidding at Business Schools*". International Economic Review. 51 (1): 99–123. doi:10.1111/j.1468-2354.2009.00572.x. ISSN 1468-2354.
  10. ^ "Tel-Aviv University registration instructions (in Hebrew)". 2020-06-15.
  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.
  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. AAMAS '10. Toronto, Canada: International Foundation for Autonomous Agents and Multiagent Systems: 873–880. ISBN 978-0-9826571-1-9.
  13. ^ a b 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.
  14. ^ Budish, Eric; Kessler, Judd B. (2016-07-25). "Can Market Participants Report their Preferences Accurately (Enough)?". Cite journal requires |journal= (help)
  15. ^ 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. SSRN 2579107. Cite journal requires |journal= (help)
  16. ^ 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.
  17. ^ 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.
  18. ^ Budish, Eric (2012-12-01). "Matching "versus" mechanism design". ACM SIGecom Exchanges. 11 (2): 4–15. doi: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". European Journal of Operational Research. 260 (1): 268–282. doi:10.1016/j.ejor.2016.12.011. ISSN 0377-2217.
  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.
Retrieved from ""