能不能形象的介绍一下 shapley 值法?

shapley值法
关注者
121
被浏览
16543
沙普利值(Shapley value),通过考虑各个代理(agent)做出的贡献,来公平地分配合作收益。代理i的沙普利值是i对于一个合作项目所期望的贡献量的平均值

这里有必要介绍一些背景。
一个合作项目C=<Ag, v>是由一些代理(Ag={1,2...,n}, n\geq 2),和每个代理在这个合作项目中所做的贡献量的特征方程v(C)=k(\geq\sum_{i\in C}^{}{x_{i} } )表示。

下面我们结合一个事例来形象的介绍一下沙普利值是如何公平分配收益的。
今天加班,一个程序C=500行代码需要编写,今天产品经理找了三个程序猿来完成,按照完成量发奖金:
v({1})=100,v({2})=125,v({3})=50,
解释:1号屌丝程序猿独立能写100行,2号大神程序猿独立能写125行,3号美女程序猿能写50行。
v({1,2})=270,v({2,3})=350,v({1,3})=375,
解释:1,2号合作能写270行,2,3号合作能写350行,1,3号合作能写375行。
(你可以脑补:美女都是催化剂,屌丝都是潜力股
v({1,2,3})=500
解释:3个人共同能完成500行。

那么合作过程将会有6种(|Ag|!)可能发生的情况需要考虑:
A. 1号程序猿邀请2号程序猿加入他组成S联盟,1,2号邀请3号加入共同编写。
B. 1号邀请3号加入成为S小组,2号加入S小组
C. 2号邀请1号加入成为S小组,3号加入S小组
D. 2号邀请3号加入成为S小组,1号加入S小组
E. 3号邀请1号加入成为S小组,2号加入S小组
F. 3号邀请2号加入成为S小组,1号加入S小组

那么根据沙普利值法,合理分配,是否公平主要考察边际贡献。
沙普利法定义i加入组织S的边际贡献(marginal contribution):
\delta i(S)=v(S\cup \left\{ i \right\} )-v(S)

那么,上述事例的边际贡献可表示为下表:
可能性 加入顺序 1号的边际贡献 2号的边际贡献 3号的边际贡献
(Acknowledge: Dr. Ka Lok Man from XJTLU)

而代理i的沙普利值可由上述的边际贡献表示:
Sh(S,i)/\varphi i=\sum_{r\in R}^{}{\delta i(Si(r))} /\left| Ag \right| !
1号代理的沙普利值为:
2号代理的沙普利值为:
3号代理的沙普利值为:

总和为v({1,2,3})=500
那么,1号屌丝程序猿应该获得的奖金为总奖金的32.3%
2号大神程序猿应该获得的奖金为总奖金的32.3%
3号美女程序猿应该获得的奖金为总奖金的35.3%

以上。