Matching Medical Students to Residencies

The Department of Education wanted to analyze the process whereby graduating medical students ought and were appointed to residencies in hospitals. A veteran of the Department, Howard Roberts was assigned this task. Howard was puzzled at first; why should the DOE be interested in studying medical student job-hunting? He assumed that, like most professions, medical students were hired into residencies like into any other job, by applying, interviewing, receiving offers, and accepting at the hospital of their choice.

Howard was wrong. The process is run with a computer-executed ``match." Each student interviews at the hospitals of his/her choice and both he/she and the hospital rank each other against all of the other hospitals and students they are considering. These rankings are sent to the National Resident Matching Program (NRMP), where they are entered into a computer and a single match is selected, wherever possible, for each student and available position. Needing more information, Howard hired a summer student, Thomas Johnson, to research the matching process. Tom's description of the NRMP matching algorithm appears in Appendix 1.

Background Interviews

Now that Howard understood the algorithm for the match, he sought to understand the possible problems with its execution. He sent Tom back out to look at the quantitative problems with the algorithm itself. while he spoke with students and hospital administrators involved in the match. Tom found some problems with the algorithm, which appear in Appendix 2. Howard's interviews were condensed and are printed below.

Interview with Jayne Doe, recently appointed to residency:

Howard:

Having been a part of the NRMP match last year, how do you feel about the process itself?

Jayne:

When its all over, your feeling depends entirely upon how well you did. If you got your first or second choice, the NRMP is great. If not, then the magnitude of your anger depends on how poorly you did. Most of my friends who graduated with me did well, so they all think it was great. They see it as an example of modern technology making a trying process as easy as it could be I didn't do so well. The computer matched me to my last ``safe" choice. I'll never know if I could have been offered a job at another hospital, but lost it because of the order of my rankings. Perhaps if I had put my third choice as number one, I could have been there instead of here at my sixth choice. One of my classmates would think me a fool to worry about this. He was not matched to any hospital. In the normal hiring process, this would mean that none of the hospitals he interviewed with wanted him, but with the match it could simply be a quirk of the rankings. It's frustrating, losing all control of the process which determines such a major step in your career.

Howard:

I never thought about how arbitrary it all must seem! Did you find any specific problems with the operation of the match? I understand the students and hospitals sign a statement that they will not ask each other to divulge their planned rankings. Did you find the participants upholding this promise of secrecy?

Jayne:

Or course not. Did you expect them to? The hospitals don't want to waste a number one ranking on someone who will not rank them first in return. You see, if a student and hospital rank each other first, then they are guaranteed to match. There is therefore great pressure to prearrange the rankings. Besides, all the form says is that you won't ask them what your rank is. If they volunteer the information you're not breaking your promise, and once they tell you their plans, you had better tell them yours, or else they might not rank you first after all.

Howard:

Were these abuses of the system common?

Jayne:

I interviewed at six hospitals and the only two which seemed interested in me ``volunteered" the information.

Howard:

Did you tell them your rankings of them?

Jayne:

Naturally. I told them both that they were my first choice.

When I didn't match to my first choice (one of the ones who had claimed that I was its first choice) I realized they lied too.

Interview with Bill Jones, director of the Resident Program at Inner City Hospital.

Howard:

Being on the hiring end of the match, how do you feel about the whole process?

Bill:

It's all a ``rich-get-richer" plot between the AMA and the big-name hospitals. The hospitals with the great facilities and the big names get all the good students. Before the match was used, we could attract students with early appointments and convince them of the social good they would be providing by working at an inner-city hospital like ours. They would accept the offer rather than wait for a possible offer from a big-name hospital.

Howard:

Can't you still convince them of the ``social good" and get them to rank you at the top of their list?

Bill:

We still try, but now they rank all of their options at the same time. If a student thinks he can get into a big-name hospital, he will give it a high rank. We've lost the jump on them because of the NRMP.

Howard:

So what happens now?

Bill:

We are continually rejected by the match and hire all our residents from foreign schools. The problem with the match is that it simply does not consider social costs and benefits. Here at Inner City Hospital we serve a large community with extensive medical needs but can't attract the good residents. The whole process is discriminatory.

Howard:

Do you find that people abuse the match? Some students claim...

Bill:

Listen, we have been participating in the match without success for several years. Of course we respect that the NRMP wished the rankings not be revealed, but if some students volunteer that information to us what can we do? We do everything we can to attract students. In our position we have to.

Howard:

What do you think can be done to improve the match process, or would everyone simply better off without it?

Bill:

If the match can't be changed, the it should be eliminated, but I think it is a good idea and could be improved and maintained.

The first thing that must be done is make the match follow the federal equal opportunity guidelines. Right now there are no stipulations in the match to maintain racial or sexual equality. The NRMP claims that the hospitals are the ones who must obey those guidelines, while the hospitals use the NRMP for cover, arguing that once the match is over they have no control. Neither have any respect for social needs.

