On the likely number of stable marriages.
Author
Lennon, Craig Thomas
Year
2007
Advisor
Pittel, Boris G.
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!)^{2n} possible instances. Boris Pittel 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. Here it is shown that the second order moment of that number is of order (n ln (n))^2. The combination of the two moment estimates implies that the fraction of problem instances with roughly c n ln(n) solutions is 0.84, at least.
Lennon, Craig Thomas
Year
2007
Advisor
Pittel, Boris G.
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!)^{2n} possible instances. Boris Pittel 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. Here it is shown that the second order moment of that number is of order (n ln (n))^2. The combination of the two moment estimates implies that the fraction of problem instances with roughly c n ln(n) solutions is 0.84, at least.