On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm

Source abstract

In a set of even cardinality n , each member ranks all the others in order of preference. A stable matching is a partition of the set into n /2 pairs, with the property that no two unpaired members both prefer each other to their partners under matching. It is known that for some problem instances no stable matching exists. In 1985, Irving found an O ( n 2 ) two-phase algorithm that would determine, for any instance, whether a stable matching exists, and if so, would find such a matching. Recently, Tan proved that Irving's algorithm, with a modified second phase, always finds a stable cyclic partition of the members set, which is a stable matching when each cycle has length two. In this paper we study a likely behavior of the algorithm under the assumption that an instance of the ranking system is chosen uniformly at random. We prove that the likely number of basic steps, i.e. the individual proposals in the first phase and the rotation eliminations, involving subsets of members in the second phase, is O ( n log n ), and that the likely size of a rotation is O (( n log n ) 1/2 ). We establish a ‘hyperbola law’ analogous to our past result on stable marriages. It states that at every step of the second phase, the product of the rank of proposers and the rank of proposal holders is asymptotic, in probability, to n 3 . We show that every stable cyclic partition is likely to be almost a stable matching, in the sense that at most O (( n log n ) 1/2 ) members can be involved in the cycles of length three or more.