Course allocation

Last updated

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.

Contents

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] An important advantage of draft mechanisms is that they are relatively fair, in the sense that all students get their t-th course before any student receives his (t+1)-th course.

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]

Another problem with draft is that it only considers the ordinal ranking of the students, and ignores their cardinal valuations. This may lead to inefficiencies. For example, suppose the first student in the random order slightly prefers course A to course B, whereas the second student strongly prefers A to B. The draft mechanism will allocate A to the first student, but it would have been more efficient (at least from a utilitarian perspective) to allocate A to the second student.

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]

Bidding mechanisms have several disadvantages. First, just like first-price auctions, they are not strategyproof. This may cause students to spend a lot of effort on deciding how much to bid on each course, by guessing how much other students would bid on these courses. Second, the outcomes may be inefficient. The students' bids have two roles: inferring student preferences, and determining who have bigger claims on seats. These two roles may be in conflict, and this may lead to inefficient outcomes. [11] Third, the outcome of a bidding mechanism may be very unfair: some students may receive no desired course, while others receive all their desired courses. [12]

Kominers et al [1] introduce a proxy bidding mechanism, which aims to computes high-quality manipulations in behalf of each student. According to their simulations, this mechanism decreases the incentives to manipulate, and hence may improve efficiency.

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; [12] Othman and Sandholm [13] provided efficient computer implementations. Budish, Cachon, Kessler and Othman improved the implementation; their implementation, called CourseMatch, has been implemented in the Wharton Business School, replacing the previous bidding-based mechanism. [14] It has been commercially implemented by Cognomos. [15] Recently, Budish, Gao, Othman, Rubinstein and Zhang presented a new algorithm for finding an approximate CEEI, which is substantially faster, attains zero clearing error on all practical instances, and has better incentive properties than the previous algorithm. [16]

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. [17] [18] 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. [14]

Soumalis, Zamanlooy, Weissteiner and Seuken [19] present a method for using machine learning to learn and correct errors in the students' report.

A major problem with A-CEEI is that it is very computationally-intensive, as it needs to search through the space of price-vectors, and for each price-vector, it should compute the optimal bundles of many students.

Combining draft with bidding

Atef-Yekta and Day [20] aim to imrpove the efficiency of draft mechanisms by incorporating elements of bidding, while still keeping its round-by-round structure that enhances the fairness. They present several heuristic algorithms:

They compared their five algorithms with the bidding and draft mechanisms on 100 sample markets, each having 900 students with a capacity of 6 courses. There were 112 course-sections, some of them belong to the same course, and some of them overlap (so they cannot be taken together). The course capacities were drawn at random from discrete uniform distributions. The characteristics are similar to those in the Harvard Business School. They evaluated the algorithms using several metrics:

In the binary and ordinal aspects, OC scored best on both efficiency and fairness; then SP-O and TTC-O; then Draft, SP and TTC; and Bidding scored worst. In the cardinal aspect, OC and BPM were the most efficient, but SP-O and TTC-O were the most fair. Draft was very inefficient, and BPM was very unfair, SP and TTC were moderately efficient and moderately fair.

As no algorithm is strategyproof, they studied the incentives for strategic manipulation in each algorithm, that is, how much a student can gain by manipulation. Their experiments show that, in the Bidding mechanism, the gain to manipulators is highest, and the harm from manipulation to truthful students is highest. The lowest gain+harm was found in TTC-O, SP-O, and Draft.

Mechanisms based on two-sided matching

Most works assume that only the students have preferences over the courses, whereas the courses do not have preferences; that is, the market is one-sided. However, some works assume that courses may also have preferences, and therefore the market is two-sided. [21] The main goal in a two-sided market is finding a stable matching, and the main algorithm is the Gale-Shapley algorithm (deferred-acceptance, DA).

Diebold, Aziz, Bichler, Matthes and Schneider [22] compare two mechanisms: student-optimal DA, and efficiency-adjusted DA. They also survey recent extensions regarding assignment of schedules of courses, rather than individual courses. They report a field experiment showing the benefits of stable matching mechanisms.

Diebold and Bichler [23] compare various mechanisms for two-sided matching on course-allocation information.

Krishna and Unver [24] and Sonmez and Unver [9] consider a one-sided market, but they still use DA, as follows. They ask each student to report both a cardinal value for each course, and an ordinal ranking of the courses; these two reports need not be consistent. When running DA, the preferences of the students are determined by their ordinal rankings, and the preferences of the courses are determined by the students' cardinal values. The rationale is that a course "prefers" to accept a student who wants it more. Like in DA algorithm, each student "proposes" to the course ranked the highest in his ordinal ranking; the over-demanded courses then order the students according to their cardinal values, and reject the lowest ones. They report that, based on theory and field experiments, this scheme improves the efficiency of the allocation. However, reporting two inconsistent sets of preferences may increase the incentive problems. Additionally, the algorithm has no fairness guarantees.

Other mechanisms

Other mechanisms for course allocation use fair random assignment. [25]

Related Research Articles

