Shapley値

Shapley値公式

$$\begin{gathered} {\varphi }_i(v)=\sum _{S\subseteq N \\ \{i\}}\frac{|S|!(|N|-|S|-1)!}{|N|!}(v(S\bigcup \{i\})-v(S)) \end{gathered}$$

例

張さん、王さん、李さんはテスト勉強しています。

$N=\{\mathrm{張}\mathrm{さ}\mathrm{ん}、\mathrm{王}\mathrm{さ}\mathrm{ん}、\mathrm{李}\mathrm{さ}\mathrm{ん}\}$

独学の場合は

張さんは40点を取れます。 $v(\mathrm{張})=40$

王さんは60点を取れます。 $v(\mathrm{王})=60$

李さんは90点を取れます。 $v(\mathrm{李})=90$

張さんと王さんに勉強会をすると合計140点を取れます。 $v(\mathrm{張},\mathrm{王})=140$

張さんと李さんに勉強会をすると合計150点を取れます。 $v(\mathrm{張},\mathrm{李})=160$

王さんと李さんに勉強会をすると合計175点を取れます。 $v(\mathrm{王},\mathrm{李})=175$

3人一緒に勉強すると合計240点を取れます。 $v(\mathrm{張}、\mathrm{王}、\mathrm{李})=240$

それぞれの貢献度を求める

$$i=\mathrm{張}\mathrm{さ}\mathrm{ん}$$ $$S\subset \{\mathrm{\varnothing },(\mathrm{王}\mathrm{さ}\mathrm{ん}),(\mathrm{李}\mathrm{さ}\mathrm{ん}),(\mathrm{王}\mathrm{さ}\mathrm{ん},\mathrm{李}\mathrm{さ}\mathrm{ん})\}$$

$S=\mathrm{\varnothing }$の場合

$$\frac{1}{3}(v(\mathrm{張})-v(\mathrm{\varnothing }))=\frac{40}{3}$$

$S=(\mathrm{王}\mathrm{さ}\mathrm{ん})$の場合

$$\frac{1}{6}(v(\mathrm{張},\mathrm{王})-v(\mathrm{王}))=\frac{1}{6}(160-60)=\frac{50}{3}$$

$S=(\mathrm{李}\mathrm{さ}\mathrm{ん})$の場合

$$\frac{1}{6}(v(\mathrm{張}，\mathrm{李})-v(\mathrm{李}))=\frac{1}{6}(160-90)=\frac{35}{3}$$

$S=(\mathrm{王}\mathrm{さ}\mathrm{ん},\mathrm{李}\mathrm{さ}\mathrm{ん})$の場合

$$\frac{1}{3}(v(\mathrm{張}，\mathrm{王}，\mathrm{李})-v(\mathrm{王},\mathrm{李}))=\frac{1}{3}(240-175)=\frac{65}{3}$$

よって、

$${\varphi }_{\mathrm{張}}(v)=\frac{190}{3}$$

$i=\mathrm{王}\mathrm{さ}\mathrm{ん},i=\mathrm{李}\mathrm{さ}\mathrm{ん}$のときも同じような計算すると

$${\varphi }_{\mathrm{王}}(v)=95$$ $${\varphi }_{\mathrm{李}}(v)=\frac{245}{3}$$