Shapley值法

設集合I=〔1,2，……n〕，I的任意子集合S都對應著一個是函數υ〔S〕，若滿足：

υ〔∮〕=0

υ〔Si∪Sj〕≥υ〔Si〕+υ〔Sj〕，Si∩Sj=∮，Si、Sj∈I

則稱[I,υ]為多人合作對策，υ為對策的特徵函數。

我們用xi表示I中成員i從合作的最大效益υ〔I〕中獲得的收入。在合作I的基礎下，合作對策的分配用X=〔x1,x2,……xn〕表示。顯然，該合作成立必須滿足如下條件：

∑xi= υ〔I〕

xi ≥ υ〔i〕，i=1,2，……n

在Shapley值法中，聯盟成員所得利益分配值成為Shapley值，通常記作Φ〔υ〕=（φ1〔υ〕，φ2〔υ〕，……φn〔υ〕），其中φi〔υ〕表示聯盟中成員i的所得利益：

φi〔υ〕=∑[〔n-|S|〕!〕〔|S|-1〕!/n!](υ(S)-υ(S/i)) (連加範圍是S∈Si)

其中Si表示包含I中成員i的所有子集，|S|表示S中成員的個數，υ(S/i)表示中除去后的聯盟收益。

shapley值的推導過程

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=