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

Pairwise preferences in the stable marriage problem

Author

Listed:
  • Agnes Cseh

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

  • Attila Juhos

    (Department of Computer Science and Information Theory,Budapest University of Technologyand Economics)

Abstract

We study the classical, two-sided stable marriage problem under pairwise preferences. In the most generalsetting, agents are allowed to express their preferences as comparisons of any two of their edges and they alsohave the right to declare a draw or even withdraw from such a comparison. This freedom isthen graduallyrestricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictlyordered lists.We study all cases occurring when combining the three known notions of stability—weak, strongand super-stability—under the assumption that each side of the bipartite market obtains one of the six degreesof orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determinethe complexity of all cases not yet known, and thus give an exact boundary in terms of preference structurebetween tractable and intractable cases.

Suggested Citation

  • 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.
    • Handle: RePEc:has:discpr:2006
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Steven Humphrey, 2001. "Non‐transitive Choice: Event‐Splitting Effects or Framing Effects?," Economica, London School of Economics and Political Science, vol. 68(269), pages 77-96, February.
    2. 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.
    3. Alesina, Alberto & Rosenthal, Howard, 1996. "A Theory of Divided Government," Econometrica, Econometric Society, vol. 64(6), pages 1311-1341, November.
    4. H. W. Kuhn, 1955. "The Hungarian method for the assignment problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 2(1‐2), pages 83-97, March.
    5. 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.
    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. 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.
    2. Kolos Csaba Agoston & Peter Biro & Iain McBride, 2016. "Integer programming methods for special college admissions problems," CERS-IE WORKING PAPERS 1632, Institute of Economics, Centre for Economic and Regional Studies.
    3. 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.
    4. 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.
    5. 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.
    6. Peter Spáč, 2021. "Pork barrel politics and electoral returns at the local level," Public Choice, Springer, vol. 188(3), pages 479-501, September.
    7. Weiqiang Shen & Chuanlin Zhang & Xiaona Zhang & Jinglun Shi, 2019. "A fully distributed deployment algorithm for underwater strong k-barrier coverage using mobile sensors," International Journal of Distributed Sensor Networks, , vol. 15(4), pages 15501477198, April.
    8. Umeno, Luis Gustavo & Bugarin, Maurício Soares, 2008. "Electoral Control in the Presence of Moral Hazard and Adverse Selection," Brazilian Review of Econometrics, Sociedade Brasileira de Econometria - SBE, vol. 28(1), May.
    9. András Frank, 2005. "On Kuhn's Hungarian Method—A tribute from Hungary," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(1), pages 2-5, February.
    10. Andina-Díaz, Ascensión & Feri, Francesco & Meléndez-Jiménez, Miguel A., 2021. "Institutional flexibility, political alternation, and middle-of-the-road policies," Journal of Public Economics, Elsevier, vol. 204(C).
    11. Francisco Jose Veiga & Linda Goncalves Veiga, 2010. "The impact of local and national economic conditions on legislative election results," Applied Economics, Taylor & Francis Journals, vol. 42(13), pages 1727-1734.
    12. Amit Kumar & Anila Gupta, 2013. "Mehar’s methods for fuzzy assignment problems with restrictions," Fuzzy Information and Engineering, Springer, vol. 5(1), pages 27-44, March.
    13. Kawamura, Kohei, 2008. "Communication for Public Goods," SIRE Discussion Papers 2008-25, Scottish Institute for Research in Economics (SIRE).
    14. Régis Renault & Alain Trannoy, 2011. "Assessing the extent of strategic manipulation: the average vote example," SERIEs: Journal of the Spanish Economic Association, Springer;Spanish Economic Association, vol. 2(4), pages 497-513, December.
    15. 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.
    16. Arianna Degan & Antonio Merlo, 2006. "Do Voters Vote Sincerely?," PIER Working Paper Archive 06-008, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania.
    17. Caselli, Francesco & Morelli, Massimo, 2004. "Bad politicians," Journal of Public Economics, Elsevier, vol. 88(3-4), pages 759-782, March.
    18. Nisse, Nicolas & Salch, Alexandre & Weber, Valentin, 2023. "Recovery of disrupted airline operations using k-maximum matching in graphs," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1061-1072.
    19. Arianna Degan & Antonio Merlo, 2011. "A Structural Model Of Turnout And Voting In Multiple Elections," Journal of the European Economic Association, European Economic Association, vol. 9(2), pages 209-245, April.
    20. Parvin Ahmadi & Iman Gholampour & Mahmoud Tabandeh, 2018. "Cluster-based sparse topical coding for topic mining and document clustering," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 12(3), pages 537-558, September.

    More about this item

    Keywords

    stable marriage; intransitivity; acyclic preferences; poset; weakly stablematching; strongly stable matching; super 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:2006. 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.