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'utilità 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)$

Bibliografia

• Robert J. Aumann e Lloyd S. Shapley. Values of non-atomic games, Princeton University Press, Pinceton, 1974.
• Sergiu Hart, Shapley Value, The New Palgrave: Game Theory, J. Eatwell, M. Milgate and P. Newman (curatori), Norton, pp. 210–216, 1989.
• Stefano Moretti e Fioravante Patrone: Transversality of the Shapley value, TOP, 16, 1-41, pp. 60–61, 2008.
• Alvin E. Roth (curatore). The Shapley value, essays in honor of Lloyd S. Shapley. Cambridge University Press, Cambridge, 1988.
• Lloyd S. Shapley: A Value for n-person Games. In Contributions to the Theory of Games, volume II (curatori: H.W. Kuhn and A.W. Tucker), Annals of Mathematical Studies v. 28, pp. 307–317. Princeton University Press, 1953.
• Eyal Winter, The shapley value, Capitolo 53 dello "Handbook of Game Theory with Economic Applications", R.J. Aumann e S. Hart (curatori), Volume 3, pp. 2025–2054, 2002.

Collegamenti esterni

• A Bibliography of Cooperative Games: Value Theory by Sergiu Hart, su ma.huji.ac.il.