A Shapley-érték komplexitása és becslése [védés előtt]

A kooperatív játékelmélet számos társadalmi dilemma illetve pénzügyi és gazdasági probléma modellje. Általában akkor alkalmazzuk, ha egy közösség által elérhető eredmény meghaladja az egyénenként elérhető eredmények összegét (szinergia), vagy egy tevékenység teljes költsége alacsonyabb, mint a részfeladatok költségeinek összege (megtakarítás) illetve teljes kockázata kisebb, mint a részfeladatok aggregált kockázata (diverzikáció). A fő kérdés pedig természetesen az, hogy hogyan osszuk el a többletet a szereplők között valamilyen „igazságos” módon. A kooperatív játékok legismertebb általános megoldását Lloyd Stowell Shapley adta meg 1953- ban A value for n-person games című cikkében. Bizonyítható, hogy Shapley megoldása, melyet azóta Shapley-értéknek neveznek, az egyetlen általános, azaz minden játékra működő megoldási koncepció, mely bizonyos igazságossági feltételeknek eleget tesz. Szépséghibája, hogy – az egyszerűen felírható formula és intuitív tartalma ellenére – konkrét játékokra nem feltétlenül tudjuk az értékét pontosan meghatározni, ha a játékosok száma túl nagy, ugyanis a képlet a játékosok számában nem polinomiális számú tag összegéből áll. A disszertáció tartalma, ha egy mondatban kéne összefoglalni: Hogyan lehet (illetve nem lehet) egy kooperatív játék Shapley-értékét hatékonyan kiszámolni vagy megbecsülni? Már a feladat pontos specikálásánál felmerül két egymást kioltó probléma. Az egyik a játék tárolásának képessége, mert egy általános TU-játék kezelhetetlen méretű adathalmaz, azonban a Shapley-érték ennek az adathalmaznak a függvényében „gyorsan” számolható. Ennek kezelésére bevezetjük a polinomiális reprezentáció fogalmát, azaz vizsgálódásainkat olyan játékosztályokra korlátozzuk, melyek valamilyen módon „jól tömöríthetőek”. A másik probláma a Shapley-érték kiszámításának képessége. Ha egy játékosztály elég jól tömöríthető ahhoz, hogy sok játékos esetén is meg tudjuk adni, akkor előfordulhat, hogy ennyi játékosra a Shapley-értéket már nincs kapacitásunk kiszámolni. A számítástudományi szempontból megoldhatatlannak tűnő problémák kezelésére két lehetőség adja magát. Az egyik a Monte-Carlo szimulációval történő becslés, a másik a speciális játékokra kifejlesztett pszeudopolinomiális algoritmus