PracticumFit and InternFit use the Gale-Shapley algorithm to calculate the optimal match from ranked preference lists for students and sites. First published in 1962, their algorithm proves to be correct, stable, and maximally efficient. Fifty years later (the Nobel committee not being known for alacrity) David Gale and Lloyd Shapley won the 2012 Nobel Prize for Economics for solving the matching problem.

Our algorithm first requires students and sites to enter their preferences for each other in ranked order. The students, of course, can only fill one job each, so they will simply list the positions they would accept in order of most to least preferred. Sites have a little more work to do. For each track, they will provide the number of openings, and a ranked list of students for the track.  They may also have a number of options to assign unfilled slots from one track to another, select students with a mix of skills, characteristics, or university programs.

When the ranking window closes, everyone’s preferences are loaded into our matching module. Each student’s list is consulted, and we try to match the student to their most preferred track. Suppose we’re matching a student, Ms. A.  If the track either has an open slot (and has her somewhere on their list) or prefers Ms. A to one currently in their list, Ms. A will tentatively be assigned to that track.  If neither is true, we’ll try her next preference, and so forth.  If we reach the end of her list before finding a match, we’ll move her to the out-of-luck list.  Now we move onto Mr. B and his ranked list.

After one pass through the list, many of the slots will be full, but a number of students will have been bumped if a student (perhaps Ms. A) processed after them was more highly ranked. Not to worry! We will now iterate through the remaining unmatched students list again. Hopefully their second or third preference will have space, or bump another student to make room for them. As long as students remain unmatched we’ll keep iterating to find you a slot! Eventually though (rather quickly on a modern computer), the match stabilizes.  Any student matched to a slot will keep it, and those unmatched (regrettably) find all of their preferences filled by students ranked higher by those sites.

Why does this work?  Each student has matched into the program highest up their preference list that will accept them (having been declined or bumped by all of their higher preferences), and all sites have the students they have ranked highest among those who considered that track (having declined the opportunity to add an unmatched student to one presently in a slot).

We would be done, but as mentioned above, in some match programs, sites can move unfilled slots to another track. And that’s good news for those without a match!  So we move those slots to create openings where there is demand, and find the best choices to fill them.  In reality, there are several cycles of moving track slots and rematching, and several checks that everyone is in the optimal slot.

You can learn more about the Gale-Shapley algorithm all over the internet, but we recommend articles on the Nobel Prize site, on Wikipedia, or on Youtube.