shapley值的推导过程

http://bbs.bossh.net/home/u/wantnon/archives/2008/448.html
注解：
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表