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

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," KRTK-KTI 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. 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.
    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.
    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. 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.
    2. 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.
    3. 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).
    4. 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.
    5. Kawamura, Kohei, 2008. "Communication for Public Goods," SIRE Discussion Papers 2008-25, Scottish Institute for Research in Economics (SIRE).
    6. 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.
    7. 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.
    8. 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.
    9. Francesco De Sinopoli & Leo Ferraris & Giovanna Iannantuoni, 2013. "Electing a parliament," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 40(3), pages 715-737, March.
    10. Antonio Merlo, 2005. "Whither Political Economy? Theories, Facts and Issues," PIER Working Paper Archive 05-033, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania, revised 01 Dec 2005.
    11. Zudenkova, Galina, 2010. "Sincere Lobby Formation," Working Papers 2072/151545, Universitat Rovira i Virgili, Department of Economics.
    12. Zhou, Shiqi & Lin, Meng & He, Jun & Wu, Yuzeng & Wang, Xu, 2025. "Unsupervised clustering research of nuclear power plants under unlabeled unknown fault diagnosis scenario," Energy, Elsevier, vol. 326(C).
    13. César Martinelli & John Duggan, 2014. "The Political Economy of Dynamic Elections: A Survey and Some New Results," Working Papers 1403, Centro de Investigacion Economica, ITAM.
    14. Pengyu Yan & Xiaoqiang Cai & Feng Chu & Debing Ni & Heng He, 2023. "An Incentive Mechanism for Private Parking-Sharing Programs in an Imperfect Information Setting," Service Science, INFORMS, vol. 15(1), pages 3-21, March.
    15. Chenchen Ma & Jing Ouyang & Gongjun Xu, 2023. "Learning Latent and Hierarchical Structures in Cognitive Diagnosis Models," Psychometrika, Springer;The Psychometric Society, vol. 88(1), pages 175-207, March.
    16. Ignacio Ortuño Ortín, 1999. "- A Model Of Voting With Incomplete Information And Opinion Polls," Working Papers. Serie AD 1999-25, Instituto Valenciano de Investigaciones Económicas, S.A. (Ivie).
    17. Aidin Rezaeian & Hamidreza Koosha & Mohammad Ranjbar & Saeed Poormoaied, 2024. "The assignment of project managers to projects in an uncertain dynamic environment," Annals of Operations Research, Springer, vol. 341(2), pages 1107-1134, October.
    18. Tran Hoang Hai, 2020. "Estimation of volatility causality in structural autoregressions with heteroskedasticity using independent component analysis," Statistical Papers, Springer, vol. 61(1), pages 1-16, February.
    19. Matteo Gamalerio & Massimo Morelli & Margherita Negri, 2025. "Electoral Systems and Immigration Policies," Economics Discussion Papers 2503, Department of Economics, The University of St Andrews Business School.
    20. Kobi Kriesler & Shmuel Nitzan, 2009. "Framing-based Choice: A Model of Decision-making Under Risk," Korean Economic Review, Korean Economic Association, vol. 25, pages 65-89.

    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: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 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.