On Constrained Matchings, Stable Under Random Preferences

ABSTRACT Colloquially, there are two groups, men and 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 , at least. Here, we consider the case that the preference lists are still complete, but a generic pair (man, woman) is admissible with probability , independently of all other pairs. It is shown that the expected number of complete stable matchings tends to 0 if, roughly, and to infinity if . We show that whp: (a) there exists a complete stable matching if , (b) the number of unmatched men and women is bounded if , and (c) this number grows as a fractional power of for .