On the Likely Number of Solutions for the Stable Marriage Problem

Source abstract

An instance of a size- n stable marriage problem involves n men and n women, each individually ranking all members of opposite sex in order of preference as a potential marriage partner. A complete matching, a set of n marriages, is called stable if no unmatched man and woman prefer each other to their partners in the matching. It is known that, for every instance of marriage partner preferences, there exists at least one stable matching, and that there are instances with exponentially many stable matchings. Our focus is on a random instance chosen uniformly from among all ( n !) 2 n possible instances. The second author had proved that the expected number of stable marriages is of order n ln n , while its likely value is of order n 1/2− o (1) at least. In this paper the second moment of that number is shown to be of order ( n ln n ) 2 . The combination of the two moment estimates implies that the fraction of problem instances with roughly cn ln n solutions is at least 0.84. Whether this fraction is asymptotic to 1 remains an open question.