Optimizing the Residency Match: A Critical Analysis

[00:00:01][Music] Welcome back for another Sheriff Fodium video. It's been a little while since I've done a journal club, so today that's just what I'm going to do. Now, for those of you unaware, Journal Club is an irregular feature on this channel where I systematically analyze and rigorously evaluate a recent paper so that I can use it as a jumping off point for my own personal hottakes. So, don't worry, this is not your program director's journal club. And today, I've got a good one for you, a paper about is there a better resident matching algorithm? And I think it's going to inspire a good discussion and help you think critically about and ultimately better understand the residency match and residency matching algorithms.

[00:00:56]The paper is this. It's called improving residency matching through computational optimization and it appeared in June in JAMAMA network open. It's written by a group of opthalmologists at the University of Washington in Seattle. And as always, I'll link to the paper in the notes below.

[00:01:12]And as usual, I'll begin by summarizing the paper first by setting out the problem. And as the authors expressed in their own introduction and in an editorial that appeared this week in Medpage Today, the problem is it seems like we should be able to do better than the current chaotic cutthroat residency matching system.

[00:01:33]Because there are more residency applicants than residency positions, there's intense competition for preferred specialties and training programs. The authors point out that the average opthalmology applicant applies to 85 programs, which is around 70% of all the opthalmology programs that exist. And at their institution, they received 650 applications for just five positions.

[00:01:56]So, a system like this, it encourages metric chasing and superficial application review. And it's only growing more expensive and timeconuming for programs and applicants as the number of applications submitted and interviews completed increases each year.

[00:02:12]Now before I move on, I hope you'll allow me some shameless self-promotion because if you want to understand the current algorithms used by the NRMP and San Francisco Match, it helps to have some historical perspective on how those algorithms were developed and implemented. And I will provide that perspective if you'll only give me a few minutes of your time. So I have a six-part series on the history of the match that I put together a couple years ago and it walks through how the current and previous algorithms work and it will tell you the the undertold stories of some of the medical students and student advocates who fought for a better system. So if you haven't watched that, I would recommend it to you in the strongest possible terms if you have interest in this topic.

[00:02:54]But back to the paper. The current algorithm used by the NRMP is called the Roth Parson algorithm. And it's derived from work that a couple of mathematicians named David Gail and Lloyd Chapley did 75 years ago in solving what was called the stable marriage problem. And again, if you want to know more about this, please go ahead and watch those other videos already because here I'm going to try to be brief because what Gail and Chappley realized is that you could match up pairs of husbands and wives or programs and applicants in a way that resulted in stable pairings if you used what's called a deferred acceptance algorithm.

[00:03:27]Now, what that means is that one partner proposes a match to another, and that partner that receives the proposal, it chooses their most preferred offer. Now, when you do this, it doesn't mean that everyone gets their first choice. But what it does mean is that if you didn't get your first choice, it's because the potential partner to whom you proposed a match liked someone else's offer better than yours. So, at the end of the match, there will be no pair of husband and wife or applicant and program where both of them would have preferred to get a different match to the one that the algorithm assigned them. So that's what makes the marriages or the matches stable.

[00:04:08]But as the authors point out in their Medpage editorial, just because an algorithm creates stable matches, that doesn't necessarily make it optimal.

[00:04:18]Because remember, the first match took place in 1952. It was run using punch cards. But nowadays there there's more computing power in the old flip phone or Blackberry sitting in your desk drawer collecting dust than than anything that those folks had easy access to. So what if we reimagined the matching algorithm?

[00:04:38]What if we used a computer to pair up programs and applicants in a way that that simply could not have been done 75 years ago? What if we considered every possible permutation of program and applicant pairings and then we picked the single best one and that's what these authors did. So rather than going through a series of proposals or trying to have an algorithm that optimized outcomes for just applicants or just programs, the authors allowed a computer to consider the universe of possible matches and then choose the optimal one.

