第五章 合作博弈ppt课件.ppt

《第五章 合作博弈ppt课件.ppt》由会员分享，可在线阅读，更多相关《第五章 合作博弈ppt课件.ppt（60页珍藏版）》请在三一办公上搜索。

1、博弈论,任课教师：南京航空航天大学 经管学院 李帮义 教授,博弈论与信息经济学,第五章 合作博弈,导论,先回忆一下囚徒困境的例子： 在囚徒困境中，还有另外一个策略组合，该组合为参与人带来的支付是。由到，每个参与人的支付都增加了，即得到一个帕累托改进。,导论,构不成一个均衡是基于参与人的个人理性。在参与人选择抵抗的情况下，每个参与人都有动机偏离这个组合，通过投机行为谋取超额收益1。如果两个参与人在博弈之前，签署了一个协议：两个人都承诺选择抵抗，为保证承诺的实现，参与人双方向第三方支付价值大于1的保证金；如果谁违背了这个协议，则放弃保证金。有了这样一个协议，就称为一个均衡，每个人的收益都得到改善。

2、 上述分析表明，通过一个有约束力的协议，原来不能实现的合作方案现在可以实现。这就是合作博弈与非合作博弈的区别。二者的主要区别在于人们的行为相互作用时,当事人是否达成一个具有约束力的协议。如果有,就是合作博弈；反之,则是非合作博弈。 因此，博弈可以划分为合作博弈与非合作博弈。,合作博弈的概念及其表示,合作博弈，非合作博弈的对称，一种博弈类型。参与者能够联合达成一个具有约束力且可强制执行的协议的博弈类型。合作博弈强调的是集体理性,强调效率、公正、公平。 合作博弈最重要的两个概念是联盟和分配。每个参与者从联盟中分配的收益正好是各种联盟形式的最大总收益,每个参与者从联盟中分配到的收益不小于单独经营所得

3、收益。 合作博弈的基本形式是联盟博弈,它隐含的假设是存在一个在参与者之间可以自由流动的交换媒介(如货币),每个参与者的效用与它是线性相关的。这些博弈被称为“单边支付”博弈,或可转移效用(Transferable Utility ,TU)博弈。,合作博弈的概念及其表示,合作博弈的结果必须是一个帕累托改进，博弈双方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受损害。合作博弈研究人们达成合作时如何分配合作得到的收益，即收益分配问题。合作博弈采取的是一种合作的方式，合作之所以能够增进双方的利益，就是因为合作博弈能够产生一种合作剩余。至于合作剩余在博弈各方之间如何分配，取决于博弈各方的力

4、量对比和制度设计。因此，合作剩余的分配既是合作的结果，又是达成合作的条件。 合作博弈的核心问题是参与人如何结盟以及如何重新分配结盟的支付。下面首先分析结盟的概念。与结盟相关联的就是特征函数。,合作博弈的概念及其表示,定义8.1.1 在 人博弈中，参与人集用 表示， 的任意子集 称为一个联盟（coalition）。 空集 和全集 也可以看成是一个联盟，当然单点集 也是一个联盟。 定义8.1.2 给定一个 人博弈， 是一个联盟， 是指 和 的两人博弈中 的最大效用， 称为联盟 的特征函数（characteristic function）。 规定 。根据定义， 表示参与人 与全体其他人博弈时的最大效

5、用值，表示为 。 用 表示参与人集为 ，特征函数为 的合作博弈，其中 是定义在 上的实值映射。 在很多情况下，一个联盟能获得的支付依赖于其他参与人所采取的行动。 有时被解释为联盟 独立于联盟 的行动可保证的最大支付 。,合作博弈的概念及其表示,合作对策的分类主要是根据特征函数的性质。下面根据特征函数的性质介绍几类特殊的合作对策。如果 仅与 的个数有关，则 称作对称博弈。如果 ，则 称作常和博弈。如果 ，则 称作简单博弈。例如，在投票博弈中，每个参与人的权重 ， 如果 ，则 称作凸博弈。,合作博弈的概念及其表示,例8.1 设有一个3人合作对策，每个参与人各有两个纯策略。当三人不合作时，其支付见下

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

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

