The Mathematical Sorting Hat

Introduction

The most well-known matching problem in recent popular culture is in J.K. Rowling's Harry Potter series [Rowling 1998]. Each year, roughly 40 new first-year students at Hogwarts School ofWitchcraft andWizardry are assigned to one of the residential Houses (Griffindor, Ravenclaw, Hufflepuff, and Slytherin). This duty is performed by the magical Sorting Hat, which considers each student in turn and determines the best match for that student among the four Houses. The Sorting Hat uses its magical perception to assign students to houses that best match their personalities. However, we also notice that the assignments split fairly evenly, with each House receiving about 5 girls and 5 boys. Perhaps this house distribution and gender balance reflects a secondary goal of the Sorting Hat.

Asimilar sorting occurs annually on college campuses across the United States. The past two decades have witnessed the rise of the first-year seminar, a curricular strategy to help students transition from high school to college [Hunter and Linder n.d.]. A seminar is a small course that emphasizes active learning, discussion, and exchange of ideas.

First-year seminars leverage the closeness of this format to introduce the paradigms and standards of higher education. First-year seminars at some institutions also strive to develop community within the classroom, the student body, and the institution as a whole, in part with a view to retaining students. Many colleges devote considerable effort in assigning students to these seminars, trying to createan immediatesense of belonging, just as the fictional Sorting Hat achieves at Hogwarts.

This paper describes the development and implementation of an automated procedure-the Mathematical Sorting Hat-for assigning first-year students to seminars, adopted at Macalester College in 2009. "The Hat" models the matching problem using a weighted bipartite graph that captures both student preferences and college constraints. We run the wellknown Hungarian algorithm to find a minimum-weight perfect matching of this graph. Such a matching corresponds to an optimal assignment of students to seminars.