NRMP Match Algorithm Question

[DocRock19]

I recently watched the NRMP video on how the matching algorithm works for couples (link: ) and left... confused. I'm wondering what would happen in the following example:

In the video, Fred ranks City as his #1 choice for program. During the video, Fred is unable to match at City initially because the couple (David and Erin) have both tentatively matched there, and so Fred is tentatively matched at his #2 program. However, later in the video, David and Erin are removed from their match at City because of... something (lol) yet the algorithm does not go back and try to re-match Fred their even though there is an opening and it was his #1 choice.

So my question is this: If I am Fred, and this were the actual match, would the algorithm attempt to rematch me at my #1 choice if a spot becomes available later on in the process or, since I'm already tentatively matched at my #2 choice, am I stuck there despite the opening?

Hope this wasn't too confusing. Thanks for the tips!

---

Members don't see this ad.

 

[MSTP18]

If a spot for Fred opens up at his #1 he will be unmatched from his #2 and tentatively matched at #1

 

[NotAProgDirector]

You're asking a really good question.

Without couples, the match algorithm is very straightforward. No matter what order you process everyone in, you get the same answer at the end. If someone is unable to match at their #1, or if they are bumped out, then nothing can happen that creates an open position there that they can fill. The match algorithm works down rank lists, it never goes back upwards.

But with couples, the algorithm becomes much more complicated, because as you suggest above one half of a couple might bump you out of a spot, but then that person might lose their spot because their partner was bumped out, and that re-opens a spot that you would still want.

The way the NRMP addresses this is that it runs the algorithm to the end. Then, it recycles through every applicant and asks whether they could be moved to a program higher on their rank list. if they can (like this example), then they are moved there, someone else gets bumped out and the algorithm continues. This process continues until no one can be moved any more.

Mathematically, the match without couples is considered to be a problem of complexity "P", which means it can be solved in polynomial time via a straightforward algorithm. But with couples, the problem becomes "NP" - there isn't a clear algorithm that can be proven to solve for a solution, but given a solution you can test if it's correct in polynomial time. Whether all NP problems are actually in P (i.e. there is an actual solution to solve the problem) is unproven and there is a million dollar prize waiting for anyone whom can prove it.