第五章 合作博弈.ppt

博弈 论任课教师： 南京航空航天大学 经管学院李帮义 教授博弈论与信息经济学——第五章 合作博弈导论先回忆一下囚徒困境的例子：在囚徒困境中，还有另外一个策略组合， 该组合为参与人带来的支付是由到，每个参与人的支付都增加了，即得到一个帕累托改 进 坦白抵抗坦白-8，-80，-10抵抗-10，0-1，-1导论构不成一个均衡是基于参与人的个人理性在参与人 选择抵抗的情况下，每个参与人都有动机偏离这个组合，通过投机 行为谋取超额收益1如果两个参与人在博弈之前，签署了一个协 议：两个人都承诺选择抵抗，为保证承诺的实现，参与人双方向第 三方支付价值大于1的保证金；如果谁违背了这个协议，则放弃保 证金有了这样一个协议，就称为一个均衡，每个人 的收益都得到改善上述分析表明，通过一个有约束力的协议，原来不能实现的合 作方案现在可以实现这就是合作博弈与非合作博弈的区别二者 的主要区别在于人们的行为相互作用时,当事人是否达成一个具有约 束力的协议如果有,就是合作博弈；反之,则是非合作博弈 因此 ，博弈可以划分为合作博弈与非合作博弈 合作博弈的概念及其表示 合作博弈，非合作博弈的对称，一种博弈类型参 与者能够联合达成一个具有约束力且可强制执行的协议 的博弈类型。

合作博弈强调的是集体理性,强调效率、公 正、公平合作博弈最重要的两个概念是联盟和分配每个参 与者从联盟中分配的收益正好是各种联盟形式的最大总 收益,每个参与者从联盟中分配到的收益不小于单独经营 所得收益合作博弈的基本形式是联盟博弈,它隐含的假设是存 在一个在参与者之间可以自由流动的交换媒介(如货币), 每个参与者的效用与它是线性相关的这些博弈被称为“ 单边支付”博弈,或可转移效用(Transferable Utility ,TU)博 弈 合作博弈的概念及其表示合作博弈的结果必须是一个帕累托改进，博弈双方 的利益都有所增加，或者至少是一方的利益增加，而另 一方的利益不受损害合作博弈研究人们达成合作时如 何分配合作得到的收益，即收益分配问题合作博弈采 取的是一种合作的方式，合作之所以能够增进双方的利 益，就是因为合作博弈能够产生一种合作剩余至于合 作剩余在博弈各方之间如何分配，取决于博弈各方的力 量对比和制度设计因此，合作剩余的分配既是合作的 结果，又是达成合作的条件 合作博弈的核心问题是参与人如何结盟以及如何重 新分配结盟的支付下面首先分析结盟的概念与结盟 相关联的就是特征函数 合作博弈的概念及其表示定义定义8.1.18.1.1 在 人博弈中，参与人集用 表示 ， 的任意子集 称为一个联盟联盟（coalition）。

空集 和全集 也可以看成是一个联盟，当然单点集 也是一个联盟 定义定义8.1.28.1.2 给定一个 人博弈， 是一个联盟， 是指 和的两人博弈中 的最大效用， 称为 联盟 的特征函数特征函数（characteristic function）规定 根据定义， 表示参与人 与全体其他人博弈时 的最大效用值，表示为 用 表示参与人集为 ，特征函数为 的合作博弈，其中 是 定义在 上的实值映射在很多情况下，一个联盟能获得的支付依赖于其他参与人所采取的 行动 有时被解释为联盟 独立于联盟 的行动可保证的最 大支付 合作博弈的概念及其表示合作对策的分类主要是根据特征函数的性质下面根据 特征函数的性质介绍几类特殊的合作对策n如果 仅与 的个数有关，则 称作对称博弈n如果 ，则 称作常和博弈n如果 ，则 称作简单博弈例如，在投票博弈中，每个参与人的权重 ，n如果 ，则 称作凸博弈 。

合作博弈的概念及其表示例8.1 设有一个3人合作对策，每个参与人各有两个纯策略 当三人不合作时，其支付见下表假设采用最稳妥策 略，即最坏情况下选择最好，求合作博弈的支付函数 合作博弈的概念及其表示解：用 表示一个联盟， 表示联盟中参与人的个数当 ＝0，自然 ，有 当 ＝1， 有3个，以 为例当 ，则 的策略集合 ，策略组合 与 进行如下矩阵对策： 合作博弈的概念及其表示上述矩阵对策没有纯策略， 的混合策略是 ， 的混合策略是 的均衡值是 故 同理，可以求出 当 ＝2， 有3个，以 为例当 ，则 的策略集合 ,策略组合 与 进行如下矩阵对策： 合作博弈的概念及其表示上述矩阵对策有纯策略， 的均衡值是 故 同理，可以求出 。

