Átruházható hasznosságú játékok prenukleoluszának kiszámításához használt emblematikus algoritmus az úgy nevezett lexikografikus közép algoritmus, ami lineáris programozási feladatok egy véges sorozata. Tudjuk, hogy egy lineáris programozási feladat polinom időben megoldható, és, hogy elég a játékosok számában lineáris sokat megoldani belőlük, az algoritmus mégis exponenciális a játékosok számában, mivel a játékosok minden egyes részhalmazához tartozik egy feltétel a lineáris programozási feladatokban. A kutatás célja olyan koalíció halmazokat találni, melyek egyértelműen meghatározzák a prenukleoluszt, ezáltal gyorsítva az algoritmust bizonyos játékosztályokon. A kutatás során definiáltuk a prenukleolusz egy hasznossági függvények bevezetésével vett általánosítását, az u.n. u-prenukleoluszt. Az általánosítás célja a prenukleoluszt meghatározó koalíciók és a lexikografikus közép algoritmus mélyebb megértése. A prenukleolusz fontos tulajdonságait megragadó tételek közül kimondtuk és bizonyítottuk a Kohlberg-tétel u-prenukleoluszra vett általánosítását és Katsev és Yanovskaya tételének az általánosítását, amivel megadtunk egy szükséges és elégséges feltételt az u-prenukleolusz egyértelműségére. Definiáltuk az u-lényeges koalíciók fogalmát, ami a lényeges koalíciók fogalmának egy általánosítása. Ezen definíció segítségével bizonyítottuk Huberman tételének az általánosítását az u-prenukleoluszra, ami kimondja, hogy az u-lényeges koalíciók egy karakterizációs halmazát adják meg az u-prenukleolusznak u-kiegyensúlyozott játékok esetén, azaz az u-prenukleolusz kiszámításakor elég az u-lényeges koalíciókat figyelembe venni. Ezen tétel speciális esetei segítségével megadhatunk egy karakterizációs halmazt a perkapita prenukleoluszra kiegyensúlyozott játékok esetén, illetve egy karakterizációs halmazt a prenukleoluszra nem kiegyensúlyozott játékok esetén is.
Dornai Zsófia
2023-04-29
Támogató: Knorr-Bremse