You are not logged in to this journal. Log in

Consider a group of $n$ men and $n$ women, each ranking the members of the opposite sex as a potential marriage partner. A matching (marriage) of men and women is called stable if there is no pair (man, woman) who are not matched but prefer each other to their partners in the matching. It is known that, for every instance of the rankings, there is at least one stable matching and that there are instances with exponentially many stable matchings. Assume that the instance is chosen uniformly at random among all $(n!)^{2n}$ possibilities. In this case the likely number of stable matchings is known to be $n^{1/2-o(1)}$, with high probability, and of order $n\ln n$, with probability $0.84$ at least. In this paper we show that the average number of fixed pairs (man, woman), i.e., pairs common to all stable matchings, is asymptotic to $\ln^2 n$. More generally, the average number of women (men) with $k$ stable husbands (wives) is asymptotic to $(\ln ^{k+1} n)/(k-1)!$.