[00:05:15]Now deciding which particular match is optimal from the entire universe set of possibilities it requires a value judgment. So the way that the authors did this was objectively by seeking to minimize the total number of ranks. Now here in the editorial they put that in layman's terms. Suppose you have a choice between a solution where an applicant gets matched to their fourth choice program and that means that the program who matches that applicant they get their sixth choice. Is that better than a match where the applicant gets their top choice and the program that they would match to then gets their eighth choice? I mean, that's a tough question, right? Because the applicant would probably say the second option is best because then they get their first choice instead of their fourth. But the program might prefer the first result because then they get their sixth choice instead of their eighth. So, whose preferences should we prioritize?

[00:06:06]Well, if we do it mathematically because 4 + 6 is 10 and 1 + 8 is 9, the second possibility is actually optimal for the system as a whole because it would minimize the total number of ranks. So by using a computer to find the solution that provides the minimum total number of ranks, you found the solution that optimizes the match outcome for the system as a whole.

[00:06:34]So, that's a cool idea, but an individual applicant or program director probably isn't as interested in harmonizing the entire systems outcomes as they are in ensuring that their own personal outcomes are maximized. So, what would something like this look like if it were actually done in the real world? That's what these authors set out to determine. So to do that they obtained real deidentified rank order list data from the SF match which of course is the matching service that conducts the opthalmology match and they took rank order lists from 2011 to 2021 and then they ran the match two different ways. First they ran it with what they call the Gail Shappley algorithm which approximates what would occur in the SF or NRMP match. And then they ran it again with what they called the residency optimizer, which was an algorithm that used mixed integer linear programming to find the minimum sum of applicant and program rank preferences.

[00:07:33]And here's what they found. The graphics here show you the results for applicants on top and programs on the bottom. And the curves show you the average rank at which an applicant matched or the program filled by the match year. Now on these graphics, the Gail Shappley algorithm is shown with the orange curve and the residency optimizer is in is in blue. And what you'll see is that the blue curve is below the orange curve, meaning that the applicants and programs overall got more desirable matches because remember the match is like golf.

[00:08:03]Lower is better because really you want to get your number one.

[00:08:07]Overall, on average, applicants did 0.45 45 rank positions better with residency optimizer and programs did 0.32 rank positions better than they did with Gail Shappley and actually residency optimizer did a better job of filling all the positions than Gail Shappley because I mean to be fair there aren't many positions that go unfilled in the opthalmology match but in most years there's at least a couple but in residency optimizer there were none in any year but getting back to individual outcomes It wasn't just that the average match position was lower. When they looked at the proportion of applicants that matched to one of their top three programs, well, 78.4% did that with residency optimizer versus just 70.9% with the Gail Shappley deferred acceptance algorithm.

[00:08:59]But we're not done yet because the authors drilled down even further to give us even more granular data on how individual applicants and programs outcomes would change. The scatter plots here show the matches generated with the Gail Shappley algorithm on the left and the residency optimizer algorithm on the right. And on these graphics, the x-axis shows the applicants rank of the program where they matched and the y-axis shows the program's rank for the applicants that they got. And what I want you to notice here is that the scatter gets reduced. There aren't many matches at all that occur at the bottom of a program or applicant's rank list. the mass in the graph gets squeezed into that left lower quadrant when you use the residency optimizer.

[00:09:45]Now, not every single applicant did better with residency optimizer. Some applicants and programs did worse than they would in the current system. And this graphic lays out the flow of outcomes when you move from one algorithm to another. So, let me orient you. On the left, you've got the outcome in Gail Chappley with rank order lists descending vertically from the top all the way down to the U, which represents the people who went unmatched. And on the right, you got the same thing for the residency optimizer algorithm. And all the colors that flow from one area to the other um indicate applicants whose outcome changed. And and all these color codes represent something. So the orange is someone who got a worse outcome with Residency Optimizer. The green shows someone who did better and the blue shows someone who went unmatched in the current system but matched with residency optimizer and the red represents someone who was matched in the old system but got unmatched in the new. So there's a lot going on here but in general the applicants who did worse only did a little worse losing on average 2.2 ranks and those who did better did quite a bit better gaining 4.1 ranks. And although 5.4% 4% of applicants who were matched in the old system got unmatched in the new. 5.8% of previously unmatched applicants now became matched.

