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

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

合作博弈：夏普利值（shapley value）性质与算法
好好恋爱
2021-01-27
夏普里值方法
Gale-Shapley
反恐网络KPP问题的一种解决思路
（读书笔记）博弈论大全2
Geekband STL与泛型编程第3周作业
博弈论学习笔记
逝者 | “博弈论里的上帝”去了天堂

@[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$

$\varphi_3(v) = \frac{1}{6}\times 2600 = 2600/6$

合作博弈：夏普利值（shapley value）性质与算法
@[toc] 简介沙普利值是合作博弈理论中的一个概念，由劳埃德-沙普利在1951年提出了这个概念，并因此在201...
好好恋爱
盖尔沙普利算法给我们的启示合作博弈处理的是群体群体之间的博弈。艾尔沙普利算法的匹配法则有：艾尔沙普利算法则是博弈...
2021-01-27
算法 | 盖尔-沙普利(Gale-Shapley)婚姻稳定匹配算法置顶Chen_Tianyang[https:/...
夏普里值方法
博弈论的奠基人之一夏普里在研究非策略多人合作的利益分配问题方面有着很高的造诣。他创作的夏普里值法对解决合作利益分配...
Gale-Shapley
Gale-Shapley GS算法全称Gale-Shapley算法，用于解决Stable matching问题，G...
反恐网络KPP问题的一种解决思路
这篇文章将博弈论中的SHAPLEY值来测度网络中的节点重要性，其原理是：基于网络子集效能来进行博弈，计算自己效能值...
（读书笔记）博弈论大全2
非合作性博弈和性质是帮助你如何在博弈中争取更大的利益，而合作性博弈解决的主要是如何分配利益的问题。合作的前提是互...
Geekband STL与泛型编程第3周作业
修正算法算法接口 fill(firstIter,endIter,value) 将元素值value填补到迭代器所指...
博弈论学习笔记
博弈论算法学习记录学习资料总结巴什博奕威佐夫博弈尼姆博弈博弈问题与SG值巴什博奕（Bash Game...
逝者 | “博弈论里的上帝”去了天堂
编者按：这是作者为本周辞世的现代合作博弈论奠基人劳埃德·沙普利撰写的纪念文章。因提出“盖尔-沙普利”算法和稳定匹配...

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

简介

定义

性质

举例1：手套博弈

举例2

相关文章

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

好好恋爱

2021-01-27

夏普里值方法

Gale-Shapley

反恐网络KPP问题的一种解决思路

（读书笔记）博弈论大全2

Geekband STL与泛型编程第3周作业

博弈论学习笔记

逝者 | “博弈论里的上帝”去了天堂

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

散文

简友广场

想法

心理