In exactly the same way, there is not accounting for the social costs of a match which regularly rejects inner-city hospitals like ours. The match is supposed to be a ``free-market" mechanism, but while it obeys the free-market maxim of screwing society, it is certainly removed from the supposed free-market maxim of individual self-determination. Thus it has all the problems of so-called free-market solutions, while not actually being in any way free.

Interview with John Doe, director of the resident program at Big Name Hospital:

Howard:

Being on the hiring end of the NRMP, how do you feel about the whole process?

John:

It certainly has its problems, but it has provided continuity in a system previously fraught with misunderstanding and confusion. Before the match, all of the hospital had to recruit earlier and earlier to get the good students. Now it is an orderly process with all of the residents being selected at the same time. It is a good market solution to the problem. Now the students and the hospitals can rank their choices and get those rankings considered as best they can in the match. It is certainly not a bad solution.

Howard:

Do you have any trouble attracting students to your programs?

John:

Certainly. We all have to accept that we cannot always get our first choice, but then there is not always all that much difference between the first and second choice anyway.

Howard:

What about abuses of the system? Some of the students have been coerced into announcing their rankings prematurely. Does that happen here?

John:

In any system, there will be abuse. The NRMP does all it can by requiring all of the participants to sign a pledge that they will not abuse it. Naturally we follow that pledge.

Assignment

1. Pose the example matching problem as a pure network, such that the objectives of students, hospitals, and society can be proportioned by design (either in the objective function or in the constraints). Assign weights to each of your objectives according to your own set of values regarding medical training and service.
2. Solve your problem on a computer (use OPTNET, LIP, or orther optimizer) and summarize your solution.
3. Compare your model to the NRMP algorithm. What biases are built into the NRMP algorithm? What problems does your solution solve and which does it not? Can all of the problems of the match be solved with quantitative methods?

Appendix 1

The NRMP uses a simple elimination algorithm to execute its match of medical students to residencies. This method takes into account the student and hospital preferences for each other in a ``Hospital First" algorithm described in the he NRMP Directory. It matches the first choices of the hospitals with the highest possible student choices as will be shown with the following example:

Eight students (A-H) have ranked their preferences for each of the four hospitals (W-Z). Similarly, the hospitals have ranked the students. Since each hospital has two openings, the NRMP algorithm defines the two highest-ranked students as ``first choices" for the hospitals.

The first stage of the NRMP algorithm tries to make a match of students' first choices with hospitals' first choices (1,1). Only one match, C to X, is achieved in this first run, as shown below [a match will be in parentheses ()].

Next, the hospitals below X on C's rank list are removed, and C is removed from their corresponding lists. This ensures that no student will ever be rematched to a lower-ranked hospital than the one to which he was earlier matched. This puts B within W's quota of openings. A second 1,1 run is executed. This run produces no matches, as W is not B's first choice. Once there are no 1,1 matches, the algorithm tries a single 2,1 match (student second choice and hospital first choice). This produces three matches, as shown below.

After the single 2,1 run, the algorithm returns to 1,1 runs. This produces an interesting conflicting result. E is matched to Z, even though E was previously matched to X. Since Z is E's first choice, this 1,1 match is executed instead of E's 2,1 match with Y, as shown below:

The algorithm thus keeps open the possibility of students improving their matches. It has no mechanism, however, for matching any student to a lower-ranked hospital once he has been matched to one with a higher ranking.

This iterative process of 1,1 and 2,1 matches is repeated until all the students who can be matched to their first or second choice have been matched. At this point the algorithm has matched the following students:

Now a single 3,1 match is run. This produces no match, so a single 4,1 match is run, matching A to W and H to Y. The match process is now complete, with the final solution shown below:

Appendix 2. Suboptimal Solutions with the NRMP Algorithm

One of the best criteria for any matching algorithm is that its solution be pareto-optimal. Considering the match as a two-actor model (with the hospital group as one actor and the student group as the other) a pareto-optimal solution would be one in which neither the hospitals not the students can improve their matches. Given that the object of the matching program is to minimize the total rankings of the students and the hospitals (or at least minimize the totals of each), then alternate optimal solutions would be those which provided the same total ``rank sum" for each group as the chosen solution. In the case of the described example:

the sum of matched students' ranking of hospitals is 16, while the sum of the matched hospitals' rankings is 25. Thus an alternate optimal match would have the same rank sums as these, while a ``better" match would have smaller sums.

Analysis of this example shows that the algorithm assigned the students and hospitals to a sub-optimal match (by the two-actor criteria). By moving student F down from his first-choice hospital (W) to his second choice (Y), student H can be moved from his fourth choice (Y) up to his first (W), as shown below (with the alternate solution marked with -'s instead of ()'s):

This new match reduces the student rank sum by two from 16 to 14, because one student moved up three while another moved down only one. The hospital rank sum remains the same, as hospital Y gains two rank points, exactly offsetting the two lost by hospital W. Thus the new solution improves the students' match without hurting the hospitals'. In the two-actor interpretation of the match, the original solution was sub-optimal; it was possible to improve one actor's rank sum without hurting that of the other actor.