One way to find a matching for a bipartite graph
In class, we learned about bipartite graphs and matchings. We went over constricted sets and how to tell if an instance cannot have a matching. However, we did not go over any algorithms to find a stable matching.
One algorithm is the Gale-Shapley algorithm:
We can consider a set of hospitals and a set of residents (stable matching means that no hospital and resident prefer each other to their pairings). First, the hospitals rank all of the residents and the residents rank all of the hospitals. As long as there is at least one unmatched hospital, we choose that unmatched hospital. The hospital goes through its list of residents, proposing to each one until a resident accepts. If the resident is unmatched, they accept the hospital and and we add this matching edge to the set. If the resident is matched, they accept the hospital when they prefer it to their current matching and we then remove that matching and add the new one to the set. Otherwise, the resident rejects and the hospital keeps going through its list of residents. This algorithm is guaranteed to find a stable matching, assuming one exists.
This algorithm has some interesting properties. We call the matching between a resident and a hospital valid if it is stable. The Gale-Shapley algorithm returns a stable matching such that each hospital is matched with their best valid match, and each resident is matched with their worst. When Gale and Shapley did their work, they looked at the problem as a marriage problem, in which there is a set of men with preferences of women and set of women with preferences of men. In the marriage problem, this means that the men always get their top choice valid matching wife but the women always get their worst choice valid match. This is clearly unfair, as the women are worse off, and there are no unstable pairings so the women will have no chance of improving their matching. However, as the inputs get very large, it is unlikely that there will be more than one possible matching and the Gale-Shapley algorithm will return the only one.
This way of matching can be applied to the marriage problem, hospitals/residents, and many other scenarios. However, it is a little bit limited as each side of the graph must rank the other. The algorithm would need some modification in an example in which each vertex on the graph had binary preferences. That is, each hospital would take certain residents and never take others, and vice versa.
Source: http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html