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