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 ℝ,$ przy czym $v(\mathrm{\varnothing })=0.$ Funkcja $v$ zwana jest również funkcją koalicyjną lub charakterystyczną.

Wartością Shapleya $\varphi (\upsilon )$ nazwiemy wektor $[{\varphi }_1(\upsilon ),{\varphi }_2(\upsilon ),...,{\varphi }_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}{\varphi }_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

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

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

$({\mathrm{\forall }}_{S\subseteq N}v(S\cup \{i\})=v(S))⟹{\varphi }_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:

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

Dla dowolnej gry koalicyjnej istnieje tylko jeden taki podział.

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

${\varphi }_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:

${\varphi }_i(v)=\frac{1}{|N|!}\sum _{\pi \in {\mathrm{\Pi }}_N}[v(P_i^{\pi }\cup \{i\})-v(P_i^{\pi })],$

gdzie:

$\pi \in {\mathrm{\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{array}{cc}1,& \text{jeżeli }S\in \{\{1,3\},\{2,3\},\{1,2,3\}\}\\ 0,& \text{w przeciwnym przypadku}\end{array}.$

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

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

Permutacja $\mathit{\pi }$	$𝑴{𝑪}_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$

${\varphi }_1(v)=(1)\left(\frac{1}{6}\right)=\frac{1}{6}.$

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

${\varphi }_2(v)={\varphi }_1(v)=\frac{1}{6},$

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

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

Zobacz też

• indeks siły Shapleya-Shubika