On constrained matchings, stable under random preferences

Abstract

Colloquially, there are two groups, $n$ men and $n$ women, each man (woman) ranking women (men) as potential marriage partners. A complete matching is called stable if no unmatched pair prefer each other to their partners in the matching. If some pairs are not admissible, then such a matching may not exist, but a properly defined partial stable matching exists always, and all such matchings involve the same, equi-numerous, groups of men and women. Earlier we proved that, for the complete, random, preference lists, with high probability (whp) the total number of complete stable matchings is, roughly, of order $n^{1/2}$, at least. Here we consider the case that the preference lists are still complete, but a generic pair (man,woman) is admissible with probability $p$, independently of all other $n^2-1$ pairs. It is shown that the expected number of complete stable matchings tends to $0$ if, roughly, $p<\frac{{\log }^{2}n}{n}$ and to infinity if $p>\frac{{\log }^{2}n}{n}$. We show that whp: (a) there exists a complete stable matching if $p>(9/4)\frac{{\log }^{2}n}{n}$, (b) the number of unmatched men and women is bounded if $p>\frac{{\log }^{2}n}{n}$, and (c) this number grows as a fractional power of $n$ for $p<\frac{{\log }^{2}n}{n}$.