[00:11:05]The authors did a couple of other things that I'm going to tell you about quickly. Since we got all these problems with application fever and interview hoarding, they wondered what would happen if we had a world where applicants actually applied to fewer programs and completed fewer interviews.

[00:11:20]Would their results hold up as well? So they modeled how well residency optimizer would work with truncated rank order lists and that's what's shown here. Notice again the blue curve is higher than the yellow curve in each of these panels meaning that the residency optimizer would still fill a larger percentage of program positions than Gail Shappley even when you had shorter rank order lists.

[00:11:44]And then they even tried to model a full NRMP match. Now of course they did not have actual NRMP data. So they had to imputee rank order lists using the general patterns and preferences about program desiraability that applicants had in the real opthalmology data that they had for their previous analyses. So they simulated rank order lists that would approximate the 2019 nrmp published statistics for the number of programs positions applicants and the number of programs ranked per applicant.

[00:12:14]And with all those assumptions, they found that the same pattern held in every single specialty that they modeled in plastic surgery, radiation oncology, otoarangology, dermatology, orthopedics, pathology, radiology, general surgery, pediatrics, and both family and internal medicine. Applicants matched at lower ranks and a greater number of positions filled with residency optimizer than with the Gail Shappley algorithm.

[00:12:44]So let me take just a moment to summarize. This is what we got. We got a new algorithm. It's called residency optimizer. And it's a simple algorithm that uses mixed integer linear programming to find the single match outcome out of the universe of all possible match outcomes that results in the lowest sum of ranks for programs and applicants. And when you test this algorithm using real rank order list data from the opthalmology match, it outperforms the deferred acceptance algorithms that we're currently using.

[00:13:12]More applicants match to their top choice. More applicants match to one of their top three choices. Overall, applicants move up by around a half of a rank order list position. And programs move up by around a third of a rank order list position. More positions get filled overall, leaving fewer applicants and programs scrambling around in the soap. And oh, by the way, all the necessary computations were done in a matter of seconds on a standard laptop.

[00:13:38]So what are we waiting for? I mean, how quickly can we change to this new system? Why would we ever want to preserve a system that's so clearly inferior in every measurable way?

[00:13:50]I got to say, I applaud the authors for doing this study, and I applaud the SF match for giving them real data, but this paper and the algorithm that it proposes has a fatal flaw. There's an assumption that's made that simply will not be true if this system were ever put into place. And if it were ever implemented, this flaw would lead to the matching system collapsing upon itself.

[00:14:13]To understand the flaw, you got to have some understanding of how the current matching system works. So to help you do that, I've made a very simple example here. Imagine a world where we have three applicants. We'll call them student A, student B, and student C. And these applicants are trying to match at one of three hospitals. The most soughta is the prestigious Ivy League Memorial Hospital. But if you can't get in there, StateU hospital is a highly reputable program. And then of course there's community general, which is a nice backup option. So all three of our students, AB, and C, they actually have the same preferences about where they want to match. They want Ivy League memorial number one, then StateU, then community. And as it turns out, the hospitals actually share the same preferences for the applicants. Student A is a slightly better applicant than student B, and student B is slightly better than student C. So even though they're all qualified, the hospitals are going to rank these applicants student A, student B, student C.

[00:15:11]So what happens when we use an applicant proposing deferred acceptance algorithm like Gail Chappley or the NRP's Roth Parson algorithm? Well, the applicants all propose a match to their top choice, which for all of them is Ivy League Memorial. But Ivy League memorial only has one position. So they accept student A's offer and they decline the other two. So now their program is filled with student A and the algorithm can move on to the next round to try to match the other applicants and programs.

[00:15:40]In round two, students B and C then propose a match to their next most preferred program, which for both of them is StateU hospital. State U would rather have student B. So now they're a match. And we'll move on to round three.

