混合策略纳什均衡.ppt

29 03 2020 1 混合策略纳什均衡MixedStrategyNashEquilibrium 理学院顾聪gucong 29 03 2020 2 两个参与人各拿一枚硬币 并选择出正面向上还是反面向上 若两枚硬币是一致的 即全部正面或全部反面 则参与人2赢走参与人1的硬币 若两枚硬币不一致 一正一反 参与人1赢得参与人2的硬币 支付矩阵如下 由划线法可知 该博弈不存在纳什均衡 所以采取纯策略不存在稳定的纳什均衡解 4 1严格竞争博弈和混合策略 1 混合策略的提出 猜硬币博弈 29 03 2020 3 在这类博弈中 不存在纯策略纳什均衡 参与人的支付取决于其他参与人的策略 以某种概率分布随机地选择不同的行动 每个参与人都想猜透对方的策略 而每个参与人又不愿意让对方猜透自己的策略 这种博弈的类型是什么 如何找到均衡 上述博弈的特征是 29 03 2020 4 策略 参与人在给定信息集的情况下选择行动的规则 它规定参与人在什么情况下选择什么行动 是参与人的 相机行动方案 纯策略 如果一个策略规定参与人在每一个给定的信息情况下只选择一种特定的行动 称为纯策略 简称 策略 即参与人在其策略空间中选取唯一确定的策略 混合策略 如果一个策略规定参与人在给定的信息情况下以某种概率分布随机地选择不同的行动 称为混合策略 参与人采取的不是明确唯一的策略 而是其策略空间上的一种概率分布 2 混合策略 混合策略博弈和混合策略纳什均衡 29 03 2020 5 混合策略vs 纯策略 不确定性vs 确定性 在博弈中 博弈方的策略空间 则博弈方以概率分布随机在其个可选策略中选择的 策略 称为一个 混合策略 其中对都成立 且纯策略可以理解为混合策略的特例 即在诸多策略中 选择该纯策略的概率为1 选其他纯策略的概率为0 为何参与人可能会选择带不确定性的混合策略而放弃确定性的纯策略 参与人主观因素造成的犹豫不决外在客观因素的不确定性带来应对策略的不确定性迷惑对手 为了让其它参与人不能清楚了解自己的选择 29 03 2020 6 混合策略扩展博弈 博弈方在混合策略的策略空间 概率分布空间 的选择看作一个博弈 就是原博弈的 混合策略扩展博弈 混合策略纳什均衡 MNE 由最优的混合策略构成的混合策略组合 29 03 2020 7 对于任意混合策略组合 若各参与人最终确定的组合 纯策略组合 为参与人的支付为发生此情况的概率为参与人的期望效用 3 期望效用 ExpectedPayoff 29 03 2020 8 由于混合策略伴随的是支付的不确定性 因此参与人关心的是其期望效用 最优混合策略 是指在给定对方的混合策略的情况下 使期望效用函数最大的混合策略 在两人博弈里 混合策略纳什均衡是两个参与人的最优混合策略的组合 29 03 2020 9 流浪 流浪汉 政府 救济 不救济 寻找工作 虽这模型没有PNE 却有下述的MNE 参与人以一定的概率选择某种策略 然后计算相应于不同概率的期望效用 4 一个例子 社会福利博弈 29 03 2020 10 设 政府救济的概率 1 2 不救济的概率1 1 2 流浪汉寻找工作的期望效用 1 2 2 1 2 1 1 5流浪的期望效用 1 2 3 1 2 0 1 5 3 2 1 3 1 1 0 0 救济 不救济1 寻找工作 游荡1 此时 流浪汉选择任何混合策略的期望效用都是1 5 则流浪汉的任何一种策略 纯的 1或 0或混合的0 1 都是政府所选择的混合策略的最优反应 29 03 2020 11 3 2 1 3 1 1 0 0 救济 不救济1 寻找工作 游荡1 而当 0 21 0 8游荡寻找工作 如果流浪汉选择这个混合策略 政府的任何策略 混合的或纯的 带给政府的期望效用为 0 2 特别的 以1 2的概率分别选择救济和不救济当然也是政府对于流浪汉所选择的混合策略的最有反应 这样 我们得到一个混合策略组合 每一个参与人的混合策略都是给定对方混合策略是的最优选择 从而构成混合策略纳什均衡 策略期望收益政府 0 5 0 5 0 2流浪汉 0 2 0 8 1 5 既然参与人在构成混合策略时选择不同纯策略之间是无差异的 他为什么不选择一个特定的纯策略而要以特定的概率随机地选择不同的纯策略呢 一个参与人选择混合策略目的是给其他参与人造成不确定性 海萨尼 Harsanyi 1973 对混合战略的解释是 混合策略均衡等价于不完全信息下的纯策略均衡 如社会福利博弈中 假定有两类特征的流浪汉 一类选择寻找工作 另一类选择游荡 每个流浪汉都知道自己的特征 但政府并不知道流浪汉的准确特征 只知道流浪汉20 概率属第一类 80 概率属第二类 在这种情况下 政府在选择自己的策略时似乎面临的是一位选择混合策略的流浪汉 29 03 2020 13 支付最大化法支付等值法最优反应函数法 4 2混合策略纳什均衡的求解 29 03 2020 14 参与人1的混合策略为 1 q 1 q 分别以概率q和1 q选择正面和反面 参与人2的混合策略为 2 r 1 r 分别以概率r和1 r选择正面和反面 1 支付最大化法求纳什均衡 猜硬币博弈 29 03 2020 15 E1 正面 1 r 1 1 r 1 2r 参与人1选取反面的期望效用为 E1 反面 1 r 1 1 r 2r 1 当给定参与人2选择混合策略 1 r 1 r 时 参与人1的选取正面的期望效用为 29 03 2020 16 类似地 得到参与人2的期望效用为 E2 E2 正面 r E2 反面 1 r 1 2q 2r 1 由一阶条件 参与人1的期望效用为 E1 E1 正面 q E1 反面 1 q 1 2r 2q 1 29 03 2020 17 流浪1 流浪汉 政府 救济 不救济1 工作 即 流浪汉以0 2的概率选择寻找工作 0 8的概率选择流浪 同理可以根据流浪汉的期望效用函数找到政府的最优混合策略 社会福利博弈 29 03 2020 18 对 0 2的解释 如果流浪汉寻找工作的概率小于0 2 政府的最优选择是不救济 如果流浪汉寻找工作的概率大于0 2 政府的最优选择是救济 对 0 5的解释 如果政府救济的概率大于0 5 流浪汉的最优选择是流浪 如果政府救济的概率小于0 5 流浪汉的最优选择是寻找工作 混合策略纳什均衡的含义 纳什均衡要求每个参与人的混合战略是给定对方的混合战略下的最优选择 因此在社会福利博弈中 0 2 0 5是唯一的混合策略纳什均衡 29 03 2020 19 由上面的例子可以看出 参与人选择的混合策略均使对方选择纯策略的期望效用相等 促使各方均采取严格策合策略 所以求解混合策略纳什均衡也可以采取如下方法 求出参与人的每个纯策略的期望效用 令其相等即可得到混合策略纳什均衡 2 支付等值法求纳什均衡 29 03 2020 20 参与人1的选取正面的期望效用为 参与人1的选取反面的期望效用为 E1 正面 1 r 1 1 r 1 2r E1 反面 1 r 1 1 r 2r 1 令纯策略期望效用相等 得 类似地 令参与人2的纯战略期望效用相等得 猜硬币博弈 29 03 2020 21 假定最优混合策略存在 给定流浪汉选择混合策略 流浪 流浪汉 政府 救济 不救济 寻找工作 政府选择纯策略救济的期望效用为 选择纯策略不救济的效用为 如果一个混合策略 而不是纯策略 是政府的最优选择 一定意味着政府在救济与不救济之间是无差异的 社会福利博弈 29 03 2020 22 在讨论连续纯策略均衡时 如古诺模型 我们使用了反应函数的概念 现在我们可以使用反应对应的概念来描述一个参与人对应于其他参与人混合策略的最优选择 两个概念的区别仅仅在于 反应函数表示的是一个参与人只有一个特定的策略是其他人给定策略的最优选择 反应对应允许一个参与人有多个 甚至无穷多个 策略是其他人给定策略的最优选择 3 最优反应函数法求纳什均衡 29 03 2020 23 纯策略均衡 反应函数 reactionfunction 在纯策略的范畴内 最优反应函数是各博弈方选择的纯策略对其他博弈方纯策略的反应 纯策略纳什均衡是博弈方反应函数的交叉点 混合策略均衡 反应对应 reactioncorrespondence 在混合策略的范围内 博弈方的决策内容为选择概率分布 最优反应函数就是一方对另一方的概率分布的反应 由于纯策略可以理解为混合策略 因此实际上最优反应函数的概念 也可以在混合策略概率分布之间反应的意义上统一起来 混合战略纳什均衡也是反应函数的交叉点 29 03 2020 24 混合策略反应函数 猜硬币博弈 r 1 r 盖硬币方选择正反面的混合策略概率分布 q 1 q 猜硬币方选择正反面的混合策略概率分布 29 03 2020 25 夫妻之争博弈 混合策略反应函数 r 1 r 丈夫的混合策略概率分布 q 1 q 妻子的混合策略概率分布 29 03 2020 26 例题监督博弈 a c F a F a c a 0 0 a a 检查 1 不检查 税收机关 逃税 1 不逃税 纳税人 其中 a 应纳税款 C 检查成本 F 罚款 a c F 检查到逃税者 a F 除了要交税款又要交罚款 求MNE两种方法 支付最大化方法 求一阶导数为0 支付等值法 即选两个纯战略是没差异 假定C a十F 在这个假设下 不存在纯战略纳什均衡 让我们来求解混合战略纳什均衡 29 03 2020 27 假定C a十F 在这个假设下 不存在纯战略纳什均衡 让我们来求解混合战略纳什均衡 a 应纳税款 C 检查成本 F 罚款 a c F 检查到逃税者 a F 除了要交税款又要交罚款 用 表示税收机关检查的概率 表示纳税人逃税的概率 给定 税收机关选择检查 1 和不检查 0 的期望收益分别为 令 29 03 2020 28 给定 纳税人选择逃税和和不逃税的期望收益分别为 得 令 得 因此 混合战略纳什均衡是 税收机关以的概率检查 纳税人以的概率选择逃税 结论 而当 则纳税人选择纳税与不纳税无差异 另一解释是 社会中有许多个纳税人 其中有比例的纳税人选择逃税 比例的纳税人选择不逃税 税收机关以比例随机地检查纳税人的纳税情况 纳税人选逃税概率越小 检查成本C越高 纳税人逃税的概率就越大 为什么应纳税款越多 纳税人逃税的概率反而越小呢 这是因为 应纳税款越多 税收机关检查的概率越高 逃税被抓住的可能性越大 因而纳税人反而不敢逃税了 这一点或许可以解释为什么逃税现象在小企业中比在大企业中更为普遍 在低收入阶层比在高收入阶层更普遍 29 03 2020 31 即 每一个有限博弈至少存在一个纳什均衡 现实中的博弈都是可以当作有限博弈来解决 这样纳什均衡的存在就是普遍的 纳什均衡的普遍存在性是纳什均衡概念最重要的性质 4 3纳什均衡的存在性定理 29 03 2020 32 2 纳什定理的推广 纳什均衡的存在性定理2 当博弈方个数有限 战略集是非空 闭的 有界的 支付函数是连续且拟凹的 则博弈至少存在一个纯战略纳什均衡 Debreu 1952 Clicksberg 1952 Fan 1952 纳什均衡的存在性定理3 当博弈方有限 战略集是非空 闭的 有界的 支付函数是连续的 则博弈至少存在一个纳什均衡 纯战略的或混合战略的 Clicksberg 1952 29 03 2020 33 尽管纳什均衡非常重要 但不是说学到了这种分析方法你就能预测所有博弈的结果 纳什均衡分析仅仅保证有个体理性的智能人的博弈结果是唯一纯策略纳什均衡时的预测 实际情况是纳什均衡分析并不能保证对所有博弈的结果都作出准确的预测 现实中的博弈可能是下面三种情况之一 1 有许多博弈不存在纯策略纳什均衡 2 有些博弈是多重纳什均衡 3 博弈方可