Valore di Shapley
# Valore di Shapley

Il valore di Shapley (in inglese Shapley value) così chiamato in onore di Lloyd Stowell Shapley, è un concetto di soluzione utilizzato per assegnare una ricompensa ad ogni giocatore presente in una coalizione, in funzione del contributo marginale che apporta ad essa. Siccome il contributo che un giocatore apporta alla coalizione varia in funzione dei giocatori presenti in essa, il valore di Shapley prende implicitamente in considerazione l'ordine con cui i giocatori si uniscono alla coalizione stessa.

## Funzione caratteristica

Chiamiamo $v\left(S\right)$ la funzione caratteristica che esprime l'utilita per ogni coalizione $S$ contenuta in un insieme $N$ di giocatori. Più precisamente:

$v\;:\;{\mathcal {P}}\left(N\right)\;\rightarrow \;\mathbb {R}$

dove ${\mathcal {P}}\left(N\right)$ indica l'insieme delle parti di $N$.

questa funzione deve godere delle seguenti proprietà:

* $v\left(\varnothing \right)=0$
* $v\left(S\cup T\right)\geq v\left(S\right)+v\left(T\right)\quad \forall \;S,T\subseteq N:S\cap T=\varnothing$

la seconda proprietà, chiamata anche super additività, indica che il coalizzarsi tra giocatori avrà sempre un effetto positivo o nullo.

## Formule per il calcolo del Valore di Shapley

Il valore di Shapley è un sistema per distribuire la ricompensa ottenuta dalla coalizione tra i suoi componenti e lo scopo che si prefigge è di distribuire tale ricompensa in modo proporzionale al contributo che ogni giocatore apporta alla coalizione. Una possibile soluzione a tale calcolo consiste nel fare una media di tutti i contributi marginali del giocatore su tutti gli ordinamenti possibili dei giocatori presenti nella coalizione.

$\phi \left(i,v\right)={1 \over \left|N\right|!}\sum _{\pi \in \Pi _{N}}v\left(\mathrm {B} \left(\pi ,i\right)\cup \left\{i\right\}\right)-v\left(\mathrm {B} \left(\pi ,i\right)\right)$

dove:

$\phi \left(i,v\right)$ indica la ricompensa ricevuta dal giocatore $i$

$v$ è la funzione caratteristica.

$\Pi _{N}$ è l'insieme di tutti gli ordinamenti possibili degli elementi di $N$ o permutazioni.

$\mathrm {B} \left(\pi ,i\right)$ è l'insieme dei giocatori che precedono il giocatore $i$ nell'ordinamento preso in considerazione.

Due altre formule ad essa equivalente sono le seguenti:

$\phi \left(i,v\right)=\sum _{S\subseteq N}{\left(\left|N\right|-\left|S\right|\right)!\;\left(\left|S\right|-1\right)! \over \left|N\right|!}\left(v\left(S\right)-v\left(S\setminus \left\{i\right\}\right)\right)$

$\phi \left(i,v\right)=\sum _{S\subseteq N\setminus \left\{i\right\}}{\left|S\right|!\;\left(\left|N\right|-\left|S\right|-1\right)! \over \left|N\right|!}\left(v\left(S\cup \left\{i\right\}\right)-v\left(S\right)\right)$

Da notare che nell'ultima formula la sommatoria è su tutti i sottoinsiemi $S$ di $N$ che non contengono il giocatore $i$.

## Proprietà

* Ogni giocatore riceve almeno quanto avrebbe ricevuto se non avesse partecipato alla coalizione: $\phi \left(i,v\right)\geq v\left(\left\{i\right\}\right)\;\forall \;i\in N$
* Il guadagno totale è distribuito (Pareto efficienza): $\sum _{i\in N}\phi \left(i,N\right)=v\left(N\right)$
* Rinominare i giocatori in modo diverso non cambia l'assegnamento della ricompensa.
* I giocatori con lo stesso contributo marginale ricevono la stessa ricompensa: $v\left(S\cup \left\{i\right\}\right)=v\left(S\cup \left\{j\right\}\right)\;\Rightarrow \;\phi \left(i,S\right)=\phi \left(j,S\right)$
* Un giocatore con contributo marginale pari a zero riceverà zero come ricompensa: $v\left(S\right)=v\left(S\cup \left\{i\right\}\right)\;\Rightarrow \;\phi \left(i,S\right)=0$
* Additività: se combiniamo due giochi, descritti da due funzioni $v$ e $w$, la ricompensa distribuita corrisponderà alla ricompensa derivante da $v$ sommata a quella derivante da $w$: $\phi \left(i,v+w\right)=\phi \left(i,v\right)+\phi \left(i,w\right)\quad \forall \;i\in N$

## Esempio

| S | v(S) |
| - | - |
| ∅ | 0 |
| {1} | 1 |
| {2} | 0 |
| {3} | 0 |
| {1, 2} | 2 |
| {1, 3} | 2 |
| {2, 3} | 2 |
| {1, 2, 3} | 3 |