[00:15:56]In round three, student C proposes a match to community general. And it turns out that student C is community's most preferred applicant remaining. So, they'll accept that offer. And now they're a match. And now the match is final.

[00:16:11]Well, now let's take a look at what happens if we use the residency optimizer. here. Instead of proposing matches or using rounds, we're just going to imagine all of the possible permutations of applicants and programs that exist. And we're going to total up the applicant's rank of the program and the program's rank of the applicant for each of those permutations and see which permutation gives us the lowest number.

[00:16:35]And if we do that for this example, turns out we'll get exactly the same result that we did with the deferred acceptance algorithm. Student A ends up at Ivy Memorial, student B to State University, and student C goes to community. And if we sum up all those ranks, 1 + 1 + 2 + 2 + 3 + 3, we end up with 12, which is the lowest possible number we could get.

[00:16:58]So, what's the problem?

[00:17:02]Well, to see it, I want you to pretend for a moment that you're student C. And student C, he's an apex level gunner. He desperately wants to get into Ivy League Memorial and he's got the test scores and he's got the research papers so he knows he's going to be in the running.

[00:17:17]But how is he gonna beat out students A and B because they got everything that he has but just a little bit more shine and pizzazz.

[00:17:25]Well, I hate to tell you this student C, but if we're using the Gail Shappley algorithm, there's nothing you can do.

[00:17:31]Your best strategy is to try to interview well, then rank programs according to your honest preferences, and then cross your fingers and light a candle and say a prayer and hope for the best on match day. There's nothing you can do to game the system. But with Residency Optimizer, there is.

[00:17:51]What you can do is try to get yourself strategically downranked at all the programs you don't actually want to go to. So when you go to your interview at stateu or community, you want to act like some difficult to tolerate blowhard. Now you don't want to cross the line or do anything bad enough that you get unranked, but you want to be as non-threateningly unimpressive as possible so that you stay just barely above the program's minimal standard and they rank a whole bunch of applicants above you. Because if you want to game the residency optimizer algorithm, the best way to do it is for every program other than your number one to put you at the very end of their rank order list in that special category of applicants that some programs classify as BTTS, better than the SOAP.

[00:18:40]So let's say that student C executes this strategy to perfection. What does that do? Well, now if residency optimizer tries to make the same match pairings that it did before, there's a problem. State U and community have student C ranked so low that putting him in any place other than his number one choice is going to result in a big number being put into the sum of all the ranks.

[00:19:04]Since we want to optimize the lowest overall sum of ranks, the optimal thing to do actually is just to let student C have his way and go to Ivy League memorial and then we'll slide everyone else down a notch. So student C is going to go to Ivy League, student A is going to go to stateU and student B is going to end up at community because when we do that, no program or applicant ends up going lower than third on their rank order list. So this is the optimal solution under a mixed integer linear programming model like residency optimizer.

[00:19:35]So the first thing I want you to think about is whether this is really the matching outcome that we would want. I mean mathematically it is optimal. It maximizes everyone's utility from the matching system. But whether it's ideal or desirable to reward someone for gaming the system or to pay for that reward by punishing applicants who played it straight. Well, I think that deserves some pondering.

[00:20:01]But I know what some of you may be thinking. You know, this this is a contrived example. I mean, here I'm talking about a paper where the authors have given me all this careful modeling and empirical data. And here I am trying to argue against it using an overly simplistic 3x3 match matrix where one applicant chooses to pursue a high-risisk highreward strategy that most god-fearing applicants wouldn't dream of pursuing. And I would agree with you that I hope applicants wouldn't pursue such a strategy because if they do, some are going to get burned and go unmatched. It it's very similar to the argument about truncating rank order lists that factored into Dr. Williams fight for a student optimal matching algorithm, which of course I discussed in part three of that match series that I was plugging earlier. But the first point that I want to make here is that setting all that aside, this is not the incentive you want to give applicants even if only a minority of them will pursue it.

