Indietro

ⓘ Valore di Shapley




                                     

ⓘ Valore di Shapley

Il valore di Shapley 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 lordine con cui i giocatori si uniscono alla coalizione stessa.

                                     

1. Funzione caratteristica

Chiamiamo v S {\displaystyle v\leftS\right} la funzione caratteristica che esprime lutilita per ogni coalizione S {\displaystyle S} contenuta in un insieme N {\displaystyle N} di giocatori. Più precisamente:

v: P N → R {\displaystyle v\;:\;{\mathcal {P}}\leftN\right\;\rightarrow \;\mathbb {R} }

dove P N {\displaystyle {\mathcal {P}}\leftN\right} indica linsieme delle parti di N {\displaystyle N}.

questa funzione deve godere delle seguenti proprietà:

  • v S ∪ T ≥ v S + v T ∀ S, T ⊆ N: S ∩ T = ∅ {\displaystyle v\leftS\cup T\right\geq v\leftS\right+v\leftT\right\quad \forall \;S,T\subseteq N:S\cap T=\varnothing }
  • v ∅ = 0 {\displaystyle v\left\varnothing \right=0}

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

                                     

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

ϕ i, v = 1 | N |! ∑ π ∈ Π N v B π, i ∪ { i }) − v B π, i) {\displaystyle \phi \lefti,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:

ϕ i, v {\displaystyle \phi \lefti,v\right} indica la ricompensa ricevuta dal giocatore i {\displaystyle i}

v {\displaystyle v} è la funzione caratteristica.

Π N {\displaystyle \Pi _{N}} è linsieme di tutti gli ordinamenti possibili degli elementi di N {\displaystyle N} o permutazioni.

B π, i {\displaystyle \mathrm {B} \left\pi,i\right} è linsieme dei giocatori che precedono il giocatore i {\displaystyle i} nellordinamento preso in considerazione.

Due altre formule ad essa equivalente sono le seguenti:

ϕ i, v = ∑ S ⊆ N | N | − | S |! | S | − 1! | N |! v S − v S ∖ { i }) {\displaystyle \phi \lefti,v\right=\sum _{S\subseteq N}{\left\left|N\right|-\left|S\right|\right!\;\left\left|S\right|-1\right! \over \left|N\right|!}\leftv\leftS\right-v\leftS\setminus \left\{i\right\}\right\right)}

ϕ i, v = ∑ S ⊆ N ∖ { i } | S |! | N | − | S | − 1! | N |! v S ∪ { i } − v S) {\displaystyle \phi \lefti,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|!}\leftv\leftS\cup \left\{i\right\}\right-v\leftS\right\right)}

Da notare che nellultima formula la sommatoria è su tutti i sottoinsiemi S {\displaystyle S} di N {\displaystyle N} che non contengono il giocatore i {\displaystyle i}.

                                     

3. Proprietà

  • Un giocatore con contributo marginale pari a zero riceverà zero come ricompensa: v S = v S ∪ { i } ⇒ ϕ i, S = 0 {\displaystyle v\leftS\right=v\leftS\cup \left\{i\right\}\right\;\Rightarrow \;\phi \lefti,S\right=0}
  • Ogni giocatore riceve almeno quanto avrebbe ricevuto se non avesse partecipato alla coalizione: ϕ i, v ≥ v { i } ∀ i ∈ N {\displaystyle \phi \lefti,v\right\geq v\left\left\{i\right\}\right\;\forall \;i\in N}
  • Rinominare i giocatori in modo diverso non cambia lassegnamento della ricompensa.
  • Il guadagno totale è distribuito Pareto efficienza: ∑ i ∈ N ϕ i, N = v N {\displaystyle \sum _{i\in N}\phi \lefti,N\right=v\leftN\right}
  • Additività: se combiniamo due giochi, descritti da due funzioni v {\displaystyle v} e w {\displaystyle w}, la ricompensa distribuita corrisponderà alla ricompensa derivante da v {\displaystyle v} sommata a quella derivante da w {\displaystyle w}: ϕ i, v + w = ϕ i, v + ϕ i, w ∀ i ∈ N {\displaystyle \phi \lefti,v+w\right=\phi \lefti,v\right+\phi \lefti,w\right\quad \forall \;i\in N}
  • I giocatori con lo stesso contributo marginale ricevono la stessa ricompensa: v S ∪ { i } = v S ∪ { j } ⇒ ϕ i, S = ϕ j, S {\displaystyle v\leftS\cup \left\{i\right\}\right=v\leftS\cup \left\{j\right\}\right\;\Rightarrow \;\phi \lefti,S\right=\phi \leftj,S\right}


                                     

4. Esempio

N = 1, 2, 3 | N | = 3 {\displaystyle N=\left1.2.3\right\qquad \left|N\right|=3}

Π N = { 1, 2, 3 ; 1, 3, 2 ; ⏟ 2, 1, 3 ; 2, 3, 1 ; ⏟ 3, 1, 2 ; 3, 2, 1 ⏟ α β γ } {\displaystyle \Pi _{N}=\left\

Come previsto dalla condizione di efficienza, si ha:

ϕ 1, v + ϕ 2, v + ϕ 3, v = 8 6 + 5 6 + 5 6 = 18 6 = 3 = v { 1, 2, 3 } {\displaystyle \phi \left1,v\right+\phi \left2,v\right+\phi \left3,v\right={8 \over 6}+{5 \over 6}+{5 \over 6}={18 \over 6}=3=v\left\left\{1.2.3\right\}\right}