CJC.org

Grace is interviewing for the residency match right now at various hospitals in the area and further out. The residency match system is actually interesting from a math/game theory point of view: the system arose out of a need to address a market failure for residents back in the early 1950s, and followed an algorithm shown to be more or less optimal by Gale and Shapley in the early 1960s.

According to various capsule histories of the match, medical residency was introduced around 1900 as a form of postgraduate education for medical students. The capsule histories don’t go into details on why, but salaries were standardized across the various residency programs: every resident makes the earns an equal salary no matter how exceptional they are, with small adjustments for local cost of living. (Presumably, there’s a notion that residency is a learning opportunity/apprenticeship, so salaries should be equal) Given that hospitals can’t compete on wages, they started competing in timing, where offers were presented to students earlier and earlier, so as to bind up their resident work pool before rival hospitals could. This became ridiculous: by the early 1940s, residencies were being finalized by the beginning of Third Year, before students had any clinical experience to make intelligent decisions on what they want to do. To address this problem, schools were prohibited by their governing association from disseminating transcripts or reference letters before early Fourth Year.

This caused grief to the hospitals, who now faced severe uncertainty as to their resident labor force: if a student rejected a hospital at the last minute, that hospital would wind up short of doctors, or at least with a less desireable applicant in that slot. Students on the other hand had no incentive to respond quickly to offers from hospitals: if their third choice offered first, why not wait for their first choice to respond? So hospitals began requiring students to very quickly decide on their offers. By the early 1950s, students were given only hours to reject or accept offers.

Because no one was happy with this situation, all the parties decided to centralize the process and developed what would be called an ordered list matching algorithm. Remarkably, they stumbled on what’s more or less the optimal solution, as shown by Gale and Shapley a decade later. This SIAM paper has a nice lay exposition of their work: suppose there are n boys and n girls (yes, Gale and Shapley wrote in the late 1950s), each boy with an ordered list of preferences for the girls, and vice versa. We proceed through a number of rounds (at most n² rounds, actually). In the first round, each boy asks his first-choice girl to marry him. Each girl considers the proposals she’s received, and says “maybe” to the highest ranked boy on her list, and “no” to everyone else. In the second round, the rejected boys go to their second-choice girl and asks the same question. Each girl looks at all her received proposals (including the one from the first round), and then says “maybe” to the highest ranked boy and no to the others; she may change the earlier “maybe” to a “no” if she receives an offer from a higher-ranked boy. We continue until there are no rejected boys, at which point the existing “maybes” are changed to “yeses” and the matched pairs are finalized.

The result of all this is a “stable” list of pairings: there does not exist a possible pairing such the partners prefer each other to the ones they are paired with. The algorithm then produces an equilibrium, what economists would call Pareto optimal (there exists no arrangement that would benefit one person without making someone else worse off).

The actually residency match is more complicated than this — hospitals don’t rank all the student that rank them, there are provisions for couples to be matched together, there is the possibility of not matching anywhere, etc. — but the algorithm follows the model well. The remarkable thing is that the algorithm was developed ad hoc, without a theoretical underpinning.

There’s currently a lawsuit by a number of residents who feel that the match system is unfair, possibly because they don’t like the idea of computers “governing” their fate. The problem they have with their lawsuit is that they would have to come up with a system to replace the current match, and this system would have to be shown to be more “fair” or optimal than the one in place right now. Given the mathematical background behind the current match, it’s unlikely they’ll be able to come up with anything better, and, in fact, they haven’t attacked the math behind the match, only that scary computers are running it (as opposed to, say, reliance on personal connections).

One further implication shown by Gale-Shapley is that there’s an asymmetry: the above model is “boy-optimal” and “girl-pessimal”, where each boy gets the best girl he can for a stable pairing, but the girl gets the worst possible boy. In the case of the residency match, where hospitals were the “boys” and students the “girls”, the hospitals have an “advantage”. The roles were reversed after a revision in the match process in the late 1990s, with the students playing the “boys” currently, though, empirically, only one resident in a thousand would wind up in a different place.

(Actually, from an economics point of view, all this match process does is to try to come up the best response to an initial market distortion, the inability of hospitals to use wages to fill out their residency slots. Arguably, a better system would be to allow wages to float. The problems with this idea are that this may be culturally distateful (wages were fixed for a reason to start with), it may harm smaller hospitals who depend on the cheap labor (which brings up other issues touching on the right to health care, and whether there are compensatory mechanisms to address this), it may hamper the teaching aim of residency, and so on. There may also be less obvious market failures involved, so floating wages may lead to worse outcomes; this may all touch on the theory of the second best. I’m not sure how many studies have been done on the effects of freeing wages for residents, though the above cited SIAM paper does refer to some work done to produce differently priced “residency slots”, to allow hospitals to offer varying wages. On the other hand, it’s not clear whether any of the more elaborate match models would have a practical effect, and may just increase stress and confusion in an already stressful and confusing process: not only would hospitals have to be ranked, but salary levels would have to be ranked, and so on.)

In a totally unrelated aside, when I first read about the cooperative game theory for the residency match, I was all excited because Shapley had a hand in the theoretical work. Long ago and far away, I did a summer math internship for the Research Experience for Undergraduates NSF program, and spent a couple of months in suburban northern New Jersey contemplating the Shapley-Shubik power index, which describes the relative power of members, say, a voting body like the UN Security Council. We actually got a paper out of this that I presented at some math conference in San Francisco; granted, it was a “look at what the undergrads did!” thing, but still, it was an opportunity for me to flub a public speaking engagement. We did submit the paper for publication, but it was rejected in a couple of places, and we didn’t pursue it much further.

This morning, after I dug up my old paper from the Mac archive .ZIP file, I typed “shapley shubik banzhaf” into Google, and, holy crap, it looks like someone did similar work on the axiomatic foundations of these indexes. I don’t have the mental circuitry anymore to evaluate what they did, nor do I remember what I did particularly well, but it looks a whole lot like what I did. Sigh.

Posted on Monday, January 5th, 2004 at 4:21 pm and is filed under Ideas. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.