The 2012 Nobel Prize in economics went to Alvin Roth and Lloyd Shapley for work they did on market-matching theories. These theories work to optimize the matching of items from one list to items in another, especially when preference is known. The media accounts list examples like matching medical students with residency hospitals, and organs with patients. I have to confess I’m not fully up to speed on all the theories, but I thought I’d take this opportunity to share how I’ve solved a similar problem with my students when picking teams for projects.
The typical setup is that my students will nominate a few projects that they’re interested in and then they indicate their preference for each project. I tell them that I’ll find the groups that maximizes the class happiness. Of course, if they self-select into appropriate size groups with their number one choices, it’s easy. However, that almost never happens.
Being basically in the dark about how these market matching theories worked back when I first ran into this problem, I went to my most ubiquitous tool in my tool box: the artificial genetic algorithm. I wondered if such an approach would work so I put some time into coding it up and testing it. I’ve been using it ever since.
So how does it work? I start by creating a population of possible groupings, by repetitively putting students in random groups. For each grouping, I calculate the fitness (see below) and then sort the groupings based on fitness. Then I select groupings to be mutated (see below) based on how fit they are and generate a new population that way. Then I repeat, constantly keeping track of the very best grouping. I stop when I get bored or it seems to stop improving.
fitness: I calculate the fitness by totaling the preferences for each student. If a student were to rank the five projects as 2, 5, 3, 1, 4 and I put them in the fifth group, that would contribute a 4 to the fitness (note that lower is better, in this case). I also add to the fitness (meaning it gets worse) a huge penalty if the groups are not all equal size. Note that in my original random groupings, all the students could be in one project, but this last correction to the fitness would give that a huge (bad) fitness. I have occasionally promised certain students that they’ll get into a particular project (maybe it’s one they’ve researched or something). I accomplish this by setting their preferences to all 10′s for the project they don’t want, and -10 for the project they do.
mutation: I mutate a grouping by randomly selecting a small number of students to be placed in a new group.
It’s fast, flexible, and a fun way to show students the power of a genetic algorithm. Now I should go read more about the Nobel Prize, I suppose.
How do you solve problems like these?