Extra uitleg (film)

Stelling: De Shapleywaarde voldoet aan efficiëntie.

Bewijs: Laat $(N,v)$ een coöperatief spel zijn. We tonen eerst aan dat iedere marginale vector efficiënt is. We nemen de volgorde $\sigma=(1,2,3,\ldots,n-2,n-1,n)$. Dan wordt de marginale vector gegeven door

$$m^{\sigma}=\big(v(\{1\}), v(\{1,2\})-v(\{1\}),\ldots,v(\{1,\ldots,n-2, n-1\})-v(\{1,\ldots,n-2\}),v(N)-v(\{1,\ldots,n-1\})\big).$$

Dit betekent dat

$$\begin{align} \sum_{i \in N}m_i^{\sigma} & =v(\{1\})+v(\{1,2\})-v(\{1\})+\ldots +v(\{1,\ldots, n-1\})-v(\{1,\ldots,n-2\})+v(N)-v(\{1,\ldots,n-1\})\\ & = v(N). \end{align}$$

De marginale vector $m^{\sigma}$ is dus efficiënt en uiteraard geldt dit op dezelfde manier voor de marginale vector behorende bij iedere volgorde. Als gevolg daarvan geldt

$$\begin{align} \sum_{i \in N}\varphi_i(v) &= \sum_{i \in N} \frac{1}{n!}\sum_{\textrm{alle } \sigma} m_i^{\sigma}\\ & = \frac{1}{n!}\sum_{\textrm{alle } \sigma} \sum_{i \in N}m_i^{\sigma}\\ & = \frac{1}{n!}\sum_{\textrm{alle } \sigma}v(N)\\ & = \frac{1}{n!} \cdot  n! \cdot v(N)\\ & = v(N).\end{align}$$

De Shapleywaarde is dus efficiënt.

Appendix: Eigenschappen sommatieteken.