当 ＝3， 有1个， ，最大的联盟 的策略空 间 有 至此特征函数的值已全部求出合作博弈的概念及其表示之所以称为特征函数，是因为这个合作博弈的性质基 本由 决定由此可见 对合作博弈的重要性n n定理定理 设 是参与人集合上 的特征函数，则有如下的超 可加性：对于联盟 和 ，如果 ，则n n证明证明 以最稳妥策略为例给出证明用 表示联盟 的策略空间 合作博弈的概念及其表示上式说明，特征函数只有满足超加性，才有形成新联盟的必要性否则，如果一个合作博弈的特征函数不满 足超可加性，那么，其成员没有动机形成联盟，已经形 成的联盟将面临解散的威胁定理3的逆命题也是正确的，即：是一个集合， 是定义在 上的一个非负实值函数 满 足：，如果 则存在一个 上的合作博弈，使 成为该合作博弈的特 征函数合作博弈的概念及其表示对于合作博弈 ，特征函数 满足超加性 ，自然有：根据上述不等式，特征函数 分成两种类型：类型类型1 1， 满足 。

即大连盟的效用是每个 参与人的效用之和这说明通过联盟并没有创造新的合 作剩余，联盟没有价值，这种联盟也不可能维持这种 对策称为非实质性对策，没有研究价值，不是本章研究 的范畴对于非实质性对策，有 ，如果 合作博弈的概念及其表示类型类型2 2， 满足 即大连盟的效用大于每个参与人的效用之和这说明通过联盟创造了新的合作剩 余，联盟有意义，这种联盟能否维持，取决于如何分配 合作剩余，使每个参与人的支付都有改善这种对策称 为实质性对策，是本章研究的范畴 分配 所谓分配就是博弈的一个 维向量集合，之所以 是维 向量，是由于每个参与人都要得到相应的分配 维的 分配向量称为博弈的“解”定义定义8.1.38.1.3 对于合作博弈 ，对每个参与 人 ，给予一个实值参数 ，形成 维向量 且其满足：则称 是联盟 的一个分配方案分配方案分配分配的定义中， 是基于个人理性，合作中的收益不能小于非合作中的收益，反映了参与人的参与 约束如果 ，那么，参与人 是不可能参加 联盟的。

是基于集体理性，每个参与人的分配之和不能超过集体剩余 另外若 没有全部被分配 ，显然 不是一个帕类托最优的分配方案，不会参与人 所接受 分配在例8.1分配中，分配显然不是一个，而是无限个，无限 个分配形成一个分配集合 对于实质博弈，其分配总是有无限个例如，对于实质博弈 ，由于存在无限个正向量 ，满足 显然如下的 都是分配，其中 用 表示一个博弈 的所有分配方案组成的集合 分配定义定义8.1.48.1.4 设 的两个分配 和 ， 是一个联盟如 果分配方案 和 满足（i） ， ；（ii） 则称分配方案 在 上优超于 ，或称分配方案 在 上劣于 ，记为 如果分配方案 在 上优超于 ，则联盟 会拒绝分 配方案 ， 方案得不到切实执行因为从 到 ， 中的每个参与人的收益都得到改善， 创造的剩余 又 足以满足他们在 中的分配 分配在优超关系中，联盟 的特征：1.单人联盟不可能有优超关系。

2.全联盟 上也不可能有优超关系因此，如果在 上有优超关系，则 3.优超关系是集合 上的序关系，这种序关系一般情况 下不具有传递性和反身性4.对于相同的联盟 ，优超关系具有传递性，即 ， ，则有 5.对于不同的联盟 ，优超关系不具有传递性 核心 尽管可行分配集合 中有无限个分配，但实际上，有许多分配是不会被执行的，或者不可能被参与人所 接受的 很显然，联盟的每一个成员都不偏好于劣分配 方案，因此，真实可行的分配方案应该剔除劣分配方案 定义定义8.3.18.3.1 在一个 人合作博弈 中，全体优分 配方案形成的集合称为博弈的核心核心(core)，记为 显然有 核心说明：1.核心 是 中的一个闭凸集2.若 ，则将 中的向量 作为分配， 既 满足个人理性，又满足集体理性3.用核心作为博弈的解，其最大缺陷是 可能是空集 核心定理定理8.3.18.3.1 分配方案 在核心 中的充要条件 是：（i） ， ，(ii) 。

证明 如果 ， 满足（i）、(ii)，则 不可能被优超，即 反证法，设存在 ，使 根据优超的定义，有:则有 ，矛盾 如果 ， 不满足 (ii)，则 一定被优超，即 核心对于 ，存在联盟 ，有 ，则定义 ，定义 ，使得 在 中平均分配， 在 中平均分配，从而得到一个新的分配 如 下：显然如此定义得向量 是个分配，且有 核心例8.2 假想的联合国安全理事会投票，超过两票算通过 该博弈的特征函数为而对所有其他的 ， 应用定理8.3.1，有 ，对各个联盟有由 ， ， ， 推得 ， ， ，而用 ， ， 又 得到 和 ，所以，核心是核心例8.3 设3人合作博弈 的特征函数如下：， ， ， ， 求其核心 。

解 由核心定义，若 ，则它必满足解此不等式组，得核心例8.4 考虑如下的合作博弈， 。