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