[00:20:59]But my second point is even if you don't like that hypothetical example, you should understand that the principle that underlies that example is already apparent in the author's data even without any gaming being involved. Let's take a look again at figure 2C from their paper. I showed you this a moment ago. It was the one that showed how applicants outcomes changed when you moved from Gail Shappley to residency optimizer. It's the one that had the color-coded pathways that show applicant movement.

[00:21:27]The first color I want you to focus on is blue because that's the color that represents the stream of opthalmology applicants who went unmatched between 2011 and 2021, but who would have matched under the optimal matching scenario provided by a mixed integer linear programming algorithm. That blue line looks like a cresting wave. It starts down in the lower leftand corner of the graphic. And look where the bulk of it ends up in the upper right hand corner connected to the group of applicants who now match at their number one choice.

[00:21:58]But what has to happen when this previously unmatched group of applicants now gets their number one choice? Well, everyone else has to move down just a little bit.

[00:22:08]Let's focus next on the orange curves, which represent applicants who still matched but whose match outcome got a little worse. I've got several of those curves highlighted here. They're all flatter. And although some applicants tumbled multiple positions, the biggest group of applicants who do worse with residency optimizer, they lose just one place. I mean, they move from their number one to their number two, their number two to their number three, their number three to their number four, and so on because they had to make room for a new applicant on top. But just like the song about 10 in the bed and the little one said, "Roll over." When they all roll over, then one falls out.

[00:22:44]And that's what's shown on the red curves. Under Gail Shappley, these applicants had matched at their third, fourth, fifth, sixth choices, but now they're out of luck. So, what I hope you can see is that the way that things shake out under residency optimizer is mechanistically identical to what I was trying to illustrate for you when I made up that teaching example with gaming.

[00:23:04]There is no free lunch. Residency Optimizer optimizes by matching the hard to match applicant.

[00:23:12]Think for instance of the prospective opthalmologist with a sterling CV and a 275 step 2CK score. They get interview offers everywhere, but it turns out they're a bit of a dud when they go to their interview. So they end up not ranked especially highly by most programs. Such an applicant goes unmatched in Gail Chappley. But under residency optimizer, mathematically the easiest way to fit in such an applicant is to let them have their number one choice because that way at least you only have to add up one large number. In contrast, a well-rounded applicant who's well-liked and and highly ranked by many programs is much easier to place at a number of different matches without having to pay a steep mathematical penalty.

[00:23:58]Now, deciding whether this is a good thing or a bad thing requires a little bit more than the statistics that the authors of this paper can give us. It it requires a value judgment. And where you fall on that question may depend on which group of applicants you think you're going to be in.

[00:24:14]But beyond that, there's a final and much more important problem with the matching result that's returned by residency optimizer. And to explain that, I need to re-emphasize a point that I made back in the beginning about the results that emerge from the Gail Shappley algorithm. So I'm showing you that again here. The matches that come out of a deferred acceptance algorithm are stable, which means that there's no matched pair where both members would prefer something different to the results they got. It does not mean that you always get what you want. Look at student B. He wanted to go to Ivy League memorial just like everybody else, but they wanted student A. Similarly, the program where he matched StateU, they would have preferred to have matched student A, but you know, she's beyond humbled and grateful to announce that from sleepless nights to a dream come true, she's Ivy League bound. # blessed.

[00:25:05]Come on, man. She's not going to go to stateu.

[00:25:09]If you use a deferred acceptance algorithm, if two applicants want the same thing, the program's rank order list is a tiebreaker and vice versa. But now, let's take a look at the results of the residency optimizer. Are these stable matches?

[00:25:24]They are not. Look at student A. She's now choking back tears on match day after finding out that she's headed to state U. And now look at Ivy League memorial. They would have preferred to get her rather than student C. And maybe the program director is perplexed at why the program fell so far down their rank order list this year. So he decides to reach out to some of his top ranked applicants and get some honest feedback about what went wrong interview season.

