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?
SuperFly Physics 
Hi Andy, one of the things that I’m always interested in, but never get around to, is using genetic algorithms to try to find optimal or obtuse strategies in board games. Of course there is a lot of overhead in programming the actual rules, which I suppose is the main reason I never get around to it.
yeah, coding the rules would definitely be the hard part. You’d also have to code in multiple players to play against.
The most well-known board game one is called the Puerto-Rico Evolver: http://www.tropiceuro.com/puerto-rico-evolver/
It’s meant to be an adaptive AI to play against.
Pingback: Automating conference scheduling using Python | gealgerobophysiculus
Pingback: Matching Students to Presentations « Solvable by Radicals
Matching students with projects is a nice article
See my blog here http://www.howtotec.com/category/internet/
Pingback: Genetic algorithm for randomizing oral exams | SuperFly Physics
Pingback: Scripting in the Dean’s office | SuperFly Physics
I’d formulate is as the classic assignment problem and use the Hungarian method to find the (or an) optimal solution. Runs on O(n^3), but will definitely turn out an answer for a classroom roster in no time.