Bipartite graphs, medical residency, and the stable marriage problem
The medical residency program, which started at the turn of the century, is the first “job” that doctors have when they get out of medical school. They work at a hospital and take care of patients under the supervision of a more experienced physician. It’s an essential part of the professional education of doctors. It’s very important to doctors where they get their internship and residency because hospitals vary in salary and location, and it’s very important to hospitals because the interns and residents are a very important part of the labor force of a hospital.
The program used to work like a simple job application in the modern day labor market, where doctors applied to the hospitals they liked and then chose the best job offer they received. However, this triggered an arms race between hospitals for the best future doctors. Hospitals began hiring students earlier and earlier, often in the middle of their college careers. This is bad because it’s hard for hospitals to tell two years before graduation which doctors will be good, and it’s hard for doctors to know which kind of jobs they want.
Medical schools intervened and attempted to solve this in 1952. Instead of hospitals grabbing students earlier and earlier, there would be a program at graduation where hospitals and students would each be matched all at once.
This creates a problem, how do you match students with their favorite hospitals, and vice versa?
What we have is a simple bipartite graph, albeit with a giant dataset. Group A is doctors wanting residency, and group B is hospitals wanting to hire the best doctors possible.
One solution to this graph is for students to simply list hospitals they would like to work at, similar to the student-dorm model we saw in lecture. However, this gives rise to the “stable marriage” problem, described by David Shapley Johnson and Lloyed Shapley in their paper “College Admissions and the Stability of Marriage.” (http://cramton.umd.edu/market-design/gale-shapley-college-admissions.pdf) The stable marriage problem arises when two conditions are met.
- There is an element X of the first matched set which prefers some given element X of the second matched set over the element to which X is already matched, and
- Y also prefers X over the element to which Y is already matched.
Said more simply, there are two separate pairs that would both rather be paired with each other than their current partners. This means the relationship is unstable. Depending on the order in which you match students with any dorm they’re okay with, the relationships may be unstable and two students may become envious of each other’s dorms. The same goes for hospitals and doctors.
The solution is to require that hospitals and students rank their preferences of each other, and then apply the Gale Shapley algorithm. The Gale Shapley algorithm is iterative, and guarantees that everyone is paired and that all pairs are stable.
In the first round, first a) each unengaged student “proposes” to the hospital they prefer most, and then b) each hospital becomes “engaged” with the student they prefer most. In each subsequent round, first a) each unengaged student proposes to the most-preferred hospital to whom they have not yet proposed, whether the hospital is engaged or not and then b) each hospital gets engaged if they are currently not engaged or if they prefer this new student to their current fiancé, in which case the student they broke up with is put back in students looking for a hospital group. The right of hospitals to break up with students gives them the ability to “trade up,” and the process loops until until everyone is engaged.
This algorithm was implemented in the National Residency Program, which is still in use today.