Stable Matching with Couples of Residents
The Hospital-Resident stable matching problem is the quintessential example of a matching market problem. Fortunately, the stable-matching problem, at least with singular residents and hospitals, can be solved efficiently in polynomial time using a generalization of the famous Gale-Shapley algorithm (Ronn 286). However, when resident couples are allowed to submit preference lists of hospitals jointly, the problem becomes far more computationally difficult–there exists no known algorithm to solve this modified problem in polynomial time.
Now, the preference lists of couples are represented as lists of ordered pairs where, if (hi, hj) is the jth ordered pair on preference list of couple (r1, r2), then h1 is the ith most preferred hospital of r1 and h2 is the ith most preferred hospital of r2. What is truly a “stable” matching between residents and hospitals in this problem becomes more complex to define, but is nevertheless based on the following key fact: a matching is stable if and only if it contains no instabilities. Applying this logic to couples, we can say there exists an instability if both a couple of residents and a hospital can be matched to each other to improve both the satisfaction of the couple and the hospital. This can occur if one of the residents in the couple, r, can be matched with a different hospital h’ such that the couple overall prefers this modified match and hospital h’ preferes r to its current match. This instability can occur with one, or potentially both, of the residents in the couple. In a problem framed like this, it is possible that no stable matching between hospitals and couples of residents exists (Ronn 289). Furthermore, determining whether one does in fact exist is even more difficult.
Obviously, it is not difficult to check whether a matching is stable, as one can in polynomial time simply check each edge not included in the matching and determine whether that edge is an instability. Finding whether such a stable matching exists, however, is far more difficult and has been proven to be an NP-complete problem–there exists no known algorithm to solve it in polynomial time. This poses a significant problem for the National Internship matching program, which has long used a variation of Gale-Shapley to match residents with hospitals but lacks any such method for matching couples of residents to hospitals.
Although many heuristics have been developed to create approximate “almost stable” matchings (Manlove 52), it cannot be guaranteed that a better matching exists. At some level, this is inherently unacceptable–error in a heuristic algorithm cannot be the deciding factor that permanently changes human lives, especially on an input size of a measly ~5000. How can a problem so similar to that solved optimally for decades stump every computer scientist on Earth? On the other hand, however, this depressing conclusion is an inevitable consequence of the fundamental limitations of logic. Until the P = NP problem is solved, we’ll have to be content with the possibility of imperfect matches.
References:
- Manlove, D.F., McBride, I. & Trimble, J. “Almost-stable” matchings in the Hospitals / Residents problem with Couples. Constraints 22, 50–72 (2017). https://doi.org/10.1007/s10601-016-9249-7
- Ronn, E. (1990). NP-complete stable matching problems. Journal of Algorithms, 11, 285–304.