IDEAS home Printed from https://ideas.repec.org/p/has/discpr/2003.html
   My bibliography  Save this paper

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," CERS-IE 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," CERS-IE 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. Vijay V. Vazirani, 2024. "The Assignment Game: New Mechanisms for Equitable Core Imputations," Papers 2402.11437, arXiv.org.
    4. 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.
    5. 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.
    6. Bettina Klaus & Flip Klijn, 2006. "Median Stable Matching for College Admissions," International Journal of Game Theory, Springer;Game Theory Society, vol. 34(1), pages 1-11, April.
    7. Kesten, Onur & Unver, Utku, 2015. "A theory of school choice lotteries," Theoretical Economics, Econometric Society, vol. 10(2), May.
    8. 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.
    9. 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.
    10. Shuji Kijima & Toshio Nemoto, 2012. "On Randomized Approximation for Finding a Level Ideal of a Poset and the Generalized Median Stable Matchings," Mathematics of Operations Research, INFORMS, vol. 37(2), pages 356-371, May.
    11. 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.
    12. Yang Liu & Zhi-Ping Fan & Yan-Ping Jiang, 2018. "Satisfied surgeon–patient matching: a model-based method," Quality & Quantity: International Journal of Methodology, Springer, vol. 52(6), pages 2871-2891, November.
    13. 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.
    14. Agnes Cseh & Robert W. Irving & David F. Manlove, 2017. "The Stable Roommates problem with short lists," CERS-IE WORKING PAPERS 1726, Institute of Economics, Centre for Economic and Regional Studies.
    15. Bettina Klaus & Flip Klijn, 2010. "Smith and Rawls share a room: stability and medians," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 35(4), pages 647-667, October.
    16. 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.
    17. 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.
    18. Jens Gudmundsson, 2019. "Compromises and Rewards: stable and non-manipulable probabilistic matching," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(2), pages 365-392, June.
    19. Juárez, Noelia & Neme, Pablo & Oviedo, Jorge, 2022. "Lattice structure of the random stable set in many-to-many matching markets," Games and Economic Behavior, Elsevier, vol. 132(C), pages 255-273.
    20. Jay Sethuraman & Teo Chung Piaw & Rakesh V. Vohra, 2003. "Integer Programming and Arrovian Social Welfare Functions," Mathematics of Operations Research, INFORMS, vol. 28(2), pages 309-326, May.

    More about this item

    Keywords

    popularmatching; NP-completeness; polynomial algorithm; stable matching;
    All these 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 (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.