合作联盟博弈ppt课件.ppt

博弈论 1 合作博弈 COOPERATIVEGAMES 2 合作博弈COOPERATIVEGAMES 熊 狼 狐狸一起抓了一只兔子 民主协商如何分配 狐狸对熊说 平均分只能各得1 3 这样吧 我们俩联合起来 平分如何 熊要答应 狼急了 于是狐狸对狼说 怎么样 我和熊联合起来可以让你什么也得不到 我可以和你合作 不过我要3 4 狼感激的点头 熊琢磨过味来 对狼说 别听那个两面三刀的 和我合作 我给你1 3 狐狸见势不妙 对狼说 别 我给你2 3 我只要1 3 狼成了抢手货 正得意 没留神狐狸和熊又开始嘀咕起来 有再次把自己晾在一边的不妙趋势 连忙钻去继续讨价还价 结果呢 3 如果在实际博弈问题中 具有有力的保障使局中人能够进行协商 谈判 联合选择行动 共同分享利益 我们就面对一个合作博弈问题 本章通过合作博弈模型的介绍 讨论在合作博弈中 局中人如何进行协商谈判 结成联盟及分享利益 1 联盟博弈2 联盟博弈的分配3 核和稳定集4 沙普利值 4 导论 先回忆一下囚徒困境的例子 在囚徒困境中 还有另外一个策略组合 该组合为参与人带来的支付是 由到 每个参与人的支付都增加了 即得到一个帕累托改进 5 导论 构不成一个均衡是基于参与人的个人理性 在参与人选择抵抗的情况下 每个参与人都有动机偏离这个组合 通过投机行为谋取超额收益1 如果两个参与人在博弈之前 签署了一个协议 两个人都承诺选择抵抗 为保证承诺的实现 参与人双方向第三方支付价值大于1的保证金 如果谁违背了这个协议 则放弃保证金 有了这样一个协议 就称为一个均衡 每个人的收益都得到改善 上述分析表明 通过一个有约束力的协议 原来不能实现的合作方案现在可以实现 这就是合作博弈与非合作博弈的区别 二者的主要区别在于人们的行为相互作用时 当事人是否达成一个具有约束力的协议 如果有 就是合作博弈 反之 则是非合作博弈 6 合作博弈的概念及其表示 合作博弈 非合作博弈的对称 一种博弈类型 参与者能够联合达成一个具有约束力且可强制执行的协议的博弈类型 合作博弈强调的是集体理性 强调效率 公正 公平 合作博弈最重要的两个概念是联盟和分配 每个参与者从联盟中分配的收益正好是各种联盟形式的最大总收益 每个参与者从联盟中分配到的收益不小于单独经营所得收益 7 合作博弈的概念及其表示 合作博弈的结果必须是一个帕累托改进 博弈双方的利益都有所增加 或者至少是一方的利益增加 而另一方的利益不受损害 合作博弈采取的是一种合作的方式 合作之所以能够增进双方的利益 就是因为合作博弈能够产生一种合作剩余 至于合作剩余在博弈各方之间如何分配 取决于博弈各方的力量对比和制度设计 合作博弈的核心问题是参与人如何结盟以及如何重新分配结盟的支付 8 合作博弈的概念及其表示 定义1在人博弈中 参与人集用表示 的任意子集称为一个联盟 coalition 空集和全集也可以看成是一个联盟 当然单点集也是一个联盟 定义2给定一个人博弈 是一个联盟 是指和的两人博弈中的最大效用 称为联盟的特征函数 characteristicfunction 规定 根据定义 表示参与人与全体其他人博弈时的最大效用值 表示为 用表示参与人集为 特征函数为的合作博弈 其中是定义在上的实值映射 在很多情况下 一个联盟能获得的支付依赖于其他参与人所采取的行动 有时被解释为联盟独立于联盟的行动可保证的最大支付 9 合作博弈的概念及其表示 合作对策的分类主要是根据特征函数的性质 下面根据特征函数的性质介绍几类特殊的合作对策 如果仅与的个数有关 则称作对称博弈 如果 则称作常和博弈 如果 则称作简单博弈 例如 在投票博弈中 每个参与人的权重 如果 则称作凸博弈 10 合作博弈的概念及其表示 之所以称为特征函数 是因为这个合作博弈的性质基本由决定 由此可见对合作博弈的重要性 定理设是参与人集合上的特征函数 则有如下的超可加性 对于联盟和 如果 则 上式说明 特征函数只有满足超加性 才有形成新联盟的必要性 否则 如果一个合作博弈的特征函数不满足超可加性 那么 其成员没有动机形成联盟 已经形成的联盟将面临解散的威胁 11 例 局中人1 卖主 要把一件物品卖掉 局中人2和3 买主 分别出价9元和10元 如果局中人1将物品卖给局中人2的要价是x元 则局中人2赢利9 x元 联盟的总收益为9元 类似 联盟的总赢利为10元 于是有 另一方面 单个局中人或者两个买主在一起都不可能赢利 即 当三个局中人在一起交易时 局中人1显然要把物品卖给局中人3 从而v 1 2 3 10 显然满足超可加性 于是我们建立了联盟博弈 特征函数是研究联盟博弈的基础 确定特征函数过程实际就是一个建立合作博弈模型的过程 有的问题 特征函数可以容易地得到 有的问题需要仔细分析 甚至需要一些专业知识 12 由策略型博弈导出特征函数型博弈 V 0V 1 0V 2 5V 1 2 10 最小最大值法 联盟外局中人将采取行动使该联盟的总和收益最小 极度悲观 联盟选择策略 最大化这些最小值 13 例 垃圾博弈 分析博弈局势 在一区域中住着7户居民 每户居民每天产生一袋垃圾 这些垃圾只能扔在这一区域的某一户人家领地 区域中没有空地 记Vn n 0 1 7 表示任意n个局中人组成的特征函数值 在合作博弈条件下 有 V0 V 0V1 6V2 5V3 4 V4 3 V5 2V6 1 V7 7 14 合作博弈的概念及其表示 例 设有一个3人合作对策 每个参与人各有两个纯策略 当三人不合作时 其支付见下表 假设采用最稳妥策略 即最坏情况下选择最好 求合作博弈的支付函数 15 合作博弈的概念及其表示 解 用表示一个联盟 表示联盟中参与人的个数 当 0 自然 有 当 1 有3个 以为例 当 则 的策略集合 策略组合 与进行如下矩阵对策 16 合作博弈的概念及其表示 上述矩阵对策没有纯策略 的混合策略是 的混合策略是 的均衡值是 故 同理 可以求出 当 2 有3个 以为例 当 则 的策略集合 策略组合 与进行如下矩阵对策 17 合作博弈的概念及其表示 上述矩阵对策有纯策略 的均衡值是3 故 同理 可以求出 当 3 有1个 最大的联盟 的策略空间 有 至此特征函数的值已全部求出 18 分配 所谓分配就是博弈的一个维向量集合 之所以是维向量 是由于每个参与人都要得到相应的分配 维的分配向量称为博弈的 解 定义3对于合作博弈 对每个参与人 给予一个实值参数 形成维向量且其满足 则称是联盟的一个分配方案 19 分配 分配的定义中 是基于个人理性 合作中的收益不能小于非合作中的收益 反映了参与人的参与约束 如果 那么 参与人是不可能参加联盟的 是基于集体理性 每个参与人的分配之和不能超过集体剩余 另外若没有全部被分配 显然不是一个帕累托最优的分配方案 不会参与人所接受 20 在前面的例子分配中 分配显然不是一个 而是无限个 无限个分配形成一个分配集合 对于实质博弈 其分配总是有无限个 例如 对于实质博弈 由于存在无限个正向量 满足 显然如下的都是分配 其中 用表示一个博弈的所有分配方案组成的集合 分配 21 分配中的优超 定义4设的两个分配和 是一个联盟 如果分配方案和满足 i ii 则称分配方案在上优超于 或称分配方案在上劣于 记为 如果分配方案在上优超于 则联盟会拒绝分配方案 方案得不到切实执行 因为从到 中的每个参与人的收益都得到改善 创造的剩余又足以满足他们在中的分配 22 分配中的优超 在优超关系中 联盟的特征 1 单人联盟不可能有优超关系 2 全联盟上也不可能有优超关系 因此 如果在上有优超关系 则 3 优超关系是集合上的序关系 这种序关系一般情况下不具有传递性和反身性 4 对于相同的联盟 优超关系具有传递性 即 则有 5 对于不同的联盟 优超关系不具有传递性 23 核心 尽管可行分配集合中有无限个分配 但实际上 有许多分配是不会被执行的 或者不可能被参与人所接受的 很显然 联盟的每一个成员都不偏好于劣分配方案 因此 真实可行的分配方案应该剔除劣分配方案 定义5在一个人合作博弈中 全体优分配方案形成的集合称为博弈的核心 core 记为 显然有 24 核心 说明 1 核心是中的一个闭凸集 2 若 则将中的向量作为分配 既满足个人理性 又满足集体理性 3 用核心作为博弈的解 其最大缺陷是可能是空集 25 核心 定理1分配方案在核心中的充要条件是 i ii 证明如果 满足 i ii 则不可能被优超 即 反证法 设存在 使 根据优超的定义 有 则有 矛盾 如果 不满足 ii 则一定被优超 即 26 核心 对于 存在联盟 有 则定义 定义 使得在中平均分配 在中平均分配 从而得到一个新的分配如下 显然如此定义得向量是个分配 且有 27 例2设有三人联盟对策 其特征函数 若由定理1易知 该博弈的核由下面不等式组确定 易知 故该博弈的核其图形为单纯形内以为顶点的四边形 如图1所示 28 图1 29 核心 练习1 设3人合作博弈的特征函数如下 求其核心 解由核心定义 若 则它必满足 30 解线形不等式组 该不等式组无解 即 上面三个例子说明了求解核心的方法 核心 练习2考虑如下的合作博弈 特征函数如下 31 核心 在合作博弈中 用核心代替分配具有明显得优点 即的稳定性 对于中的每一个分配 每个联盟都没有反对意见 都没有更好的分配 每个分配都可以得到执行 当然 用代替也有致命的缺陷 即可能是空集 而 定理2对于人的联盟博弈 核心非空的充分必要条件是线性规划有解 32 核心 定理的直观意义很明显 线性规划 L 若有解 则最优解一定属于 若 则中的每个向量都是可行解 自然线性规划 L 有最优解 对于原线性规划 P 写出它的对偶规划 DP 33 核心 定理对策有的充分必要条件是 对于满足的向量 有 定义设是个0 1简单对策 若存在一个参与人 满足 则称作一个否决人 定理简单对策中 充分必要条件是中存在一个否决人 34 核心 证明设是中一个否决人 定义 1处于第的位置 根据定理2 是一个分配 且 用反证法 设 且不存在否决人 即 则 故有 从而 也即 矛盾 35 核仁 为评估对满意性 定义如下的被称作超出一个指标 的大小反映了对满意性 越大 对越不满意 因为中所有参与人的分配之和远没有达到其所创造的合作剩余 越小 对越满意 当为负值时 中所有参与人不但分配了其所创造的合作剩余 还分配了其他联盟所创造的价值 36 核仁 对于同一个 共有个 可以表示为 故可以计算出个 联盟对的满意性取决于中的最大的 故可以对个由大到小排列 得到一个的向量 其中 联盟对的满意性取决于的大小 越小 联盟对越满意 37 核仁 对于两个不同的分配 分别计算出 如果是小的 则联盟对的满意性大于联盟对的满意性 自然优于 当然这种向量大小的比较不同于数字的比较 是采用字典序的比较方法 字典序的比较方法的比较方法如下 对于向量和 存在一个下标 使得 则称字典序小于 用符号表示 有了上述的定义 就可以给出核仁的定义了 38 核仁 定义对于合作博弈 核仁是一些分配的集合 即 使得任取一个 都是字典序最小的 即 定理4对于合作博弈 其核仁 且只包含一个元素 定理5对于合作博弈 如果核心 则有 39 核仁 例5考虑如下的合作博弈 特征函数如下 求该博弈的核仁 解先求出该博弈的核心 再求核仁 根据核心的条件 充分必要条件 解此不等式组 得到 40 核仁 故有 下面开始求 对于核心 开始求 有 4 4 0 有 0 有 0 有 5 有 7 有 6 0 有 10 10 0 当 上式在达到 故有 该结果验证了 41 Shapley值 分配是合作博弈最重要的概念 但遗憾的是在一个博弈中 分配有无限个 且许多根本就得不到执行 利用优超的概念 对分配进行了分类 形成了核心的概念 但遗憾的是 许多博弈中核心可能是空集 为此 引入了超出这一指标 寻求最大超出最小化的分配 即核仁 核仁这一解的优势体现在核仁总存在 且是唯一的 这一解的缺陷就是计算太复杂 因为共有个 本节引入了一个很直观的解的概念 即Shapley值 参与人按照Shapley值进行分配 42 Shapley值 定理6对每个博弈 存在唯一的Shapley值 其中 8 5 1 下面对这一计算公式给出非数学化的解释 1 就是按照参与人的平均贡献来安排的分配设计 2 在一个博弈中 每个人的所得应该与其贡献成正比 对于联盟 其合作剩余 如加入 则新联盟的合作剩余是 因此的贡献是 43 Shapley值 3 在博弈中 不包含的有个 对每个都有一个贡献值 因此 Shapley值的计算公式中有项 4 即使对于一个固定的 与中参与人的排列顺序无关 与中参与人的顺序无关 因此的系数中存在 为什么系数中有 主要是为了计算的平均值 44 Shapley值 5 对于也可以作出这样解释 加入 其贡献是 加入的概率是多少 如果个局中人以次参加博弈 当加入该博弈时 其前面已有一些参与人 加入后 后继的参与人集合 和中参与人的顺序与无关 加入的概率是 的数学期