8、足： ，如果 则存在一个 上的合作博弈，使 成为该合作博弈的特征函数。,合作博弈的概念及其表示,对于合作博弈 ，特征函数 满足超加性，自然有： 根据上述不等式，特征函数 分成两种类型： 类型1， 满足 。即大连盟的效用是每个参与人的效用之和。这说明通过联盟并没有创造新的合作剩余，联盟没有价值，这种联盟也不可能维持。这种对策称为非实质性对策，没有研究价值，不是本章研究的范畴。 对于非实质性对策，有 ，如果 。,合作博弈的概念及其表示,类型2， 满足 。即大连盟的效用大于每个参与人的效用之和。这说明通过联盟创造了新的合作剩余，联盟有意义，这种联盟能否维持，取决于如何分配合作剩余，使每个参与人的支付

9、都有改善。这种对策称为实质性对策，是本章研究的范畴。,分配,所谓分配就是博弈的一个 维向量集合，之所以 是维向量，是由于每个参与人都要得到相应的分配。 维的分配向量称为博弈的“解”。定义8.1.3 对于合作博弈 ，对每个参与人 ，给予一个实值参数 ，形成 维向量 且其满足： 则称 是联盟 的一个分配方案。,分配,分配的定义中， 是基于个人理性，合作中的收益不能小于非合作中的收益，反映了参与人的参与约束。如果 ，那么，参与人 是不可能参加联盟的。 是基于集体理性，每个参与人的分配之和不能超过集体剩余 。另外若 没有全部被分配，显然 不是一个帕类托最优的分配方案，不会参与人所接受。,分配,在例8.

10、1分配中，分配显然不是一个，而是无限个，无限个分配形成一个分配集合。 对于实质博弈，其分配总是有无限个。例如，对于实质博弈 ，由于存在无限个正向量 ，满足 。显然如下的 都是分配，其中 。用 表示一个博弈 的所有分配方案组成的集合。,分配,定义8.1.4 设 的两个分配 和 ， 是一个联盟。如果分配方案 和 满足 （i） ， ； （ii） 。 则称分配方案 在 上优超于 ，或称分配方案 在 上劣于 ，记为 。 如果分配方案 在 上优超于 ，则联盟 会拒绝分配方案 ， 方案得不到切实执行。因为从 到 ，中的每个参与人的收益都得到改善， 创造的剩余 又足以满足他们在 中的分配。,分配,在优超关系中

11、，联盟 的特征：1.单人联盟不可能有优超关系。2.全联盟 上也不可能有优超关系。 因此，如果在 上有优超关系，则 。 3.优超关系是集合 上的序关系，这种序关系一般情况下不具有传递性和反身性。4.对于相同的联盟 ，优超关系具有传递性，即 ， ，则有 。 5.对于不同的联盟 ，优超关系不具有传递性。,核心,尽管可行分配集合 中有无限个分配，但实际上，有许多分配是不会被执行的，或者不可能被参与人所接受的 。很显然，联盟的每一个成员都不偏好于劣分配方案，因此，真实可行的分配方案应该剔除劣分配方案。 定义8.3.1 在一个 人合作博弈 中，全体优分配方案形成的集合称为博弈的核心(core)，记为 。显

12、然有 。,核心,说明： 1.核心 是 中的一个闭凸集。 2.若 ，则将 中的向量 作为分配， 既满足个人理性，又满足集体理性。 3.用核心作为博弈的解，其最大缺陷是 可能是空集。,核心,定理8.3.1 分配方案 在核心 中的充要条件是： （i） ， ， (ii) 。证明 如果 ， 满足（i）、(ii)，则 不可能被优超，即 。反证法，设存在 ，使 。根据优超的定义，有:则有 ，矛盾。如果 ， 不满足 (ii)，则 一定被优超，即 。,核心,对于 ，存在联盟 ，有 ，则定义 ，定义 ，使得 在 中平均分配， 在 中平均分配，从而得到一个新的分配 如下：显然如此定义得向量 是个分配，且有 。,核心

