Matching with Couples: Stability and Algorithm

This paper defines a notion of semi-stability for matching problem with couples, which is a natural generalization of, and further identical to, the conventional stability for matching without couples. It is shown that there always exists a semi-stable matching for couples markets with strict preferences, and the set of semi-stable matchings can be partitioned into subsets, each of which forms a distributive lattice. We further prove that a semi-stable matching is stable when couples play reservation strategies. This result perfectly explains the puzzle of NRMP even for finite markets. Moreover, we define a notion of asymptotic stability and present sufficient conditions for a sequential couples market to be asymptotically stable. Another remarkable contribution is that we develop a new algorithm, called Persistent Improvement Algorithm, for finding semi-stable matchings, which is also more efficient than the Gale-Shapley algorithm for finding stable matchings for singles markets. Lastly, this paper investigates the welfare property and incentive issues of semi-stable mechanisms.