合作博弈：夏普利值（shapley value）性质与算法

作者: Cache_wood | 来源:发表于2022-03-28 17:29 被阅读0次

@[toc]

简介

沙普利值是合作博弈理论中的一个概念，由劳埃德-沙普利在1951年提出了这个概念，并因此在2012年获得了诺贝尔经济学奖。对于每个合作博弈，它为所有玩家的联盟产生的总盈余分配了一个独特的分配。沙普利值的特点是有一系列的理想属性。

其设置如下：一个玩家联盟进行合作，并从合作中获得一定的整体收益。由于一些玩家对联盟的贡献可能大于其他玩家，或者可能拥有不同的讨价还价能力（例如威胁要破坏整个盈余），在任何特定的游戏中，所产生的盈余在玩家之间的最终分配应该是什么？或者换个说法：每个参与者对整个合作有多重要，他或她可以合理地期待什么回报？沙普利值为这个问题提供了一个可能的答案。

定义

从形式上看，一个联盟博弈的定义是：有一个集合N（n个玩家）和一个函数v，将玩家的子集映射到实数： $v:2^n\rightarrow R,v(\varnothing)=0$ 。其中 $\varnothing$ 表示空集。函数v被称为特征函数。

函数v的含义如下：如果S是一个玩家联盟，那么v(S)称为联盟S的价值，表示S的成员通过合作可以获得的总的预期报酬总和。

Shapley值是将总收益分配给参与者的一种方式，假设他们都进行合作。它是一种 "公平 "的分配，因为它是唯一具有以下某些理想特性的分配。根据沙普利值，在给定的联盟博弈(v,N)中，玩家i得到的金额是
$\varphi_i(v) = \sum_{S \subseteq N/\{i\}}\frac{|S|!(n-|S|-1)!}{n!}(v(S\cup \{i\})-v(S)) \\ =\sum_{S \subseteq N/\{i\}}\left( \begin{array}{cc} n \\ 1,|S|,n-|S|-1\end{array} \right)^{-1}(v(S\cup \{i\})-v(S))$

其中n是玩家总数，总和扩展到不包含玩家i的N的所有子集S上。该公式可以解释如下：设想联盟是由多个玩家组成的，每个玩家要求他们的贡献 $v(S\cup \{i\})-v(S)$ 作为公平补偿。对每个玩家来说，在可能形成联盟的不同排列组合中取这个贡献的平均值。

沙普利值的等价公式是
$\varphi _i(v) = \frac{1}{n!}\sum_{R}[v(P_i^R \cup \{i\})-v(P_i^R)]\\$
所有玩家的排列R的总数为n!， $P_i^R$ 是R中第i个玩家之前的排序。

性质

有效性 efficiency

所有玩家沙普利值的总和等于联盟的价值，所以所有收益都在参与玩家之间分配。
$\sum_{i \in N}\varphi _i(v) = v(N)\\ proof:\sum_{i \in N}\varphi _i(v) =\frac{1}{|N|!}\sum_R \sum_{i \in N} v(P_i^R \cup \{i\})-v(P_i^R)\\ =\frac{1}{|N|!}\sum_R v(N)= \frac{1}{|N|!}|N|!·v(N) = v(N)$
对称性 symmetry

如果i和j是两个平等的玩家，那么 $v(S \cup \{i\}) = v(S\cup \{j\})$ ,对N中包含i或j的任意子集S，都有 $\varphi_i(v) = \varphi_j(v)$ ，这一性质也被叫做同等条件下的平等待遇。
线性性 linearity

如果两个收益函数v和w确定的两个联邦博弈结合起来，那么收益分配应当与它们单独的收益相对应。
$\varphi_i(v+w) = \varphi_i(v)+\varphi_i(w)\\ \varphi_i(av) = a\varphi_i(v)$
Null player

没有玩家的博弈v的沙普利值为0。给定结合N，沙普利值是唯一从博弈集合到支付向量的映射，满足有效性、对称性、线性性、空玩家。
匿名性 anonymity