$N=\left(1,2,3\right)\qquad \left|N\right|=3$

$\Pi _{N}=\left\{{\begin{matrix}\underbrace {\left(1,2,3\right);\left(1,3,2\right);} &\underbrace {\left(2,1,3\right);\left(2,3,1\right);} &\underbrace {\left(3,1,2\right);\left(3,2,1\right)} \\\alpha &\beta &\gamma \end{matrix}}\right\}$

per $i=1$:

${\begin{array}{lcl}\alpha &=&\left[\left(v\left(\varnothing \cup \left\{1\right\}\right)-v\left(\varnothing \right)\right)+\left(v\left(\varnothing \cup \left\{1\right\}\right)-v\left(\varnothing \right)\right)\right]\\&=&\left(1-0\right)+\left(1-0\right)=2\end{array}}$

${\begin{array}{lcl}\beta &=&\left[\left(v\left(\left\{2\right\}\cup \left\{1\right\}\right)-v\left(\left\{2\right\}\right)\right)+\left(v\left(\left\{2,3\right\}\cup \left\{1\right\}\right)-v\left(\left\{2,3\right\}\right)\right)\right]\\&=&\left(2-0\right)+\left(3-2\right)=3\end{array}}$

${\begin{array}{lcl}\gamma &=&\left[\left(v\left(\left\{3\right\}\cup \left\{1\right\}\right)-v\left(\left\{3\right\}\right)\right)+\left(v\left(\left\{3,2\right\}\cup \left\{1\right\}\right)-v\left(\left\{3,2\right\}\right)\right)\right]\\&=&\left(2-0\right)+\left(3-2\right)=3\end{array}}$

$\phi \left(1,v\right)={1 \over \left|N\right|!}\left[\alpha +\beta +\gamma \right]={1 \over 3!}(2+3+3)={8 \over 6}$

per $i=2$:

${\begin{array}{lcl}\alpha &=&\left[\left(v\left(\left\{1\right\}\cup \left\{2\right\}\right)-v\left(\left\{1\right\}\right)\right)+\left(v\left(\left\{1,3\right\}\cup \left\{2\right\}\right)-v\left(\left\{1,3\right\}\right)\right)\right]\\&=&\left(2-1\right)+\left(3-2\right)=2\end{array}}$

${\begin{array}{lcl}\beta &=&\left[\left(v\left(\varnothing \cup \left\{2\right\}\right)-v\left(\varnothing \right)\right)+\left(v\left(\varnothing \cup \left\{2\right\}\right)-v\left(\varnothing \right)\right)\right]\\&=&\left(0-0\right)+\left(0-0\right)=0\end{array}}$

${\begin{array}{lcl}\gamma &=&\left[\left(v\left(\left\{3,1\right\}\cup \left\{2\right\}\right)-v\left(\left\{3,1\right\}\right)\right)+\left(v\left(\left\{3\right\}\cup \left\{2\right\}\right)-v\left(\left\{3\right\}\right)\right)\right]\\&=&\left(3-2\right)+\left(2-0\right)=3\end{array}}$

$\phi \left(2,v\right)={1 \over \left|N\right|!}\left[\alpha +\beta +\gamma \right]={1 \over 3!}(2+0+3)={5 \over 6}$

per $i=3$:

${\begin{array}{lcl}\alpha &=&\left[\left(v\left(\left\{1,2\right\}\cup \left\{3\right\}\right)-v\left(\left\{1,2\right\}\right)\right)+\left(v\left(\left\{1\right\}\cup \left\{3\right\}\right)-v\left(\left\{1\right\}\right)\right)\right]\\&=&\left(3-2\right)+\left(2-1\right)=2\end{array}}$

${\begin{array}{lcl}\beta &=&\left[\left(v\left(\left\{2,1\right\}\cup \left\{3\right\}\right)-v\left(\left\{2,1\right\}\right)\right)+\left(v\left(\left\{2\right\}\cup \left\{3\right\}\right)-v\left(\left\{2\right\}\right)\right)\right]\\&=&\left(3-2\right)+\left(2-0\right)=3\end{array}}$

${\begin{array}{lcl}\gamma &=&\left[\left(v\left(\varnothing \cup \left\{3\right\}\right)-v\left(\varnothing \right)\right)+\left(v\left(\varnothing \cup \left\{3\right\}\right)-v\left(\varnothing \right)\right)\right]\\&=&\left(0-0\right)+\left(0-0\right)=0\end{array}}$

$\phi \left(3,v\right)={1 \over \left|N\right|!}\left[\alpha +\beta +\gamma \right]={1 \over 3!}(2+3+0)={5 \over 6}$

Come previsto dalla condizione di efficienza, si ha:

$\phi \left(1,v\right)+\phi \left(2,v\right)+\phi \left(3,v\right)={8 \over 6}+{5 \over 6}+{5 \over 6}={18 \over 6}=3=v\left(\left\{1,2,3\right\}\right)$

