<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>8482</REFNUM><AUTHORS><AUTHOR>Scott,S.</AUTHOR></AUTHORS><YEAR>2005</YEAR><TITLE>A Study Of Stable Marriage Problems With Ties</TITLE><PLACE_PUBLISHED>DCS Technical Report Series</PLACE_PUBLISHED><PUBLISHER>Dept of Computing Science, University of Glasgow</PUBLISHER><ISBN>TR-2005-234</ISBN><LABEL>Scott:2005:8482</LABEL><ABSTRACT>We study a number of variants of the <i>Stable Marriage</i> 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 <i>super-stability</i>, <i>strong stability</i> and <i>weak stability</i>. 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.
<p>
The first variant that we study is the <i>Hospitals/Residents</i> 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 <i>Stable Roommates</i> 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.
<p>
We then introduce the <i>Stable Fixtures</i> 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.
<p>
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 <i>rotation</i>, 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 <i>meta-rotations</i>. We then use this structure to show that we can find an <i>egalitarian</i> super-stable matching, a <i>minimum regret</i> super-stable matching and all the <i>super-stable pairs</i> in polynomial-time, and generate all the super-stable matchings with polynomial-time between successive matchings.
<p>
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 <i>forbidden</i> is NP-complete. By contrast we present a linear-time algorithm for finding a super-stable matching in such an instance.
<p>
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 <i>man minimum regret</i> weakly stable matching in time linear in