如果i和j是两个玩家，w是一个获得函数，除了i和j被交换以外，w和v等同，所以 $\varphi_i(v) = \varphi_j(w)$ 。这意味着玩家的标签在分配它们的收益时不起作用。
边际性 marginalism

沙普利值被看作只使用玩家i的边际贡献率为参数的函数。

举例1：手套博弈

玩家1和2各有一只右手手套，玩家3有一只左手手套，联盟博弈的价值函数是
$v(i) = \left\{ \begin{array}{rcl} 1 & \mbox{if} \quad S\in \{\{1,3\},\{2,3\},\{1,2,3\}\} \\ 0 &\quad otherwise \end{array}\right.$

找出所有排列3!，玩家1的边际贡献率如下表

Order R	MC1
1,2,3	$v(\{1\})-v(\varnothing) = 0$
1,3,2	$v(\{1\})-v(\varnothing) = 0$
2,1,3	$v(\{1,2\})-v(\{1\}) = 0$
2,3,1	$v(\{1,2,3\})-v(\{2,3\}) = 1-1=0$
3,1,2	$v(\{1,3\})-v(\{3\}) = 1-0=0$
3,2,1	$v(\{1,2,3\})-v(\{2,3\}) = 1-1=0$

$\varphi_1(v) = \frac{1}{6}\times 1 = \frac{1}{6}$
根据对称性， $\varphi_1(v) = \varphi_2(v) = \frac{1}{6}$
根据有效性， $\varphi_3(v) = \frac{2}{3}$

举例2

共有三家公司，公司1，2，3单独投资可盈利 $v_1=100，v_2==200，v_3=300$ ，如果公司1和公司2联合，可获利 $v_{12}=500$ ；公司2和公司3联合，可获利 $v_{23}=600$ ；公司1和公司3联合，可获利 $v_{13}=700$ ；公司1、公司2和公司3联合，可获利 $v_{123}=1000$ ；那么三个公司一起合作，每个公司应各获利多少？

找出所有排列3!，公司1的边际贡献率如下表

Order R	MC1
1,2,3	$v(\{1\})-v(\varnothing) = 100$
1,3,2	$v(\{1\})-v(\varnothing) = 100$
2,1,3	$v(\{1,2\})-v(\{1\}) = 500-200=300$
2,3,1	$v(\{1,2,3\})-v(\{2,3\}) = 1000-600=400$
3,1,2	$v(\{1,3\})-v(\{3\}) = 700-300=400$
3,2,1	$v(\{1,2,3\})-v(\{2,3\}) = 1000-600=400$

$\varphi_1(v) = \frac{1}{6}\times 1700 = 1700/6$

找出所有排列3!，公司2的边际贡献率如下表

Order R	MC2
1,2,3	$v(\{1,2\})-v(\{1\}) = 500-100=400$
1,3,2	$v(\{1,2,3\})-v(\{1,3\}) = 1000-700=300$
2,1,3	$v(\{2\})-v(\varnothing) =200$
2,3,1	$v(\{2\})-v(\varnothing) =200$
3,1,2	$v(\{1,2,3\})-v(\{1,3\}) = 1000-700=300$
3,2,1	$v(\{2,3\})-v(\{3\}) = 600-300=300$

$\varphi_2(v) = \frac{1}{6}\times 1700 = 1700/6$

找出所有排列3!，公司3的边际贡献率如下表

Order R	MC3
1,2,3	$v(\{1,2,3\})-v(\{1,2\}) = 1000=500=500$
1,3,2	$v(\{1,3\})-v(\{1\}) = 700-100=600$
2,1,3	$v(\{1,2,3\})-v(\{1,2\}) = 1000-500=500$
2,3,1	$v(\{2,3\})-v(\{2\}) = 600-200=400$
3,1,2	$v(\{3\})-v(\varnothing) = 300$
3,2,1	$v(\{3\})-v(\varnothing) = 300$