13、,例8.2 假想的联合国安全理事会投票，超过两票算通过。该博弈的特征函数为而对所有其他的 ， 。应用定理8.3.1，有 ，对各个联盟有 由 ， ， ， 推得 ， ， ，而用 ， ， 又得到 和 ，所以，核心是,核心,例8.3 设3人合作博弈 的特征函数如下： ， ， ， ， 求其核心 。解 由核心定义，若 ，则它必满足 解此不等式组，得,核心,例8.4 考虑如下的合作博弈， ，特征函数如下： ， ； 。解线形不等式组： 。该不等式组无解，即 。上面三个例子说明了求解核心的方法。,核心,在合作博弈中，用核心代替分配具有明显得优点，即 的稳定性。对于 中的每一个分配，每个联盟都没有反对意见，都没有

14、更好的分配，每个分配都可以得到执行。当然，用 代替 也有致命的缺陷，即 可能是空集，而 。 定理8.3.2 对于 人的联盟博弈，核心 非空的充分必要条件是线性规划 有解。 ，,核心,定理的直观意义很明显，线性规划（L）若有解，则最优解一定属于 ；若 ，则 中的每个向量都是可行解，自然线性规划（L）有最优解解。对于原线性规划（P），写出它的对偶规划（DP）： ，,核心,定理 对策 有 的充分必要条件是：对于满足 的向量 ，有 。定义 设 是个0-1简单对策，若存在一个参与人 ，满足 ，则 称作一个否决人。定理 简单对策 中， 充分必要条件是 中存在一个否决人。,核心,证明 设 是 中一个否决人，

15、定义 ，1处于第 的位置。根据定理8.3.2， 是一个分配，且 。用反证法。设 ，且不存在否决人，即 。 ，则 。 故有 ，从而 。也即 ，矛盾。,核仁,为评估 对 满意性，定义如下的被称作超出一个指标： 的大小反映了 对 满意性。 越大， 对越不满意，因为 中所有参与人的分配之和远没有达到其所创造的合作剩余 ； 越小， 对 越满意，当 为负值时， 中所有参与人不但分配了其所创造的合作剩余 ，还分配了其他联盟所创造的价值。,核仁,对于同一个 ， 共有 个，可以表示为 。故可以计算出 个 。联盟对 的满意性取决于 中的最大的 ，故可以对 个 由大到小排列，得到一个 的向量：其中 。 联盟对 的满

16、意性取决于 的大小， 越小，联盟对 越满意。,核仁,对于两个不同的分配 ，分别计算出 。如果是 小的，则联盟对 的满意性大于联盟对 的满意性，自然 优于 。当然这种向量大小的比较不同于数字的比较，是采用字典序的比较方法。字典序的比较方法的比较方法如下： 对于向量 和 ，存在一个下标 ，使得 ， ，则称 字典序小于 ，用符号表示 。 有了上述的定义，就可以给出核仁的定义了。,核仁,定义 对于合作博弈 ，核仁 是一些分配的集合，即 ，使得任取一个 ， 都是字典序最小的，即 。 定理5.4 对于合作博弈 ，其核仁 ，且 只包含一个元素 。 定理5.5 对于合作博弈 ，如果核心 ，则有 。 证明 用反

