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

The stable marriage problem with ties and restricted edges

Author

Listed:
  • Agnes Cseh

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

  • Klaus Heeger

    (Technische Universität Berlin, Faculty IV Electrical Engineering and Computer Science, Institute of Software Engineering and Theoretical Computer Science, Chair of Algorithmics and Computational Complexity)

Abstract

In the stable marriage problem, a set of men and a set of women are given, each of whom has a strictly ordered preference list over the acceptable agents in the opposite class. A matching is called stable if it is not blocked by any pair of agents, who mutually prefer each other to their respective partner. Ties in the preferences allow for three different definitions for a stable matching: weak, strong and super-stability. Besides this, acceptable pairs in the instance can be restricted in their ability of blocking a matching or being part of it, which again generates three categories of restrictions on acceptable pairs. Forced pairs must be in a stable matching, forbidden pairs must not appear in it, and lastly, free pairs cannot block any matching.Our computational complexity study targetsthe existence of a stable solution for each of the three stability definitions, in the presence of each of the three types of restricted pairs. We solve all cases that were still open. As a byproduct, we also derive that the maximum size weakly stable matching problem is hard even in very dense graphs, which may be of independent interest.

Suggested Citation

  • Agnes Cseh & Klaus Heeger, 2020. "The stable marriage problem with ties and restricted edges," CERS-IE WORKING PAPERS 2007, Institute of Economics, Centre for Economic and Regional Studies.
    • Handle: RePEc:has:discpr:2007
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Peter Biro & Sofya Kiselgof, 2013. "College admissions with stable score-limits," CERS-IE WORKING PAPERS 1306, Institute of Economics, Centre for Economic and Regional Studies.
    2. Yi-Chun Chen & Alfredo Di Tillio & Eduardo Faingold & Siyang Xiong, 2012. "The Strategic Impact of Higher-Order Beliefs," Cowles Foundation Discussion Papers 1875, Cowles Foundation for Research in Economics, Yale University.
    3. Tommy Andersson & Lars Ehlers, 2020. "Assigning Refugees to Landlords in Sweden: Efficient, Stable, and Maximum Matchings," Scandinavian Journal of Economics, Wiley Blackwell, vol. 122(3), pages 937-965, July.
    4. Péter Biró & Sofya Kiselgof, 2015. "College admissions with stable score-limits," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 23(4), pages 727-741, December.
    5. Jui-Kuei Chen & I-Shuo Chen, 2012. "An Inno-Qual performance system for higher education," Scientometrics, Springer;Akadémiai Kiadó, vol. 93(3), pages 1119-1149, 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. Agnes Cseh & Klaus Heeger, 2020. "The stable marriage problem with ties and restricted edges," IEHAS Discussion Papers 2007, Institute of Economics, Centre for Economic and Regional Studies.
    2. Surender Baswana & Partha Pratim Chakrabarti & Sharat Chandran & Yashodhan Kanoria & Utkarsh Patange, 2019. "Centralized Admissions for Engineering Colleges in India," Interfaces, INFORMS, vol. 49(5), pages 338-354, September.
    3. Ágoston, Kolos Csaba & Biró, Péter & Kováts, Endre & Jankó, Zsuzsanna, 2022. "College admissions with ties and common quotas: Integer programming approach," European Journal of Operational Research, Elsevier, vol. 299(2), pages 722-734.
    4. Csató, László & Tóth, Csaba, 2020. "University rankings from the revealed preferences of the applicants," European Journal of Operational Research, Elsevier, vol. 286(1), pages 309-320.
    5. 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.
    6. L'aszl'o Csat'o & Csaba T'oth, 2018. "University rankings from the revealed preferences of the applicants," Papers 1810.04087, arXiv.org, revised Feb 2020.
    7. Ferenc Forgó & László Kóczy & Miklós Pintér, 2015. "Editorial," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 23(4), pages 723-725, December.
    8. Katarína Cechlárová & Tamás Fleiner & David Manlove & Iain McBride & Eva Potpinková, 2015. "Modelling practical placement of trainee teachers to schools," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 23(3), pages 547-562, September.
    9. Adam Kapor & Mohit Karnani & Christopher Neilson, 2019. "Negative Externalities of Off Platform Options and the Efficiency of Centralized Assignment Mechanisms," Working Papers 635, Princeton University, Department of Economics, Industrial Relations Section..
    10. Peter Biro & Tamas Fleiner & Rob Irving, 2013. "Matching Couples with Scarf's Algorithm," CERS-IE WORKING PAPERS 1330, Institute of Economics, Centre for Economic and Regional Studies.
    11. Agnes Cseh & Attila Juhos, 2020. "Pairwise preferences in the stable marriage problem," CERS-IE WORKING PAPERS 2006, Institute of Economics, Centre for Economic and Regional Studies.
    12. Peng Shi, 2022. "Optimal Priority-Based Allocation Mechanisms," Management Science, INFORMS, vol. 68(1), pages 171-188, January.
    13. V. Bhaskar & Caroline Thomas, 2019. "The Culture of Overconfidence," American Economic Review: Insights, American Economic Association, vol. 1(1), pages 95-110, June.
    14. Miralles, Antonio & Pycia, Marek, 2021. "Foundations of pseudomarkets: Walrasian equilibria for discrete resources," Journal of Economic Theory, Elsevier, vol. 196(C).
    15. Martin Hellwig, 2016. "A Homeomorphism Theorem for the Universal Type Space with the Uniform Topology," Discussion Paper Series of the Max Planck Institute for Research on Collective Goods 2016_17, Max Planck Institute for Research on Collective Goods, revised Jul 2022.
    16. Bergemann, Dirk & Morris, Stephen & Takahashi, Satoru, 2017. "Interdependent preferences and strategic distinguishability," Journal of Economic Theory, Elsevier, vol. 168(C), pages 329-371.
    17. Hagen, Martin, 2022. "Tradable immigration quotas revisited," Journal of Public Economics, Elsevier, vol. 208(C).
    18. Kuei-Hu Chang & Yung-Chia Chang & Kai Chain & Hsiang-Yu Chung, 2016. "Integrating Soft Set Theory and Fuzzy Linguistic Model to Evaluate the Performance of Training Simulation Systems," PLOS ONE, Public Library of Science, vol. 11(9), pages 1-29, September.
    19. Mustafa Oğuz Afacan & Umut Dur, 2023. "Strategy‐proof size improvement: is it possible?," Scandinavian Journal of Economics, Wiley Blackwell, vol. 125(2), pages 321-338, April.
    20. Yanbin Li & Feng Zhang & Yun Li & Bingkang Li & Zhen Li, 2019. "Evaluating the Power Grid Investment Behavior in China: From the Perspective of Government Supervision," Energies, MDPI, vol. 12(21), pages 1-23, November.

    More about this item

    Keywords

    stable matchings; restricted edges; complexity;
    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:2007. 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.