[00:25:51]And when he does, he's going to learn that actually student A wanted to be there, too. This is not a stable match because we now have an applicant and a program that both wanted something that they weren't assigned by the algorithm.

[00:26:06]And if that's how the game's going to turn out, well, it won't take too long for programs and applicants to decide that they don't want to play it anymore.

[00:26:14]They do better by not playing it. If you allow a system in which programs and applicants have an incentive to make deals outside the match, the match won't last long.

[00:26:26]Now, could you constrain the algorithm to examine potential solutions for these unstable pairings and and not accept any result that included one? I suppose you could, but it would take more computing power. And I don't mean a little bit of computing power. I mean a lot more because the math and programming are going to get a lot more complicated. And I'm honestly not sure how good the solutions that return are going to be or whether this approach would even be feasible on a set the size of the NRMP match.

[00:26:55]I think the lack of stable outcomes is a fundamental problem with this algorithm.

[00:27:00]But I don't know, maybe you don't care about that. And maybe you also are okay with the valuebased trade-offs for the hard to match applicant that I was highlighting a moment ago. Because after all, the authors did convincingly demonstrate that overall programs and applicants match to lower positions on their rank order list. And if that's you, then I have just one more thing that I want you to think about.

[00:27:23]Because if we were to implement residency optimizer in the future, then we should have no reasonable expectation that the real life results would approximate the impressive numbers that are reported in this paper because expecting that would require an assumption that is just not justified.

[00:27:40]Let me tell you what I mean. The strength of this paper is that they use real life rank order lists from the SF match. But these are the real life rank order lists that applicants and programs submitted when they were trying to optimize their outcomes in the current system. It's a serious mistake to assume that the rank order list preferences of applicants and programs will not change when all of a sudden we have a new system with new incentives. And with a new algorithm, there will be a new incentive for certain applicants to make themselves easy to match at their top program and hard to match anywhere else.

[00:28:16]That by itself will cause some externalities. Just the existence of this kind of high-risk, highreward strategy is going to cause unnecessary stress. But some applicants are actually going to try to implement it. And the ways that that will shape application and interview stra day strategy, I promise will not be appreciated by programs who are on the receiving end.

[00:28:38]But the important thing is that once applicants start submitting strategic rank orderer lists, lists that don't reflect their honest preferences, but instead represent some calculus about trying to widen the difference between their rank of the program and the program's l rank of them. The effect estimates that are reported here, they they fall apart. I mean, the algorithm will still return the match with the lowest sum of ranks, but what that really means is uncertain. and whether the result will be truly optimal with dishonest rank order lists. It'll be highly doubtful that it would be.

[00:29:15]Before I quit, I want to say just one last thing about the topic of this paper.

[00:29:20]I think if you pulled residency applicants, you would find a substantial number who have a very negative perception of the match.

[00:29:29]But I think what they're thinking of when they hear the match is the residency selection process writ large.

[00:29:35]you know, the whole package deal of grinding and hoop jumping and CV buffing and buttkissing throughout medical school and the interview trail, all to have the the final outcome of that process put in the hands of a faceless computer.

[00:29:50]And you know, there are a lot of problems with our medical education and residency selection system, and you've heard me discuss many of them right here on this channel. But I'll give you my honest opinion. The matching algorithm isn't one of them. It returns the best possible outcome for students who submit an honest rank order list and it ensures that all the matches it returns are stable pairings. Now, that doesn't mean that the overall system is fair, and it certainly doesn't mean that everybody's going to get what they want. But remember, residency selection is a zero- sum game. For every person or program who wins, there's going to be another who loses. And that unfortunately is an inherent property of the system. It's not a problem that you can solve by changing the matching algorithm. If you want to fix any of those more serious problems, you're going to need solutions that get at their root causes.

[00:30:40]And so, although I thought this was a cool paper and I really enjoyed thinking about it for a few minutes, and I hope you did, too. I don't think implementing this algorithm would make the match or the residency selection process any better. So, for now, that's all I've got. Thanks for listening.

[00:31:00][Music]