17、证法。设存在一个分配 。根据核心的性质，由 可知：必存在一个联盟 ，满足 ，由此可知 。 设 。 是所有 中最大的，故有 。,核仁,由 可知，存在分配 。根据分配的性质，任取一个 ，有 ，由此可知 满足 。 ， ， ； ， ， 。这与 矛盾。定理得证。,核仁,例8.5 考虑如下的合作博弈， ，特征函数如下： ； ； 。求该博弈的核仁。 解 先求出该博弈的核心，再求核仁。根据核心的条件， 充分必要条件：解此不等式组，得到 。,核仁,，故有 。下面开始求 。对于核心 ，开始求 ， 。 ，有 440； ，有 0 ； ，有 0 ； ，有 5 ； ，有 7 ； ，有 6 0； ，有 10100； 当 ，

18、 。上式在 达到，故有 。该结果验证了 ， 。,Shapley值,分配是合作博弈最重要的概念，但遗憾的是在一个博弈中，分配有无限个，且许多根本就得不到执行。利用优超的概念，对分配进行了分类，形成了核心的概念，但遗憾的是，许多博弈中核心可能是空集。为此，引入了超出这一指标，寻求最大超出最小化的分配，即核仁。核仁这一解的优势体现在核仁总存在，且是唯一的，这一解的缺陷就是计算太复杂，因为共有 个。 本节引入了一个很直观的解的概念，即Shapley值。参与人按照Shapley值进行分配。,Shapley值,定理 对每个博弈 ，存在唯一的Shapley值 ，其中 （8.5.1）下面对这一计算公式给出非数

19、学化的解释：1， ， 就是按照参与人的平均贡献来安排的分配设计。2，在一个博弈中，每个人的所得应该与其贡献成正比。对于联盟 ，其合作剩余 。如 加入 ，则新联盟的合作剩余是 。因此 的贡献是 。,Shapley值,3，在博弈 中，不包含 的 有 个，对每个 都有一个贡献值 ，因此，Shapley值的计算公式中有 项。4，即使对于一个固定的 ， 与 中参与人的排列顺序无关，与 中参与人的顺序无关。因此 的系数中存在 。为什么系数中有 ？主要是为了计算 的平均值。,Shapley值,5，对于 也可以作出这样解释： 加入 ，其贡献是 。 加入 的概率是多少？如果 个局中人以次参加博弈，当 加入该博弈

20、时，其前面已有一些参与人 ， 加入后，后继的参与人集合 。 和 中参与人的顺序与 无关。 加入 的概率是 ， 的数学期望（或者平均值）就是Shapley值。 6，Shapley值不一定是个分配，即理性约束 可能不满足。,Shapley值,例1 假设联合国安理会进行投票，部分国家可以形成联盟。该博弈的特征函数为： 而对所有其他 ， 。为了求 ，对所有包含参与人1的联盟按Shapley值求和。 与 有差异的联盟 只有 、 、 、 、 、 和 ，对于其他的 ， 0。所以有 类似地， 。 于是， ， 。这样，参与人1、2比参与人3、4、5重要得多。,Shapley值,定理若博弈 满足超加性，即 , ,

21、则Shapley向量 ，即Shapley值是分配。证明 满足超加性，则 。,合作博弈在经济管理中的应用,成本分担,主要包括：,供应链协调,供应链协调,供应链是围绕核心企业，通过对信息流、物流、资金流的控制，从采购原材料开始，制成中间产品以及最终产品，最后由销售网络把产品送到消费者手中的将供应商、制造商、分销商、零售商、直到最终用户连成一个整体的功能网链结构模式。最简单的供应链包括一个供应商（Supplier）和一个分销商（Retailer）,供应商确定批发价格,分销商决定订货量。,批发价格契约,回购价格契约,批发价格契约,供应商的参数与决策变量： ：供应商的制造成本； 供应商的缺货损失费； 供

