Math 428/529: Discrete Optimization

Suppose that there are \(n\) companies and \(n\) interns and every company wants to hire exactly one intern. In other words, we are looking for a matching in the complete bipartite graph between the set of companies and interns. Of course, we want to find the best matching, under some definition of “best.”

At first, one may think that the maximum weight matching algorithm presented in Section 3.3 is perfectly suited for this job. However, in a free society, the maximum weight perfect matching may lead to poor outcomes. For example, if there is an intern who prefers another company over the one that they have been matched to, and that company simultaneously prefers that intern over the one that they were assigned, then that company may fire their current intern and send a job offer to the other one. If we are trying to assign interns to jobs in practice, it might be nice to avoid such a situation.

This leads us to the topic of this section, the Stable Marriage Problem. In this problem, each intern has a ranking of all \(n\) companies based on their preferences and each company has a ranking of all \(n\) candidates. All of these rankings are strict (there are no ties). A perfect matching of interns to companies is unstable if there exists an intern \(i\) and a company \(c\) such that \(i\) prefers \(c\) over the company that they are matched to and, simultaneously, \(c\) prefers \(i\) over the intern that they are matched to. Otherwise, it is stable. As it turns out, stable matchings always exists and, moreover, they can be found in polynomial time.

Now, let us show that this algorithm always outputs a stable perfect matching. First, let us show that this algorithm reaches a perfect matching. If it does not, then there must be a company \(c\) that gets rejected from all \(n\) interns. However, this implies that every intern receives at least one offer (since they received one from \(c\)). However, every intern that receives an offer eventually gets matched with a company, because they never reject all of their offers. So, this means that, at the end of the algorithm, every intern has a pending offer. No company ever has two pending offers because, in each round, the only companies that make offers are the ones that do not already have a pending offer. So, all interns get matched to a company and no two companies are matched to the same intern. This implies that all companies must get matched as well because there are the same number of companies as interns. To see that the matching is stable, we observe that, for any company, they have already made offers to each intern that they would prefer over the one that they are matched to which were rejected because that intern had a better offer at the time. Moreover, that intern will only reject this better offer if they get an even better one later on. So, the matching is stable. The running time is clearly \(O(n^2)\) because no company makes an offer to the same candidate twice.

The correctness of the above algorithm implies the following.

For general bipartite graphs (i.e. bipartite graphs that are not necessarily complete or balanced) one can always obtain a stable matching, but it may not be perfect. In this setting, a matching \(M\) is stable if, for every edge \(xy\in E(G)\setminus M\text{,}\) either \(M\) matches \(x\) to a vertex that it prefers over \(y\text{,}\) or it matches \(y\) to a vertex that it prefers over \(x\text{.}\)