shapley值法初学入门详细介绍

快来打我* 2022-07-15 03:24 625阅读 0赞

#     #

## 一、什么是shapley值法？ ##

shapley值法是指所得与自己的贡献相等，是一种分配方式。普遍用于经济活动中的利益合理分配等问题。最早由美国洛杉矶加州大学教授罗伊德·夏普利（Lloyd Shapley）提出。shapley值法的提出给合作博弈在理论上的重要突破及其以后的发展带来了重大影响。

简单的来说就是使分配问题更加的合理，用于为分配问题提供一种合理的方式。例如，价值链利益分配问题。

## 二、shapley值法的由来 ##

通过一则寓言故事来说明——[引自百度百科\_夏普利值][Link 1]

约克和汤姆结对旅游。约克和汤姆准备吃午餐。约克带了3块饼，汤姆带了5块饼。这时，有一个路人路过，路人饿了。约克和汤姆邀请他一起吃饭。路人接受了邀请。约克、汤姆和路人将8块饼全部吃完。吃完饭后，路人感谢他们的午餐，给了他们8个金币。路人继续赶路。

约克和汤姆为这8个金币的分配展开了争执。汤姆说：“我带了5块饼，理应我得5个金币，你得3个金币。”约克不同意：“既然我们在一起吃这8块饼，理应平分这8个金币。” 约克坚持认为每人各4块金币。为此，约克找到公正的夏普里。

夏普里说：“孩子，汤姆给你3个金币，因为你们是朋友，你应该接受它；如果你要公正的话，那么我告诉你，公正的分法是，你应当得到1个金币，而你的朋友汤姆应当得到7个金币。”

约克不理解。

夏普里说：“是这样的，孩子。你们3人吃了8块饼，其中，你带了3块饼，汤姆带了5块，一共是8块饼。你吃了其中的1/3，即8/3块，路人吃了你带的饼中的3-8/3=1/3；你的朋友汤姆也吃了8/3，路人吃了他带的饼中的5-8/3=7/3。这样，路人所吃的8/3块饼中，有你的1/3，汤姆的7/3。路人所吃的饼中，属于汤姆的是属于你的的7倍。因此，对于这8个金币，公平的分法是：你得1个金币，汤姆得7个金币。你看有没有道理？”

约克听了夏普里的分析，认为有道理，愉快地接受了1个金币，而让汤姆得到7个金币。

在这个故事中，我们看到，夏普里所提出的对金币的“公平的”分法，遵循的原则是：所得与自己的贡献相等。

这就是夏普里值的意思。

## 三、shapley值法的数学推导以及公理解释 ##

### 1、定义变量 ###

（1）n：代表n个局中人，也就是n个相关人。

（2）N：代表n个局中人组成的集合，即N=\{1,2,3…n\}。

（3）S：代表n个局中人可能组成的企业联盟，所以S是N的一个子集，表示为S ⊂ N

（4）V(S):代表企业联盟S通过联盟后的优势所获得的最大收益。我们将V(S)成为企业联盟S的特征函数。

（5）：表示局中人能从联盟中获得的最大收益。

（6）∅(V)=\{\}:表示一种分配方案。

### 2、shapley值法的公理 ###

#### (1)对称公理：参与人因合作而分配得到的利益与他所赋予的记号无关。 ####

设λ是N=\{1,2,3…n\}的一个排列，即N中的一个 一对一映射，如λi是i的对应，对企业联盟博弈V有:(λV)S=V(λS)。

#### （2）有效公理：成员对于企业联盟没有做出贡献就不能获得报酬。 ####

如果对于所有包含i的子集S都有V(S\\i)=V(S),则φ1(V)=0,且φi(V)中i从1到n的和等于V(N)。

#### （3）加法公理：局中人同时进行两项合作时，总分配是两项的和。 ####

对于定义在N中的任意两个特征函数U和V，则φ(U+V)=φ(U)+φ(V)。

### 2、求解shapley值 ###

对于满足以上公理的φ(V)值称为shapley值。shapley证明了对于任何n人合作博弈，shapley的值是唯一的。

公式为：

![lazy_placeholder.gif][]

## 四、举例分析shapley值法——财产分配问题 ##

### 1、提出问题 ###

100万的遗产由A、B、C三人来分，且假定A拥有50%的票力，B拥有40%的票力，C拥有10%的票力。规则规定，当超过50%的票认可了某种方案时，才能获得整个财产，否则三人将一无所获。

