IDEAS home Printed from https://ideas.repec.org/a/ksa/szemle/2061.html

Egyoldali párosítási piacok nehézségi eredményei magasabb dimenzióban
[Hardness results of one-sided matching markets in higher dimensions]

Author

Listed:
  • Kondor, Gábor

Abstract

Az egyoldali párosítási piacok tekintetében az irodalom nagyrészt kétfős párok létrehozását vizsgálja. A gyakorlati problémáknál - mint például a vese csere prog ra mok vagy a szobatársak beosztása - ugyanakkor előfordul, hogy háromfős vagy nagyobb csoportok létrehozása a feladat. A vesecserékre található olyan gyakorlati megoldás, amely súlyozott párosítási feladatra vezethető vissza. Ez alapján meghatározunk egy gráfparticionálási problémával ekvivalens megoldást, amelynek eredménye Pareto-hatékony. Megmutatjuk, hogy a felírt gráf particio ná lási és - ezek speciális eseteként - az egyenletes klaszterezési feladatok megoldása magasabb dimenzióban, vagyis legalább háromfős csoportok kialakítására általánosan NP-nehéz. A gyakorlatban ez azt jelenti, hogy bár biztosan tudjuk, hogy e problémákra létezik optimális megoldás, azt a résztvevők nagyobb száma esetén - jelen ismereteink szerint - képtelenek vagyunk meghatározni.* Journal of Economic Literature (JEL) kód: C78, D47.

Suggested Citation

  • Kondor, Gábor, 2022. "Egyoldali párosítási piacok nehézségi eredményei magasabb dimenzióban [Hardness results of one-sided matching markets in higher dimensions]," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(7), pages 825-840.
    • Handle: RePEc:ksa:szemle:2061
    DOI: 10.18414/KSZ.2022.7-8.825
    as

    Download full text from publisher

    File URL: http://www.kszemle.hu/tartalom/letoltes.php?id=2061
    Download Restriction: Registration and subscription. 3-month embargo period to non-subscribers.
    File URL: https://libkey.io/10.18414/KSZ.2022.7-8.825?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Atay, Ata & Mauleon, Ana & Vannetelbosch, Vincent, 2021. "A bargaining set for roommate problems," Journal of Mathematical Economics, Elsevier, vol. 94(C).
    2. Chung, Kim-Sau, 2000. "On the Existence of Stable Roommate Matchings," Games and Economic Behavior, Elsevier, vol. 33(2), pages 206-230, November.
    3. Alvin E. Roth, 2012. "The Theory and Practice of Market Design," Nobel Prize in Economics documents 2012-5, Nobel Prize Committee.
    4. Roth, Alvin E, 1984. "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory," Journal of Political Economy, University of Chicago Press, vol. 92(6), pages 991-1016, December.
    5. Roth, Alvin E & Vande Vate, John H, 1990. "Random Paths to Stability in Two-Sided Matching," Econometrica, Econometric Society, vol. 58(6), pages 1475-1480, November.
    6. Morrill, Thayer, 2010. "The roommates problem revisited," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1739-1756, September.
    7. Diamantoudi, Effrosyni & Miyagawa, Eiichi & Xue, Licun, 2004. "Random paths to stability in the roommate problem," Games and Economic Behavior, Elsevier, vol. 48(1), pages 18-28, July.
    8. Woeginger, Gerhard J., 2013. "A hardness result for core stability in additive hedonic games," Mathematical Social Sciences, Elsevier, vol. 65(2), pages 101-104.
    9. Roth, Alvin E, 1991. "A Natural Experiment in the Organization of Entry-Level Labor Markets: Regional Markets for New Physicians and Surgeons in the United Kingdom," American Economic Review, American Economic Association, vol. 81(3), pages 415-440, June.
    10. Mingers, J. & O'Brien, F. A., 1995. "Creating student groups with similar characteristics: A heuristic approach," Omega, Elsevier, vol. 23(3), pages 313-321, June.
    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. Konishi, Hideo & Unver, M. Utku, 2006. "Credible group stability in many-to-many matching problems," Journal of Economic Theory, Elsevier, vol. 129(1), pages 57-80, July.
    2. Hideo Konishi & M. Utku Ünver, 2003. "Credible Group Stability in Multi-Partner Matching Problems," Working Papers 2003.115, Fondazione Eni Enrico Mattei.
    3. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    4. repec:ehu:ikerla:13424 is not listed on IDEAS
    5. Peter Biro & Elena Iñarra & Elena Molis, 2014. "A new solution for the roommate problem. The Q-stable matchings," ThE Papers 14/04, Department of Economic Theory and Economic History of the University of Granada..
    6. Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 537-569, March.
    7. Bo Chen & Satoru Fujishige & Zaifu Yang, 2010. "Decentralized Market Processes to Stable Job Matchings with Competitive Salaries," KIER Working Papers 749, Kyoto University, Institute of Economic Research.
    8. Biró, Péter & Iñarra, Elena & Molis, Elena, 2016. "A new solution concept for the roommate problem: Q-stable matchings," Mathematical Social Sciences, Elsevier, vol. 79(C), pages 74-82.
    9. Emiliya Lazarova & Dinko Dimitrov, 2017. "Paths to stability in two-sided matching under uncertainty," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(1), pages 29-49, March.
    10. Klaus, B.E. & Klijn, F. & Walzl, M., 2007. "The evolution of roommate networks: a comment on Jackson and Watts JET (2002)," Research Memorandum 012, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    11. Assaf Romm, 2014. "Implications of capacity reduction and entry in many-to-one stable matching," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 43(4), pages 851-875, December.
    12. 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.
    13. Atay, Ata & Mauleon, Ana & Vannetelbosch, Vincent, 2021. "A bargaining set for roommate problems," Journal of Mathematical Economics, Elsevier, vol. 94(C).
    14. Mauleon, Ana & Roehl, Nils & Vannetelbosch, Vincent, "undated". "Constitutions and Social Networks," Climate Change and Sustainable Development 206451, Fondazione Eni Enrico Mattei (FEEM).
    15. Radoslav Raykov, 2017. "Stability and Efficiency in Decentralized Two-Sided Markets with Weak Preferences," Staff Working Papers 17-4, Bank of Canada.
    16. Hakan İnal, 2014. "A Generalization of the Lone Wolf Theorem," Metroeconomica, Wiley Blackwell, vol. 65(4), pages 541-547, November.
    17. Diamantoudi, Effrosyni & Miyagawa, Eiichi & Xue, Licun, 2015. "Decentralized matching: The role of commitment," Games and Economic Behavior, Elsevier, vol. 92(C), pages 1-17.
    18. Burak Can & Bettina Klaus, 2013. "Consistency and population sensitivity properties in marriage and roommate markets," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 41(4), pages 835-862, October.
    19. Florian M. Biermann, 2011. "A Measure to compare Matchings in Marriage Markets," Discussion Paper Series dp575, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    20. Alvin E. Roth, 2024. "Market Design and Maintenance," NBER Chapters, in: New Directions in Market Design, National Bureau of Economic Research, Inc.
    21. Joseph E. Duggan, 2020. "Subjective Homophily and the Fixtures Problem," Games, MDPI, vol. 11(1), pages 1-13, February.

    More about this item

    JEL classification:

    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D47 - Microeconomics - - Market Structure, Pricing, and Design - - - Market Design

    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:ksa:szemle:2061. 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: Odon Sok The email address of this maintainer does not seem to be valid anymore. Please ask Odon Sok to update the entry or send us the correct address (email available below). General contact details of provider: http://www.kszemle.hu .

    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.