Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
7372716 | Mathematical Social Sciences | 2018 | 33 Pages |
Abstract
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 Ïn21â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â2âo(1), (1âO(2ânâ2) resp.).
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Boris Pittel,