On random exchange-stable matchings

Boris Pittel

Mathematical Social Sciences, 2018, vol. 93, issue C, 1-13

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.).

Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165489618300039
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matsoc:v:93:y:2018:i:c:p:1-13

DOI: 10.1016/j.mathsocsci.2018.01.002

Access Statistics for this article

Mathematical Social Sciences is currently edited by J.-F. Laslier

More articles in Mathematical Social Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().