IDEAS home Printed from https://ideas.repec.org/a/ksa/szemle/2061.html
   My bibliography  Save this article

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 search 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. 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.
    3. Morrill, Thayer, 2010. "The roommates problem revisited," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1739-1756, September.
    4. 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.
    5. Chung, Kim-Sau, 2000. "On the Existence of Stable Roommate Matchings," Games and Economic Behavior, Elsevier, vol. 33(2), pages 206-230, November.
    6. Woeginger, Gerhard J., 2013. "A hardness result for core stability in additive hedonic games," Mathematical Social Sciences, Elsevier, vol. 65(2), pages 101-104.
    7. 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.
    8. 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.
    9. 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.
    10. Roth, Alvin E., 2012. "The Theory and Practice of Market Design," Nobel Prize in Economics documents 2012-5, Nobel Prize Committee.
    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. 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.
    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. 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.
    7. 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.
    8. 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.
    9. 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).
    10. Mauleon, Ana & Roehl, Nils & Vannetelbosch, Vincent, 2019. "Paths to stability for overlapping group structures," Journal of Mathematical Economics, Elsevier, vol. 83(C), pages 19-24.
    11. Jean-Jacques Herings, P. & Mauleon, Ana & Vannetelbosch, Vincent, 2017. "Stable sets in matching problems with coalitional sovereignty and path dominance," Journal of Mathematical Economics, Elsevier, vol. 71(C), pages 14-19.
    12. 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.
    13. Agustín G. Bonifacio & Elena Inarra & Pablo Neme, 2022. "Stable Decompositions of Coalition Formation Games," Working Papers 110, Red Nacional de Investigadores en Economía (RedNIE).
    14. Klaus, Bettina & Klijn, Flip, 2007. "Paths to stability for matching markets with couples," Games and Economic Behavior, Elsevier, vol. 58(1), pages 154-171, January.
    15. 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.
    16. 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.
    17. Florian M. Biermann, 2011. "A Measure to compare Matchings in Marriage Markets," Working Papers 005-11, International School of Economics at TSU, Tbilisi, Republic of Georgia.
    18. Agustin G. Bonifacio & Elena Inarra & Pablo Neme, 2020. "A characterization of absorbing sets in coalition formation games," Papers 2009.11689, arXiv.org, revised May 2024.
    19. Atay, Ata & Mauleon, Ana & Vannetelbosch, Vincent, 2021. "A bargaining set for roommate problems," Journal of Mathematical Economics, Elsevier, vol. 94(C).
    20. Elliott Peranson & Alvin E. Roth, 1999. "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design," American Economic Review, American Economic Association, vol. 89(4), pages 748-780, September.

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