2017/07/05 by Pittel, Boris
#05A05 #05A16 #60C05 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1707.01540
Consider the group of n men and n women, each with their own preference list for a potential marriage partner. The stable marriage is a bipartite matching such that no unmatched pair (man, woman) prefer each other to their partners in the matching. Its non-bipartite version, with an even number n of members, is known as the stable roommates problem. Jose Alcalde introduced an alternative notion of exchange-stable, one-sided, matching: no two members prefer each other's partners to their own partners in the matching. Katarina Cechlárová and David Manlove showed that the e-stable matching decision problem is NP-complete for both types of matchings. We prove that the expected number of e-stable matchings is asymptotic to ((πn)/(2))1/2 for two-sided case, and to e1/2 for one-sided case. However, the standard deviation of this number exceeds 1.13n, (1.06n resp.). As an obvious byproduct, there exist instances of preference lists with at least 1.13n (1.06n resp.) e-stable matchings. The probability that there is no matching which is stable and e-stable is at least 1-e^-n1/6+o(1), (1-O(2-n/2) resp.).