Paper ID: 7748
DCS Tech Report Number: TR-2004-177
Man-Exchange Stable Marriage
Tech Report (internal)
Page Numbers : 1-11
We study a variant of the classical stable marriage problem in which there is an additional requirement for a stable matching, namely that there should not be two men each of whom prefers the other's partner in the matching. The problem is motivated by the experience of practical medical matching schemes that use stable matchings, where two students have been known to register a complaint on discovering that each of them would prefer the other's allocation. We show that the problem of deciding whether an instance of the classical stable marriage problem admits a stable matching with this additional man-exchange stability property is NP-complete. This implies a similar result for the hospitals/residents problem, which is a many-to-one generalisation of stable marriage.
Keywords: Algorithms, Computational complexity.