Extra uitleg (film)

Stelling: De Shapleywaarde voldoet aan symmetrie.

Bewijs: $(N,v)$ is een coöperatief spel waarin spelers $i$ en $j$ symmetrisch zijn. $\sigma^{ij}$ is een willekeurige volgorde waarin $i$ voor $j$ staat. Laat $S$ de coalitie spelers zijn voor speler $i$ en coalitie $T$ de coalitie spelers tussen $i$ en $j$. Zowel $S$ als $T$ kunnen leeg zijn. Dan geldt

$$m_i^{\sigma^{ij}}(v)  = v(S\cup \{i\})-v(S)$$ en $$m_j^{\sigma^{ij}}(v)  = v(S\cup \{i\} \cup T \cup \{j\})-v(S \cup \{i\} \cup T)$$

In volgorde $\sigma^{ji}$ staan alle spelers op dezelfde plaats als in $\sigma^{ij}$, behalve spelers $i$ en $j$: die zijn omgewisseld. Dan geldt

$$m_j^{\sigma^{ji}}  = v(S\cup \{j\})-v(S),$$ en $$m_i^{\sigma^{ji}}(v)  = v(S\cup \{j\}\cup T \cup \{i\})-v(S\cup \{j\}\cup T)$$

Dus

$$\begin{align} m_i^{\sigma^{ij}}(v) +m_i^{\sigma^{ji}}(v) & = v(S\cup \{i\})-v(S) + v(S\cup \{j\}\cup T \cup \{i\})-v(S\cup \{j\}\cup T)\\ & = v(S\cup \{j\})-v(S) + v(S\cup \{i\}\cup T \cup \{j\})-v(S\cup \{i\}\cup T)\\ & = v(S\cup \{i\}\cup T \cup \{j\})-v(S\cup \{i\}\cup T)+v(S\cup \{j\})-v(S)\\ & = m_j^{\sigma^{ij}}(v) +m_j^{\sigma^{ji}}(v), \end{align}$$

waarbij de tweede gelijkheid volgt uit de symmetrie tussen spelers $i$ en $j$.

Voor iedere volgorde $\sigma^{ij}$ bestaat een volgorde $\sigma^{ji}$ en de som van de marginale bijdragen van spelers $i$ en $j$ over deze twee volgorden is gelijk. Omdat de Shapleywaarde het gemiddelde is over al marginale bijdragen geldt dus dat:

$$\begin{align}\varphi_i(v) & = \frac{1}{n!}\sum_{\textrm{alle } \sigma} m^{\sigma}_i(v)\\ & = \frac{1}{n!}\sum_{\textrm{alle } \sigma} m^{\sigma}_j(v)\\ & = \varphi_j(v). \end{align}$$