Paper ID: 9319
The Stable Roommates problem with Globally-Ranked Pairs
Internet Mathematics, volume 5, number 4
Page Numbers : 493-515
URL: This publication is available at this URL.
We introduce a restriction of the stable roommates problem
in which roommate pairs are ranked globally. In contrast to
the unrestricted problem, weakly stable matchings are
guaranteed to exist, and additionally, can be found in
polynomial time. However, it is still the case that strongly
stable matchings may not exist, and so we consider the
complexity of finding weakly stable matchings with various
desirable properties. In particular, we present a
polynomial-time algorithm to find a rank-maximal (weakly
stable) matching. This is the first generalization of the
algorithm due to Irving et al. [R.W. Irving, D. Michail, K.
Mehlhorn, K. Paluch, and K. Telikepalli, Rank-maximal
matchings, ACM Transactions on Algorithms, 2(4):602–610,
2006] to a non-bipartite setting. Also, we describe several
hardness results in an even more restricted setting for each
of the problems of finding weakly stable matchings that are
of maximum size, are egalitarian, have minimum regret, and
admit the minimum number of weakly blocking pairs.
Keywords: Stable Roommates problem; Globally ranked pairs; Rank-maximal matchings; Egalitarian weakly stable matching