Egyoldali párosítási piacok nehézségi eredményei magasabb dimenzióban

Kondor, Gábor (2022) Egyoldali párosítási piacok nehézségi eredményei magasabb dimenzióban. KÖZGAZDASÁGI SZEMLE, 69 (7-8). pp. 825-840. ISSN 0023-4346

Preview

Text 02Kondor.pdf Download (196kB) | Preview

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.

Actions (login required)

Edit Item