s为联合,v(s)为联合s的获利,x为利益的分配向量.
Si表示的是I的包含i的子集族.
shapley值公式的推导如下：
总联合收益v(I)可以看作是如下积累起来的：
从一个空联合s'=(此时收益为0)开始依次加入玩家1,2,3,...,n,则s'不断扩允.每加入一个玩家,它都给当前联合带来一个增益v(s'Ui)-v(s'),有：
即当所有玩家都加进来后,所有这些增益积累成v(I),因此要将v(I)分配给n个人,可以按照他们的加入所带来的增益来分配,即给i分配利益v(s'Ui)-v(s').
但这样做是有一个缺点,那就是这种分配方法与n个玩家的加入顺序有关,例如：
最初如果先加入玩家1,再加入玩家2,则
玩家1分得利益
玩家2分得利益
而如果先加入玩家2,再加入玩家1,则
可见不同加入顺序下的利益分配是有分歧的.
为了消除这种分歧,需要对所有可能顺序进行平均以得到xi的期望：
xi
某一特定加入顺序出现的概率显然是.
所以
xi
=
=...(1)
此式已经可以直接用于计算,也可继续整理如下：
排列中i的增益只取决于i之前加入的玩家集合s',即s'相同的排列具有相同的i增益.因此可将i的增益按不同的s'进行分类计算：
i前玩家集合为s'的排列有|s'|!(n-|s'|-1)!个,相应的i增益均为v(s'Ui)-v(s').
所以所有排列的i增益和为.
于是(1)式变为：
xi
=
=
由于用s表示I中包含i的子集,则有s=s'Ui及|s|=|s'|+1,于是得
xi=
即shapley公式：
xi=
其中