In social choice theory, a dictatorship mechanism is a rule by which, among all possible alternatives, the results of voting mirror a single pre-determined person's preferences, without consideration of the other voters. Dictatorship by itself is not considered a good mechanism in practice, but it is theoretically important: by Arrow's impossibility theorem, when there are at least three alternatives, dictatorship is the only ranked voting electoral system that satisfies unrestricted domain, Pareto efficiency, and independence of irrelevant alternatives. Similarly, by Gibbard's theorem, when there are at least three alternatives, dictatorship is the only strategyproof rule.

<span class="mw-page-title-main">Market design</span>

Market design is a practical methodology for creation of markets of certain properties, which is partially based on mechanism design. In some markets, prices may be used to induce the desired outcomes — these markets are the study of auction theory. In other markets, prices may not be used — these markets are the study of matching theory.

<span class="mw-page-title-main">Arunava Sen</span> Indian researcher and teacher

Arunava Sen is a professor of economics at the Indian Statistical Institute. He works on Game Theory, Social Choice Theory, Mechanism Design, Voting and Auctions.

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among n partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency.

Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.

Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:

Top trading cycle (TTC) is an algorithm for trading indivisible items without using money. It was developed by David Gale and published by Herbert Scarf and Lloyd Shapley.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.

Fair random assignment is a kind of a fair division problem.

Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people.

A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).

Various experiments have been made to evaluate various procedures for fair division, the problem of dividing resources among several people. These include case studies, computerized simulations, and lab experiments.

Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.

When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as maximin-share fairness (MMS), envy-freeness up to one item (EF1), proportionality up to one item (PROP1), and equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then.

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.

Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.

Budget-proposal aggregation (BPA) is a problem in social choice theory. A group has to decide on how to distribute its budget among several issues. Each group-member has a different idea about what the ideal budget-distribution should be. The problem is how to aggregate the different opinions into a single budget-distribution program.

Donor coordination is a problem in social choice. There are several donors, each of whom wants to donate some money. Each donor supports a different set of targets. The goal is to distribute the total donated amount among the various targets in a way that respects the donors' preferences.

References

  1. 1 2 Kominers, Scott Duke; Ruberry, Mike; Ullman, Jonathan (2010). "Course Allocation by Proxy Auction". In Saberi, Amin (ed.). Internet and Network Economics. Lecture Notes in Computer Science. Vol. 6484. Berlin, Heidelberg: Springer. pp. 551–558. doi:10.1007/978-3-642-17572-5_49. ISBN   978-3-642-17572-5.
  2. 1 2 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. 7271: 1. doi:10.4230/DagSemProc.07271.15.
  3. 1 2 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. S2CID   5132273.
  4. ↑ Hoshino, Richard; Raible-Clark, Caleb (2014-07-27). "The Quest Draft: An Automated Course Allocation Algorithm". Proceedings of the AAAI Conference on Artificial Intelligence. AAAI'14. Québec City, Québec, Canada: AAAI Press. 28 (2): 2906–2913. doi:10.1609/aaai.v28i2.19025. S2CID   14197118.
  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. S2CID   225044860.
  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. S2CID   8455104.
  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. S2CID   7713320.
  9. 1 2 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. S2CID   154573224.
  10. ↑ "Tel-Aviv University registration instructions (in Hebrew)". 2020-06-15.
  11. ↑ Krishna, Aradhna; Ünver, M. Utku (2008-03-01). "Research Note—Improving the Efficiency of Course Bidding at Business Schools: Field and Laboratory Studies". Marketing Science. 27 (2): 262–282. doi:10.1287/mksc.1070.0297. ISSN   0732-2399.
  12. 1 2 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. S2CID   1161325.
  13. ↑ 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.
  14. 1 2 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.
  15. ↑ "Course Match is the fairest course registration platform in higher education". www.cognomos.com. Retrieved 2023-06-14.
  16. ↑ Budish, Eric; Gao, Ruiquan; Othman, Abraham; Rubinstein, Aviad; Zhang, Qianfan (2023). "Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)". arXiv: 2305.11406 [cs.GT].
  17. ↑ Budish, Eric; Kessler, Judd B. (2016-07-25). "Can Market Participants Report their Preferences Accurately (Enough)?". Working Paper Series. doi:10.3386/w22448.{{cite journal}}: Cite journal requires |journal= (help)
  18. ↑ 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. doi:10.2139/ssrn.2579107. S2CID   109825489. SSRN   2579107.{{cite journal}}: Cite journal requires |journal= (help)
  19. ↑ Soumalias, Ermis; Zamanlooy, Behnoosh; Weissteiner, Jakob; Seuken, Sven (2022). "Machine Learning-powered Course Allocation". arXiv: 2210.00954 [cs.GT].
  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. S2CID   213466767.
  21. ↑ Budish, Eric (2012-12-01). "Matching "versus" mechanism design". ACM SIGecom Exchanges. 11 (2): 4–15. doi:10.1145/2509002.2509005. S2CID   5938165.
  22. ↑ 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. S2CID   493430.
  23. ↑ 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.
  24. ↑ Kominers, Scott Duke; Ruberry, Mike; Ullman, Jonathan (2010). "Course Allocation by Proxy Auction". In Saberi, Amin (ed.). Internet and Network Economics. Lecture Notes in Computer Science. Vol. 6484. Berlin, Heidelberg: Springer. pp. 551–558. doi:10.1007/978-3-642-17572-5_49. ISBN   978-3-642-17572-5.
  25. ↑ 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.