Paper ID: 8482
DCS Tech Report Number: TR-2005-234
A Study Of Stable Marriage Problems With Ties
Tech Report (internal)
DCS Technical Report Series
Page Numbers :
Publisher: Dept of Computing Science, University of Glasgow
We study a number of variants of the Stable Marriage problem. Such problems have a long history, but there has been an upsurge in interest in recent years as the various possibilities that arise when ties are allowed in preference lists have been studied. The inclusion of ties in preference lists gives rise to three different versions of stability, so-called super-stability, strong stability and weak stability. The study of these three versions has thrown up a number of challenging problems, and this thesis contributes a range of new results in some of these areas.
The first variant that we study is the Hospitals/Residents problem with ties, a many-to-one variant of the Stable Marriage problem. We present two different polynomial-time algorithms for finding a strongly stable matching, one favouring the residents and the other the hospitals. We also study the Stable Roommates problem with Ties, a non-bipartite variant of the Stable Marriage problem, and we again present a polynomial-time algorithm for finding a strongly stable matching.
We then introduce the Stable Fixtures problem, a many-to-many variant of the Stable Roommates problem, initially focusing on the version in which preferences are strict. We present an algorithm, which runs in time linear in the input size, to find a stable matching. We then consider the problem when ties are allowed in the preference lists, and we present an algorithm, again linear in the input size, to find a super-stable matching.
We also study the structure underlying the set of super-stable matchings for the Stable Marriage problem with ties (SMT). We extend the concept of a rotation, essentially the minimum difference between stable matchings, to super-stability, and show that we can construct a directed acyclic graph to represent precedence amongst these meta-rotations. We then use this structure to show that we can find an egalitarian super-stable matching, a minimum regret super-stable matching and all the super-stable pairs in polynomial-time, and generate all the super-stable matchings with polynomial-time between successive matchings.
We then explore some of the issues arising in weak stability, where a number of the key problems are known to be NP-hard. We show a relationship between the sizes of weakly stable matchings and the size of a strongly stable matching in an instance of SMT, and also in a number of the other variants. We give an improved approximation algorithm for finding a maximum cardinality weakly stable matching when ties are sparse. Efficient generation of weakly stable matchings remains an open problem. As a first step in this direction we show how to determine whether an instance of SMT admits a unique weakly stable matching. However, we also show that the problem of determining whether there is a weakly stable matching for an instance of SMT in which some pairs are forbidden is NP-complete. By contrast we present a linear-time algorithm for finding a super-stable matching in such an instance.
Finally we consider the special case of SMT in which one or both sets of participants have preference lists which are sublists of a master list. We show that many weak stability problems remain NP-hard even with this remarkably strong restriction, though there are a limited number of exceptions. We show that we can find an egalitarian weakly stable matching, a minimum regret weakly stable matching, and a man minimum regret weakly stable matching in time linear in the number of men in the instance, if all preference lists are complete and both sets have lists that are sublists of a master list. Under the same restrictions we show that we can find all the stable pairs in time linear in the number of stable pairs, and generate all the weakly stable matchings with time linear in the number of men between successive generations.