Paper ID: 8049
The Exchange-Stable Marriage Problem
Discrete Applied Mathematics, volume 152
Page Numbers : 109-122
Publisher: Elsevier Science
URL: This publication is available at this URL.
In this paper we consider instances of stable matching problems, namely the classical Stable Marriage (SM) and Stable Roommates (SR) problems and their variants. In such instances we consider a stability criterion that has recently been proposed, that of exchange-stability. In particular, we prove that ESM - the problem of deciding, given an SM instance, whether an exchange-stable matching exists - is NP-complete. This result is in marked constrast with Gale and Shapley's classical linear-time algorithm for finding a stable matching in an instance of SM. We also extend the result for ESM to the SR case. Finally, we study some variants of ESM under weaker forms of exchange-stability, presenting both polynomial-time solvability and NP-completeness results for the corresponding existence questions.
Keywords: Stable Marriage problem; Stable Roommates problem; Matching; Coalition-exchange-stable; Man-exchange-stable