On random exchange-stable matchings

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'arov'a 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 $\left(\frac{\pi n}{2}\right)^{1/2}$fortwo-sidedcase,andto$e^{1/2}$ for one-sided case. However, the standard deviation of this number exceeds ${1.13}^n$, (${1.06}^n$ resp.). As an obvious byproduct, there exist instances of preference lists with at least ${1.13}^n$ (${1.06}^n$ resp.) e-stable matchings. The probability that there is no matching which is stable and e-stable is at least $1-e^{-n^{1\mathrm{/}6+o(1)}}$, ($1-O(2^{-n\mathrm{/}2})$ resp.).