Valore di Shapley

Da Wikipedia, l'enciclopedia libera.

Valore di Shapley[modifica | modifica sorgente]

Il Valore di Shapley, noto anche come Shapley value e chiamato così in onore di Lloyd Stowell Shapley, è un concetto di soluzione utilizzato per assegnare una ricompensa ad ogni giocatore presente nella 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, è fondamentale considerare anche l'ordine con il quale il giocatore si unisce alla coalizione stessa.

Funzione caratteristica[modifica | modifica sorgente]

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 \; \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 ) \ge 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[modifica | modifica sorgente]

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 ( \Beta \left ( \pi,i \right ) \cup \left \{ i \right \} \right ) -v \left ( \Beta \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.

\Beta \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à[modifica | modifica sorgente]

  • Ogni giocatore riceve almeno quanto avrebbe ricevuto se non avesse partecipato alla coalizione: \phi \left ( i,v \right ) \ge 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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

  • Robert J. Aumann e Lloyd S. Shapley. Values of non-atomic games, Princeton Univ. 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[modifica | modifica sorgente]