IDEAS home Printed from https://ideas.repec.org/p/has/discpr/2003.html

Understanding popular matchings via stable matchings

Author

Listed:
  • Agnes Cseh

    (Centre for Economic and Regional Studies, Institute of Economics)

  • Yuri Faenza

    (IEOR, Columbia University, New York, USA)

  • Telikepalli Kavitha

    (Tata Institute of Fundamental Research, Mumbai, India)

  • Vladlena Powers

    (IEOR, Columbia University, New York, USA)

Abstract

An instance of the marriage problem is given by a graph G together with, for each vertex of G, a strict preference order over its neighbors. A matching M of Gis popular in the marriage instance if M does not lose a head-to-head election against anymatching where vertices are voters. Every stable matching is a min-size popular matching; another subclass of popular matchings that always exist and can be easily computed is theset of dominant matchings. A popular matching M is dominant if M wins the head-to-headelection against any larger matching. Thus every dominant matching is a max-size popularmatching and it is known that the set of dominant matchings is the linear image of the set ofstable matchings in an auxiliary graph. Results from the literature seem to suggest that stableand dominant matchings behave, from a complexity theory point of view, in a very similarmanner within the class of popular matchings.The goal of this paper is to show that indeed there are differences in the tractability of stableand dominant matchings, and to investigate further their importance for popular matchings.First, we show that it is easy to check if all popular matchings are also stable, however it isco-NP-hard to check if all popular matchings are also dominant. Second, we show how somenew and recent hardness results on popular matching problems can be deduced from the NP-hardnessof certain problems on stable matchings, also studied in this paper, thus showing thatstable matchings can be employed not only to show positive results on popular matching (as isknown), but also most negative ones. Problems for which we show new hardness results includefinding a min-size (resp. max-size) popular matching that is not stable (resp. dominant). Aknown result for which we give a new and simple proof is the NP-hardness of finding a popularmatching when G is non-bipartite.

Suggested Citation

  • Agnes Cseh & Yuri Faenza & Telikepalli Kavitha & Vladlena Powers, 2020. "Understanding popular matchings via stable matchings," KRTK-KTI WORKING PAPERS 2003, Institute of Economics, Centre for Economic and Regional Studies.
    • Handle: RePEc:has:discpr:2003
    as

    Download full text from publisher

    File URL: https://www.mtakti.hu/wp-content/uploads/2020/01/CERSIEWP202003.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Agnes Cseh & Chien-Chung Huang & Telikepalli Kavitha, 2017. "Popular matchings with two-sided preferences and one-sided ties," KRTK-KTI WORKING PAPERS 1723, Institute of Economics, Centre for Economic and Regional Studies.
    2. Chung-Piaw Teo & Jay Sethuraman, 1998. "The Geometry of Fractional Stable Matchings and Its Applications," Mathematics of Operations Research, INFORMS, vol. 23(4), pages 874-891, 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. Chen, Peter & Egesdal, Michael & Pycia, Marek & Yenmez, M. Bumin, 2016. "Median stable matchings in two-sided markets," Games and Economic Behavior, Elsevier, vol. 97(C), pages 64-69.
    2. Fleiner, Tamas, 2003. "On the stable b-matching polytope," Mathematical Social Sciences, Elsevier, vol. 46(2), pages 149-158, October.
    3. James Boudreau & Vicki Knoblauch, 2013. "Preferences and the price of stability in matching markets," Theory and Decision, Springer, vol. 74(4), pages 565-589, April.
    4. Federico Echenique & SangMok Lee & Matthew Shum & M. Bumin Yenmez, 2021. "Stability and Median Rationalizability for Aggregate Matchings," Games, MDPI, vol. 12(2), pages 1-15, April.
    5. Gutin, Gregory Z. & Neary, Philip R. & Yeo, Anders, 2024. "Finding all stable matchings with assignment constraints," Games and Economic Behavior, Elsevier, vol. 148(C), pages 244-263.
    6. Martin Van der Linden, 2019. "Deferred acceptance is minimally manipulable," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(2), pages 609-645, June.
    7. Teo Chung Piaw & Jay Sethuraman & Rakesh V. Vohra, 2001. "Integer Programming and Arrovian Social Welfare Functions," Discussion Papers 1316, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    8. Pavlos Eirinakis & Dimitrios Magos & Ioannis Mourtos & Panayiotis Miliotis, 2014. "Polyhedral Aspects of Stable Marriage," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 656-671, August.
    9. Agnes Cseh & Robert W. Irving & David F. Manlove, 2017. "The Stable Roommates problem with short lists," KRTK-KTI WORKING PAPERS 1726, Institute of Economics, Centre for Economic and Regional Studies.
    10. Schwarz, Michael & Yenmez, M. Bumin, 2011. "Median stable matching for markets with wages," Journal of Economic Theory, Elsevier, vol. 146(2), pages 619-637, March.
    11. Jay Sethuraman & Chung-Piaw Teo & Liwen Qian, 2006. "Many-to-One Stable Matching: Geometry and Fairness," Mathematics of Operations Research, INFORMS, vol. 31(3), pages 581-596, August.
    12. Klaus, B.E. & Klijn, F., 2007. "Smith and Rawls share a room," Research Memorandum 026, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    13. Manjunath, Vikram & Turhan, Bertan, 2016. "Two school systems, one district: What to do when a unified admissions process is impossible," Games and Economic Behavior, Elsevier, vol. 95(C), pages 25-40.
    14. Nicolò, Antonio & Salmaso, Pietro & Sen, Arunava & Yadav, Sonal, 2023. "Stable sharing," Games and Economic Behavior, Elsevier, vol. 141(C), pages 337-363.
    15. Agnes Cseh & Telikepalli Kavitha, 2020. "Popular Matchings in Complete Graphs," KRTK-KTI WORKING PAPERS 2004, Institute of Economics, Centre for Economic and Regional Studies.
    16. Boudreau, James W. & Knoblauch, Vicki, 2014. "What price stability? Social welfare in matching markets," Mathematical Social Sciences, Elsevier, vol. 67(C), pages 27-33.
    17. Kesten, Onur & Unver, Utku, 2015. "A theory of school choice lotteries," Theoretical Economics, Econometric Society, vol. 10(2), May.
    18. Kominers, Scott Duke, 2010. "Matching with preferences over colleagues solves classical matching," Games and Economic Behavior, Elsevier, vol. 68(2), pages 773-780, March.
    19. Aditya Kuvalekar & Antonio Romero-Medina, 2024. "A fair procedure in a marriage market," Review of Economic Design, Springer;Society for Economic Design, vol. 28(3), pages 533-550, September.
    20. Neme, Pablo & Oviedo, Jorge, 2021. "On the set of many-to-one strongly stable fractional matchings," Mathematical Social Sciences, Elsevier, vol. 110(C), pages 1-13.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    JEL classification:

    • C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:has:discpr:2003. 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: Nora Horvath The email address of this maintainer does not seem to be valid anymore. Please ask Nora Horvath to update the entry or send us the correct address (email available below). General contact details of provider: https://edirc.repec.org/data/iehashu.html .

    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.