合作博弈：联盟、分配和核心core

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

合作博弈：联盟、分配和核心core
（读书笔记）博弈论大全2
夏普里值方法
比特币是在构建一种非合作博弈系统
晨读感悟你死我活还是双赢？
零和博弈
《从0到1—开启商业与未来的秘密》读书笔记
Spring
Spring体系架构
零和博弈

@[toc]

合作博弈

概念及其表示

合作博弈：非合作博弈的对称，一种博弈类型。参与者能够联合达成一个具有约束力且可强制执行的协议的博弈类型。合作博弈强调的是集体理性，强调效率、公正、公平。

合作博弈最重要的两个概念是联盟和分配。每个参与者从联盟中分配的收益正好是各种联盟形式的最大总收益每个参与者从联盟中分配到的收益不小于单独经营所得收益。

合作博弈的基本形式是联盟博弈，它隐含的假设是存在一个在参与者之间可以自由流动的交换媒介（如货币），每个参与者的效用与它是线性相关的。这些博弈被称为"单边支付"博弈，或可转移效用（Transferable Utility ，TU）博弈。

合作博弈的结果必须是一个帕累托改进，博弈双方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受损害。合作博弈研究人们达成合作时如何分配合作得到的收益，即收益分配问题。合作博弈采取的是一种合作的方式，合作之所以能够增进双方的利益，就是因为合作博弈能够产生一种合作剩余。至于合作剩余在博弈各方之间如何分配，取决于博弈各方的力量对比和制度设计。因此，合作剩余的分配既是合作的结果，又是达成合作的条件。

合作博弈的核心问题是参与人如何结盟以及如何重新分配结盟的支付。下面首先分析结盟的概念。与结盟相关联的就是特征函数。

定义 8.1.1

在n人博弈中，参与人集用 $N = \{1,2,…,n\}$ 表示，N 的任意子集S称为一个联盟(coalition)。空集 $\varnothing$ 和全集N也可以看成一个联盟，单点集{i}也是一个联盟。

定义 8.1.2

给定一个n人博弈，S是一个联盟，v(S)是指S和 $N-S = \{i|i\in N,i \notin S\}$ 的两人博弈中S的最大效用， $v(S)$ 称为联盟S的特征函数(characteristic function)。

规定 $v(\varnothing) = 0$ 。根据定义, $v(\{i\})$ 表示参与人i与全体其他人博弈时的最大效用值，表示为 $v(i)$ 。

用(N,v)表示参与人集为N,特征函数为v的合作博弈，其中v是定义在 $2^N$ 上的实值映射。

在很多情况下，一个联盟能获得的支付依赖于其他参与人所采取的行动。 $v(S)$ 有时被解释为联盟S独立于联盟N-S的行动可保证的最大支付。

合作对策的分类主要是根据特征函数的性质。下面根据特征函数的性质介绍几类特殊的合作对策。

