A Shapley-érték komplexitása és becslése

Illés, Ferenc (2024) A Shapley-érték komplexitása és becslése. PhD thesis, Budapesti Corvinus Egyetem, Közgazdasági és Gazdaságinformatikai Doktori Iskola. DOI https://doi.org/10.14267/phd.2024004

[img]
Preview
PDF : (az értekezés)
1MB
[img]
Preview
PDF : (az értekezés tézisei magyar nyelven)
431kB
[img]
Preview
PDF : (draft in English)
238kB

Official URL: https://doi.org/10.14267/phd.2024004

Abstract

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.

Item Type:Thesis (PhD thesis)
Supervisor:Csóka Péter
Subjects:Mathematics. Econometrics
ID Code:1337
Date:8 February 2024
DOI:https://doi.org/10.14267/phd.2024004
Deposited On:11 Oct 2023 11:31
Last Modified:19 Feb 2024 13:03

Repository Staff Only: item control page

Downloads

Downloads per month over past two year

View more statistics