IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v24y2012i2p245-259.html
   My bibliography  Save this article

Finding All Stable Pairs and Solutions to the Many-to-Many Stable Matching Problem

Author

Listed:
  • Pavlos Eirinakis

    (Department of Management Science and Technology, Athens University of Economics and Business, 10434 Athens, Greece)

  • Dimitrios Magos

    (Department of Informatics, Technological Educational Institute of Athens, 12210 Egaleo, Greece)

  • Ioannis Mourtos

    (Department of Management Science and Technology, Athens University of Economics and Business, 10434 Athens, Greece)

  • Panayiotis Miliotis

    (Department of Management Science and Technology, Athens University of Economics and Business, 10434 Athens, Greece)

Abstract

The many-to-many stable matching problem (MM), defined in the context of a job market, asks for an assignment of workers to firms satisfying the quota of each agent and being stable, pairwise or setwise, with respect to given preference lists or relations. In this paper, we propose a time-optimal algorithm that identifies all stable worker--firm pairs and all stable assignments under pairwise stability, individual preferences, and the max-min criterion. We revisit the poset graph of rotations to obtain an optimal algorithm for enumerating all solutions to the MM and an improved algorithm finding the minimum-weight one. Furthermore, we establish the applicability of all aforementioned algorithms under more complex preference and stability criteria. In a constraint programming context, we introduce a constraint that models the MM and an encoding of the MM as a constraint satisfaction problem. Finally, we provide a series of computational results, including the case where side constraints are imposed.

Suggested Citation

  • Pavlos Eirinakis & Dimitrios Magos & Ioannis Mourtos & Panayiotis Miliotis, 2012. "Finding All Stable Pairs and Solutions to the Many-to-Many Stable Matching Problem," INFORMS Journal on Computing, INFORMS, vol. 24(2), pages 245-259, May.
  • Handle: RePEc:inm:orijoc:v:24:y:2012:i:2:p:245-259
    DOI: 10.1287/ijoc.1110.0449
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.1110.0449
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.1110.0449?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
    ---><---

    References listed on IDEAS

    as
    1. Charles Blair, 1988. "The Lattice Structure of the Set of Stable Matchings with Multiple Partners," Mathematics of Operations Research, INFORMS, vol. 13(4), pages 619-628, November.
    2. Echenique, Federico & Oviedo, Jorge, 2006. "A theory of stability in many-to-many matching markets," Theoretical Economics, Econometric Society, vol. 1(2), pages 233-273, June.
    3. David Gale, 2001. "The Two-Sided Matching Problem: Origin, Development And Current Issues," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 3(02n03), pages 237-252.
    4. Jean-Claude Picard, 1976. "Maximal Closure of a Graph and Applications to Combinatorial Problems," Management Science, INFORMS, vol. 22(11), pages 1268-1272, July.
    5. Fleiner, Tamas, 2003. "On the stable b-matching polytope," Mathematical Social Sciences, Elsevier, vol. 46(2), pages 149-158, October.
    6. Martinez, Ruth & Masso, Jordi & Neme, Alejandro & Oviedo, Jorge, 2004. "An algorithm to compute the full set of many-to-many stable matchings," Mathematical Social Sciences, Elsevier, vol. 47(2), pages 187-210, March.
    7. Sotomayor, Marilda, 1999. "Three remarks on the many-to-many stable matching problem," Mathematical Social Sciences, Elsevier, vol. 38(1), pages 55-70, July.
    8. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    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. Ayşe Yazıcı, 2017. "Probabilistic stable rules and Nash equilibrium in two-sided matching problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(1), pages 103-124, March.
    2. Paula Jaramillo & Çaǧatay Kayı & Flip Klijn, 2014. "On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(4), pages 793-811, April.
    3. Bettina Klaus & David F. Manlove & Francesca Rossi, 2014. "Matching under Preferences," Cahiers de Recherches Economiques du Département d'économie 14.07, Université de Lausanne, Faculté des HEC, Département d’économie.
    4. Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 537-569, March.
    5. Hatfield, John William & Kominers, Scott Duke, 2017. "Contract design and stability in many-to-many matching," Games and Economic Behavior, Elsevier, vol. 101(C), pages 78-97.
    6. Klijn, Flip & Yazıcı, Ayşe, 2014. "A many-to-many ‘rural hospital theorem’," Journal of Mathematical Economics, Elsevier, vol. 54(C), pages 63-73.
    7. Danilov, V., 2021. "Stable systems of schedule contracts," Journal of the New Economic Association, New Economic Association, vol. 51(3), pages 12-29.
    8. Somouaoga Bonkoungou, 2021. "Decentralized college admissions under single application," Review of Economic Design, Springer;Society for Economic Design, vol. 25(1), pages 65-91, June.
    9. Hideo Konishi & M. Utku Ünver, 2003. "Credible Group Stability in Multi-Partner Matching Problems," Working Papers 2003.115, Fondazione Eni Enrico Mattei.
    10. Klaus, Bettina & Walzl, Markus, 2009. "Stable many-to-many matchings with contracts," Journal of Mathematical Economics, Elsevier, vol. 45(7-8), pages 422-434, July.
    11. Jiao, Zhenhua & Tian, Guoqiang, 2017. "The Blocking Lemma and strategy-proofness in many-to-many matchings," Games and Economic Behavior, Elsevier, vol. 102(C), pages 44-55.
    12. Westkamp, Alexander, 2010. "Market Structure and Matching with Contracts," Bonn Econ Discussion Papers 02/2010, University of Bonn, Bonn Graduate School of Economics (BGSE).
    13. Konishi, Hideo & Unver, M. Utku, 2006. "Credible group stability in many-to-many matching problems," Journal of Economic Theory, Elsevier, vol. 129(1), pages 57-80, July.
    14. Bando, Keisuke & Hirai, Toshiyuki, 2021. "Stability and venture structures in multilateral matching," Journal of Economic Theory, Elsevier, vol. 196(C).
    15. Echenique, Federico & Yenmez, M. Bumin, 2007. "A solution to matching with preferences over colleagues," Games and Economic Behavior, Elsevier, vol. 59(1), pages 46-71, April.
    16. Tamás Fleiner, 2003. "A Fixed-Point Approach to Stable Matchings and Some Applications," Mathematics of Operations Research, INFORMS, vol. 28(1), pages 103-126, February.
    17. Tamás Fleiner & Ravi Jagadeesan & Zsuzsanna Jankó & Alexander Teytelboym, 2019. "Trading Networks With Frictions," Econometrica, Econometric Society, vol. 87(5), pages 1633-1661, September.
    18. Pérez-Castrillo, David & Sotomayor, Marilda, 2019. "Comparative statics in the multiple-partners assignment game," Games and Economic Behavior, Elsevier, vol. 114(C), pages 177-192.
    19. Klaus, Bettina & Klijn, Flip, 2017. "Non-revelation mechanisms for many-to-many matching: Equilibria versus stability," Games and Economic Behavior, Elsevier, vol. 104(C), pages 222-229.
    20. Tam'as Fleiner & Zsuzsanna Jank'o & Ildik'o Schlotter & Alexander Teytelboym, 2018. "Complexity of Stability in Trading Networks," Papers 1805.08758, arXiv.org, revised Feb 2019.

    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:inm:orijoc:v:24:y:2012:i:2:p:245-259. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: . General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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: Matthew Walls (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.