Kondor Gábor

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

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.

LXIX. évf., 2022. július-augusztus (825—840. o.), DOI:10.18414/KSZ.2022.7-8.825, Tanulmány

(PDF formátum, 191.89 kB)