合作博弈四川大学教学提纲

《合作博弈四川大学教学提纲》由会员分享，可在线阅读，更多相关《合作博弈四川大学教学提纲（144页珍藏版）》请在金锄头文库上搜索。

1、2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,博弈论及其应用,第5章 合作博弈,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,2,第5章 合作博弈,主要内容： 5.1 基本概念 5.2 占优方法：合作博弈一类解概念 5.3 估值方法：合作博弈的一类解概念 5.4 合作博弈的应用范例,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,3,5.1 基本概念,5.1.1 纳什谈判解与联盟 5.1.2 联盟与特征函数 5.1.

2、3 特征函数的性质 5.1.4 合作博弈中的解概念,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,5,2人纳什谈判解的决定,在2人纳什谈判解讨论中，是二人经过谈判后可能达到的结果集。是谈判的初始参考点，经过纳什公理化体系，通过求解 ，可以得到一对谈判解。,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,6,n人纳什谈判解的决定,设 是局中人的集合， 是n人经过谈判进行合作的可达结果集。当允许采用抽彩方法对结果分配时，结果集是一个凸集。 令 是谈判

3、达不成协议的支付分配（或n个局中人的保守收益），作为谈判的初始参考点。将纳什公理化体系扩大到n人，则有n人纳什谈判解的唯一结果 。 一般情况下，它由下式决定：,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,7,纳什谈判的例子,例5.1.1 设有三个人参与分配300元，若第个人分得，则它的效用为 ，三个人提出的分配方案分别为 ，则当三个人方案一致时有收益，否则收益为零，用收益函数表达为：,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,8,纳什谈判

4、的例子,很显然，这时可达结果集为： 而三个人所得的最低水平为0，即：初始参考点是 应用（5.1.1）式，容易得： 在这一博弈中，三人都采用了同样的策略 显然，作为理性的局中人，它的策略中不会使自己的收益小于 100元，而他若使自己的收益高于100元，则不会使其他人得到认同。,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,9,纳什谈判的例子,例5.1.2 类同例5.1.1，但规定只有当局中人1和局中人2提出的分配策略不同时，各局中人的收益所得为0；若局中人1和局中人2提出的分配策略相同时，即，则按这一分配向各局中人支付，

5、其收益函数可表达为： 这时的可达结果结仍为：,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,10,纳什谈判的例子,在例5.1.2博弈中，局中人1和局中人2可以联合起来对支付的分配策略进行选择，而局中人3的任何策略都无法干预分配方案。因而，可以合理地认为该博弈仅在局中人1和局中人2两人之间进行分配讨论。若局中人1和局中人2采用二人合作博弈的纳什谈判解。则其结果将是（150，150，0）。 在人谈判问题中，若出现联盟，则可能发生实质性的变化。,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,20

6、10-3-3,博弈论及其应用 （汪贤裕）,11,纳什谈判的例子,例5.1.3 类同例5.1.1 。但该博弈规定，如果有两个局中人提出相同的分配策略时，则每人按这一策略进行支付，否则每个局中人的支付都为0。其收益函数可以表达为： 这时的可达结果集仍为：,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,12,纳什谈判的例子,在例5.1.3的博弈中，情况就非常复杂了。若局中人1和局中人2谈判分配方案为，局中人3可以和其中一个局中人再谈判.如与局中人1再谈判,提出分配方案 此后局中人2又可以和1，3中一个局中人，如局中人3谈判，

7、提出分配方案，这种过程可以一直进行下去。,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,13,纳什谈判的例子,对这一谈判过程的终止可以有两种规定： 一是规定局中人通过一轮谈判后形成一个协议，按照协议规定，每个局中人进行再谈判不能与以前的谈判相违背。可以看到，在三人博弈中，先行谈判的局中人具有先动优势。 二是规定谈判的次数的顺序。如规定谈判的顺序是先由1，2谈判,其次由2，3谈判。第3由1，3谈判，最后1，2，3谈判,这时局中人1和局中人3，即1，3谈判具有后动的优势。,2010-3-3,博弈论及其应用 （汪贤裕）博弈论

8、及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,14,合作博弈与非合作博弈区分的 两个假设条件,作为合作博弈与非合作博弈的相区分的主要两个假设条件如下： 合作博弈中允许局中人在博弈前进行谈判；而非合作博弈不允许。 合作博弈中一旦达成协议，形成一个联盟，则协议有了强制约束力，因而联盟的一系列行动被局中人所承认；在非合作博弈中也有一定的博弈前沟通，如“相关均衡”，但它不具有强制的约束力，只能用利益进行诱导或激励。 在多人合作博弈中，联盟具有核心重要的作用。,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕

9、）,15,5.1.2 联盟与特征函数, 联盟的定义 可转移效用（TU） 特征函数的定义 特征函数的确定,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,16,联盟的定义,定义5.1.1 设博弈的局中人集合为 ，则任意 ，称S为N的一个联盟（coalition）。 特殊情况，允许取 和 ，后一种情况称为一个大联盟。 若 ，则 中联盟个数为 。,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,17,可转移效用（TU）,若联盟S中局中人的收益可以自由地分

10、配，且任何局中人的收益变化1个单位，它的效用也变化1个单位，我们称为可转移效用（TU）（transformable utility），也称有旁支付的（with side-payments）。本章仅对可转移效用情况进行讨论。 可在转移效用（TU）的合作博弈中，联盟S的一个收益 表示它加入大联盟进行博弈的机会收益，或联盟 S 独立活动可获得的最大收益。这是进行合作博弈首先应确立的。,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,18,特征函数的定义,定义5.1.2 设博弈的局中人集合为 ， 是定义在N的一切子集（即联盟）上

11、的实值函数，其满足： （1） （5.1.4） （2） （5.1.5） 称 为一个特征函数(characteristic function)，或联盟函数(coalitional function)。,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,19,给定局中人集合和特征函数，所进行的合作博弈称为可转移效用下合作博弈，记为 。它称为特征函数式博弈（characteristic function form）或联盟式博弈（coalitional form）。 在可转移效用下合作博弈，我们着重研究联盟中的收益分配问题。由于本章

12、不涉及到不可转移效用，因此下面简称合作博弈。,特征函数的定义,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,20,特征函数的确定,方法一 若联盟S的成立可以获得独立于联盟S之外成交行为的收益，值 表示此时联盟可获得的最大机会收益。 在例5.1.1中 在例5.1.2中 在例5.1.3中,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,21,特征函数的确定,方法二 联盟S的成立可以获得受到独立于联盟S之外局中人的影响和阻扰下的最好收益。 下面我们从策

13、略式博弈到特征函数式博弈的转换加以说明。 若给定一个策略形的非合作博弈 ，其中局中人的混合策略集合为，收益函数为 ，可以由多种方法从策略式博弈推导出特征函数。,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,22,特征函数的确定,第一种方法： -特征函数和 -特征函数。 在 中（给定 的子集，即联 ）, 特征函数定义为： 其中 为在混合策略 情况下，局中人 的期望收益 。 -特征函数是把局中人集合划分为两个联盟 和 这两个联盟进行一种二人零和博弈。联盟 将联盟 看成利益完全冲突的对立面，以保证自己的保守收益。,2010-

14、3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,23,特征函数的确定,例5.1.4 设有一个非合作博弈 其中 每个局中人的纯策略均为 ，其收益函数如右表所示：,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,24,特征函数的确定,设局中人1，2组成联盟 则和进行的二人零和博弈支付矩阵如右所示： 可得矩阵博弈的值，即联盟S的所得为,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,25,特

15、征函数的确定,若局中人3组成一个联盟， ，则和 进行的二人零和博弈支付矩阵为： 可得矩阵博弈的值，即联盟的解为： 类似计算可得：,联盟,联盟,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,26,在中，给定的的子集，即联盟, -特征函数定义为： -特征函数，仍是假定局中人集合分为联盟和联盟 ，两个联盟进行二人零和博弈。联盟是联盟形成利益冲突的对立面。定义-特征函数确定过程中，联盟是先行动，对任何策略选择，联盟之外的成员将选择策略使联盟的收益最小。在-特征函数确定过程中，联盟是后行动，对联盟之外的选择的任何策略，联盟将选择策略使自己的收益最大。,特征函数的确定,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,27,第二种方法，防御均衡特征函数（defensive-equilibrium characteristic function）。 在中，给定局中人集合的一个子集，即联盟防御均衡特征函数定义为： 其中，由如下方法确定：考虑一个二人非零和博弈，是博弈的纳什均衡。,特征函数的确定,2010-3-3,博弈论及其应用 （汪贤裕）博弈论及其应用 （汪贤裕）,#,2010-3-3,博弈论及其应用 （汪贤裕）,28,例5.1.5 有一个可转移效