Wartość Shapleya – pojęcie z teorii gier, nazwane na cześć Lloyda Shapleya, który wymyślił je w 1953 roku jako sposób podziału zysku pomiędzy graczami będącymi w koalicji[1][2]. Wartość ta jest określona jednoznacznie dla każdego gracza w grze kooperacyjnej przez odpowiednią dystrybucję całości zysku z wielkiej koalicji, tj. koalicji złożonej ze wszystkich graczy, zachowującą pewne własności[3][4]. Intuicyjnie Wartość Shapleya określa, ile dany gracz powinien się spodziewać zysku z całości, biorąc pod uwagę to, jaki średnio ma wkład w dowolnej koalicji.
Niech dana będzie gra kooperacyjna
gdzie N to zbiór graczy
a
to funkcja, która przypisuje dowolnemu podzbiorowi (koalicji)
graczy liczbę rzeczywistą:
przy czym
Funkcja
zwana jest również funkcją koalicyjną lub charakterystyczną.
Wartością Shapleya
nazwiemy wektor
który zachowuje następujące własności:
1. Racjonalność grupowa (efektywność):
Suma zysków graczy jest równa zyskowi wielkiej koalicji
![{\displaystyle \sum _{i\in N}\phi _{i}(v)=v(N).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57e8457e6f890e3cf9b50158e630e3fa6ad0a11e)
2. Symetria:
Jeśli funkcja
jest symetryczna wobec i oraz j, to ich wartości Shapleya są również identyczne
![{\displaystyle (\forall _{S\subseteq N\setminus \{i,j\}}\ v(S\cup \{i\})=v(S\cup \{j\}))\Rightarrow \phi _{i}(\upsilon )=\phi _{j}(\upsilon ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/455d2c7e424fe20612affed66d2a3ea5d542d023)
3. Gracz nieistotny:
Wartość Shapleya
gracza, który nic nie wnosi do żadnej koalicji jest równa zero.
![{\displaystyle (\forall _{S\subseteq N}\ v(S\cup \{i\})=v(S))\Longrightarrow \phi _{i}(\upsilon )=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d0016eca160a0c303978cacd350e6ca233b6a8b)
4. Addytywność:
Jeżeli
są różnymi grami kooperacyjnymi z funkcjami charakterystycznymi
to:
oraz ![{\displaystyle \forall _{i\subseteq N}\ \phi _{i}(av)=a\phi _{i}(v).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5febcbd67b00354592faf63ce50620b994fb7cb9)
Dla dowolnej gry koalicyjnej istnieje tylko jeden taki podział.
Do wyliczenia tej wartości można wykorzystać następujący wzór:
![{\displaystyle \phi _{i}(v)=\sum _{S\subseteq N\setminus \{i\}}{\frac {|S|!\;(n-|S|-1)!}{n!}}(v(S\cup \{i\})-v(S)).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2811baf666e3eeaeedd09112779ef26f74588d6)
Wartość
nazywa się też wkładem marginalnym gracza
Alternatywnie, równoważny jest również zapis:
![{\displaystyle \phi _{i}(v)={\frac {1}{|N|!}}\sum _{\pi \in \Pi _{N}}\left[v(P_{i}^{\pi }\cup \{i\})-v(P_{i}^{\pi })\right],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab1c7a492520ffaf9036cd4dc0210c4c55418fb1)
gdzie:
– permutacja zbioru graczy,
– zbiór graczy z
którzy występują w permutacji
przed graczem ![{\displaystyle i.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ffcf9ad7ad44f04fa43c5b604b4801e089981cb)
Weźmy za przykład grę kooperacyjną, w której gracze posiadają rękawice, prawe i lewe, a której celem jest stworzenie par.
Mamy trzech graczy:
przy czym gracz 1 i 2 posiadają prawą rękawicę, a 3 lewą.
Funkcja koalicyjna będzie wyglądać następująco:
![{\displaystyle v(S)={\begin{cases}1,&{\text{jeżeli }}S\in \left\{\{1,3\},\{2,3\},\{1,2,3\}\right\}\\0,&{\text{w przeciwnym przypadku}}\end{cases}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8863b6ef0929e5ceeb7e37ad10eff5dc734d9c3)
Biorąc pod uwagę wzór
wypisujemy wszystkie permutacje
Następująca tabelka wylicza wkłady marginalne gracza pierwszego.
Permutacja
|
|
|
|
|
|
|
|
|
|
|
|
|
|
![{\displaystyle \phi _{1}(v)=(1)\!\left({\frac {1}{6}}\right)={\frac {1}{6}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b88934861b7370789cd6548ff92c9e445728f926)
Dzięki symetrii graczy 1 i 2, wiemy również, że:
![{\displaystyle \phi _{2}(v)=\phi _{1}(v)={\frac {1}{6}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/306333652e5db7dab50f3dac28d8ab8d495c1bd8)
a jako że wartości sumują się do
to:
![{\displaystyle \phi _{3}(v)=1-{\frac {2}{6}}={\frac {4}{6}}={\frac {2}{3}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21875a440aa827f5508cce3d642e94402c29f8be)
- ↑ Lloyd S. Shapley. „A Value for n-person Games”. In Contributions to the Theory of Games, volume II, by H.W. Kuhn and A.W. Tucker, editors. Annals of Mathematical Studies v. 28, s. 307–317. Princeton University Press, 1953.
- ↑ Alvin E. Roth (editor). The Shapley value, essays in honor of Lloyd S. Shapley. Cambridge University Press, Cambridge, 1988.
- ↑ Sergiu Hart, Shapley Value, The New Palgrave: Game Theory, J. Eatwell, M. Milgate and P. Newman (Editors), Norton, s. 210–216, 1989.
- ↑ A Bibliography of Cooperative Games: Value Theory by Sergiu Hart [1].
- ↑ Wstęp do teorii gier – 12. Gry Koalicyjne II – MIM UW [online], mst.mimuw.edu.pl [dostęp 2016-02-09] .