完全信息静态博弈教学课件PPT.ppt

1 博弈论 第二章完全信息静态博弈 2 前言 完全信息静态博弈 各博弈方同时决策 且所有博弈方对各方得益都了解的博弈 完全信息静态博弈是非合作博弈中最基本的类型 囚徒困境 齐威王田忌赛马 猜硬币 石头剪子布 古诺产量决策都属于完全信息静态博弈 博弈有两种表述方法 1 策略型表述 适合表示静态博弈 2 扩展型 博弈树 表述 适合表示动态博弈 3 本章主要内容 2 1基本分析思路和方法2 2纳什均衡2 3无限策略博弈分析和反应函数2 4混合策略和混合策略纳什均衡2 5纳什均衡的存在性2 6纳什均衡的选择和分析方法扩展 4 2 1基本分析思路和方法 2 1 1上策均衡2 1 2严格下策反复消去法2 1 3划线法2 1 4箭头法 5 2 1 1上策均衡 上策 Dominantstrategy 在某个博弈中 如果不管其他博弈方选择什么策略 一博弈方的某个策略给他带来的得益始终高于其他 所有 策略 至少不低于其他策略 上策均衡 Dominant strategyEquilibrium 如果一个博弈的某个策略组合中的所有策略都是各个博弈方各自的上策 那么这个策略组合肯定是所有博弈方都愿意选择的 必然是该博弈比较稳定的结果 我们称这样的策略组合为该博弈的一个上策均衡 6 2 1 1上策均衡 因为上策均衡反映了所有博弈方的绝对偏好 因此非常稳定 跟据上策均衡可以对博弈结果做出最肯定的预测 进行博弈分析时 首先判断各个博弈方是否都有上策 是否存在上策均衡 7 2 1 1上策均衡 例1 囚徒困境对于囚徒1 策略 坦白 的得益向量为 5 0 策略 不坦白 的得益向量为 8 1 显然 5 0 8 1 所以 坦白 对于囚徒1来说是一个上策 8 2 1 1上策均衡 同理 对于囚徒2 策略 坦白 的得益向量为 策略不坦白的得益向量为 显然 所以 坦白 对于囚徒2来说是一个上策 那么 坦白 坦白 就是该博弈的一个上策均衡 这种策略的组合是稳定的 9 2 1 1上策均衡 例2 市场竞争中典型的囚徒困境现象之一寡头1 低价 150 70 高价 100 20 寡头2 低价 150 70 高价 100 20 低价均为两个博弈者的上策 上策均衡即为 低价 低价 10 2 1 1上策均衡 上策均衡不是普遍存在的 需要双方都存在上策 有些博弈就是不存在上策 如 猜硬币博弈博弈的参与人都不存在上策 博弈也就不存在所谓的上策均衡 11 2 1 2严格下策反复消去法 严格下策反复消去法思路和原理 严格下策 StrictlyDominatedStrategy 不管其他博弈方的策略如何变化 一个博弈方的某种策略给他带来的得益 总是比另一种或另一些策略给他带来的得益要小 则称前一种策略为相对于后一种或一些策略的一个 严格下策 严格下策是理性博弈方都不会去选择的策略 可以消去 对于严格下策的消去过程 可以在同一博弈方的策略空间中反复运用 也可以在各个博弈方的策略空间上交叉运用 只要有就可以消去 不必计较消去的顺序与过程 12 例1 无上策 无上策均衡 用严格下策反复削去法 博弈方一 2 1 2严格下策反复消去法 博弈方二 对博弈方二 明显地 右 的得益向量 1 0 中 的得益向量 3 2 所以博弈方二绝对不会选择 右 13 2 1 2严格下策反复消去法 例2 智猪博弈 第一步 博弈描述与假设有两头非常聪明的猪 一大一小 共同生活在一个猪圈里 猪圈的一端有一个踏板 踏板连着开放饲料的机关 只要踏一下 在猪圈的另外一端的食槽就会出现10个单位食物 任何一头猪去踏这个踏板都会付出相当于2个单位食物的成本 每只猪都可以选择 踏 或 不踏 踏板 大猪比小猪吃得快 两头猪跑得一样快 食槽 10 大猪 小猪 踏板 14 2 1 2严格下策反复消去法 第二步 要素分析 1 局中人 大猪 小猪 2 策略集合 均为 踏 不踏 3 行为顺序 同时决策 4 得益 见下页分析 15 2 1 2严格下策反复消去法 踏 需要猪跑一个折返 不踏 的猪只需要在食槽旁等食 情况1 一起跑去踏 一起折返 一起吃 大猪吃8 小猪吃2 情况2 大猪踏 小猪等 大猪踏完往回跑的时候 小猪趁机多吃2 大猪只能吃6单位 小猪可以吃4单位 情况3 小猪踏 大猪等 小猪踏完往回跑的时候 大猪趁机把10单位的食物都吃了 小猪白跑吃不到食物 情况4 都不踏 都忍着 没有食物吃 食槽 10 大猪 小猪 踏板 16 2 1 2严格下策反复消去法 减去2单位 踏 的成本后 两头猪在各种情形下的得益 情况一 同时踏 大猪8 2 6 小猪2 2 0 情况二 大猪踏 小猪等候 大猪6 2 4 小猪4 情况三 小猪踏 大猪等候 大猪10 小猪0 2 2 情况四 都不踏 无食物无成本 大猪0 小猪0 两头猪的得益矩阵 见上方 17 2 1 2严格下策反复消去法 第三步 分析求解最终稳定的策略组合为 大猪 踏 小猪 不踏 第四步 结构分析 模型简单 18 2 1 2严格下策反复消去法 第五步 启示 结论与建议现实中某些 搭便车 现象的博弈解释 这种现象 主要是由于局中人对某项事物或工作的效用有很大差异 具有大效用的局中人有时不得不付出更多的劳动 而对于这项事物或工作持可有可无态度的局中人往往就 搭便车 其他现象 团队合作等 问题 如何解决 作业题1 19 2 1 2严格下策反复消去法 关于作业 请手写 勿打印 别着急写 不急着交 等课程基本结束以后 要前后联系课程内容 写出结论就可以 不必复杂的公式与推导 不必正规的陈述 没有什么格式要求 只需要写出对这个问题的看法 自己想到的解决方案 里面用到了那些博弈思想就可以了 20 2 1 2严格下策反复消去法 练习一 博弈方1没有严格下策 从博弈方2开始 博弈的得益结构发生改变 下策可能就出现了 21 2 1 3划线法 与上策分析法的情形类似 大部分博弈是不存在严格下策的 虽然与上策均衡分析法相比 严格下策反复消去法适应更多情况 但是仍然不能够满足博弈分析的要求 我们需要一种更普遍适用的博弈分析方法 划线法 22 2 1 3划线法 划线法的思路和方法先找出自己针对其他博弈方每种策略或策略组合的最佳策略 即找最佳对策 这种最佳策略可能不唯一 然后在此基础上 通过对其他博弈方策略选择的判断 包括对其他博弈方对自己策略判断的判断等 我知道 对方知道我会选择某个策略的判断 预测可能结果和确定自己的最优策略 23 2 1 3划线法 例1 24 2 1 3划线法 例2 囚徒困境 25 2 1 3划线法 例3 猜硬币博弈 此博弈不存在确定性结果 没有策略组合是双方同时愿意接受的 我们不能预测这个博弈的结果 26 例4 夫妻之争 现实中的例子 两人同时出发到不同地方汇合 企业之间关联产品技术和规格等方面的合作也是类似博弈 2 1 3划线法 27 2 1 3划线法 夫妻之争有两个具有稳定性的结果 哪一个结果出现都是合理的 具体选择哪一个不得而知 但是 我们可以猜测到 这个博弈的结果会受到夫妻在家庭中的实际地位的影响 如果在家庭中 丈夫是强势的 那么 最后博弈的结果很可能是夫妇一起看足球 如果妻子是强势的 那么很可能夫妇二人一起看时装 28 例5 公共资源的过度使用 公共地悲剧 现实生活中的例子 如免费校园网络的使用 免费道路的使用 解决办法 消除或减弱公共物品的性质 如收费 发许可等 2 1 3划线法 29 2 1 4箭头法 箭头法思路与方法利用策略组合的稳定性和局中人的策略选择 动机 为思路 对博弈模型的结果进行分析和预测 30 2 1 4箭头法 例1 囚徒困境从任意一个策略组合开始分析 这里从 不坦白 不坦白 这个策略组合开始 博弈参与人得益的提高是改变策略的动机 由囚徒1开始分析 31 2 1 4箭头法 例2 夫妻之争 32 2 1 4箭头法 例3 猜硬币博弈 33 2 1 4箭头法 例4 公共地的悲剧 34 2 1 4箭头法 箭头有进无出的策略组合 表明此时博弈局中人已经没有改变策略的动机 即博弈方再改变策略已经不能带来得益的提高 因此 箭头有进无出的策略组合是稳定的策略组合 箭头法可以清晰地表明局中人改变行为决策的 动机 即得益 payoff 的提高 但如果博弈过于复杂 得益矩阵过于繁琐 箭头法的可用性就不强了 35 2 2纳什均衡 2 2 1纳什均衡的定义2 2 2纳什均衡的一致预测性质2 2 3纳什均衡与严格下策反复消去法 36 2 2 1纳什均衡的定义 博弈 博弈方的策略空间和得益的一般表示法 G表示一个博弈 n个博弈方 S1 S2 Sn表示每个博弈方的可选策略集合 称为策略空间 Sij Si表示博弈方i的第j个策略 博弈方i的得益用ui表示 ui是各博弈方策略的多元函数 n个博弈方的博弈G S1 S2 Sn u1 u2 un 37 2 2 1纳什均衡的定义 纳什均衡 NashEquilibrium 定义在博弈中 如果由各个博弈方的某一个策略组成的某个策略组合中 任一博弈方i的策略s i 都是对其余各个博弈方的组合的最佳对策 也即对任意都成立 则称为G的一个纳什均衡直白地说 NE就是一组最优策略的组合 是每个参与人都不想改变自身决策的一种策略组合和稳定状态 38 2 2 2纳什均衡的一致预测性质 一致预测 如果所有博弈方都预测一个特定的博弈结果会出现 那么所有的博弈方都不会利用该预测或者这种预测能力来选择与预测结果不一致的策略 简单说 没有哪个博弈方有偏离这个预测结构的愿望 因此这个预测结果最终真会成为博弈的结果 一致 的含义 各博弈方的实际行为选择与他们的预测一致 而不是不同博弈方的预测相同 无差异 只有纳什均衡才具有一致预测的性质 一致预测性是纳什均衡的本质属性 一致预测并不意味着一定能准确预测 因为有多重均衡 会有不一致的可能 39 2 2 3纳什均衡与严格下策反复消去法 上策均衡与纳什均衡的关系 上策均衡包含在纳什均衡范围之内 上策均衡肯定是纳什均衡 纳什均衡不一定是上策均衡 上策均衡是比纳什均衡更强 稳定性更高的均衡概念 首先考察是否存在上策均衡 如不存在上策均衡再寻找纳什均衡 划线法是在可以用得益矩阵表示的博弈中寻找纳什均衡的有效方法 40 2 2 3纳什均衡与严格下策反复消去法 纳什均衡与严格下策反复消去法的关系 命题2 1在n个博弈方的博弈中 如果严格下策反复削去法排除了除之外的所有策略组合 那么一定是该博弈的纳什均衡 命题2 2在n个博弈方的博弈中 如果是G的一个纳什均衡 那么严格下策反复消去法一定不会将它削去 41 2 2 3纳什均衡与严格下策反复消去法 命题2 1和命题2 2保证了严格下策反复消去法和纳什均衡分析之间的相容性 保证了在进行纳什均衡分析之前先通过严格下策反复消去法简化博弈是可行的 42 2 3无限策略博弈分析和反应函数 2 3 1古诺的寡头模型2 3 2反应函数2 3 3伯特兰德寡头模型2 3 4公共资源问题2 3 5反应函数的问题和局限性 43 2 3无限策略博弈分析和反应函数 我们前面所讨论的分析和求解博弈模型的方法 划线法 箭头法的适用范围 只是可通过策略之间进行两两比较分析的有限策略博弈 但是对于无限多种可选策略博弈时是不适用的 我们需要使用新的方法来寻找这类博弈纳什均衡的求法 44 2 3 1古诺的寡头模型 1838 Cournot 第一步 模型描述与假设 模型描述 两个厂商占领某种产品的市场 形成寡头垄断的市场结构 两寡头厂商通过决策自己的产量来实现自身利润最大化 假设条件 假定两个寡头厂商生产同质产品 两厂商的产品可完全替代 产量可无限分割 不必取整 1 市场总产量 Q q1 q2 2 市场出清价格 P P Q 8 Q 3 边际成本 c1 c2 2 且无固定成本 4 两厂商同时决定各自的产量 45 2 3 1古诺的寡头模型 第二步 博弈模型要素分析 1 博弈方 厂商1 厂商2 2 策略空间 选择各自产量q1 q2 3 博弈的顺序 厂商1和厂商2同时决策 4 得益 各自的利润u1 u2 厂商利润 收益 成本 双方的得益 利润 均取决于双方的策略 产量 46 2 3 1古诺的寡头模型 第三步 均衡求解 本博弈中的两博弈方都有无限多种可选策略 因而 无法用得益矩阵表示该博弈 纳什均衡的概念还是适用的 即只要两博弈方的一个策略组合 q1 q2 满足其中的q1 和q2 是博弈双方都没有动机改变的策略 从而形成稳定状态 或互为对方最佳策略的最优对策 从而在互相影响的局势下实现自身得益最大化 那么这个策略组合就构成一个纳什均衡 理性的博弈方 厂商 将会分别选择这两个产量 47 2 3 1古诺的寡头模型 如果策略组合是本博弈的纳什均衡 那么必须是最大值问题的解 即 是博弈方都没有动机改变的策略组合 实现了在相互影响的情况下 博弈方自身得益最大化 因此该策略组合具有稳定性 48 2 3 1古诺的寡头模型 求两个厂商利润函数的一阶偏导数 并令两个一阶偏导数都为0 可得 即产量组合 2 2 为该博弈的纳什均衡 49 2 3 1古诺的寡头模型 第四步 模型结构分析 古诺寡头博弈纳什均衡状态下的市场信息 1 商品总产量 Q q1 q2 2 2 4 2 商品市场出清价格 P 8 q1 q2 8 4 4 3 双方各自的利润 u1 u2 4 4 两厂商利润总和 u1 u2 4 4 8 50 2 3 1古诺的寡头模型 效率分析 个体理性与集体理性的比较 1 从两厂商总体利益最大化的角度出发 则厂商1和厂商2的总利润 2 总体利润函数求对Q的一阶偏导数 并令一阶偏导数为0 51 2 3 1古诺的寡头模型 共同利益最大化的集体理性 与 两厂商独立决策 追求自身而不是共同利益最大化的个体理性 的博弈结果相比 集体理性 的总产量较小 38 也就是说 如果两厂商更多考虑合作 联合起来决定产量 先定出使总利益最大的产量后 各自生产一半 1 5单位 则各自分享的利益为4 5 比只考虑自身利益的独立决策行为得到的利益要高 52 2 3 1古诺的寡头模型 当然 在两个厂商缺少有力合作机制的时候 这种联合通常是很难实现的 即使实现 常常也是不稳定的 因为每个博弈方都会有破坏这种合作的动机 从下面的分析我们就可以看到这种现象 53 2 3 1古诺的寡头模型 两寡头间的囚徒困境博弈 1 博弈方 厂商1 厂商2 2 策略 厂商1 突破1 5的平分合作产量 不突破1 5的平分合作产量 厂商2 突破1 5的平分合作产量 不突破1 5的平分合作产量 54 2 3 1古诺的寡头模型 3 得益情形1 双方都不突破平分的合作总产量 1 5 平分 9 的总利润 此时 q1 q2 1 5 u1 u2 4 5 情形2 厂商1私自突破平分合作产量 1 5 达到自身利益最大化产量 2 厂商2浑然不知 仍然生产 1 5 的平分合作产量 此时 q1 2 q2 1 5 Q 3 5 P 8 Q 8 3 5 4 5u1 4 5 2 2 5 u2 4 5 2 1 5 3 75 55 2 3 1古诺的寡头模型 情形3 厂商2私自突破平分合作产量 1 5 达到自身利益最大化产量 2 厂商1浑然不知 仍然生产 1 5 的平分合作产量 此时 q2 2 q1 1 5 Q 3 5 P 8 Q 8 3 5 4 5u2 4 5 2 2 5 u1 4 5 2 1 5 3 75情形4 双方都突破平分的合作产量1 5 各自生产使自身利益最大化的产量2 此时 q1 q2 2 u1 u2 4 56 2 3 1古诺的寡头模型 这样 这个两寡头间的囚徒困境博弈就可以使用如下的博弈矩阵表示 57 2 3 1古诺的寡头模型 从上面的模型分析我们可以知道 每个博弈方都有动机破坏合作的产量 以获得更高的个人收益 这将会使总体利益最大化的合作策略组合 不突破 不突破 变得不稳定 难以实现 或即使实现 也难以维持 古诺模型在现实经济中的最好例子之一 如石油输出国组织的限额和突破问题 58 2 3 2反应函数 古诺模型的纳什均衡也可以通过划线法思路的推广来分析与求解 划线法的思路是先找出每个博弈方针对其他博弈方所有策略 或策略组合 的最佳策略 然后再找出相互构成最佳对策的各博弈方策略组成的策略组合 在无限策略的古诺模型中 其他博弈方的策略有无限多种 因此 各个博弈方的最佳对策也有无限种 它们之间往往构成一种连续函数关系 59 2 3 2反应函数 厂商1 对于厂商2的任意产量q2 厂商1的最佳对策q1 就是使自己在厂商2生产q2情况下最大化自身利润的那个产量 即q1是最大化问题 的解 厂商2 与厂商1的情形完全相同 厂商2的对策q2是最大化问题 的解 60 2 3 2反应函数 分别对厂商1和厂商2的效用表达式求厂商决策变量q1 q2的一阶偏导数 并令一阶偏导数为0 得到q1 R q2 和q2 R q1 61 2 3 2反应函数 q1 R q2 表示 对于厂商2的每一个可能的产量 厂商1的最佳对策产量的计算公式 它是厂商2产量的一个连续函数 我们称这个连续函数为厂商1对厂商2的一个 反应函数 同样 q2 R q1 表示 对于厂商1的每一个可能的产量 厂商2的最佳对策产量的计算公式 它是厂商1产量的一个连续函数 我们称这个连续函数为厂商2对厂商1的一个 反应函数 所谓 反应函数 简单地说 就是针对其他博弈参与人策略的一个最佳的策略函数 使用的是划线法的思想 62 2 3 2反应函数 古诺模型的反应函数 3 0 0 3 0 6 6 0 2 2 63 2 3 2反应函数 从上页的反应函数曲线中我们可以做出如下分析 1 首先分析厂商1的反应曲线R1 q2 当厂商2选择0产量时 即q2 0 厂商1的最佳反应为3 即q1 3 这正是实现市场总利益最大的产量 厂商1独自得到市场的总体利益 当厂商2的产量达到6时 厂商1被迫选择0产量 因为此时厂商1坚持生产已经无利可图 2 其次分析厂商2的反应曲线R2 q1 与厂商1反应曲线分析是完全相同的 64 2 3 2反应函数 3 两条反应函数曲线的交点是 2 2 是由相互对对方的最佳反应产量构成的产量组合 是纳什均衡 4 2 2 点以外的其他点都仅仅是一方对另一方的最佳反应 而不是 相互 的最佳反应 这与纳什均衡的定义是一致的 65 2 3 3伯特兰德寡头模型 1883 背景与假设伯特兰德寡头模型是价格博弈 古诺寡头模型是产量博弈 寡头间生产的产品不同质 具有一定的可替代性 因此即使某个寡头厂商的产品价格较高也会有销售 这里仍只考虑两寡头的情形 66 2 3 3伯特兰德寡头模型 寡头1与寡头2各自的需求函数为 其中d1 d2 0是两厂商产品的替代系数 假设厂商生产无固定成本 边际成本为c1 c2 两厂商同时决定价格 67 2 3 3伯特兰德寡头模型 博弈要素分析 1 博弈方 厂商1 厂商2 2 策略 厂商1与厂商2决定自身产品的价格P1 P2 3 顺序 同时决策 4 得益 各自的利润u1 u2 68 2 3 3伯特兰德寡头模型 博弈双方的得益 69 2 3 3伯特兰德寡头模型 从自身效用最大化角度求厂商1和厂商2的反应函数对于厂商1 求如下最大化问题的解 求厂商1利润函数对于厂商1的决策变量q1的一阶偏导数 并令其为0 70 2 3 3伯特兰德寡头模型 同理 可求得厂商2的反应函数综上 两厂商对对方策略 价格 的反应函数 71 2 3 3伯特兰德寡头模型 求解纳什均衡即求两个反应函数的交点 也就是解方程组 过程略 72 2 3 3伯特兰德寡头模型 纳什均衡多寡头情形的纳什均衡的求解 技术上就是求n个反应函数的交点 实例 彩电价格战 囚徒困境的另一个实例 73 2 3 4公共资源问题 公共资源无独立所有权 公众可以自由利用的自然资源或人类生产的供大众免费使用的设施 休谟 DavidHume 1739 74 2 3 4公共资源问题 公共草地放牧问题博弈要素分析 1 博弈方 n个农户 2 策略空间 农户可能选择的养羊数qi 3 顺序 同时决策 4 农户的得益 其中V Q 表示羊只的单位产出 c表示农户养殖每只羊的成本 这里假设c是个常数 75 2 3 4公共资源问题 这里一个重要的假设就是每只羊的产出是羊只总数Q的减函数 这是因为如果羊太多 那么牧草等养殖资源不足 就会造成羊的质量下降 76 2 3 4公共资源问题 为了使讨论比较简单和能够得到直观的结论 我们假设 1 农户数 n 3 2 单位羊只养殖成本 c 4 3 单位羊只产出函数 4 那么3个博弈方 即3个农户的得益为 收入 成本 77 2 3 4公共资源问题 使用得益最大化思想分别求出三个农户各自对其他两个农户策略的反应函数农户1 效用函数对q1求偏导数 并令偏导数为0 78 2 3 4公共资源问题 最终三个反应函数为 三个反应函数的交点即为纳什均衡 79 2 3 4公共资源问题 总体利益最大的情况与个体理性决策进行比较 个体理性 80 2 3 4公共资源问题 结论过度放牧 资源浪费 农户没有获得更好的效益 这也是一类囚徒困境问题 81 2 3 4公共资源问题 这个例子再一次证明了纳什均衡 或者说非合作博弈的结果可能是低效率的 公共资源悲剧的现实例子 冬虫草 和田玉 公共网络 公共交通 防护林的保护 公共设施问题 公共设施搭便车者总是比提供者合算的 公共设施供给不足 公共资源利用 公共设施提供 政府的组织 协调和制约是非常必要的 82 2 3 5反应函数的问题和局限性 在许多博弈中 博弈方的策略是有限且非连续时 其得益函数不是连续可导函数 无法求得反应函数 从而不能通过解方程组的方法求得纳什均衡 83 图b 图a 2 3 5反应函数的问题和局限性 即使得益函数可以求导 也可能各博弈方的得益函数比较复杂 因此各自的反应函数也比较复杂 并不总能保证各博弈方的反应函数有交点 图a 特别是不能保证有唯一的交点 图b 84 2 4混合策略和混合策略纳什均衡 2 4 1严格竞争博弈和混合策略的引进2 4 2多重均衡博弈和混合策略2 4 3混合策略和严格下策反复消去法2 4 4混合策略反应函数 85 严格竞争博弈 各博弈方的利益和偏好始终不一致 在通常策略上没有纳什均衡的博弈问题猜硬币博弈纯 确定性 策略下 没有纳什均衡 但博弈方仍不能随意决策 2 4 1严格竞争博弈和混合策略的引进 86 2 4 1严格竞争博弈和混合策略的引进 首先 对盖硬币方进行分析 这个博弈中各博弈方决策的第一个原则 自己的策略选择不能预先被另一方知道或猜测到 否则 对方就会利用这点来选择策略 从而在博弈中获胜 其次 自己选择策略要避免规律性 选择策略如果出现规律性 比如一次正面 一次反面 一次正面 那么对方也会利用这个规律获胜 更进一步 如果盖硬币方已经使用随机策略 随机地选择盖正面或反面 但总体上出某个策略的概率更大 那么对方仍然会有机可乘 87 2 4 1严格竞争博弈和混合策略的引进 因此 如果盖硬币方以1 2的概率随机选择自身的策略 那么对方就无法从选择策略的偏好中占得任何便宜 也就是说 博弈方必须保证自身策略选择的随机性 以及重视各个策略的概率分布 以防止其他博弈方猜到自己的策略 或利用自己对策略选择的偏好获利 88 2 4 1严格竞争博弈和混合策略的引进 混合策略 MixedStrategies 一套出招的随机概率 在博弈G S1 S2 Sn u1 u2 un 中 博弈方i的策略空间为Si Si1 Sik 则博弈方i以概率分布pi pi1 pik 随机在其k个可选策略中选择的 策略 称为 混合策略 其中0 pik 1对j 1 2 k都成立 且pi1 pik 1 纯 确定性 策略也可以看作混合策略 即选择相应纯策略的概率为1 选择其余纯策略的概率为0的混合策略 混合策略可以看作纯策略的扩展 如果给一个博弈的每个博弈方的纯策略空间赋予不同的概率分布 就形成了不同的混合策略 89 2 4 1严格竞争博弈和混合策略的引进 混合策略扩展博弈 纯策略空间si1 si2 概率分布Pi1 pi11 pi12 Pi2 pi21 pi22 Pi 新 纯策略si1 pi11si1 pi12si2 si2 pi21si1 pi22si2 si 90 2 4 1严格竞争博弈和混合策略的引进 当博弈方在这个 新产生 的混合策略空间中的选择看作一个博弈时 原博弈的混合策略就成了后面这个扩展出来的博弈的纯策略 扩展出来的博弈可称为原博弈的混合策略扩展博弈 91 2 4 1严格竞争博弈和混合策略的引进 混合策略纳什均衡博弈从纯策略向混合策略扩展后 纳什均衡的概念仍然是成立的 其实质是没有改变的 纳什均衡意味着任何博弈方单独改变自己的策略 或者随机选择各个纯策略的概率分布 都不能给自己增加任何利益 如果确实是一个严格意义上的混合策略组合 即未退化为纯策略组合 构成一个纳什均衡 则称为一个 混合策略纳什均衡 92 2 4 1严格竞争博弈和混合策略的引进 博弈方1的混合策略 随机选择A B的概率PA和PB 一定要使博弈方2选C和选D的期望得益相等 即 这样 博弈方1的策略选择就不会让博弈方2有任何 倾向性 博弈方2就不可能通过博弈方1的选择偏好获利 博弈方2选择C和D无差异 博弈方2 博弈方1 93 2 4 1严格竞争博弈和混合策略的引进 博弈方2的混合策略 随机选择C D的概率PC和PD 一定要使博弈方1选A和选B的期望得益相等 即 这样的话 博弈方2的策略选择就不会让博弈方1有任何 倾向性 94 2 4 1严格竞争博弈和混合策略的引进 求解混合策略纳什均衡 该博弈的混合策略纳什均衡为 95 2 4 1严格竞争博弈和混合策略的引进 博弈方1和博弈方2的期望得益 96 2 4 1严格竞争博弈和混合策略的引进 综上所述 该博弈的混合策略纳什均衡为 博弈方1在均衡状态下的期望得益为2 6 博弈方2在均衡状态下的期望得益为2 6 97 齐威王田忌赛马 2 4 1严格竞争博弈和混合策略的引进 田忌 齐威王 得益矩阵 PaPbPcPdPePf PgPhPiPjPkPl 98 2 4 1严格竞争博弈和混合策略的引进 齐威王的混合策略一定要使田忌选g h i j k l的期望得益相等 这样的话 齐威王的策略选择就不会让田忌有任何 倾向性 从而使田忌从中占到便宜 则有 令 99 2 4 1严格竞争博弈和混合策略的引进 同理 田忌也会选择使得齐威王各种策略期望收益相等的混合策略 令 解得 令 解得 100 2 4 1严格竞争博弈和混合策略的引进 在上述混合策略下 齐威王的期望得益为1 田忌的期望得益为 1 即多次进行这样的赛马 齐威王平均每次能赢田忌一千斤铜 这是因为齐威王三匹马的总体实力略胜于田忌三匹马的总体实力的缘故 101 小偷和守卫的博弈 泽尔腾 1996 上海 在纯策略下 不存在纳什均衡 使用图解法求混合策略纳什均衡 2 4 1严格竞争博弈和混合策略的引进 守卫睡的期望得益S D S 1 pt D pt守卫不睡的期望得益 0 pt 0 S 1 pt 0 102 2 4 1严格竞争博弈和混合策略的引进 首先讨论小偷 偷 与 不偷 两种策略概率的确定 守卫得益 睡 小偷偷的概率 S 0 1 D 横轴表示小偷 偷 的概率Pt 分布在0 1之间 不偷 的概率则为1 Pt 纵轴反映对应于小偷 偷 的不同概率 守卫选择 睡 的期望收益 图中S D连线 S D S 1 pt D pt 当小偷 偷 的概率大于pt 时 守卫 睡 的期望得益小于 不睡 的得益0 因此他肯定百分之百选择 不睡 从而小偷偷一次被抓一次 103 2 4 1严格竞争博弈和混合策略的引进 当小偷 偷 的概率大于pt 时 守卫 睡 的期望得益小于 不睡 的期望得益0 因此他肯定百分之百选择 不睡 从而小偷 偷 一次被抓一次 当小偷 偷 的概率小于pt 时 守卫 睡 的期望得益大于 不睡 的得益0 因此他肯定百分之百选择 睡 从而小偷偷窃会得益 只要 偷 的概率不大于pt 的概率 小偷都会得益 因此胆子越来越大 会逐渐提高偷窃概率 直到pt 均衡点是pt 偷 1 pt 不偷 此时守卫 睡 与 不睡 的期望收益均为0 104 2 4 1严格竞争博弈和混合策略的引进 小偷得益 偷 守卫睡的概率 0 1 V P P V V pg P 1 pg 其次讨论守卫 睡 与 不睡 两种策略概率的确定 当守卫 睡 的概率大于pg 时 小偷 偷 的期望得益大于 不偷 的得益0 因此他肯定百分之百选择 偷 105 2 4 1严格竞争博弈和混合策略的引进 当守卫 睡 的概率大于pg 时 小偷 偷 的期望得益大于 不偷 的期望得益0 因此他肯定百分之百选择 偷 当守卫 睡 的概率小于pg 时 小偷 偷 的期望得益小于 不偷 的期望得益0 因此他肯定百分之百选择 不偷 只要守卫 睡 的概率不大于pg 小偷就不会偷窃 因此守卫的胆子越来越大 会逐渐提高 睡 的概率 直到pg 均衡点是pg 睡 1 pg 不睡 此时小偷 偷 与 不偷 的期望收益均为0 106 激励的悖论 守卫得益 睡 小偷偷的概率 S 0 1 D D S D S 1 pt D pt 1 加重对守卫的处罚 D增加 短期中的效果是使守卫真正尽职 睡 的期望收益为负 守卫短期内会选择 不睡 在长期中并不能使守卫更尽职 pg 并不会下降 但会降低盗窃发生的概率 pt 会下降 即加重对守卫的处罚不会对守卫的工作态度产生长期影响 反而会间接降低小偷偷窃的概率 2 4 1严格竞争博弈和混合策略的引进 107 2 4 1严格竞争博弈和混合策略的引进 激励的悖论 小偷得益 偷 守卫睡的概率 0 1 V P P P V V pg P 1 pg 2 加重对小偷的处罚 短期内能抑制盗窃发生率 偷 期望收益短期内为负数 小偷短期内会选择 不偷 长期并不能降低盗窃发生率 pt 并不会改变 但会使守卫更多的偷懒 pg 会上升 108 夫妻之争的混合策略纳什均衡妻子的概率选择 使丈夫选择两种策略的期望得益相同 2 4 2多重均衡博弈和混合策略 109 丈夫的概率选择 使妻子选择两种策略的期望得益相同妻子的期望得益丈夫的期望得益 2 4 2多重均衡博弈和混合策略 110 2 4 2多重均衡博弈和混合策略 我们发现 在夫妻之争博弈中 双方进行沟通交流 一方迁就另一方的结果要比上面分析的混合策略纳什均衡结果要好 因为相互迁就的纯策略纳什均衡最少会使得丈夫或妻子得到1的确定收益 这要大于混合策略均衡时的期望收益0 75 111 制式问题零配件匹配偏好问题 厂商1偏好 2 2 均衡 而厂商2偏好于 1 3 2 4 2多重均衡博弈和混合策略 112 2 4 2多重均衡博弈和混合策略 混合策略纳什均衡为 厂商1 0 4 0 6 期望收益 0 664厂商2 0 67 0 33 期望收益 1 296 相互协商达成的纯策略的得益也是要大于混合策略均衡下的期望收益 113 市场机会博弈 过程请同学们自己完成 2 4 2多重均衡博弈和混合策略 厂商1 2 3 1 3 期望收益 0厂商2 2 3 1 3 期望收益 0 114 2 4 3混合策略和严格下策反复消去法 在包括混合策略的情况下 严格下策反复消去法的结论仍然成立 1 任何博弈方不会采用严格下策 不管它们是纯策略还是混合策略 2 严格下策反复消去法不会消去任何纳什均衡 包括纯策略纳什均衡和混合策略纳什均衡 3 如果经过反复消去后留下的策略组合是惟一的 那么一定是纳什均衡 115 2 4 3混合策略和严格下策反复消去法 博弈方2采用纯策略L时 博弈方1用上述混合策略的期望得益为 博弈方2采用纯策略R时 博弈方1用上述混合策略的期望得益为 博弈方2采用混合策略 q 1 q 时 博弈方1用上述混合策略的期望得益为 博弈方1采取混合策略 以概率 1 2 1 2 0 选择 U M D 时 与这个混合策略相比 D一定是博弈方1的严格下策 116 2 4 3混合策略和严格下策反复消去法 因此 不管博弈方2采用哪种策略 包括所有可能得纯策略和所有混合策略 对应q的所有可能值 博弈方1采用 1 2 1 2 0 的期望收益始终为3 2 都要大于采用D策略时得到的确定性得益1 由于我们假设博弈方是风险中性的 D相对于混合策略 1 2 1 2 0 是严格下策 117 2 4 3混合策略和严格下策反复消去法 需要注意的是 并不是包括混合策略以后 博弈中一定会存在可以先行削去的纯策略严格下策 如将博弈的得益修改为 D就不再是严格下策 1 3 2 2 没有严格的优劣 118 2 4 4混合策略反应函数 反应函数即一博弈方对另一博弈方每种可能的决策内容的最佳反应决策构成的函数 在纯策略的范畴内 反应函数是各博弈方选择的纯策略对其他博弈方纯策略的反应 在混合策略的范畴内 博弈方的决策内容为选择概率分布 反应函数就是一方对另一方的概率分布的反应 同样也是一定的概率分布 119 2 4 4混合策略反应函数 猜硬币博弈 正反盖硬币方 r 1 r 猜硬币方 q 1 q qU 盖反 r 1即对方猜正面的概率小 我盖正面有便宜 所以我倾向于盖正面 故r 1 我总盖正面 q 1 2时 U 盖反 U 盖正 r任意q 1 2时 U 盖正 U 盖反 r 0 r1 2时 U 猜正 U 猜反 q 1 r q 0 1 2 1 r R1 q 1 2 1 q R2 r 对方猜正面的概率 对方盖正面的概率 混和策略NE盖 1 2 1 2 猜 1 2 1 2 120 2 4 4混合策略反应函数 夫妻之争分析妻子 对丈夫的混合策略 q 1 q 的对策分析 1 妻子选择 宫心计 的期望收益U C 3q 0 1 q 3q 2 妻子选择 世界杯 的期望收益U F 0q 1 1 q 1 q因此 当q1 4时 r 1 1 r 0 丈夫的分析同妻子 121 2 4 4混合策略反应函数 分析丈夫 对妻子的混合策略 r 1 r 的对策分析 1 丈夫选择 宫心计 的期望收益U C 1r 0 1 r r 2 丈夫选择 世界杯 的期望收益U F 0r 3 1 r 3 3r因此 当r3 4时 q 1 1 q 0 122 2 4 4混合策略反应函数 夫妻之争 宫心计世界杯妻子 r 1 r 丈夫 q 1 q 妻子 qU C r 0q 1 4时 U F U C r取 0 1 任意值 q 1 4时 U C U F r 1 丈夫 rU C q 0r 3 4时 U F U C q取 0 1 任意值 r 3 4时 U C U F q 1 0 1 4 r 3 4 1 q 1 r R1 q q R2 r 纯策略NE1 世界杯 世界杯 纯策略NE1 宫心计 宫心计 混和策略NE妻 3 4 1 4 丈 1 4 3 4 123 2 5纳什均衡的存在性 纳什定理 Nash1950 在一个有n个博弈方的博弈G S1 Sn u1 un 中 如果n是有限的 其Si都是有限集 对i 1 2 n 则该博弈至少存在一个纳什均衡 但可能包括混合策略纳什均衡 每一个有限博弈都至少有一个混合策略纳什均衡定理证明 不动点定理 纳什定理的意义 NE存在的普遍性 一致预测 成为博弈问题分析方法 124 2 6纳什均衡的选择和分析方法扩展 纳什均衡是博弈问题最基本的分析概念 是均衡分析概念的基础 但纳什均衡分析并不一定能彻底解决一个博弈问题 因为纳什均衡的存在性不等于惟一性 在许多博弈中纳什均衡是不惟一的 而且不同的纳什均衡相之间也没有明显的优劣关系 从而博弈方的选择会遇到困难 夫妻之争博弈就是这样的一个典型例子 125 2 6纳什均衡的选择和分析方法扩展 即使一个博弈的几个纳什均衡之间存在优劣关系 帕累托效率意义上的 也不能保证博弈方一定会选择较优的纳什均衡 风险 破坏者 串通 的存在 使得博弈结果无法用纳什均衡加以解释 因此对有些博弈问题仅仅进行纳什均衡分析是不够的 必须在纳什均衡分析的基础上再作进一步的深入分析 126 2 6纳什均衡的选择和分析方法扩展 2 6 1帕累托和风险上策均衡 帕累托上策均衡 风险上策均衡2 6 2聚点和相关均衡 聚点均衡 相关均衡2 6 3共谋和防共谋均衡 多人博弈中的共谋问题 防共谋均衡 127 2 6 1帕累托和风险上策均衡 帕累托上策均衡 依据帕累托效率意义上的优劣关系 某一个纳什均衡给所有博弈方带来的利益都大于其他所有纳什均衡会带来的利益 博弈方选择的倾向性是一致的 两个纯策略纳什均衡 战争 战争 和平 和平 在帕累托效率意义上 和平 和平 明显较好 构成一个帕累托上策均衡 如果两国的决策者都是理性的 那么两个国家之间就不应该会发生战争 128 2 6 1帕累托和风险上策均衡 风险上策均衡 如果所有博弈方在预计其他博弈方采用两种纳什均衡的策略的概率相同时 都偏爱其中某一纳什均衡 则该纳什均衡就是一个风险上策均衡 明显地 U L 为帕累托上策均衡 但是选择这个NE对双方都有很大风险 一旦对方偏离这个均衡 那么自身的得益损失是非常大的 相对于这种高风险 D R 就有了相对优势 129 2 6 1帕累托和风险上策均衡 混合策略纳什均衡 混合策略纳什均衡是博弈方使得对方行为选择无差异时 自身行为的概率分布 博弈方1 令博弈方2选择L与R无差异博弈方2 令博弈方1选择U与D无差异 130 2 6 1帕累托和风险上策均衡 检查博弈方的策略偏好 博弈方1的混合策略 PU和PD 与博弈方2策略L与R的偏好性 当PU1 8时 有U L U R 即此时博弈方2对策略R具有偏好 131 2 6 1帕累托和风险上策均衡 检查博弈方的策略偏好 博弈方2的混合策略 PL和PR 与博弈方1策略U与D的偏好性 当PL1 8时 有U U U D 即博弈方2对策略D具有偏好 132 2 6 1帕累托和风险上策均衡 如果博弈方1倾向于策略D的随机概率大于12 5 那么博弈方2的R策略相对于帕累托均衡策略L就具有期望得益上的优势 因此博弈方2偏好于R 如果博弈方2倾向于R的随机概率大于12 5 那么博弈方1的D策略相对于帕累托均衡策略D就具有期望得益上的优势 因此博弈方1偏好于D 133 2 6 1帕累托和风险上策均衡 总结 偏离的概率要求小于1 8 12 5 才能保证帕累托上策均衡 U L 可以实现 这比较不保险 一旦对方偏离帕累托上策均衡的概率大于12 5 如果自己不改变帕累托上策均衡的策略 那么很有可能获得0收益 风险很大 所以 在收益相差不是很大的情况下 D R 相对于 U L 具有风险上的较大优势 D R 就是一个风险上策均衡 说白了 一方 不靠谱 使得另一方选择更加保险的策略 134 2 6 1帕累托和风险上策均衡 猎鹿博弈 详细分析如上例 请同学们自行完成 猎鹿有风险捕兔有保障 其中一种简单情况 假如另一方选择猎鹿和抓兔的概率都是1 2 那么 猎鹿 的期望收益仅为2 5 小于抓兔子的确定性收益3 因此 兔子 兔子 就是这个博弈的一个风险上策均衡 猎人1猎鹿 猎人2猎鹿 135 2 6 1帕累托和风险上策均衡 博弈方对风险上策均衡的选择倾向 有一种自我强化的机制 当部分或所有博弈方选择风险上策均衡的可能性增强时 都担心对方偏离帕累托上策均衡 任一博弈方选择帕累托上策均衡策略的期望得益都会进一步变小 这就使各博弈方更倾向于选择风险上策均衡 从而形成一种选择风险上策均衡的正反馈机制 使其出现的机会越来越大 合作难 多人合作更难 136 2 6 2聚点和相关均衡 1 聚点均衡人们的决策选择受心理 习惯 文化 环境等多种因素影响 体现出这些因素的纳什均衡 就称为聚点均衡 137 2 6 2聚点和相关均衡 例1 报时博弈 1 博弈参与人 博弈方1 博弈方2 2 策略 双方选择0点到24点的任意时间报时 无限 3 顺序 同时 4 得益 2人报时间相同 获得100元 报时不同 获得0元 选择整点后 即聚点 虽然不能保证双方的选择一致 但至少能大大提高双方选择一致的概率 138 2 6 2聚点和相关均衡 聚点均衡 在多重纳什均衡的博弈中 双方同时选择一个聚点构成的纳什均衡称为 聚点均衡 139 2 6 2聚点和相关均衡 例2 城市博弈上海 南京 长春 哈尔滨 两人将以上四个城市分成两组 如果两人的分组相同 获得100元 中国人 通常会 上海 南京 长春 哈尔滨 按南方和北方城市的特征分组 地理常识 产生聚点 140 2 6 2聚点和相关均衡 聚点均衡首先是纳什均衡 是多重纳什均衡中比较容易被选择的纳什均衡 聚点均衡是利用博弈规则以外的特定信息选择的均衡 文化背景中的习惯或规范 共同的知识或者其他各种特征都可能是聚点均衡的依据 141 2 6 2聚点和相关均衡 2 相关均衡人们在现实中遇到选择困难时 特别是在长期中反复遇到相似的选择难题时 通常会通过收集更多的信息 形成特定的机制和规则 也就是某种形式的制度安排等主动寻找出路 142 2 6 2聚点和相关均衡 相关均衡例子 存在三个纳什均衡 其中 两个是纯策略均衡 U L D R 一个是混合策略均衡 1 2 1 2 1 2 1 2 纯策略均衡虽然都能使双方得到6单位的得益总和 但是个人得益差距很大 很难形成自然妥协 聚点 不适用 若采用混合策略纳什均衡