22、应商对分销商的批发价格。分销商的参数与决策变量： ：分销商的分销成本； 分销商的缺货损失费； 剩余产品的价值； 分销商的固定零售价格； 分销商的决策订货量。市场参数： ：市场随机需求； ： 的分布函数； ： 的密度函数； ：的数学期望。令 ， 。如果订货量为 ，则期望销售量 为： 有 。,批发价格契约,则期望剩余存货 为： 。则期望缺货量为 ： 。因此，分销商的收益函数为： 供应商的收益函数为： 则供应链的整体利润为：,批发价格契约,整个供应链作为一个整体,进行最优化的集成决策，最优订货量 满足 的一阶条件。由此，从供应链整体最优化的角度，得到最优订货量 满足：订货量是分销商的决策变量，分销商

23、的决策是使 最大化。利用 关于 的一阶条件，得到分销商的最优决策：,批发价格契约,是从供应链整体角度的最优订货量,符合整体理性; 是分销商从个体角度的最优订货量,符合个体理性. 如果 ,则整体利益与个体利益就是协调的。 能够等于 吗? 显然有， 供应商的批发价格不可能低于其生产成本，因此， 不可能等于 ,即批发价格不能协调整个供应链。,回购价格契约,回购价格契约是指供应商为鼓励分销商订货，对分销商剩余的产品以回购价格 回收，降低分销商多订货的风险。回购价格契约条件下，分销商的收益函数为： 如果供应商决定批发价格和回购价格，使分销商的收益正比于整个供应链的收益，例如使 ，则分销商的最优化策略也是

24、供应链整体的最优策略。,回购价格契约,由 ，得到供应商的契约设计如下，如此设计的契约就可以协调整个供应链：因此,回购契约能够协调整个供应链，供应商可以通过 任意分配供应链的整体利润。,成本分担,在现实生活和经济管理活动中，经常遇到这种情况：一些人或者经济组织为了实现各自的目标，大家或者部分成员联合起来，进行共同投资，以实现各自的目标，又降低各自所负担的公共投资的费用。这就是费用分担问题。大家能否实现合作，费用分担是否合理是关键。 下面通过两个例题说明如何解决费用分担问题。,成本分担,例 在一个地区有一个公共服务机构，如自来水场、有线电视网等，如图中O所示。三个乡镇（图 中的 所示）需要连接到这

25、个公共服务机构。乡镇与服务机构之间、乡镇与乡镇之间的连接路线造价为边的权。问如何构建这个连接网络并分配建设费用？,O,11,10,9,9,8,成本分担,解：这显然是一个最小支撑树的构建和建设成本分担问题。 、 、 分别连接到O的建设成本为C( )9，C( )10，C( )11;将 、 连接到O的最小树的建设成本（最小支撑树的长度）为C( ， )17，同样，C( ， )18， C( ， )11；将3个顶点连接到O的最小树的建设成本（最小支撑树的长度）C( ， ， )18。设 、 、 分别承担的建设费用为 ,则建设费用的分配应该满足: 有无限个向量 满足上式，每个向量都可以作为一个建设费用的分配方

26、案。,成本分担,核心集合： 核仁： Shapley值： 除了合作博弈的方法，在现实生活中还有一些符合惯常约定、经常被采用且大家也觉得基本合理的分配方法，如资源占用费用分担法和费用增量法。,成本分担,资源占用费用分担法是按照每个参与人对公共资源的使用来分摊费用，占用公共资源多，则分摊费用即大，否则，即小。最小费用最小网络如下：,1,8,9,为3个参与人公用，费用9在3个参与人之间分配； 为2个参与人公用，费用8在2个参与人之间分配； 为 自用，费用1由 自己承担。因此，按照资源占用费用分担法，费用分担向量： 。,成本分担,费用增量法是按照合作所增加的总量按照一定的比例在参与人之间进行分配的一种方法。例如，如果3个参与人都不进行合作，则需要承担的费用分别是9、10、11，比例是 。如果3个参与人进行合作，则总的建设费用是18。将总建设费用18按照比例 在3个参与人之间进行分配，则3个参与人分别承担的费用是： 分析发现： 根本就不在核心中，因为 和 会形成一个联盟，反对这样一个分配， 承担的费用太小。,谢谢！,