Stable Marriage (Hospital Residents) Algorithm used in SocSci TA Matching

The algorithm used to match TA's to courses/instructors is based on the original algorithm to solve the Stable Marriage problem -- originally written about by Gale and Shapley in the early 60's.^[1]
But our problem in Social Sciences is actually closer to a derivative of Stable Marriage, called the Hospital-Resident problem: In classic stable marriage, there are n boys and n girls, with each girl getting offers from boys and matching with only 1 boy at a time (and temporarily accepting an offer until the next boy comes along who is higher in her preference ranking than the boy she is currently matched with). In hospital-resident matching, it works the same way, except that each hospital residency program may be matched with more than one resident. That is, each residency program has a certain number of "slots" for residents. The NMRP is the classic example of hospital-resident matching.
Thus, "hospital residency program" is to "medical residency applicant" as our "course/professor" is to "TA applicant". TA applicants make "offers" to "courses/profs" and the profs accept the applicants to be TA's for them until the slots fill up for that course and the next TA comes along who is higher on the prof's preference ranking, and bumps them out. (Then, the next time around, the TA applicant tries again, with the course next-lower on their preference list.) This goes on iteratively until all slots are filled or no more TA applicants can be found who want these courses.
It's important to remember (both with S-M and H-R) that who does the offering and who does the accepting/rejecting is important. Normally, the boys are looped through and they make offers to their preferred girls (and TA applicants make offers to their preferred Courses/Profs). However, the algorithm could be run exactly the opposite way, with girls making offers to boys and Courses making offers to TA's. Whichever way it is run, it's important to remember that the ones doing the offering (the boys, or, in our case, the TA applicants) actually are in a better position, because they get to run through their entire preference list, starting from the top, while a Course/Prof has to wait for TA applicants to make an offer. Thus, a professor/course may prefer Joe Smith highest, but never get an offer from Joe (because that course is not on Joe's preference list, or is at least very low on it). Thus, TA's will be happy to know that the preferences of TA's are in such a way given a slight advantage over the preferences of the professors.
On the other hand, it's also important to remember that no matter in which direction the algorithm is run, a course and a TA are highly likely to get matched if they both rank each other highly. Likewise, they are highly unlikely to get get matched if they are both low on each other's preference ranking.
It's also important to note that I have compensated for this slight imbalanace by adding on to the TAs' preference lists all the other courses which they did not choose from the web interface, but which still fit in their schedule. Thus, if they don't get one of their top 10 chosen preferences, then in the algorithm, they will still make offers to all other courses until they find one that accepts them. Thus, all courses which fit their schedules are on the TA's preference lists -- it's just a matter of how far up or down.
I was able to obtain Java code tailored to the hospital resident problem from Ryan Abel and Christopher Mueller, engineering graduate students at the University of Iowa. The code needed to be tweaked a little^[2], and also required that I write a pre-processor PHP program (getprefs.php), which I now use each time to create the necessary input file (for the Java program) from our database (where the professors' and ta-applicants' preferences are stored when they use our web-apps).
Further adjustments made to the algorithm:
- Committed^[3] students are always preferred over uncommitted students, even if the committed student is lower on the professor's preference ranking.
- Students must pick at least 10 courses
- Students must pick at least 1 and at most 2 majors within which they will teach if they don't get 1 of their first 10. Courses in these majors which fit their schedule are added onto their preference ranking after their first 10.
- The rest of their preference ranking (i.e., added on to the end, lowest in preference) is filled in with courses still left in their schedule but which were not in one of the above 2 sets.
- Some exceptions (forced exclusions and forced matches) are still made before the matching, using a web application I made for John on our portal. Then getprefs.php takes these exceptions into account in order to generate an adjusted input file for the Java matching program.
Some exceptions and switches are also made manually by John after the matching algorithm has run.

[1] D. Gale, and L. S. Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9-14, 1962. Also, Gusfield and Irving do an excellent survey of the algorithm and its variants in The Stable Marriage Problem : Structure and Algorithms ( ISBN-13: 978-0262515528, ISBN-10: 0262515520), (Antpac), (abebooks.com).

[2] To update the code for the latest version of Java; fix a bug with multiple slot-assignments; augment printed reports; differentiate between committed and uncommitted students; improve I/O and so on

[3] By committed we mean "a student to whom we are committed to providing a TA-ship in this quarter"

Back

revisions: 2018.05.15, 2016.01.14, 2006,10.21
jeff stern [jas at uci dot edu]