### 2、分析问题 ###

从题目限定的条件中我们可以看出，任何一个人票力都没有超过50%，所以每个人都不能单独决定财产的分配。如果想要分配财产那么就必须要拥有大于50%的票力，所以形成联盟是必须的！也就是说，在这个题目的限制条件下任何一个人都不单独的具有财产分配的决定权。

那么此时我们很容易的想到按照票力的比例来进行财产分配。但是一旦按照ABC三人的票力进行分配，此时总的票力大于50%，所以三人都具有财产的分配能力，那么每个人都想获得更多乃至于全部的财产，此时就会再次陷入相互之间的博弈。那么如何更好的解决呢？——使用shapley值法

### 3、解决问题 ###

在这个博弈的过程中，理性的人会形成联盟ab、ac或abc。但哪个联盟能够形成呢？最终的分配结果应该是怎样的呢？

shapley值是这样的一个值：在各种可能的联盟次序下，参与者对联盟的边际贡献之和除以各种可能的联盟组合。

在这个财产分配问题上，我们可以写出各种可能的联盟顺序。而边际贡献就在于在这个顺序中谁是这个联盟的“关键加入者”。如果是关键加入者，那么他的边际贡献就为100万元。

<table style="border-width:1px 0px 0px 1px; border-style:solid; font-family:Helvetica,Arial,&quot;Hiragino Sans GB&quot;,&quot;Microsoft YaHei&quot;,&quot;WenQuanYi Micro Hei&quot;,sans-serif; font-size:14px; margin:0px 0px 1.5em; outline:0px; padding:0px; vertical-align:baseline; border-spacing:0px; width:800px; color:rgb(51,51,51)"> 
 <tbody style="border:0px; font-family:inherit; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
  <tr style="border:0px; font-family:inherit; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <th style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline; text-align:left"> 财产问题中各种排列下的关键加入者</th> 
  </tr> 
  <tr style="border:0px; font-family:inherit; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> 次序</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> ABC</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> ACB</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> BAC</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> BCA</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> CAB</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> CBA</td> 
  </tr> 
  <tr style="border:0px; font-family:inherit; font-style:inherit; font-weight:inherit; margin:0px; outline:0px; padding:0px; vertical-align:baseline"> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> 关键加入者</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> B</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> C</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> A</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> A</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> A</td> 
   <td style="border-width:0px 1px 1px 0px; border-style:solid; font-family:inherit; font-size:14px; font-style:inherit; margin:0px; outline:0px; padding:12px 15px; vertical-align:baseline"> A</td> 
  </tr> 
 </tbody> 
</table>

由上表，我们得到ABC三人的夏普里值分别为：

A=4/6;B=1/6;C=1/6;

### 4、分配财产 ###

A=100万\*4/6; B=100万\*1/6; C=100万\*1/6;

### 5、理解问题 ###

shapley值是先验实力的一种度量。根据shapley值定义，所有排列的顺序是等可能的=1/6。而在每一个排列下，每个参与者对这个排列的联盟有一个边际贡献。所以，shapley值所反映的是参与者在各种可能下的“影响程度”。在投票博弈中，这个值反映的是参与者与其他参与者结成联盟的可能性，因此shapley值反映的是参与者的“权力”。

### 5、那么票力有什么作用呢？ ###

票力是虚假的实力表示。B、C的票里虽然不同，但是夏普里值却相同，也就是说权利相同，他们在形成获胜联盟中作为关键加入者的可能性是一样的。

参与者的真正实力体现在他与其他参与者形成获胜联盟的可能程度，一个参与者能形成获胜联盟可能性大——shapley值大，同时意味着，一旦他退出，本来能获胜的联盟就归于失败。这也表明，该参与者的影响程度大。

所以也就说明了——shapley值是参与者的权力的一个度量

转载自[Neilx's Blog网站《shapley值法初学入门详细介绍》][Neilx_s Blog_shapley]

[Link 1]: http://baike.baidu.com/link?url=nUQvaLFPbIL0u8HnKYNeNYLl8iCt_Dpzh1qMChVurD3eXB5w0bPzmZY13LDc_6vUp0aCzP__ALl5gQebH0XoLq
[lazy_placeholder.gif]: https://www.neilx.com/blog/wp-content/plugins/a3-lazy-load/assets/images/lazy_placeholder.gif
[Neilx_s Blog_shapley]: https://www.neilx.com/blog/