如果 $v(S)$ 仅与S的个数有关，则(N,v)称作对称博弈。
如果 $v(S) + v(N-S) = v(N)$ ,则(N,v)称作常和博弈。
如果 $\left\{ \begin{array}{rcl}0,S=\{i\}\\1,S=N \end{array}\right.$ ，则(N,v)称作简单博弈。

例如，在投票博弈中，每个参与人的权重 $w_i(w_i<Q),1\leq i \leq n$ ,
$\left\{ \begin{array}{rcl}0,\sum_{i\in S} w_i <Q\\1,\sum_{i\in S} \geq Q \end{array}\right.$
如果 $v(S)+v(T)\leq v(S\cup T)+v(S\cap T)$ ,则(N,v)称作凸博弈。

v之所以称为特征函数，是因为这个合作博弈的性质基本由v决定。由此可见v对合作博弈的重要性。

定理：设v是参与人集合上N的特征函数，则有如下的超可加性：对于联盟 $S_1$ 和 $S_2$ ，如果 $S_1\cap S_2=\varnothing$ ,则 $v(S_1\cup S_2)\geq v(S_1)+v(S_2)$
证明：以最稳妥策略为例给出证明。用 $S^*(X)$ 攻示联盟X的策略空间。
$v(S_1\cup S_2) = \max_{\zeta \in S^*(S_1\cup S_2)} \min_{\eta \in S^*(N/S_1\cup S_2) } U(\zeta,\eta)\\ \geq \max_{\zeta \in S^*(S_1\cup S_2)}\{\min_{\eta \in S^*(N-S_1) } U(\zeta,\eta)+ \min_{\eta\in S^*(N-S_2)} U(\zeta,\eta)\}\\ =v(S_1)+v(S_2)$

上式说明，特征函数只有满足超加性，才有形成新联盟的必要性。否则，如果一个合作博弈的特征函数不满足超可加性，那么其成员没有动机形成联盟，已经形成的联盟将面临解散的威胁。

定理3的逆命题也是正确的，即：N是一个集合，v是定义在 $2^N$ 上的一个非负实值函数。v满足: $v(\varnothing) = 0,v(S_1\cup S_2)\geq v(S_1)+v(S_2)$ ,如果 $S_1\cap S_2 = \varnothing$ ,则存在一个N上的合作博弈，使v成为该合作博弈的特征函数。

对于合作博弈 $(N,v),N=\{1,2,…,n\}$ ，特征函数v满足超加性，自然有：
$v(N)\geq v(\{1\})+v(\{2,…,n\})\geq v(\{1\})+v(\{2\})+v(\{3,…,n\})\geq …\geq \sum_{i=1}^n v(\{i\})$
根据上述不等式，特征函数v分成两种类型：

类型1：v满足 $v(N) = \sum_{i=1}^n v(\{i\})$ 。即大连盟的效用是每个参与人的效用之和。这说明通过联盟并没有创造新的合作剩余，联盟没有价值，这种联盟也不可能维持。这种对策称为非实质性对策，没有研究价值，不是本章研究的范畴。

对于非实质性对策，有 $v(S_1\cup S_2)= v(S_1)+v(S_2)$ ,如果 $S_1\cap S_2 = \varnothing$ 。

类型2：v满足 $v(N)>\sum_{i=1}^n v(\{i\})$ 。即大连盟的效用大于每个参与人的效用之和。这说明通过联盟创造了新的合作剩余，联盟有意义，这种联盟能否维持，取决于如何分配合作剩余，使每个参与人的支付都有改善。这种对策称为实质性对策，是本章研究的范畴。

分配

所谓分配就是博弈的一个n维向量集合，之所以是n维向量，是由于每个参与人都要得到相应的分配。n维的分配向量称为博弈的“解”。

定义8.1.3

对于合作博弈 $(N,v),N={1,2,…,n}$ ，对每个参与人 $i\in N$ ,给予一个实值参数 $x_i$ ，形成n维向量 $x = (x_1,…,x_n)$ 且其满足：
$x_i\geq v(\{i\}),\sum_{i=1}^n x_i=v(N)$
则称x是联盟S的一个分配方案。

分配的定义中， $x_i\geq v(\{i\})$ 是基于个人理性，合作中的收益不能小于非合作中的收益，反映了参与人的参与约朿。如果 $x_i<v(i)$ ,那么，参与人i是不可能参加联盟的。 $\sum_{i=1}^n =v(N)$ 是基于集体理性，每个参与人的分配之和不能超过集体剩余v(N)。另外若v(N)没有全部被分配，显然X不是一个帕累托最优的分配方案，不会参与人所接受。

在例8.1分配中，分配显然不是一个，而是无限个，无限个分配形成一个分配集合。对于实质博弈，其分配总是有无限个。例如，对于实质博弈(N,v),由于
$\Delta = v(N)-\sum_{i=1}^nv(\{i\})>0$
存在无限个正向量 $u = (u_1,u_2,…,u_n)$ ，满足 $\Delta u = u_1+u2,…,+u_n$ .显然如下的 $x = (x_1,…,x_n)$ 都是分配，其中 $x_i = v(\{i\})+u_i,1\leq i\leq n$ .用E(v)表示一个博弈v的所有分配方案组成的集合。

定义8.1.4

设E(v)的两个分配x和y，S是一个联盟。如果分配方案x和y满足

（i） $x_i>y_i<\forall i \in S;$

（ii） $\sum_{i\in S} x_i \leq v(S)$

则称分配方案x在上优超于y，或称分配方案y在S上劣于x，记为 $x \succ_S y$

如果分配方案x在S上优超于y ，则联盟S会拒绝分配方案y, y方案得不到切实执行。因为从y到x,S中的每个参与人的收益都得到改善，S创造的剩余v(S)又足以满足他们在x中的分配。

在优超关系中，联盟S的特征:

单人联盟不可能有优超关系。
全联盟N上也不可能有优超关系。因此，如果在S上有优超关系，则 $2\leq |S|\leq n-1$
优超关系是集合E(v)上的序关系，这种序关系一般情况下不具有传递性和反身性。
对于相同的联盟S ,优超关系具有传递性,即 $x\succ_S y，y\succ_S z，则有x\succ_S z$ 。
对于不同的联盟S ,优超关系不具有传递性。

核心

尽管可行分配集合E(v)有无限个分配，但实际上，有许多分配是不会被执行的，或者不町能被参与人所接受的。很显然，联盟的每一个成员都不偏好于劣分配方案，因此，真实可行的分配方案应该剔除劣分配方案。

定义8.3.1

在一个n人合作博弈(N,v)中，全体优分配方案形成的集合称为博弈的核心(core),记为C(v)。显然有 $C(v)\subseteq E(v)$ .

说明:

1 .核心C(v)是E(v)中的一个闭凸集。

2.若 $C(v)\ne \varnothing$ 中的向量X作为分配，X既满足个人理性，又满足集体理性。

3.用核心作为博弈的解，其最大缺陷是C(v)可能是空集。

定理8.3.1

分配方案 $x = (x_1,…,x_n)$ 在核心C(v)中的充要条件是：

（i） $\sum_{i\in S} x_i \geq v(S), \forall S\subset N$

（ii） $\sum_{i=1}^n x_i = v(N)$

证明：如果 $x\subseteq E(v)$ ,x满足(i)(ii)，则x不可能被优超，即 $x\in C(v)$

反证法：设存在S，使 $y\succ_S x$ 。根据优超的定义，有：
$x_i<y_i,\forall i \in S , \sum_{i\in S}y_i \leq v(S)$
则有 $v(S)\leq \sum_{i\in S}x_i < \sum_{i\in S}\leq v(S)$ ，矛盾。

如果 $x\subseteq E(v)$ ,x不满足（ii）,则x一定被优超，即 $x\ne C(v)$ 。

对于 $x\subseteq E(v)$ ,存在联盟S，有 $\sum_{i\in S}x_i < v(S)$ ,则定义 $\zeta = v(S)-\sum_{i\in S}x_i >0,\eta = v(N)-v(S)-\sum_{i \in N/S} v(\{i\})>0$ ，使得 $\zeta$ 在S中平均分配， $\eta$ 在N-S中平均分配，从而得到一个新的分配 $y = (y_1,…,y_n)$ 如下：
$\left\{ \begin{array}{rcl}x_i+\frac{\zeta}{|S|},\forall i \in S\\v(\{i\})+\frac{\eta}{n-|S|},\forall i\ne S \end{array}\right.$
显然如此定义的向量 $y = (y_1,…,y_n)$ 是个分配，且有 $y \succ_S x$ 。

在合作博弈中，用核心代替分配具有明显的优点，即C(v) 的稳定性。对于C(v)中的每一个分配，每个联盟都没有反对意见，都没有更好的分配，每个分配都可以得到执行。当然，用C(v)代替E(v)也有致命的缺陷，即C(v)有可能是空集, 而 $E(v)\ne \varnothing$ 。

定理8.3.2

对于n人的联盟博弈，核心C(v)非空的充分必要条件是线性规划(P)有解。
$(P) \quad \min \sum_{i=1}^nx_i \leq v(N)\\ s.t. \left \{ \begin{array}{rcl}\sum_{i \in S}x_i\geq v(S)\\ & \forall S \subset N\\ \sum_{i=1}^n x_i = v(N)\end{array}\right.$
定理的直观意义很明显，线性规划（L）若有解，则最优解一定属于C(v);若 $C(v)\ne \varnothing$ ,则C(v)中的每个向量都是可行解，自然线性规划（L）有最优解解。

对于原线性规划（P）,写出它的对偶规划（DP）
$(DP) \quad \max \sum_{S\subseteq N}^n y_S v(S) \leq v(N)\\ s.t. \left \{ \begin{array}{rcl}\sum_{S \subseteq N}y_S =1\\ & \forall S \subset N\\ y_S\geq 0\end{array}\right.$
定理：对策(N,v)有 $C(v)\ne \varnothing$ 的充分必要条件是:

对于满足 $s.t. \left \{ \begin{array}{rcl}\sum_{S \subseteq N}y_S =1\\ & \forall S \subset N\\ y_S\geq 0\end{array}\right.$ 的向量 $\{y_S\}$ ，有 $\sum_{S\subseteq N}y_S v(S) \leq v(N)$

定义：设(N,v)是个0-1简单对策，若存在一个参与人i ,满足 $v(N-\{i\}) = 0$ ，则i称作一个否决人。

定理：简单对策(N,v)中， $C(v)\ne \varnothing$ 充分必要条件是N中存在一个否决人。

证明：设j是N中一个否决人,定义$e_i =( 0,0,…,1,0,…,0), 1处于第i的位置。

根据定理8.3.2, $e_i=(0,0,…,1,0,…,0$ 是一个分配,且 $e_i \in C(v)$ 。

用反证法。设 $C(v) \ne \varnothing$ ，且不存在否决人，即 $v(N-\{i\})=1.\forall x \in C(v), 则x(N) = 1,x(N-\{i\})\geq v(N-\{i\})\geq 1,i\in N.$

故有 $1 = x(N) = x(N-\{i\})+x(\{i\}) \geq 1+x,i\in N$ ,从而 $x_i\leq 9,i\in N,也即v(N) = \sum_{i \in N} x_i \leq 0$ 矛盾。

核仁

为评估S对X满意性，定义如下的被称作超出一个指标：
$e(S,x) = v(S）-\sum_{i\in S}x_i$
e(S,x)的大小反映了 S对x的满意性。e(S,x)越大，S对x越不满意，因为S中所有参与人的分配之和远没有达到其所创造的合作剩余v(S); e(S,x)越小，S对X越满意，当e(S,x)为负值时，S中所有参与人不但分配了其所创造的合作剩余v(S)，还分配了其他联盟所创造的价值。

对于同一个x, S共有 $2^n$ 个，可以表示为 $S_j,j=1,2,…,2^n$ 。故可以计算出 $2^n$ 个 $e(S_j,x),j = 1,2,...,2^n$ 。联盟对x的满意性取决于 $e(S_j,x)$ 中的最大的 $j=1,2,…,2^n$ ,故可以对 $2^n$ 个 $e(S_j,x)$ 由大到小排列，得到一个 $2^n$ 的向量：
$\theta(x) = (\theta_1(x),\theta_2(x),…,\theta_{2^n}(x))$
其中 $\theta_j(x) = e(S_j,x),j=1,2,…,2^n,\theta_1(x)\geq \theta_2(x)\geq …\geq \theta_{2^n}(x)$ 。联盟对x的满意性取决于 $\theta(x)$ 的大小， $\theta(x)$ 越小，联盟对x越满意。

对于两个不同的分配x,y ,分别计算出 $\theta (x),\theta (y)$ 。如果 $\theta(x)$ 小的，则联盟对x的满意性大于联盟对y的满意性，自然x优于y。当然这种向量大小的比较不同于数字的比较，是釆用字典序的比较方法。字典序的比较方法的比较方法如下：

对于向量 $\theta(x) = (\theta_1(x),\theta_2(x),…,\theta_{2^n}(x))$ 和

$\theta(y) = (\theta_1(y),\theta_2(y),…,\theta_{2^n}(y))$ 存在-个下标左，使得 $\theta_j(x) = \theta_j(y),1\leq j \leq k-1,\theta_k(x)<\theta_k(y)$ 则称 $\theta(x)$ 字典序小于 $\theta(y)$ _,用符号表示 $\theta(x) \prec_L \theta(y)$ 。有了上述的定义，就可以给岀核仁的定义了。

定义：对于合作博弈(N,v)，核仁是一些分配的集合，即 $\tilde N \subset E(v)$ ,使得任取一个 $x\in \tilde N,\theta(x)$ 都是字典序最小的，即 $\tilde N = \{x \in E(v):\forall y \in E(v),y\ne x,\theta(x)\prec_L\theta(y)$

定理5.4

对于合作博弈(N,v),其核仁 $\tilde N\ne \varnothing$ ,且 $\tilde N$ 只包含一个元素x。

定理5.5

对于合作博弈(N,v)，如果核心 $C\ne \varnothing$ ,则有 $\tilde N \subseteq C$ 。

证明：用反证法。设存在一个分配

根据核心的性质，由居顷知：必存在一个联盟S,满足2><心)，由此可知*,》)= *)-

例8.5

考虑如下的合作博弈(N,v),N = {1,2,3},特征函数如下:

v({1}) = 4,v({2}) = v({3}) = 0 ；

v({1, 2}) = 5, v({1,3}) = 7, v({2,3}) = 6 ； v({1,2,3}) = 10。求该博弈的核仁。

解：先求出该博弈的核心，再求核仁。

根据核心的条件 $x = (x_1,x_2,x_3)\in C(v)$ 充分必要条件：
$\left \{ \begin{array}{rcl}x_1\geq 4,x_i\geq 0,i=2,3\\ x_1+x_2\geq 5\\ x_1+x_3\geq 7\\ x_2+x_3\geq 6\\ x_1+x_2+x_3=10\end{array}\right.$

解此不等式组，得到 $C(v) = {(4,6-x,x):3\leq x\leq5}$

$C(v)\ne \varnothing$ ,故有 $\tilde N \subseteq C$ .下面开始求核仁。

对于核心 $C(v) = {(4,6-x,x):3\leq x\leq 5},$ 开始求 $e(S,x) = v(S)-\sum_{i \in S} x_i,x\in C(v)$
$S_1 = \{1\},e(S_1,x) = 4-4=0\\ S_2=\{2\},e(S_2,x) =0 -(6 - x) = x-6 \\ S_3=\{3\},e(S_3,x) =0- x = -x\\ S_4=\{1,2\},e(S_4,x) =5— [4 + (6 -x)] = x - 5 \\ S_5={1,3},e(S_5,x) = 7 - (4+x) =3-x \\ S_6 = {2,3}, e(S_6,x) =6- [(6-x) + x] =0\\ S_7 ={1,2,3},e(S_7,x) =10-10 = 0$
当 $3\leq x\leq 5, \theta_1(x) = \min \max_{j=1} e(S_j, x) = \min \max_{\{x - 5,3 - x\}}$ 上式在x=4 达到，故有 $\tilde N =\{(4,6-x,x) : x = 4\} = \{(4,2,4)\}$ 。该结果验证了 $\tilde N \ne \varnothing, |\tilde N| = 1.$

合作博弈：联盟、分配和核心core
@[toc] 合作博弈概念及其表示合作博弈：非合作博弈的对称，一种博弈类型。参与者能够联合达成一个具有约束力且...
（读书笔记）博弈论大全2
非合作性博弈和性质是帮助你如何在博弈中争取更大的利益，而合作性博弈解决的主要是如何分配利益的问题。合作的前提是互...
夏普里值方法
博弈论的奠基人之一夏普里在研究非策略多人合作的利益分配问题方面有着很高的造诣。他创作的夏普里值法对解决合作利益分配...
比特币是在构建一种非合作博弈系统
“ 回顾整个社会的发展，早期都是以合作博弈的方式来管理，比如宗教、政治，都对分配这个问题非常敏感。这个分配机制能检...
晨读感悟你死我活还是双赢？
合作中除了你赢我输的局面，还有一种可能叫双赢，即非零和博弈。非零和博弈是一种合作下的博弈，博弈中各方的收益或损失...
零和博弈
零和博弈（zero-sum game），又称零和游戏，与非零和博弈相对，是博弈论的一个概念，属非合作博弈。指参与博...
《从0到1—开启商业与未来的秘密》读书笔记
零和博弈（zero-sum game），又称零和游戏，与非零和博弈相对，是博弈论的一个概念，属非合作博弈。指参与博...
Spring
1.Spring整体架构（1）Core container 核心容器包括了Core、Beans、Context和...
Spring体系架构
1、Core Container(核心容器)该模块主要包含Core、Beans、Context和SpEL模块。其中...
零和博弈
零和博弈又称零和游戏，与非零和博弈相对，是博弈论的一个概念，属非合作博弈。指参与博弈的各方，在严格竞争下，一方的收...

合作博弈：联盟、分配和核心core

合作博弈

概念及其表示

定义 8.1.1

定义 8.1.2

分配

定义8.1.3

定义8.1.4

核心

定义8.3.1

定理8.3.1

定理8.3.2

核仁

定理5.4

定理5.5

例8.5

相关文章

合作博弈：联盟、分配和核心core

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

夏普里值方法

比特币是在构建一种非合作博弈系统

晨读感悟你死我活还是双赢？

零和博弈

《从0到1—开启商业与未来的秘密》读书笔记

Spring

Spring体系架构

零和博弈

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读