Wartość Shapleya

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. 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. 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.

Definicja

Niech dana będzie gra kooperacyjna $G=<N,\upsilon >,$ gdzie N to zbiór graczy $N=\{{1,2,...,n}\},$ a $v$ to funkcja, która przypisuje dowolnemu podzbiorowi (koalicji) $S\subseteq N$ graczy liczbę rzeczywistą: $v\;:\;2^{N}\to \mathbb {R} ,$ przy czym $v(\emptyset )=0.$ Funkcja $v$ zwana jest również funkcją koalicyjną lub charakterystyczną.

Wartością Shapleya $\phi (\upsilon )$ nazwiemy wektor $[\phi _{1}(\upsilon ),\phi _{2}(\upsilon ),...,\phi _{n}(\upsilon )]$ który zachowuje następujące własności:

1. Racjonalność grupowa (efektywność):
Suma zysków graczy jest równa zyskowi wielkiej koalicji

$\sum _{i\in N}\phi _{i}(v)=v(N).$

2. Symetria:
Jeśli funkcja $v$ jest symetryczna wobec i oraz j, to ich wartości Shapleya są również identyczne

$(\forall _{S\subseteq N\setminus \{i,j\}}\ v(S\cup \{i\})=v(S\cup \{j\}))\Rightarrow \phi _{i}(\upsilon )=\phi _{j}(\upsilon ).$

3. Gracz nieistotny:
Wartość Shapleya $\phi _{i}(v)$ gracza, który nic nie wnosi do żadnej koalicji jest równa zero.

$(\forall _{S\subseteq N}\ v(S\cup \{i\})=v(S))\Longrightarrow \phi _{i}(\upsilon )=0.$

4. Addytywność:
Jeżeli $G_{1}=<N,\upsilon >,G_{2}=<N,w>$ są różnymi grami kooperacyjnymi z funkcjami charakterystycznymi $\upsilon ,w$ to:

$\forall _{i\subseteq N}\ \phi _{i}(v+w)=\phi _{i}(v)+\phi _{i}(w)$ oraz $\forall _{i\subseteq N}\ \phi _{i}(av)=a\phi _{i}(v).$

Dla dowolnej gry koalicyjnej istnieje tylko jeden taki podział.

Do wyliczenia tej wartości można wykorzystać następujący wzór:

$\phi _{i}(v)=\sum _{S\subseteq N\setminus \{i\}}{\frac {|S|!\;(n-|S|-1)!}{n!}}(v(S\cup \{i\})-v(S)).$

Wartość $(v(S\cup \{i\})-v(S))$ nazywa się też wkładem marginalnym gracza $i.$

Alternatywnie, równoważny jest również zapis:

$\phi _{i}(v)={\frac {1}{|N|!}}\sum _{\pi \in \Pi _{N}}\left[v(P_{i}^{\pi }\cup \{i\})-v(P_{i}^{\pi })\right],$

gdzie:

$\pi \in \Pi _{N}$ – permutacja zbioru graczy,

$P_{i}^{\pi }$ – zbiór graczy z $N,$ którzy występują w permutacji $\pi$ przed graczem $i.$

Przykład

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: $N=\{1,2,3\},$ przy czym gracz 1 i 2 posiadają prawą rękawicę, a 3 lewą.

Funkcja koalicyjna będzie wyglądać następująco:

$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}}.$

Biorąc pod uwagę wzór $\phi _{i}(v)={\frac {1}{|N|!}}\sum _{\pi \subseteq \Pi _{N}}\left[v(P_{i}^{\pi }\cup \{i\})-v(P_{i}^{\pi })\right],$ wypisujemy wszystkie permutacje $\pi \in \Pi _{N}.$

Następująca tabelka wylicza wkłady marginalne gracza pierwszego.

Permutacja ${\boldsymbol {\pi }}$	${\boldsymbol {MC_{1}}}$
$1,2,3$	$v(\{1\})-v(\varnothing )=0-0=0$
$1,3,2$	$v(\{1\})-v(\varnothing )=0-0=0$
$2,1,3$	$v(\{1,2\})-v(\{2\})=0-0=0$
$2,3,1$	$v(\{1,2,3\})-v(\{2,3\})=1-1=0$
$3,1,2$	$v(\{1,3\})-v(\{3\})=1-0=1$
$3,2,1$	$v(\{1,2,3\})-v(\{2,3\})=1-1=0$

$\phi _{1}(v)=(1)\!\left({\frac {1}{6}}\right)={\frac {1}{6}}.$

Dzięki symetrii graczy 1 i 2, wiemy również, że:

$\phi _{2}(v)=\phi _{1}(v)={\frac {1}{6}},$

a jako że wartości sumują się do $v(N)=v(\{1,2,3\})=1,$ to:

$\phi _{3}(v)=1-{\frac {2}{6}}={\frac {4}{6}}={\frac {2}{3}}.$

Zobacz też

• indeks siły Shapleya-Shubika