jess gets married?
Here’s a shout-out to Jess, who is nearing the end game of her new career as a nutritionist. She was accepted to her top choice of internship programs and will be spending her proximate future in Houston (nb, this is a good thing, not a punishment). Congrats Jess!
Her friends here have heard a lot about the selection process and the weird lottery/matching system that is used for the registered dietician programs in the country. [They use the same system for doctors and vet residents too.] For those unfamiliar, the way it works is, the student picks her top three choices of where to go, and all the programs pick their top students. Then, some cranky ancient computer from 1984 wheezes and chugs for months, and in the end, somehow figures out how to match the students with their top choice of programs and programs with their top choice of students.
Idly wondering about why such a weird system exists and how it works has come up quite a few times around here, and due to an odd bit of intertwingularity, I happened to discover the answer because I’ve been working through some MIT OpenCourseWare material lately.
One of the courses I’m working through is 6.042J Mathematics for Computer Science which is about as exciting as it sounds. But it’s a weak spot in my range, so I’ve been trying to get better there.
Anyhow, it turns out that Jess’s matching program is described in the lecture on state machines, and is more familiarly known as the Stable Marriage Problem.
Suppose that there are n boys and n girls. Each boy ranks all of the girls according to his preference, and each girl ranks all of the boys. For example, Bob might like Alice most, Carol second, Hildegard third, etc. There are no ties in anyone’s rankings; Bob cannot like Carol and Hildegard equally. Furthermore, rankings are known at the start and stay fixed for all time.
The general goal is to marry off boys and girls so that everyone is happy; we’ll be more precise in
a moment. Every boy must marry exactly one girl and vice-versa—no polygamy.
The stable marriage algorithm we describe was first published in a paper by D. Gale and L.S. Shapley in 1962. At the time of publication, Gale and Shapley were unaware of perhaps the most impressive example of the algorithm. It was used to assign residents to hospitals by the National Resident Matching Program (NRMP) that actually predates their paper by ten years. Acting on behalf of a consortium of major hospitals (playing the role of the girls), the NRMP has, since the turn of the twentieth century, assigned each year’s pool of medical school graduates (playing the role of boys) to hospital residencies (formerly called “internships”).
Before the procedure ensuring stable matches was adopted, there were chronic disruptions and awkward countermeasures taken to preserve assignments of graduates to residencies. The stable marriage procedure was discovered and applied by the NRMP in 1952. It resolved the problem so successfully, that the procedure continued to be used essentially without change at least through 1989.
[From Professor Albert R. Meyer’s lecture notes, 5th lesson]
If you work through the lecture notes, the obvious difference between the example given and Jess’s situation is the imbalance between boys (students) and girls (programs) in the real world. Obviously after the final, real round, there will be unmarried boys who don’t get to be RDs. Sorry!
The other difference is that the lecture notes describe an algorithm that gives the boys their optimal choice and the girls their pessimal choice. Sounds good for Jess, but of course, we could easily just flip the roles around and make the students girls and the programs boys. Based on the theory that most things in life are designed to screw over students, that’s my guess on their implementation.
A third difference is that we don’t know whether the girls can be polyandrous and take on multiple boys.
A note on the running time. In the example, the running time of the algorithm is O(n2). In Jess’s case, it’s actually O(n * m) where n is the number of boys and m is the number of girls. Still, that’s quadratic time, which isn’t so bad, and there’s no reason that even an actual computer from 1984 would need two months to figure out the results. I’m not sure why they introduced all the high drama and suspense. Again, the theory of messing around with students’ minds is the only logical answer.
And there you have it — a brief glimpse into what computer science is actually about, which is to say, a bunch of math that seems really dry, but turns out to have surprisingly interesting real world applications. Oh, and an example that illustrates the lesson at hand very clearly, but true understanding is only demonstrated when the student can adapt and apply the simple example to a situation with different parameters.