2024/06/14 by Boris Pittel, Pittel, Boris
Economics, Econometrics and Finance · #05C05 #60C05 #92B10 #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2406.10319
openalex publication_date 2024/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 n1/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 n2-1 pairs. It is shown that the expected number of complete stable matchings tends to 0 if, roughly, p<\tfraclog2 nn and to infinity if p>\tfraclog2 nn. We show that whp: (a) there exists a complete stable matching if p>(9/4)\tfraclog2 nn, (b) the number of unmatched men and women is bounded if p> \tfraclog2nn, and (c) this number grows as a fractional power of n for p<\tfraclog2 nn.