Course Allocation

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.

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.

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.

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.

Other variants are the quest draft and Pareto-improving draft.

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.

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.

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 and Tel-Aviv University.

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; Othman and Sandholm provided efficient computer implementations. The mechanism has been implemented in the Wharton Business School, replacing the previous bidding-based mechanism.

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. 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.

Other mechanisms

Other mechanisms for course allocation include fair random assignment, stable matching, and optimization based mechanisms.

References

{{Reflist

Fair item allocation
Higher education