|
|
一个例子
这个例子将会贯穿全文。
假设有一个资本家 (c) 和两个工人 (w_1, w_2) ，他们之间合作带来的收益如下：
- F(c)=F(w_1)=F(w_2)=0
- F(c\cup w_1)=F(c\cup w_2)=3, ~F(w_1\cup w_2)=0
- F(c\cup w_1\cup w_2)=4
解释：仅有资本家或仅有工人都不能带来任何收益；一个资本家与一个工人合作能带来3的收益；三人共同合作则能带来4的收益。
这就是合作博弈的例子，资本家和工人们进行合作，然后对得到的收益进行分配。
合作博弈基本概念
定义
通常表示为二元组 (N,v) ，其中 N 是玩家集合， v:2^N\rightarrow \mathbb{R} 表示所有可能的合作组合 S 的收益函数 例子中， N=3 ， v 实际上就是 F 。
超可加性(Superadditive)
博弈 G=(N,v) 若对任何 S,T\subset N ， S\cap T=\emptyset ，都有 v(S\cup T)\geq v(S) +v(T) ，则称该博弈是超可加的 超可加性描述的是合作比分离收益高，大联盟比小联盟收益高。例子是满足超可加性的，比如可以验证：
- v(c\cup w_1)=3>v(c)+v(w_1)=0
- v(c\cup w_1\cup w_2)=4>v(c\cup w_1)+v(w_2)=3
其余任何一种分法也都成立。
合作博弈要解决的两个问题
- 如何构建联盟？例子中资本家与一个工人合作 (c\cup w_1) 是否比与两个工人合作(c\cup w_1\cup w_2) 更好？
- 如何分配收益？例子中 (c\cup w_1\cup w_2) 得到4的收益如何分配给资本家和每个工人？
对于问题1，需要考虑联盟的稳定性。假设确定了某种合作，是否会有人不满分配到的收益而希望离开联盟寻找新的联盟？即说明这种联盟是不合理的？
这个问题将通过核(Core)进行探讨。
对于问题2，需要考虑联盟的公平性。如何公平的分配收益？让贡献越大的人获得越多的收益？
这个问题将通过沙普利值(Shapley Value)进行探讨。
沙普利值
思想：按照联盟中成员的边际贡献的比例来分配收益。
边际贡献
假设考虑加入联盟的顺序，新加入者对联盟收益的贡献就是边际贡献 例子中，假设 c 先加入联盟，随后 w_1 加入，最后 w_2 加入，此时三者的边际贡献分别为
\begin{align} &m(c)=v(c)=0\\ &m(w_1)=v(c\cup w_1)-v(c)=3\\ &m(w_2)=v(c\cup w_1\cup w_2)-v(c\cup w_1)=1 \end{align}\\
三条原则
对任意收益 v ，若成员 i,j 对其余任何成员组合的边际贡献都相等，则 i,j 分配到的收益相等，即 \psi_i(N,v)=\psi_j(N,v) 例子中，对 w_1 和 w_2 来说， v(w_1)=v(w_2)=0 ， v(c\cup w_1)-v(c)=v(c\cup w_2)-v(c)=3 ，即他们加入联盟 \emptyset 或者联盟 (c) 都有相同的边际贡献，故他们分配的收益应当相等。
若成员 i 对其余任何成员组合的边际贡献都为0，则 i 分配应为0，即 \psi_i(N,v)=0 例子中不存在无效的成员。
若博弈分为两部分分别博弈，即 (v_1+v_2)(S)=v_1(S)+v_2(S) ，则对任意 v_1,v_2 ，应当满足 \psi_i(N,v_1+v_2)=\psi_i(N,v_1)+\psi_i(N,v_2) 可加性实际上就是说若进行两项互不影响的博弈，则它们的分配也应当互相不影响。例子不涉及这种情况，但可以假想，如果资本家和工人们又经营了一家新的公司，则新公司的分配策略应当与当前公司无关。
沙普利值的计算
收益分配应当按照如下公式计算：
\phi_i(N,v)=\frac{1}{N!}\sum_{S\subset N\backslash{i}}|S|!(|N|-|S|-1)![v(S\cup\{i\})-v(S)]\\
已有定理保证，对于满足对称性、无效性、可加性的合作博弈，沙普利值唯一。
拆分公式理解：
- [v(S\cup\{i\})-v(S)] 表示对于序列 S 观察加入 i 的边际贡献
- |S|! 表示序列 S 有多少种可能
- (|N|-|S|-1)! 表示加入 i 之后到构成整个联盟，这期间加入的成员有多少种序列可能
- \Sigma_{S\subset N\backslash{i}} 表示对所有 i 前可能发生的序列做遍历
- 1/N! 表示除以对所有成员的序列可能，类似除以权重归一处理
实际上就是列出所有的可能情况，然后取个平均。公式看起来比较复杂，但对于实际例子非常好理解。
例子中对 c 而言，先列出所有可能序列(成员加入联盟的顺序)，共六种：
\begin{align} &()\rightarrow(c)\rightarrow(c,w_1)\rightarrow(c,w_1,w_2)~~~~~~~~&(1)\\ &()\rightarrow(c)\rightarrow(c,w_2)\rightarrow(c,w_1,w_2)~~~~~~~~&(2)\\ &()\rightarrow(w_1)\rightarrow(c,w_1)\rightarrow(c,w_1,w_2)~~~~~~~~&(3)\\ &()\rightarrow(w_1)\rightarrow(w_1,w_2)\rightarrow(c,w_1,w_2)~~~~~~~~&(4)\\ &()\rightarrow(w_2)\rightarrow(c,w_2)\rightarrow(c,w_1,w_2)~~~~~~~~&(5)\\ &()\rightarrow(w_2)\rightarrow(w_1,w_2)\rightarrow(c,w_1,w_2)~~~~~~~~&(6)\\ \end{align}\\
然后计算 c 每种情况的边际贡献：
\begin{align} &(1)~~v(c)=0\\ &(2)~~v(c)=0\\ &(3)~~v(c\cup w_1)-v(w_1)=3\\ &(4)~~v(c\cup w_1\cup w_2)-v(w_1\cup w_2)=4\\ &(5)~~v(c\cup w_2)-v(w_2)=3\\ &(6)~~v(c\cup w_1\cup w_2)-v(w_1\cup w_2)=4 \end{align}
沙普利值就是各种情况边际贡献的平均，即 \phi_c(N,v)=\frac{1}{6}(0+0+3+4+3+4)=\frac{7}{3} 。同理可以计算 \phi_{w_1}(N,v)=\phi_{w_2}(N,v)=\frac{5}{6} 。
再来理解一下公式， S 有 (),(w_1),(w_2),(w_1,w_2) 四种情况，权重 |S|!(|N|-|S|-1)! 分别为 2，1，1，2 ，对应式子 (1)(2),(3),(5),(4)(6) 。
核
定义
博弈 G=(N,v) ，分配向量 x 若满足 \forall S\subset N,\sum_{i\in S}x_i\geq v(S) ，则称 x 在 G 的核中 也就是说核是由一些分配方式组成，这些分配方式要保证大联盟比任何分离的小联盟要好(至少不会更差)。这个概念核纳什均衡很像，按照核分配能保证成员不会背叛大联盟。这时，就要关心几个问题：
- 存在性。核一定非空吗？
- 唯一性。核中的分配方式唯一吗？
- 和沙普利值的关系。沙普利值一定在核中吗？
先来看看例子中的核是什么。假设分配向量 x=(x_c,x_{w_1},x_{w_2}) 是分配给三人的收益，则满足分配收益之和为联盟获得的收益，即 x_c+x_{w_1}+x_{w_2}=v(c\cup w_1\cup w_2)=4 ；同时分给任何几个成员的收益之和要不少与他们独立组成小联盟的收益，即 x_c\geq v(c)=0,~x_{w_1}\geq v(w_1)=0,~x_{w_2}\geq v(w_2)=0\\ x_c+x_{w_1}\geq v(c\cup w_1)=3,~x_c+x_{w_2}\geq v(c\cup w_2)=3\\ x_{w_1}+x_{w_2}\geq v(w_1\cup w_2)=0
等于0的不用考虑，所以最终核需满足：
\begin{align} x_c+x_{w_1}+x_{w_2}=4\\ x_c+x_{w_1}\geq =3\\ x_c+x_{w_2}\geq =3\\ \end{align}\\
比如 (2,1,1),(3,0,1),(3,0.5,0.5) 都在核中，沙普利值 (\frac{7}{3},\frac{5}{6},\frac{5}{6}) 也在核中。但 (1,1,2) 就不在核中，此时 c 和 w_1 更倾向于离开联盟组成新联盟 (c\cup w_1) ，能获得更多的收益。
这个例子的核中有很多分配方式，存在但不唯一，且沙普利值也在核中。
在某些限定条件下，有一些理论探讨关心的三个问题。
简易博弈(Simple Game)
称博弈 G=(N,v) 是简易的，如果对所有的 S\in N,~V(S)\in\{0,1\} 否决者(Veto Player)
如果 v(N\backslash\{i\})=0 ，则 i 是否决者 例子中的资本家 c 就是否决者，没有他就没有收益。
定理
在简易博弈中，当且仅当不存在否决者时，核为空
凸博弈(Convex Game)
称博弈 G=(N,v) 是凸的，如果对任意 S,T\in N ， v(S\cup T)\geq v(S)+v(T)-v(S\cap T) 这时一个比超可加性更强的条件。
定理
凸博弈的核非空
凸博弈情况下，沙普利值在核中
沙普利值与核的关系
沙普利值描述的是公平性，核描述的是稳定性。
若沙普利值不在核中，且我们取了沙普利值作为分配方案，此时实际上因为联盟的不稳定，这个联盟压根就无法形成。
若沙普利值不在核中，且我们取了核中的分配方案，此时联盟是稳定的，但是并不公平，可能收益大部分或者全部都给了否决者(比如资本家)，而其他人(比如工人)只分配到少量收益甚至没有收益。
若沙普利值在核中，此时取沙普利值作为分配方案就是最佳的。 |
|
发表于 2022-9-19 10:00:06
