【夏普利值——详细讲解】

夏普利值的介绍

沙普利值是合作博弈理论中的一个概念，由劳埃德-沙普利在1951年提出了这个概念，并因此在2012年获得了诺贝尔经济学奖。对于每个合作博弈，如联邦学习，可以将机构产生的模型的总提升在各个机构上形成一个有效的贡献分配。沙普利值的特点是有一系列的理想属性。
存在以下特点：
1.对称性：合作获利的分配，不随每个人在合作中的记号或次序变化
2.有效性：合作各方获利总和等于合作获利
3.冗员性：如果一个成员对于任何他参与的合作联盟都没有贡献，则他不应当从全体合作中获利
4.有多种合作时，每种合作的利益分配方式与其他合作结果无关

定义

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

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

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

• S是从N中除i以外的所有玩家组成的任意子集
• |S|是子集S中的元素个数，也就是除了玩家i之外其他玩家的数量
• n是集合N中总的玩家数量
• v ( S ∪ { i } ) v(S \cup \{i\} ) v(S∪{i})表示在集合S加上玩家i后形成的联盟所带来的收益
• $v(S)$表示仅由集合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个玩家之前的排序。

举例

假设有三个机构{A，B，C}进行联邦学习:
三个机构分别单独训练可以得到$v_A=0.80,v_B=0.70,v_C=0.75$,
两两联合训练的正确率为，$v_{AB}=0.85,v_{BC}=0.80,v_{AC}=0.90$,
集合起来一起训练得$v_{ABC}=0.95$
问应该如何分配模型的贡献率：

对于机构A而言：

对于A而言贡献为$(0.8\ast 2+0.15\ast 4)/3!=\mathrm{0.366666.....}$

对于机构B而言

对于B而言贡献为$(0.7\ast 2+0.05\ast 4)/3!=\mathrm{0.266666.....}$

对于机构C而言

对于C而言贡献为$(0.75\ast 2+0.1\ast 4)/3!=\mathrm{0.3166666.....}$

三个机构的总贡献率为：0.36666…+0.2666…+0.31666…=0.95

参考

https://www.jianshu.com/p/f02320e1f091
https://zhuanlan.zhihu.com/p/483891565