经济博弈论第四章 重复博弈.ppt

2020 1 13 1 第四章重复博弈 本章主要内容 1重复博弈的概念 2作为一种特殊的动态博弈 有限次和无限次重复博弈的子博弈完美纳什均衡的求解方法 3无限次重复博弈古诺模型和效率工资模型 本章主要结论 民间定理 由于参与者在重复博弈中具有了长期利益 可以通过在后面阶段中采取的报复策略使得威胁变得可信 从而摆脱静态博弈中 追求自身利益最大化 导致的囚徒困境 实现长期合作的结局 2020 1 13 2 第一节几个概念 重复博弈的概念有限次重复博弈的概念 2020 1 13 3 4 1 1重复博弈的概念 1由简单的静态博弈 或动态博弈 的有限次 或无限次 重复进行构成的 2每一阶段博弈方 策略集合 规则和得益都相同 3包括 有限次重复博弈和无限次重复博弈4例子 多场决胜负的体育比赛 有限次 两寡头市场上两个厂商之间的竞争 无限次 商场与顾客交易 2020 1 13 4 定义 给定一个博弈G 重复进行T次G 并且在每次重复之前各博弈方都能观察到以前博弈的结果 称为G的一个 T次重复博弈 记为G T 其中 G成为G T 的原博弈 每次重复称为G T 的一个阶段 4 1 2有限次重复博弈的概念 2020 1 13 5 4 1 2有限次重复博弈的概念 几个概念 1子博弈 从某一阶段 不包括第一阶段 开始 包含以后所有阶段的原重复博弈的一部分 2策略 博弈方在每个阶段针对每种情况如何行动的计划 注 在每一阶段之前 博弈方是可以观察到以前博弈的结果的 2020 1 13 6 3路径 是每个阶段博弈结果 原博弈的一个策略组合 连接而成 对于具有n个策略组合的原博弈 重复T次的路径数为nT 重复博弈的求解即找出具有稳定性的均衡路径 4得益 不同于一般的动态博弈 重复博弈的得益为各个阶段得益的加总 考虑到时间的价值 需要引进 贴现系数 将未来的得益折算成当期得益的价值 4 1 2有限次重复博弈的概念 2020 1 13 7 第二节有限次重复博弈 有限次重复的猜硬币博弈 原博弈为零和博弈有限次重复的囚徒困境博弈 原博弈有唯一的纯策略纳什均衡有多个纳什均衡的重复博弈的策略设计 触发策略有多个纳什均衡重复博弈的得益范围 民间定理 2020 1 13 8 在零和博弈中 双方不存在合作的可能性 因此在长期进行的重复博弈中 子博弈完美纳什均衡由各个阶段原博弈的纳什均衡构成 例 在猜硬币博弈中以0 5的概率选择正面或者反面 即采取混合策略 实际上 所有以零和博弈为原博弈所构成的重复博弈与猜硬币博弈构成的重复博弈一样 各博弈方的正确策略就是在每次重复中都采用一次性博弈中的纳什均衡策略 4 2 1有限次重复的猜硬币博弈 2020 1 13 9 4 2 2有限次重复的囚徒困境博弈 图4 1囚徒困境求解思路 对于有限次重复囚徒困境博弈 根据动态博弈的逆推归纳法可以求解 坦白 不坦白 坦白不坦白 2020 1 13 10 4 2 2有限次重复的囚徒困境博弈 以两阶段 以该博弈作为原博弈G重复两次 为例 分析最后一阶段 子博弈即为原博弈 唯一的均衡为 5 5 分析第一阶段 将最后阶段的收益 5 添加到第一阶段的矩阵中 即 此时 博弈的纳什均衡仍是 坦白 坦白 坦白不坦白 坦白 不坦白 2020 1 13 11 结论 在有限次重复博弈G T 中 如果原博弈G存在唯一的纯策略纳什均衡组合 则重复博弈的唯一的子博弈完美纳什均衡解为各博弈方在每阶段都采取的原博弈纳什均衡策略 含义 在原博弈具有唯一均衡的有限次重复博弈中 由于完全理性的博弈方具有 共同知识 的分析推理能力 因此在从最后阶段开始的逆推过程中 仍然无法摆脱囚徒困境 4 2 2有限次重复的囚徒困境博弈 2020 1 13 12 4 2 2有限次重复的囚徒困境博弈 如果原博弈存在唯一的纯策略纳什均衡组合 则有限次重复博弈的唯一的均衡解即各博弈方在每阶段 即每次重复 中都采用原博弈的纳什均衡策略 由于在这样的双方策略下 均衡路径中的每个阶段都不存在不可信的威胁或许诺 因此这种均衡是子博弈完美纳什均衡 2020 1 13 13 4 2 2有限次重复的囚徒困境博弈 定理设原博弈G有唯一的纯策略纳什均衡 则对任意正整数T 重复博弈G T 有唯一的子博弈完美的解 即各博弈方每个阶段都采用G的纳什均衡策略 各博弈方在G T 中的总得益为在G中得益的T倍 平均每阶段得益等于原博弈G中的得益 2020 1 13 14 4 2 3有两个纳什均衡的重复博弈 例两个厂商1和2 同时面临两个市场机会A和B 假设每个厂商都只有能力选择一市场发展 即他们的可选择策略都是A或B 其得益矩阵如图所示 此博弈具有2个纯策略纳什均衡 1 4 4 1 和混合策略纳什均衡概率 0 5 0 5 AB 图4 2两厂商差别市场博弈 2020 1 13 15 考虑三次重复博弈各策略组合子博弈纳什均衡路径 1 由原博弈的纳什均衡组合而成的路径 如采取轮换策略 在上述的协调博弈中 双方轮换采取纯纳什均衡策略 路径为 A B B A A B 不考虑时间的价值 贴现系数 每阶段的平均得益为 4 1 2 2 5 高于混合策略的得益2 2 触发策略 博弈方首先采取合作行为 如果发现对方没有进行合作 那么在后续阶段的博弈中采取不合作策略进行惩罚 4 2 3有两个纳什均衡的重复博弈 2020 1 13 16 在图4 2中 触发策略的设计为 1 博弈方1的策略是第一阶段合作A 如果发现对方采取B不合作 则第二阶段采取不合作的B策略惩罚 否则第二阶段继续合作 第三阶段无条件采取B策略 2 博弈方2的策略是第一阶段合作A 如果发现对方采取B不合作 则后续两个阶段一直采取不合作的B策略 如果发现对方采取合作A 则第二阶段采取不合作B 第三阶段采取合作A 4 2 3有两个纳什均衡的重复博弈 2020 1 13 17 策略设计分析 1 在博弈方1和2中 在第一阶段都采取了合作行为A 并针对对方的不合作行为B 都设计了在后续2个阶段采取不合作B的相应惩罚措施 2 如果对方在第一阶段中采取了合作行为 在后续阶段的策略设计中要保证博弈结局具有稳健性 因此 针对第一阶段的合作行为 后续阶段的策略设计是为了实现双方的行动协调 以保证实现纳什均衡 B A 或 A B 4 2 3有两个纳什均衡的重复博弈 2020 1 13 18 结果分析 子博弈路径 A A A B B A 为子博弈纳什均衡 因为后续两阶段的结局 A B 和 B A 为纳什均衡 而第一阶段的合作结局 A A 是由于触发策略针对对方偏离合作的行为设计了后续两阶段都不合作的惩罚措施 其单方面偏离的路径 B A B B B B 收益并不增加 因此不存在偏离的动机 4 2 3有两个纳什均衡的重复博弈 2020 1 13 19 问题的提出 由于具有多个纳什均衡的重复博弈可以设计多种策略 在双方缺乏沟通的情况下 结局具有不确定性 因此 这里讨论具有多个纳什均衡的重复博弈可以实现的收益范围 个体理性得益 不管对方采取何种行动 只要自己的行为合理就可以保证实现的收益 可实现得益 各纯策略组合得益的加权平均数组 注意 并非一定是均衡策略的组合得益 因此在图4 2中 3 3 也是可实现得益 4 2 4民间定理 2020 1 13 20 4 2 4民间定理 用wi记博弈方i在一次性博弈中最差的均衡得益 用w记各博弈方的wi构成的得益数组 结合 个体理性得益 和 可实现得益 则有限但次数很多的重复博弈有如下民间定理 定理 将一次性博弈中最差的均衡得益数组记为w 如果原博弈G的一次性博弈有均衡得益数组优于w 那么在有限次重复博弈G T 中 所有个体理性得益和可实现得益都至少有一个子博弈完美纳什均衡来实现 2020 1 13 21 在图4 2一次性博弈中 博弈方均衡得益分别为纯策略的得益 1 4 4 1 和混合策略的得益 2 2 最差的均衡得益数组为w 1 1 图4 3民间定理 4 2 4民间定理 厂商2得益 厂商1得益 2020 1 13 22 在图4 3中 通过不同得益的组合 阴影部分 包括连线 的得益都是可实现得益 民间定理揭示出 在有限次重复博弈中 可以通过设计触发策略来实现 或者逼近 阴影部分的得益 4 2 4民间定理 2020 1 13 23 定理分析 民间定理表明 在具有多个纳什均衡的有限次重复博弈中 通过设计具有可信威胁的触发策略 即在第一阶段采取合作行为 当对方不合作时通过在后续阶段采取相应的不合作策略进行惩罚 当对方合作时 在最后阶段采取一次性原博弈的纳什均衡策略作为稳定的结局 可以使得博弈方在重复博弈的过程中具有了一定学习能力 从而达到博弈的帕累托前沿得益 4 2 4民间定理 2020 1 13 24 例 两人各三种可选策略 LMRLMR图4 4多种策略博弈的重复博弈该博弈具有两个纯策略纳什均衡和一个混合策略纳什均衡 但是双方存在一个更好的得益 4 4 对于二次重复博弈 根据民间定理可以设计一个触发策略来实现这个得益 4 2 4民间定理 2020 1 13 25 触发策略 博弈方1在第一阶段采取M策略 如果对方合作 则第二阶段采取R策略作为奖励 否则第二阶段采取L策略进行惩罚 注意 L L 也是纳什均衡 因此具有稳定性 博弈方2也采取同样策略 策略分析 如果任何一方在第一阶段偏离 仅仅多获得5 4 1单位得益 而在第二阶段的得益 L L 仅仅为1 如果在第一阶段合作 第二阶段的得益为3 因此双方不存在偏离该策略的动机 4 2 4民间定理 2020 1 13 26 例 双方各五种可选策略重复博弈 LMRPQLMRPQ图4 5双方各五种可选策略重复博弈 4 2 4民间定理 2020 1 13 27 该博弈具有4个纯策略纳什均衡 在二次重复博弈中 触发策略设计 第一阶段双方采取 M M 策略 如果博弈方1偏离此策略 那么第二阶段采取 Q Q 策略对博弈方1进行惩罚 对博弈方2进行奖励 同理 如果博弈方2偏离了此策略 那么采取 P P 策略对博弈方2进行惩罚 对博弈方1进行奖励 如果双方都没有偏离 那么第二阶段采取具有较高收益的纳什均衡 R R 策略 如果双方都偏离了此策略 第二阶段同样采取纳什均衡的 R R 策略 4 2 4民间定理 2020 1 13 28 策略分析 与图4 4例子相比较 由于博弈的特殊结构 这个触发策略的设计对偏离行为和合作行为分别进行惩罚和奖励 因此策略具有很强的可信性 而在图4 4例子中 针对对方的偏离行为采取了 L L 策略进行惩罚 但是惩罚对方的同时 自身的利益也受到了损害 因此可信性不强 4 2 4民间定理 2020 1 13 29 第三节无限次重复博弈 在有限次重复博弈中 1 由于完全理性的博弈方可以运用逆推归纳法 因此对于原博弈具有唯一纳什均衡 如囚徒困境博弈 的有限次重复博弈 重复博弈结局尚无法摆脱囚徒困境 2 但是对于原博弈具有多个纳什均衡的有限次重复博弈 根据民间定理可以设计出具有可信威胁的触发策略 达到帕累托最优的博弈结局 2020 1 13 30 第三节无限次重复博弈 在本节的无限次重复博弈中 由于无法运用逆推归纳法 因此对于原博弈具有唯一纳什均衡 如囚徒困境博弈 的无限次重复博弈 考虑到时间的价值后 也可以设计出具有可信威胁的触发策略 摆脱囚徒困境 达到帕累托最优的博弈结局 2020 1 13 31 4 3 1几个概念 无限次重复博弈求解存在的问题 1 由于不存在最后一个阶段 无法运用逆推归纳法求解 2 如果不考虑时间的价值 在无限次重复加总过程中 几乎所有子博弈路径的总得益都为无穷大 因此无法比较不同路径的优劣 解决方法 考虑到时间的价值 人们更为注重近期的得益 引入贴现系数 将未来阶段的收益折算到当期阶段 这样在无限次重复博弈中 总收益值将是一个有限数 可以加以比较 2020 1 13 32 贴现系数 1 1 其中 为以一阶段为期限的市场利率 给定贴现系数 若无限次重复博弈一路径的某博弈方各阶段的收益为 则该博弈方在该无限次重复博弈中的总收益为各阶段博弈中得益的 现在值 4 3 1几个概念 2020 1 13 33 4 3 1几个概念 定义 给定一博弈G 无限次重复进行G博弈的过程称为G的 无限次重复博弈 记为G 其中 是各博弈方得益共同的贴现系数 并且 对任意的t 在进行第t阶段 第t次重复 博弈之前 所有博弈方都能看到前 t 1 阶段博弈的结果 各博弈方在G 中的 得益 等于各阶段得益的现在值 2020 1 13 34 4 3 2无限次重复的囚徒困境博弈 在有限次重复囚徒困境博弈中 双方采取背叛策略 L L 将是唯一的子博弈完美均衡路径 现在分析无限次重复博弈中 触发策略是否会带来更好的结局 触发策略 双方在第一阶段采取合作的策略R 如果前 t 1 都是合作 那么继续合作 否则 如果对方背叛 则在后续阶段一直采取背叛策略L作为惩罚 LR LR 图4 6 2020 1 13 35 策略分析 如果一方背叛 那么其路径 L R L L L L 的总收益为 如果一方一直采取合作策略 那么总收益为 当满足条件时 博弈方采取合作策略将获得更大的总收益 求解可得 4 3 2无限次重复的囚徒困境博弈 2020 1 13 36 4 3 2无限次重复的囚徒困境博弈 结论 在原博弈具有唯一纳什均衡的无限次重复博弈中 在满足一定条件下 采取触发策略可以摆脱囚徒困境 这个条件表明贴现系数较大 博弈方比较看重未来阶段的收益 直观上看 当博弈方注重长期利益时 通过采取触发策略可以实现长期合作的圆满结局 2020 1 13 37 4 3 3无限次重复博弈的民间定理 本节介绍无限次重复博弈的一个基本结论 为此先介绍 无限次重复博弈的平均得益 概念 可实现得益 概念已经在4 2 4节加以介绍 可实现得益 阶段博弈各种纯策略组合得益的加权平均所构成的得益数组 其中权数非负且总合为1 记为 2020 1 13 38 在图4 6的囚徒困境例子中 图4 7阴影部分即为可实现得益 图4 7可实现得益 4 3 3无限次重复博弈的民间定理 2020 1 13 39 无限次重复博弈平均得益的定义 如果有一常数 它作为一无限次重复博弈每个阶段的得益能产生与该博弈无限次重复中某博弈方的无穷得益数列 1 2 相同的贴现值 则称 为 1 2 的平均得益 4 3 3无限次重复博弈的民间定理 2020 1 13 40 4 3 3无限次重复博弈的民间定理 平均得益的计算 给定贴现系数 每阶段得益都为 时 无限次重复博弈的贴现值为 如果每阶段的得益为 1 2 无限次重复博弈的贴现值为 两式联立 可以解得 2020 1 13 41 无限次重复博弈的民间定理 设G是一个完全信息的静态博弈 其一个纳什均衡的得益记为 e1 en 其可实现得益记为 x1 xn 如果对于任意博弈方i都有xi ei 并且 足够接近于1 那么无限次重复博弈G 一定存在一个子博弈完美纳什均衡路径 能实现大小为 x1 xn 的重复博弈中各博弈方平均得益 4 3 3无限次重复博弈的民间定理 2020 1 13 42 几点说明 1 定理表明 以得益较低的纳什均衡 e1 en 作为可信的威胁 无限次重复博弈中可以实现更好的收益 x1 xn 由于对于任意博弈方i都有xi ei 因此这个得益是帕累托改进的 2 定理的条件为 足够接近于1 即博弈方都比较看重未来长期合作的得益 因此避免了短期行为 3 不同于有限次重复博弈的民间定理 这里并不要求原博弈具有多个纳什均衡 4 3 3无限次重复博弈的民间定理 2020 1 13 43 图例分析 原博弈为图4 6的囚徒困境博弈 在菱形区域的可实现得益区间中 只有阴影部分才满足对于任意博弈方i都有xi ei的帕累托改进条件 因此 当 足够大时 无限次重复博弈总有一个路径实现阴影部分的收益 4 3 3无限次重复博弈的民间定理 图4 8 2020 1 13 44 回忆静态博弈的古诺模型 1 市场总产量为Q q1 q2 两厂商的策略是制定各自的产量q1和q2 市场需求函数为P Q 8 Q 厂商无固定成本 边际成本为2 求解纳什均衡策略 根据利润最大化原则 厂商1和2的利润函数 u1 P Q q1 C q1 q1 8 q1 q2 2q1 6q1 q1q2 q12u2 P Q q2 C1 q2 q2 8 q1 q2 2q2 6q2 q1q2 q22对利润函数求导 得最大值 4 3 4无限次重复博弈的古诺模型 2020 1 13 45 联立解得 双方均衡产量 古诺产量 q2 q1 2 双方各自利润分别为 u1 u2 4 2 如果两厂商合谋 在市场上形成一个垄断厂商 追求总利润的最大化 U P Q Q C Q Q 8 Q 2Q 6Q Q2求导得 最大的总产量Q 3 最大的总利润u 9 每个厂商的平均产量为1 5 平均利润为u1 u2 4 5 大于不合作情况下古诺产量的利润4 4 3 4无限次重复博弈的古诺模型 2020 1 13 46 下面分析无限次重复博弈古诺模型的3个策略 触发策略1 第一阶段各自生产垄断产量1 5 如果双方在前 t 1 阶段都进行合作 保持了垄断产量 1 5 1 5 那么第t阶段继续合作 否则生产具有较低收益的作为纳什均衡的古诺产量2 4 3 4无限次重复博弈的古诺模型 2020 1 13 47 策略1分析 如果双方一直保持合作 则每阶段的垄断收益都为4 5 因此总收益 4 5 1 2 4 5 1 1 如果一方在第一阶段偏离合作 其应在对方采取垄断产量1 5情况下 采取使其利润最大化的产量 即 max 8 1 5 q2 q2 2q2 max 4 5 q2 q2解得q2 2 25 此时利润u max 4 5 q2 q2 5 0625 4 3 4无限次重复博弈的古诺模型 2020 1 13 48 无限次重复博弈的古诺模型 但是在后续阶段中只能得到古诺产量下的利润4 因此总收益 5 0625 4 2 5 0625 4 1 2 如果得益满足 1 2 触发策略下保持合作的垄断产量将构成子博弈完美纳什均衡 可以解得 9 17 2020 1 13 49 关于触发策略的更一般结论 在触发策略1中 如果满足条件 9 17 博弈方可以通过古诺产量作为威胁 迫使对方合作达成帕累托最优的垄断产量 但是 如果为了达到其它利润较低的可实现得益 相应的贴现系数要求是否可以降低 即博弈方是否可以不那么看重未来长期利益 下面讨论两者之间的关系 触发策略2 第一阶段生产q 如果前 t 1 阶段结局都是 q q 那么继续生产q 否则采取纳什均衡的古诺产量2 4 3 4无限次重复博弈的古诺模型 2020 1 13 50 策略2分析 如果双方一直合作 利润 8 2q q 2q 6 2q q 总得益 6 2q q 1 2 6 2q q 1 3 如果一方在第一阶段偏离合作 其应在对方采取q 产量的情况下 采取使其利润最大化的产量 即 max 8 q q2 q2 2q2 对q2求导解得q2 6 q 2 此时利润u 6 q 2 4 4 3 4无限次重复博弈的古诺模型 2020 1 13 51 4 3 4无限次重复博弈的古诺模型 但是在后续阶段中只能得到古诺产量下的利润4 因此总收益 6 q 2 4 4 2 6 q 2 4 4 1 4 如果得益满足 3 4 触发策略下保持合作的产量q 将构成子博弈完美纳什均衡 可以解得 q 2 9 5 9 2020 1 13 52 结论 对于不同的贴现系数 无限次重复博弈的古诺模型可以相应的实现不同的可实现得益 两者之间的关系为q 2 9 5 9 其中 当 9 17时 q 1 5 即为触发策略1 当 0时 q 2 即为一次性博弈中纳什均衡的古诺产量 4 3 4无限次重复博弈的古诺模型 2020 1 13 53 一种胡萝卜加大棒的策略3 第一阶段双方生产垄断产量1 5 如果在第 t 1 阶段结果为 1 5 1 5 没有发生偏离 则继续保持合作 如果双方同时偏离并产量相等 也既往不咎 继续保持垄断产量1 5 如果对方单方面偏离 则采取惩罚性的高产量x 4 3 4无限次重复博弈的古诺模型 2020 1 13 54 4 3 4无限次重复博弈的古诺模型 策略3分析 如果一方在第一阶段中偏离垄断产量 其应在对方采取垄断产量1 5情况下 采取使其利润最大化的产量 即 max 8 1 5 q2 q2 2q2 max 4 5 q2 q2解得q2 2 25 此时利润u max 4 5 q2 q2 5 0625 相对于合作垄断产量 1 5 1 5 的得益4 5 第一阶段偏离后得益的增加值为 5 0625 4 5 0 5625 5 2020 1 13 55 这一偏离行为在第二阶段中将面临着来自对方的惩罚性高产量x 根据策略设计 如果在第二阶段也采取同样的产量x 那么在第三阶段以后将继续保持合作垄断的结局 因此 第二阶段也采取惩罚性高产量x 此阶段得益为 8 2x x 2x 6x 2x2 4 3 4无限次重复博弈的古诺模型 2020 1 13 56 4 3 4无限次重复博弈的古诺模型 相对于合作垄断产量的得益4 5 考虑贴现系数后 此阶段的得益损失为 4 5 6x 2x2 6 当得益满足 5 6 时 保持合作的垄断产量将构成子博弈完美纳什均衡 解得 0 5625 4 5 6x 2x2 2020 1 13 57 结论 上式表明 博弈方是否采取偏离行为 不仅与贴现系数 有关 而且与惩罚性产量x的大小有关 当 0 5时 只有满足x 2 25才能保证博弈方不发生偏离 注意 由于纳什均衡的古诺产量为2 因此x 2 25高于纳什均衡产量 故称为惩罚性高产量 4 3 4无限次重复博弈的古诺模型 2020 1 13 58 比较策略2和策略3 策略2表明了在无限次重复博弈的古诺模型中 采取触发策略下双方是否能够达成合作的垄断产量 取决于贴现系数和可实现得益的相应产量q 两者之间存在替代关系 即q 2 9 5 9 策略3表明了采取胡萝卜加大棒策略下双方是否能够达成合作的垄断产量 取决于贴现系数和 大棒 的惩罚力度 两者之间也存在替代关系 即 加大惩罚力度x可以相应的降低贴现系数 0 5625 4 5 6x 2x2 4 3 4无限次重复博弈的古诺模型 2020 1 13 59 问题提出 厂商提供较高的工资w 可以促进工人努力工作 但是也增加了成本 因此需要确定一个适当的工资率 工人根据自己的能力决定拒绝或接受这个工资水平 如果工人接受工作 可以选择努力工作或者偷懒 4 3 5无限次重复博弈的效率工资模型 2020 1 13 60 原博弈的结构 原博弈为一个两阶段动态博弈 4 3 5无限次重复博弈的效率工资模型 2020 1 13 61 4 3 5无限次重复博弈的效率工资模型 原博弈结构的说明 如果工人努力工作 其付出的代价为e 但会获得一个y 0的高产量 如果工人偷懒 其仅仅有概率p获得高产量 而获得低产量的概率为 1 p 厂商只能通过产量判断工人的努力程度 产品的价格为1 一次性博弈的结局 在厂商必须支付工资w条件下 工人将选择偷懒 此时厂商的收益 py