The Problem
This semester, I am responsible for leading discussion sections for an undergraduate cognitive neuroscience course. These sections consist of ~30-40 students at a time, and are in addition to two weekly faculty lectures attended by the entire class. Smaller groups give students a chance to interact with the course material more directly than is possible during the lectures, which are given to an audience of well over 100 people.
As a Graduate Student Instructor (GSI), one of my other responsibilities is coordinating with students who want or need to change which of the six discussion sections they attend (3 on Tuesday, 3 on Thursday). Requests to change section are often due to time conflicts with other classes. As instructors, we don’t care which students end up in each section, just that the class numbers are balanced and do not exceed the pre-set class size.
While we initially asked the students to work out swaps amongst themselves, it quickly became apparent that this would fail to resolve most of the conflicts. In a perfect world, every student seeking to switch out of one section and into another would be matched with another student seeking so make the opposite switch, resulting in everyone getting their desired discussion section. In this course, that kind of bi-directional swap was only possible for one pair of students, leaving 8 people stuck in discussion sections that don’t work for them.
The table below contains all requested discussion section changes. The only possible pairwise swap is between students H and I.
Being a nice guy, I started thinking about the swap requests for the remaining students to see if I could figure out a multi-person swap solution. After a few minutes, I realized that this was actually quite an interesting problem, and one that I’m sure others have tried to solve before. So I went online and did some research.
Research on Stable Matching and Optimal Assignment
I’m completely new to this literature, but as best I can tell this student section swapping problem appears to be at least somewhat analogous to a sort of Stable Matching or Assignment problem in which multiple entities must be optimally assigned or matched based on their preferences. Examples of other problems in this class include matching medical residents with hospitals, assigning roommates to multi-person rooms, and matching organ donors to recipients. These real-world problems can quickly become incredibly complex, especially if agents aren’t honest about their true preferences, and their outcomes can have major personal or economic consequences. In fact, these questions are so ubiquitous and important that the 2012 Nobel Prize in Economics was awarded to Alvin Ross and Lloyd Shapley for their work in this area. The Royal Swedish Academy of Sciences has a fantastic short summary of their work.
Our situation is a bit different from all of the examples I’ve seen in the literature, insofar as each discussion section can hold a limited number of students (but more than 1), and there is no preference as to which students end up in each section (other than the preference expressed by the student). Further, even though there are pre-set limits on class size, as instructors we may choose to make an exception and allow an extra 1 or 2 students into a section if doing so would result in a section-swap cascade that resolves matches for multiple other students. I’m sure someone, somewhere must have done work on solving problems with these kind of constraints, but I haven’t had much in my searches. The closest I’ve come is the idea of the Top Trading Cycle (an algorithm for finding mutually-beneficial exchanges) and a very old thread about how to solve a student-section matching problem in Perl.
My Solution
Because I’m only dealing with 8 students and 6 sections, I ended up just using a pen and paper to work out a series of swaps and class-size exceptions that would resolve things for all students. Here’s what I came up with.
I’m not necessarily going to try to claim that this is an optimal solution, but it works and that’s what matters. In the future, I may try to cobble together an algorithm to solve this problem for me, as even a very computationally inefficient algorithm will likely be faster than me doing things manually. Please post in the comments if you have suggestions of concepts/algorithms to look at or strategies to try.
Further Reading
A few resources I came across in my research which may be of interest to some of you:
– Stanford CS364A: Algorithmic Game Theory, Lecture #10: Kidney Exchange and Stable Matching
– Berkeley EECS 70: Discrete Mathematics and Probability Theory, Note 4: The Stable Marriage Problem
– Algorithm Design – Stable Matching
– Numberphile – Stable Marriage Problem (video)