Networks

Bipartite Graphs and Matching in The National Resident Matching Program

https://www.nrmp.org/matching-algorithm/

Last semester in CS 2110 we learned about The National Resident Matching Program (NRMP). This reminded me of our discussion about bipartite graphs from class, and how the nodes are split up into 2 groups, applicants and programs in this case, and a perfect matching is attempted to be found. The NRMP is the program that is used to match residents to their most preferred programs. The way the algorithm works is as follows:

1. The algorithm starts by trying to match each applicant to their most preferred program, if this doesn’t create a perfect matching, then the algorithm will try to match the applicant to their second choice and so on. This continues until there is a match, or the applicant runs out of program options, and that applicant will not be matched.
2. For a match to occur, both an applicant and a program must both match to each other.
   1. There must be an edge that connects the applicant node to the program node.

Here is an example from the video link about the algorithm

In this example here is how the algorithm matches each perspective applicant to their program:

Before I begin let me define a term that the algorithm uses, the term is tentative match. An applicant is a tentative match to a program until the algorithm finishes because there is a chance that the applicant will end up not being matched to that same program at the end of the algorithm.

1. Arthur matches to City
   1. Arthur matches city and city matches Arthur, so they are a tentative match
2. Sunny matches to City
   1. Sunny matches city and city matches Sunny, so they are a tentative match
3.  Joseph matches to city
   1. Since city already has 2 matches, Joseph can no longer be matched to city because he is lower ranked than both Arthur and Sunny who are already matched to City.
4. Joseph matches to general
   1. Joseph matches general and general matches Jospeh, so they are a tentative match
5. Latha matches mercy
   1. Latha matches mercy, but mercy doesn’t match Latha so they are no longer a match
6. Latha matches city
   1. Since city already has 2 matches, Latha can no longer be matched to city because she is lower ranked than both Arthur and Sunny who are already matched to City.
7. Latha matches general
   1. Latha matches general and general matches Latha, so they are a tentative match
8. Darrius matches to city
   1. Even though city already has 2 matches, city ranks Darrius first so he is given a tentative match to city, while Sunny, being the lowest rank among the 3 matched, gets unmatched.
9. Sunny matches to mercy
   1. Sunny matches mercy, but mercy doesn’t not match Sunny, so they are no longer a match
10. The match is final
    1. Latha has no match, Arthur and Darrius match to city, Joseph and Latha match to general.

This can be thought of in another way. In class we talked about bipartite graphs. The bipartite graph for this particular problem would look like this: the left column would be the nodes of the applicants, and the right column would be the nodes of the programs. There is an edge between the nodes if the applicant ranks the program in his/her ranking. Note: For a perfect matching, there can be 2 edges coming into each program because each program has 2 positions.

The applicants are ranked on the left from top to bottom in the order in which they get to choose their program.

There are 2 problems with this bipartite graph.

1. This bipartite graph only represents the rankings of the applicants to the programs. It fails to include the programs rankings of the applicants
   1. An improvement would look like this: add another side which includes the programs rankings of the applicants. This would then mean that an applicant can only be matched to a program if there is an edge from the applicant node on the left to the program node, and an edge from the program node to the applicant node on the right.                                                        
2. This bipartite graphs doesn’t take into account the rankings of the applicants/programs. In this bipartite graph, each edge has the same weight, which is not the case in the actual algorithm.
   1. An improvement would have the edges would have to be weighted based on the respective rankings of the applicants/programs                                                                   

Now with this bipartite type graph, we can find a perfect matching. To find the perfect matching:

1. Start with the top-most applicant that does not have a tentative match, place them in the program for which the edge between them and that program has the lowest weight. Do this only if they have any programs remaining. If they have already tried to match to the program with the lowest weight and failed, at the next iteration through, try matching to the program with weight 1+previous weight.
2. Look to see if the program has the an edge from them to the applicant in the right sided bipartite graph, is so make a tentative match between the applicant and the program, if not, do not make a tentative match between the applicant and the program.
3. If an applicant is attempting to match to a program that already has 2 tentative matches, compare the weights of the program to the tentative matches and the new applicant. Whichever applicant has the lowest weight from program to applicant in the right hand side bipartite graph is no longer tentatively matched to that program.

This will result in a different type of perfect matching than we have seen in class. A perfect matching, in class, means that every node on the left is matched to a different node on the right, and there is an edge between the two nodes. In this example, a perfect matching will be when each of the applicants is matched to a program, or if the applicant runs out of programs, they are allowed to be unmatched to any program node.

Comments

Leave a Reply

Name (required)

Mail (will not be published) (required)

Website