IDEAS home Printed from https://ideas.repec.org/a/eee/matsoc/v93y2018icp1-13.html
   My bibliography  Save this article

On random exchange-stable matchings

Author

Listed:
  • Pittel, Boris

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

Suggested Citation

  • Pittel, Boris, 2018. "On random exchange-stable matchings," Mathematical Social Sciences, Elsevier, vol. 93(C), pages 1-13.
    • Handle: RePEc:eee:matsoc:v:93:y:2018:i:c:p:1-13
    DOI: 10.1016/j.mathsocsci.2018.01.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0165489618300039
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.mathsocsci.2018.01.002?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Robert W. Irving, 2008. "Stable matching problems with exchange restrictions," Journal of Combinatorial Optimization, Springer, vol. 16(4), pages 344-360, November.
    2. Itai Ashlagi & Yash Kanoria & Jacob D. Leshno, 2017. "Unbalanced Random Matching Markets: The Stark Effect of Competition," Journal of Political Economy, University of Chicago Press, vol. 125(1), pages 69-98.
    3. José Alcalde, 1994. "Exchange-proofness or divorce-proofness? Stability in one-sided matching markets," Review of Economic Design, Springer;Society for Economic Design, vol. 1(1), pages 275-287, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Piazza, Adriana & Torres-Martínez, Juan Pablo, 2024. "Coalitional stability in matching problems with externalities and random preferences," Games and Economic Behavior, Elsevier, vol. 143(C), pages 321-339.
    2. Wouter Vergote, 2019. "Revisiting stability in one-to-one matching problems," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 7(1), pages 59-75, May.
    3. Vergote, W., 2015. "One-to-One Matching Problems with Location Restrictions," LIDAM Discussion Papers CORE 2015054, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Gutin, Gregory Z. & Neary, Philip R. & Yeo, Anders, 2023. "Unique stable matchings," Games and Economic Behavior, Elsevier, vol. 141(C), pages 529-547.
    5. Michael Bates & Michael Dinerstein & Andrew C. Johnston & Isaac Sorkin, 2022. "Teacher Labor Market Equilibrium and Student Achievement," CESifo Working Paper Series 9551, CESifo.
    6. Michael Greinecker & Christopher Kah, 2018. "Pairwise stable matching in large economies," Graz Economics Papers 2018-01, University of Graz, Department of Economics.
    7. Azar Abizada, 2019. "Exchange-stability in roommate problems," Review of Economic Design, Springer;Society for Economic Design, vol. 23(1), pages 3-12, June.
    8. Saraiva, Gustavo, 2021. "An improved bound to manipulation in large stable matches," Games and Economic Behavior, Elsevier, vol. 129(C), pages 55-77.
    9. Ortega, Josué & Klein, Thilo, 2022. "Improving Efficiency and Equality in School Choice," QBS Working Paper Series 2022/02, Queen's University Belfast, Queen's Business School.
    10. Ortega, Josué, 2018. "Social integration in two-sided matching markets," Journal of Mathematical Economics, Elsevier, vol. 78(C), pages 119-126.
    11. Liu, Ce, 2023. "Stability in repeated matching markets," Theoretical Economics, Econometric Society, vol. 18(4), November.
    12. Alcalde, Jose & Revilla, Pablo, 2004. "Researching with whom? Stability and manipulation," Journal of Mathematical Economics, Elsevier, vol. 40(8), pages 869-887, December.
    13. Marcelo Ariel Fernandez & Kirill Rudov & Leeat Yariv, 2022. "Centralized Matching with Incomplete Information," American Economic Review: Insights, American Economic Association, vol. 4(1), pages 18-33, March.
    14. Boris Pittel, 2019. "On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 122-146, February.
    15. Richter, Michael & Rubinstein, Ariel, 2024. "Unilateral stability in matching problems," Journal of Economic Theory, Elsevier, vol. 216(C).
    16. Hugo Gimbert & Claire Mathieu & Simon Mauras, 2021. "Constrained School Choice with Incomplete Information," Papers 2109.09089, arXiv.org.
    17. Papai, Szilvia, 2004. "Unique stability in simple coalition formation games," Games and Economic Behavior, Elsevier, vol. 48(2), pages 337-354, August.
    18. Yannai A. Gonczarowski & Ori Heffetz & Clayton Thomas, 2022. "Strategyproofness-Exposing Mechanism Descriptions," Papers 2209.13148, arXiv.org, revised Jul 2023.
    19. Kolos Csaba Ágoston & Péter Biró & Iain McBride, 2016. "Integer programming methods for special college admissions problems," Journal of Combinatorial Optimization, Springer, vol. 32(4), pages 1371-1399, November.
    20. Guillaume Haeringer & Vincent Iehlé, 2019. "Two-Sided Matching with (Almost) One-Sided Preferences," American Economic Journal: Microeconomics, American Economic Association, vol. 11(3), pages 155-190, August.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:matsoc:v:93:y:2018:i:c:p:1-13. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/505565 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.