The Quest Draft: An Automated Course Allocation Algorithm

Richard Hoshino, Caleb Raible-ClarkAAAI 2014 · DOI

TL;DR

This paper introduces the "Quest Draft," a novel four-part AI algorithm designed to automate course allocation at a small liberal arts university. It addresses the inherent complexities and fairness issues of assigning students to limited course seats, moving beyond traditional first-come-first-served methods to a more transparent, equitable, and effective system.

What Problem Does This Paper Address?

Universities face a perennial challenge in allocating limited course seats to students, especially in popular courses. This is particularly acute at institutions like Quest University, which has a unique block-based academic calendar (one course per month) and a student-designed curriculum, leading to highly individualized course needs. Traditional methods, such as first-come-first-served (dubbed "Fastest-Finger" Serial Dictatorship), are prone to unfairness, welfare loss, and student anxiety, as they disproportionately reward students with faster internet connections rather than genuine preference. Existing auction-based mechanisms, while theoretically sound, can be complex and prone to manipulation. The paper aims to create a mechanism that is transparent, impartial, and effective, maximizing overall student welfare.

Methods

The Quest Draft is a four-part algorithm:

  1. Cyclically-Shifted Snake-Order Draft: This is a novel draft order designed to distribute picks more equitably across students and rounds. Unlike a standard snake draft, it cyclically shifts the order to ensure each student's picks are spread across different "quartiles" of the draft. This aims to prevent situations where some students get all their top choices while others get none.
  2. Caveats and Backtracking: To accommodate individual student constraints, the system allows for "caveats." These include "at-most" conditions (limiting the number of courses from a specific set) and "if-and-only-if" conditions (requiring two courses to be taken together or not at all). A backtracking mechanism is employed to handle violations of these caveats, ensuring that if a student cannot get a required course, the system reverts to their previous selection and re-evaluates.
  3. Pairwise-Swapping Algorithm: This heuristic algorithm optimizes professor teaching schedules by iteratively swapping course months. The goal is to minimize "shafted" students (those left without any available course in a given month), particularly addressing issues with the availability of foundational courses.
  4. Strategic Computer Proxy (Proposed but not implemented): The paper discusses a proposed "perfect-information proxy" that would strategically draft courses on behalf of each student, aiming to maximize their utility. This proxy would use a geometric utility function and a backtracking mechanism to ensure optimal outcomes. However, this part was ultimately rejected due to student and faculty concerns about complexity and perceived unfairness.

Datasets

Not discussed in the paper. The paper describes the implementation at Quest University, which involved student-provided ranked wishlists of courses.

Key Insights and Ideas

  • The "Fastest-Finger" is Fundamentally Unfair: The paper clearly demonstrates that simple first-come-first-served registration systems are not only unfair but also lead to welfare loss, as they don't reflect true student preferences.
  • Equitable Draft Order Matters: The development of the "Cyclically-Shifted Snake-Order Draft" is a key innovation. It moves beyond simple randomization or linear ordering to ensure a more balanced distribution of opportunities for students throughout the draft.
  • Caveats are Crucial for Real-World Adoption: The inclusion of "caveats" (constraints) is vital for making an automated system practical. Students need to express complex preferences and requirements, and the system must accommodate them without breaking.
  • Backtracking is a Robust Solution for Constraints: The backtracking mechanism, while computationally more intensive, provides a necessary safety net to handle constraint violations, ensuring that the system doesn't leave students in impossible situations.
  • Strategic Play is a Persistent Challenge: The paper highlights that even sophisticated allocation mechanisms can be subject to strategic manipulation, leading to ex-post Pareto inefficiencies. The proposed proxy aimed to combat this but was deemed too complex for the target audience.

Key Results

  • The Quest Draft replaced the "Fastest-Finger" Serial Dictatorship, significantly reducing student anxiety and improving perceived fairness.
  • The Cyclically-Shifted Snake-Order Draft resulted in an average score (sum of preference rankings) of 4.84, compared to 5.27 for the Random Serial Dictatorship.
  • 98% of students in the CSSOD received at least three of their first-choice courses, compared to 81% with RSD.
  • The automated draft process, including caveats, ran in a remarkably short 1.6 seconds for 550 students and 2200 picks.
  • The pairwise-swapping algorithm led to a significant reduction in "shafted" students, particularly for foundational courses, with 18 first-year students no longer being shafted.
  • In the first implementation, 100% of fourth-year students got their first-choice course in all four months, with average scores improving for all year levels compared to previous systems.

Limitations and Future Work

  • Strategic Proxy Rejection: The most advanced part of the proposed algorithm, the strategic computer proxy, was not implemented due to concerns about complexity and perceived unfairness among students and faculty. This leaves open the possibility of strategic manipulation, although the implemented system is significantly more robust than previous methods.
  • Manual Data Entry: A significant bottleneck identified is the manual input of student-to-course assignments into the university's record-management system, which is time-consuming and prone to errors. Future work involves developing a more efficient upload process.
  • Utility Function Flexibility: The paper acknowledges that the geometric utility function used for the proxy might not be universally applicable. Future work could involve allowing students to specify different utility functions or developing a mechanism to infer them.
  • AI Collaboration: The authors express a desire for continued collaboration with AI researchers to develop even more effective and efficient course allocation systems, particularly focusing on welfare-maximizing strategic proxies.

Summary updated

BibTeX
@inproceedings{hoshino2014quest,
  author = {Richard Hoshino and Caleb Raible-Clark},
  title = {{The Quest Draft: An Automated Course Allocation Algorithm}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i2.19025},
}
Figure