第四章重复博弈精选文档.ppt

《第四章重复博弈精选文档.ppt》由会员分享，可在线阅读，更多相关《第四章重复博弈精选文档.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章重复博弈2023/1/241本讲稿第一页，共八十一页第一节第一节 几个概念几个概念l l重复博弈的概念重复博弈的概念l l有限次重复博弈的概念有限次重复博弈的概念本讲稿第二页，共八十一页4.1.1 4.1.1 重复博弈的概念重复博弈的概念 1 1 由简单的静态博弈（或动态博弈）的有限次由简单的静态博弈（或动态博弈）的有限次（或无限次）重复进行构成的。（或无限次）重复进行构成的。2 2 每一阶段博弈方、策略集合、规则和得益都相每一阶段博弈方、策略集合、规则和得益都相 同。同。3 3 包括：有限次重复博弈和无限次重复博弈包括：有限次重复博弈和无限次重复博弈 4 4 例子：例子：多场决胜负的体

2、育比赛（有限次）多场决胜负的体育比赛（有限次）两寡头市场上两个厂商之间的竞争（无限次）两寡头市场上两个厂商之间的竞争（无限次）商场与顾客交易商场与顾客交易本讲稿第三页，共八十一页 定义定义：给定一个博弈：给定一个博弈G G，重复进行，重复进行T T次次G G，并且在，并且在每次重复之前各博弈方都能观察到以前博弈的结每次重复之前各博弈方都能观察到以前博弈的结果，称为果，称为G G的一个的一个“T T次重复博弈次重复博弈”，记为，记为G(T)G(T)。其中，其中，G G成为成为G(T)G(T)的的原博弈原博弈。每次重复称为。每次重复称为G(T)G(T)的一个的一个阶段阶段。4.1.2 4.1.2

3、有限次重复博弈的概念有限次重复博弈的概念本讲稿第四页，共八十一页4.1.2 4.1.2 有限次重复博弈的概念有限次重复博弈的概念 几个概念：几个概念：1 1 子博弈子博弈：从某一阶段（不包括第一阶段）开始，：从某一阶段（不包括第一阶段）开始，包含以后所有阶段的原重复博弈的一部分。包含以后所有阶段的原重复博弈的一部分。2 2 策略策略：博弈方在每个阶段针对每种情况如何行：博弈方在每个阶段针对每种情况如何行动的计划（注：在每一阶段之前，博弈方是可动的计划（注：在每一阶段之前，博弈方是可以观察到以前博弈的结果的）。以观察到以前博弈的结果的）。本讲稿第五页，共八十一页3 3 路径路径：是每个阶段博弈结

4、果（原博弈的一个是每个阶段博弈结果（原博弈的一个策略组合）连接而成。对于具有策略组合）连接而成。对于具有n n个策略组合个策略组合的原博弈，重复的原博弈，重复T T次的路径数为次的路径数为n nT T，重复博弈，重复博弈的求解即找出具有稳定性的均衡路径。的求解即找出具有稳定性的均衡路径。4 4 得益得益：不同于一般的动态博弈，重复博弈的得：不同于一般的动态博弈，重复博弈的得益为各个阶段益为各个阶段得益的加总得益的加总。考虑到时间的价值，。考虑到时间的价值，需要引进需要引进“贴现系数贴现系数”将未来的得益折算成当将未来的得益折算成当期得益的价值。期得益的价值。4.1.2 有限次重复博弈的概念有限

5、次重复博弈的概念本讲稿第六页，共八十一页第二节第二节 有限次重复博弈有限次重复博弈l l有限次重复的猜硬币博弈有限次重复的猜硬币博弈原博弈为零和博弈原博弈为零和博弈l l有限次重复的囚徒困境博弈有限次重复的囚徒困境博弈原博弈有唯一的原博弈有唯一的纯策略纳什均衡纯策略纳什均衡l l有多个纳什均衡的重复博弈的策略设计有多个纳什均衡的重复博弈的策略设计触发触发策略策略l l有多个纳什均衡重复博弈的得益范围有多个纳什均衡重复博弈的得益范围民间定民间定理理本讲稿第七页，共八十一页 在零和博弈中，双方不存在合作的可能性，在零和博弈中，双方不存在合作的可能性，因此在长期进行的重复博弈中，子博弈完美纳什因此在

6、长期进行的重复博弈中，子博弈完美纳什均衡由各个阶段原博弈的纳什均衡构成（例，在均衡由各个阶段原博弈的纳什均衡构成（例，在猜硬币博弈中以猜硬币博弈中以0.50.5的概率选择正面或者反面，的概率选择正面或者反面，即采取混合策略）。即采取混合策略）。实际上，所有以零和博弈为原博弈所构成的实际上，所有以零和博弈为原博弈所构成的重复博弈与猜硬币博弈构成的重复博弈一样，各重复博弈与猜硬币博弈构成的重复博弈一样，各博弈方的正确策略就是在每次重复中都采用一次博弈方的正确策略就是在每次重复中都采用一次性博弈中的纳什均衡策略。性博弈中的纳什均衡策略。4.2.1 4.2.1 有限次重复的猜硬币博弈有限次重复的猜硬币

7、博弈本讲稿第八页，共八十一页4.2.2 4.2.2 有限次重复的囚徒困境博弈有限次重复的囚徒困境博弈 图图图图4 4 4 41 1 1 1 囚徒困境囚徒困境囚徒困境囚徒困境l l求解思路：对于有限次重复囚徒困境博弈，根据求解思路：对于有限次重复囚徒困境博弈，根据求解思路：对于有限次重复囚徒困境博弈，根据求解思路：对于有限次重复囚徒困境博弈，根据动态博弈的动态博弈的动态博弈的动态博弈的逆推归纳法逆推归纳法逆推归纳法逆推归纳法可以求解。可以求解。可以求解。可以求解。5 5 5 5，5 5 5 5 0 0 0 0，8 8 8 88 8 8 8，0 0 0 01 1 1 1，1 1 1 1坦白坦白坦白

8、坦白不坦白不坦白不坦白不坦白 坦白坦白坦白坦白 不坦白不坦白不坦白不坦白本讲稿第九页，共八十一页4.2.2 4.2.2 有限次重复的囚徒困境博弈有限次重复的囚徒困境博弈 以以以以两阶段两阶段两阶段两阶段（以该博弈作为原博弈（以该博弈作为原博弈（以该博弈作为原博弈（以该博弈作为原博弈G G G G重复两次）为重复两次）为重复两次）为重复两次）为例：分析最后一阶段，子博弈即为原博弈，唯一的例：分析最后一阶段，子博弈即为原博弈，唯一的例：分析最后一阶段，子博弈即为原博弈，唯一的例：分析最后一阶段，子博弈即为原博弈，唯一的均衡为（均衡为（均衡为（均衡为（5 5 5 5，5 5 5 5）；分析第一阶段，

9、将最后阶段）；分析第一阶段，将最后阶段）；分析第一阶段，将最后阶段）；分析第一阶段，将最后阶段的收益（的收益（的收益（的收益（5 5 5 5）添加到第一阶段的矩阵中，即：）添加到第一阶段的矩阵中，即：）添加到第一阶段的矩阵中，即：）添加到第一阶段的矩阵中，即：此时，博弈的纳什均衡仍是（坦白，坦白）。此时，博弈的纳什均衡仍是（坦白，坦白）。此时，博弈的纳什均衡仍是（坦白，坦白）。此时，博弈的纳什均衡仍是（坦白，坦白）。坦白坦白坦白坦白 不坦白不坦白不坦白不坦白坦白坦白坦白坦白不坦白不坦白不坦白不坦白10101010，10101010 5 5 5 5，1313131313131313，5 5 5

10、56 6 6 6，6 6 6 6本讲稿第十页，共八十一页l l结论结论：在有限次重复博弈在有限次重复博弈G(T)G(T)中，如果原博中，如果原博弈弈G G存在存在唯一的唯一的纯策略纳什均衡组合，则重复纯策略纳什均衡组合，则重复博弈的唯一的子博弈完美纳什均衡解为各博弈博弈的唯一的子博弈完美纳什均衡解为各博弈方在每阶段都采取的原博弈纳什均衡策略。方在每阶段都采取的原博弈纳什均衡策略。l l含义含义：在原博弈具有唯一均衡的有限次重复博：在原博弈具有唯一均衡的有限次重复博弈中，由于完全理性的博弈方具有弈中，由于完全理性的博弈方具有“共同知识共同知识”的分析推理能力，因此在从最后阶段开始的的分析推理能力

11、，因此在从最后阶段开始的逆推过程中，仍然无法摆脱囚徒困境。逆推过程中，仍然无法摆脱囚徒困境。4.2.2 4.2.2 有限次重复的囚徒困境博弈有限次重复的囚徒困境博弈本讲稿第十一页，共八十一页4.2.2 4.2.2 有限次重复的囚徒困境博弈有限次重复的囚徒困境博弈l l如果原博弈存在唯一的纯策略纳什均衡组合，则如果原博弈存在唯一的纯策略纳什均衡组合，则有限次重复博弈的唯一的均衡解即各博弈方在每有限次重复博弈的唯一的均衡解即各博弈方在每阶段（即每次重复）中都采用原博弈的纳什均衡阶段（即每次重复）中都采用原博弈的纳什均衡策略。由于在这样的双方策略下，均衡路径中的策略。由于在这样的双方策略下，均衡路径

12、中的每个阶段都不存在不可信的威胁或许诺，因此这每个阶段都不存在不可信的威胁或许诺，因此这种均衡是子博弈完美纳什均衡。种均衡是子博弈完美纳什均衡。本讲稿第十二页，共八十一页4.2.2 4.2.2 有限次重复的囚徒困境博弈有限次重复的囚徒困境博弈 定理定理 设原博弈设原博弈G有唯一的纯策略纳什均衡，则有唯一的纯策略纳什均衡，则对任意正整数对任意正整数T，重复博弈，重复博弈G（T）有唯一的子）有唯一的子博弈完美的解，即各博弈方每个阶段都采用博弈完美的解，即各博弈方每个阶段都采用G的纳什均衡策略。各博弈方在的纳什均衡策略。各博弈方在G（T）中的总得）中的总得益为在益为在G中得益的中得益的T倍，平均每阶

13、段得益等于原倍，平均每阶段得益等于原博弈博弈G中的得益。中的得益。本讲稿第十三页，共八十一页重复博弈重复博弈-广告博弈广告博弈l两个企业(Kelloggs&General Mills)的经理想最大化利润l策略是广告活动l同步博弈l一次博弈l无限重复博弈l有限重复博弈本讲稿第十四页，共八十一页一次广告博弈一次广告博弈通用面粉通用面粉凯洛格凯洛格策略策略无广告无广告中等强度中等强度高强度高强度无广告无广告1212，12121 1，2020-1-1，1515中等强度中等强度2020，1 16 6，6 60 0，9 9高强度高强度1515，-1-19 9，0 02 2，2 2本讲稿第十五页，共八十一页

14、一次广告博弈的均衡一次广告博弈的均衡纳什均衡纳什均衡通用面粉通用面粉凯洛格凯洛格策略策略无广告无广告中等强度中等强度高强度高强度无广告无广告1212，12121 1，2020-1-1，1515中等强度中等强度2020，1 16 6，6 60 0，9 9高强度高强度1515，-1-19 9，0 02 2，2 2n劣策略：不管其他参与人采取什么策略，都能导致最低收益的策略n理性参与人永远不会选择劣策略n许多博弈中参与者都没有占优策略，但仍可能通过劣策略的重复剔除进行分析，这种方法称劣策略重复剔除法本讲稿第十六页，共八十一页如果企业每年都进行这种一次博弈，并且永远进行下去，这时参与人可以对对手的如果

15、企业每年都进行这种一次博弈，并且永远进行下去，这时参与人可以对对手的“欺骗欺骗”行为进行惩罚或报复。在这种情况下，共谋起作用吗？行为进行惩罚或报复。在这种情况下，共谋起作用吗？l密歇根大学爱克斯罗德教授的计算机模拟 他首先邀请全世界的学者递交自认为最优的策略程序，然后将这些策略相互之间交替进行不特定次数的“重复囚徒博弈”，根据最终排名来判定优劣。第一轮14个程序之间的竞赛结果显示，“一报还一报”的简单策略获得第一。之后，又有63位科学家递交了改进的程序，进行第二轮竞赛，其中包括多个以“一报还一报”策略为基础的改良品种。令人惊异的是，第二轮比赛的优胜者仍然是“一报还一报”。l触发策略“如果对手在

16、过去没有做过广告，我就不做；一旦对手作广告，自此以后，我就用高强度的广告活动来惩罚他”l事实上，只要对手在过去没有过“欺骗”行为，各个企业都会同意“合作”。因为欺骗行为会引发以后所有时期的惩罚无限重复博弈本讲稿第十七页，共八十一页假设假设General MillsGeneral Mills采用了这种触发策略，采用了这种触发策略，KelloggsKelloggs的利润是多少呢的利润是多少呢?合作 =12+12/(1+i)+12/(1+i)2+12/(1+i)3+=12+12/i相当于每年年底得到￥12的永久年金欺骗 =20+2/(1+i)+2/(1+i)2+2/(1+i)3+=20+2/i通用面

17、粉通用面粉凯洛格凯洛格策略策略无广告无广告中等强度中等强度高强度高强度无广告无广告1212，12121 1，2020-1-1，1515中等强度中等强度2020，1 16 6，6 60 0，9 9高强度高强度1515，-1-19 9，0 02 2，2 2本讲稿第十八页，共八十一页KelloggKellogg从欺骗行为中获得的好处从欺骗行为中获得的好处:l欺骗-合作=20+2/i-(12+12/i)=8-10/i假设i=.05l欺骗-合作=8-10/.05=8-200=-192l欺骗没有好处.在无限次重复博弈中共谋是纳什均衡!通用面粉通用面粉凯洛格凯洛格策略策略无广告无广告中等强度中等强度高强度高

18、强度无广告无广告1212，12121 1，2020-1-1，1515中等强度中等强度2020，1 16 6，6 60 0，9 9高强度高强度1515，-1-19 9，0 02 2，2 2本讲稿第十九页，共八十一页欺骗行为的收益和成本欺骗行为的收益和成本l如果 当前收益 未来成本的现值 欺骗行为是有利的l如果 当前收益 未来成本的现值欺骗行为没有好处通用面粉通用面粉凯洛格凯洛格策略策略无广告无广告中等强度中等强度高强度高强度无广告无广告1212，12121 1，2020-1-1，1515中等强度中等强度2020，1 16 6，6 60 0，9 9高强度高强度1515，-1-19 9，0 02 2

19、，2 2本讲稿第二十页，共八十一页关键点关键点l当博弈无限重复没有确定的“终结之日”时，共谋作为纳什均衡就能够维持下去l这需要:有能力监督对手的行动有惩罚叛徒的能力和名声低利率在未来进行博弈的机会多 本讲稿第二十一页，共八十一页共谋在现实世界中的例子共谋在现实世界中的例子l垃圾搜集行业l水表制造业l石油输出国组织l黑手党组织本讲稿第二十二页，共八十一页说明说明l根据谢尔曼反托拉斯法案第二节，共谋是违法的.l后果可能是罚款和坐牢lOPEC是国际间组织，美国法律不适用于它本讲稿第二十三页，共八十一页如果博弈有限重复进行，共谋起作用吗如果博弈有限重复进行，共谋起作用吗?有限重复博弈有限重复博弈假设广

20、告博弈被重复两次通用面粉通用面粉凯洛格凯洛格策略策略无广告无广告中等强度中等强度高强度高强度无广告无广告1212，12121 1，2020-1-1，1515中等强度中等强度2020，1 16 6，6 60 0，9 9高强度高强度1515，-1-19 9，0 02 2，2 2纳什均衡本讲稿第二十四页，共八十一页用逆向归纳法，结论是：不用逆向归纳法，结论是：不.l在第二阶段，博弈是一次博弈，因此在这最后阶段，均衡是高强度的广告活动.l由于每个人都知道第二阶段的结果，因此，第一阶段就变成了最后阶段.l两个企业在两个时期的均衡策略都是高强度的广告活动.l如果博弈重复已知的有限次数，同样的结果依然成立本

21、讲稿第二十五页，共八十一页期末问题的应用期末问题的应用l当参与方确切地知道一个重复博弈什么时候结束时，期末问题就出现了。由于无法在最后一次对对手违背协议行为进行惩罚，因此参与方就会采取如同一次博弈的策略l59岁现象l辞职问题l虚假广告l火车站和旅游点的商贩本讲稿第二十六页，共八十一页4.2.3 4.2.3 有两个纳什均衡的重复博弈有两个纳什均衡的重复博弈例例例例 两个厂商两个厂商两个厂商两个厂商1 1 1 1和和和和2 2 2 2，同时，同时，同时，同时面临两个市场机会面临两个市场机会面临两个市场机会面临两个市场机会A A A A和和和和B B B B。假。假。假。假设每个厂商都只有能力选择设

22、每个厂商都只有能力选择设每个厂商都只有能力选择设每个厂商都只有能力选择一市场发展，即他们的可选一市场发展，即他们的可选一市场发展，即他们的可选一市场发展，即他们的可选择策略都是择策略都是择策略都是择策略都是A A A A或或或或B B B B，其得益矩，其得益矩，其得益矩，其得益矩阵如图所示。阵如图所示。阵如图所示。阵如图所示。此博弈具有此博弈具有此博弈具有此博弈具有2 2 2 2个纯策略纳什均衡（个纯策略纳什均衡（个纯策略纳什均衡（个纯策略纳什均衡（1 1 1 1，4 4 4 4）、）、）、）、（4 4 4 4，1 1 1 1）和混合策略纳什均衡概率（）和混合策略纳什均衡概率（）和混合策略纳

23、什均衡概率（）和混合策略纳什均衡概率（0.50.50.50.5，0.50.50.50.5）。）。）。）。A BA BA BA BA A A A B B B B3 3 3 3，3 3 3 31 1 1 1，4 4 4 44 4 4 4，1 1 1 10 0 0 0，0 0 0 0图图图图4 42 2 两厂商差别市场博弈两厂商差别市场博弈两厂商差别市场博弈两厂商差别市场博弈本讲稿第二十七页，共八十一页 考虑三次重复博弈各策略组合子博弈纳什均衡路考虑三次重复博弈各策略组合子博弈纳什均衡路径：径：1.1.由原博弈的纳什均衡组合而成的路径由原博弈的纳什均衡组合而成的路径，如采，如采取取轮换策略轮换策略（

24、在上述的协调博弈中，双方轮换采取（在上述的协调博弈中，双方轮换采取纯纳什均衡策略，路径为纯纳什均衡策略，路径为(A,B)(A,B)，(B,A)(B,A)，(A,B)(A,B).不考虑时间的价值（贴现系数），每阶段的平均得不考虑时间的价值（贴现系数），每阶段的平均得益为（益为（4 41 1）/2/2 2.52.5，高于混合策略的得益，高于混合策略的得益2 2。2.2.触发策略触发策略，博弈方首先采取合作行为，如果，博弈方首先采取合作行为，如果发现对方没有进行合作，那么在后续阶段的博弈中发现对方没有进行合作，那么在后续阶段的博弈中采取不合作策略进行惩罚。采取不合作策略进行惩罚。4.2.3 4.2.

25、3 有两个纳什均衡的重复博弈有两个纳什均衡的重复博弈本讲稿第二十八页，共八十一页 在图在图在图在图4 4 4 42 2 2 2中，中，中，中，触发策略的设计触发策略的设计触发策略的设计触发策略的设计为：为：为：为：（1 1 1 1）博弈方）博弈方）博弈方）博弈方1 1 1 1的策略是第一阶段合作的策略是第一阶段合作的策略是第一阶段合作的策略是第一阶段合作A A A A，如果发现对方采取，如果发现对方采取，如果发现对方采取，如果发现对方采取B B B B不合作，不合作，不合作，不合作，则第二阶段采取不合作的则第二阶段采取不合作的则第二阶段采取不合作的则第二阶段采取不合作的B B B B策略惩罚，

26、否则第二阶段继续合作；第三阶策略惩罚，否则第二阶段继续合作；第三阶策略惩罚，否则第二阶段继续合作；第三阶策略惩罚，否则第二阶段继续合作；第三阶段无条件采取段无条件采取段无条件采取段无条件采取B B B B策略。策略。策略。策略。（惩罚放在第二阶段）（惩罚放在第二阶段）（惩罚放在第二阶段）（惩罚放在第二阶段）（2 2 2 2）博弈方）博弈方）博弈方）博弈方2 2 2 2的策略是第一阶段合作的策略是第一阶段合作的策略是第一阶段合作的策略是第一阶段合作A A A A，第二阶段无条件选，第二阶段无条件选，第二阶段无条件选，第二阶段无条件选B B B B，如果第，如果第，如果第，如果第一阶段结果是（一阶

27、段结果是（一阶段结果是（一阶段结果是（A A A A，A A A A），则第三阶段），则第三阶段），则第三阶段），则第三阶段A A A A；如果第一阶段结果是（；如果第一阶段结果是（；如果第一阶段结果是（；如果第一阶段结果是（B B B B，A A A A），），），），则第三阶段选则第三阶段选则第三阶段选则第三阶段选B B B B。（惩罚放在第三阶段）。（惩罚放在第三阶段）。（惩罚放在第三阶段）。（惩罚放在第三阶段）（3 3 3 3）是一子博弈完美纳什均衡，双方每阶段的平均得益为（）是一子博弈完美纳什均衡，双方每阶段的平均得益为（）是一子博弈完美纳什均衡，双方每阶段的平均得益为（）是一子博弈

28、完美纳什均衡，双方每阶段的平均得益为（3+1+43+1+43+1+43+1+4）/3=2.67,/3=2.67,/3=2.67,/3=2.67,效率较高。效率较高。效率较高。效率较高。（4 4 4 4）如果增加博弈的重复次数到）如果增加博弈的重复次数到）如果增加博弈的重复次数到）如果增加博弈的重复次数到101101101101次。若采用的触发策略是：次。若采用的触发策略是：次。若采用的触发策略是：次。若采用的触发策略是：博弈方博弈方博弈方博弈方1 1 1 1在前在前在前在前99999999次中都选次中都选次中都选次中都选A A A A，但从其中的第二次开始，一旦发现，但从其中的第二次开始，一旦

29、发现，但从其中的第二次开始，一旦发现，但从其中的第二次开始，一旦发现 4.2.3 4.2.3 有两个纳什均衡的重复博弈有两个纳什均衡的重复博弈本讲稿第二十九页，共八十一页4.2.3 4.2.3 有两个纳什均衡的重复博弈有两个纳什均衡的重复博弈 那一次的结果不是（A，A），则改为B并坚持到底，最后两次重复与三次重复博弈后两次重复的策略相同；博弈方2：前99次选A，但从其中的第二次开始，一旦发现那一次的结果不是（A，A），则改为B并坚持到底，最后两次重复与三次重复博弈后两次重复的策略相同；双方的每阶段的平均得益是（993+1+4）/101=2.99,非常接近效率最高的得益（3，3）本讲稿第三十页，

30、共八十一页 策略设计分析策略设计分析：（1 1）在博弈方在博弈方1 1和和2 2中，在第一阶段都采取了合作中，在第一阶段都采取了合作行为行为A A，并针对对方的不合作行为，并针对对方的不合作行为B B，都设计了在，都设计了在后续后续2 2个阶段采取不合作个阶段采取不合作B B的相应惩罚措施；的相应惩罚措施；（2 2）如果对方在第一阶段中采取了合作行为，在）如果对方在第一阶段中采取了合作行为，在后续阶段的策略设计中要保证博弈结局具有稳健后续阶段的策略设计中要保证博弈结局具有稳健性。因此，针对第一阶段的合作行为，后续阶段性。因此，针对第一阶段的合作行为，后续阶段的策略设计是为了实现双方的行动协调，

31、以保证的策略设计是为了实现双方的行动协调，以保证实现纳什均衡（实现纳什均衡（B,AB,A）或（）或（A,BA,B）。）。4.2.3 4.2.3 有两个纳什均衡的重复博弈有两个纳什均衡的重复博弈本讲稿第三十一页，共八十一页 结果分析结果分析结果分析结果分析：子博弈路径（子博弈路径（子博弈路径（子博弈路径（A,A)A,A)A,A)A,A)，（，（，（，（A,BA,BA,BA,B），（），（），（），（B,AB,AB,AB,A）为子博弈纳）为子博弈纳）为子博弈纳）为子博弈纳什均衡。什均衡。什均衡。什均衡。因为后续两阶段的结局（因为后续两阶段的结局（因为后续两阶段的结局（因为后续两阶段的结局（A,BA

32、,BA,BA,B）和（）和（）和（）和（B,AB,AB,AB,A）为纳什均）为纳什均）为纳什均）为纳什均衡，而第一阶段的合作结局（衡，而第一阶段的合作结局（衡，而第一阶段的合作结局（衡，而第一阶段的合作结局（A,A)A,A)A,A)A,A)是由于触发策略针是由于触发策略针是由于触发策略针是由于触发策略针对对方偏离合作的行为设计了后续两阶段都不合作的惩罚对对方偏离合作的行为设计了后续两阶段都不合作的惩罚对对方偏离合作的行为设计了后续两阶段都不合作的惩罚对对方偏离合作的行为设计了后续两阶段都不合作的惩罚措施，其单方面偏离的路径（措施，其单方面偏离的路径（措施，其单方面偏离的路径（措施，其单方面偏离

33、的路径（B,AB,AB,AB,A）（）（）（）（B,BB,BB,BB,B）（）（）（）（B,BB,BB,BB,B）收）收）收）收益并不增加，因此不存在偏离的动机。益并不增加，因此不存在偏离的动机。益并不增加，因此不存在偏离的动机。益并不增加，因此不存在偏离的动机。4.2.3 4.2.3 有两个纳什均衡的重复博弈有两个纳什均衡的重复博弈本讲稿第三十二页，共八十一页l l问题的提出问题的提出：由于具有多个纳什均衡的重复博弈：由于具有多个纳什均衡的重复博弈可以设计多种策略，在双方缺乏沟通的情况下，可以设计多种策略，在双方缺乏沟通的情况下，结局具有不确定性。因此，这里讨论具有多个纳结局具有不确定性。因

34、此，这里讨论具有多个纳什均衡的重复博弈什均衡的重复博弈可以实现的收益范围可以实现的收益范围。l l个体理性得益个体理性得益：不管对方采取何种行动，只要自：不管对方采取何种行动，只要自己的行为合理就可以保证实现的收益。己的行为合理就可以保证实现的收益。l l可实现得益可实现得益：各纯策略组合得益的加权平均数组。：各纯策略组合得益的加权平均数组。注意：并非一定是均衡策略的组合得益，因此在注意：并非一定是均衡策略的组合得益，因此在图图4 42 2中，（中，（3 3，3 3）也是可实现得益。）也是可实现得益。4.2.4 4.2.4 民间定理民间定理本讲稿第三十三页，共八十一页4.2.4 4.2.4 民

35、间定理民间定理 用用w wi i记博弈方记博弈方i i在一次性博弈中最差的均衡得在一次性博弈中最差的均衡得益，用益，用w w记各博弈方的记各博弈方的w wi i构成的得益数组。结合构成的得益数组。结合“个体理性得益个体理性得益”和和“可实现得益可实现得益”，则，则有限但次有限但次数很多数很多的重复博弈有如下的重复博弈有如下民间定理民间定理：定理定理：将一次性博弈中最差的均衡得益数组：将一次性博弈中最差的均衡得益数组记为记为w,w,如果原博弈如果原博弈G G的一次性博弈有得益数组优于的一次性博弈有得益数组优于w w，那么在有限次重复博弈，那么在有限次重复博弈G(T)G(T)中，所有个体理性中，所

36、有个体理性得益和可实现得益都至少有一个子博弈完美纳什得益和可实现得益都至少有一个子博弈完美纳什均衡来实现。均衡来实现。本讲稿第三十四页，共八十一页 在图在图在图在图4-24-24-24-2一次性博弈中，博弈方均衡得益分别为纯一次性博弈中，博弈方均衡得益分别为纯一次性博弈中，博弈方均衡得益分别为纯一次性博弈中，博弈方均衡得益分别为纯策略的得益（策略的得益（策略的得益（策略的得益（1 1 1 1，4 4 4 4）和混合策略的得益（）和混合策略的得益（）和混合策略的得益（）和混合策略的得益（2 2 2 2，2 2 2 2）,最最最最差的均衡得益数组为差的均衡得益数组为差的均衡得益数组为差的均衡得益数

37、组为w=(1,1)w=(1,1)w=(1,1)w=(1,1)。图图图图4-3 4-3 4-3 4-3 民间定理民间定理民间定理民间定理4.2.4 4.2.4 民间定理民间定理(1,4)(1,4)(3,3)(3,3)(1,1)(1,1)(4,1)(4,1)厂厂商商2 2得得益益厂商厂商1 1得益得益本讲稿第三十五页，共八十一页 在图在图4-34-3中，通过不同得益的组合，阴影部中，通过不同得益的组合，阴影部分（包括连线）的得益都是可实现得益。分（包括连线）的得益都是可实现得益。民间定理揭示出：在有限次重复博弈中，可民间定理揭示出：在有限次重复博弈中，可以通过设计触发策略来实现（或者逼近）阴影部以

38、通过设计触发策略来实现（或者逼近）阴影部分的得益。分的得益。4.2.4 4.2.4 民间定理民间定理本讲稿第三十六页，共八十一页 定理分析定理分析：民间定理表明，在具有多个纳：民间定理表明，在具有多个纳什均衡的有限次重复博弈中，通过设计什均衡的有限次重复博弈中，通过设计具有可具有可信威胁的触发策略信威胁的触发策略（即在第一阶段采取合作行（即在第一阶段采取合作行为，当对方不合作时通过在后续阶段采取相应为，当对方不合作时通过在后续阶段采取相应的不合作策略进行惩罚；当对方合作时，在最的不合作策略进行惩罚；当对方合作时，在最后阶段采取一次性原博弈的纳什均衡策略作为后阶段采取一次性原博弈的纳什均衡策略作

39、为稳定的结局。），可以使得博弈方在重复博弈稳定的结局。），可以使得博弈方在重复博弈的过程中具有了一定学习能力，从而达到博弈的过程中具有了一定学习能力，从而达到博弈的的帕累托前沿得益帕累托前沿得益。4.2.4 4.2.4 民间定理民间定理本讲稿第三十七页，共八十一页l l例（两人各三种可选策略）：例（两人各三种可选策略）：例（两人各三种可选策略）：例（两人各三种可选策略）：L M RL M RL M RL M R L L L L M M M M R R R R 图图图图4 4 4 44 4 4 4多种策略博弈的重复博弈多种策略博弈的重复博弈多种策略博弈的重复博弈多种策略博弈的重复博弈 该博弈具有

40、两个纯策略纳什均衡和一个混合策略纳该博弈具有两个纯策略纳什均衡和一个混合策略纳该博弈具有两个纯策略纳什均衡和一个混合策略纳该博弈具有两个纯策略纳什均衡和一个混合策略纳什均衡，但是双方存在一个更好的得益（什均衡，但是双方存在一个更好的得益（什均衡，但是双方存在一个更好的得益（什均衡，但是双方存在一个更好的得益（4 4 4 4，4 4 4 4）。对于二）。对于二）。对于二）。对于二次重复博弈，根据民间定理可以设计一个次重复博弈，根据民间定理可以设计一个次重复博弈，根据民间定理可以设计一个次重复博弈，根据民间定理可以设计一个触发策略触发策略触发策略触发策略来实来实来实来实现这个得益。现这个得益。现这

41、个得益。现这个得益。1 1 1 1，1 1 1 15 5 5 5，0 0 0 00 0 0 0，0 0 0 00 0 0 0，5 5 5 54 4 4 4，4 4 4 40 0 0 0，0 0 0 00 0 0 0，0 0 0 00 0 0 0，0 0 0 03 3 3 3，3 3 3 34.2.4 4.2.4 民间定理民间定理本讲稿第三十八页，共八十一页 触发策略触发策略：博弈方：博弈方1 1在第一阶段采取在第一阶段采取M M策略，策略，如果对方合作，则第二阶段采取如果对方合作，则第二阶段采取R R策略作为奖策略作为奖励；否则第二阶段采取励；否则第二阶段采取L L策略进行惩罚（注意策略进行惩

42、罚（注意(L,L)(L,L)也是纳什均衡，因此具有稳定性）。博也是纳什均衡，因此具有稳定性）。博弈方弈方2 2也采取同样策略。也采取同样策略。策略分析策略分析：如果任何一方在第一阶段偏离，：如果任何一方在第一阶段偏离，仅仅多获得仅仅多获得5 54 41 1单位得益，而在第二阶段单位得益，而在第二阶段的得益（的得益（L,LL,L）仅仅为）仅仅为1 1；如果在第一阶段合作，；如果在第一阶段合作，第二阶段的得益为第二阶段的得益为3 3。因此双方不存在偏离该。因此双方不存在偏离该策略的动机。策略的动机。4.2.4 4.2.4 民间定理民间定理本讲稿第三十九页，共八十一页l l例（双方各五种可选策略重复

43、博弈）：例（双方各五种可选策略重复博弈）：例（双方各五种可选策略重复博弈）：例（双方各五种可选策略重复博弈）：L M R P QL M R P QL M R P QL M R P Q L L L L M M M M R R R R P P P P Q Q Q Q 图图图图4 4 4 45 5 5 5双方各五种可选策略重复博弈双方各五种可选策略重复博弈双方各五种可选策略重复博弈双方各五种可选策略重复博弈1 1 1 1,1 1 1 15,05,05,05,00,00,00,00,00,00,00,00,00,00,00,00,00,50,50,50,54,44,44,44,40,00,00,00,

44、00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,03 3 3 3,3 3 3 30,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,04 4 4 4,1/21/21/21/20,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,01/21/21/21/2,4 4 4 44.2.4 4.2.4 民间定理民间定理本讲稿第四十页，共八十一页 该博弈具有该博弈具有4 4个纯策略纳什均衡，在二次重个纯策略纳什均衡，在二次重复博弈

45、中，复博弈中，触发策略设计触发策略设计：第一阶段双方采取：第一阶段双方采取(M,M)(M,M)策略，如果博弈方策略，如果博弈方1 1偏离此策略，那么第二偏离此策略，那么第二阶段采取阶段采取(Q,Q)(Q,Q)策略对博弈方策略对博弈方1 1进行惩罚，对博弈进行惩罚，对博弈方方2 2进行奖励；同理，如果博弈方进行奖励；同理，如果博弈方2 2偏离了此策略，偏离了此策略，那么采取那么采取(P,P)(P,P)策略对博弈方策略对博弈方2 2进行惩罚，对博弈进行惩罚，对博弈方方1 1进行奖励。如果双方都没有偏离，那么第二进行奖励。如果双方都没有偏离，那么第二阶段采取具有较高收益的纳什均衡阶段采取具有较高收益

46、的纳什均衡(R,R)(R,R)策略。策略。如果双方都偏离了此策略，第二阶段同样采取纳如果双方都偏离了此策略，第二阶段同样采取纳什均衡的什均衡的(R,R)(R,R)策略。策略。4.2.4 4.2.4 民间定理民间定理本讲稿第四十一页，共八十一页 策略分析策略分析：与图：与图4 44 4例子相比较，由于博弈的特殊例子相比较，由于博弈的特殊结构，这个触发策略的设计对偏离行为和合作行为结构，这个触发策略的设计对偏离行为和合作行为分别进行惩罚和奖励，因此策略分别进行惩罚和奖励，因此策略具有很强的可信性具有很强的可信性。而在图而在图4-44-4例子中，针对对方的偏离行为采取了例子中，针对对方的偏离行为采取

47、了（L,LL,L）策略进行惩罚，但是惩罚对方的同时，自）策略进行惩罚，但是惩罚对方的同时，自身的利益也受到了损害，因此可信性不强。身的利益也受到了损害，因此可信性不强。4.2.4 4.2.4 民间定理民间定理本讲稿第四十二页，共八十一页第三节第三节 无限次重复博弈无限次重复博弈l l在在在在有限次重复博弈有限次重复博弈有限次重复博弈有限次重复博弈中，中，中，中，（1 1 1 1）由于完全理性的博弈方可以运用逆推归纳法，）由于完全理性的博弈方可以运用逆推归纳法，）由于完全理性的博弈方可以运用逆推归纳法，）由于完全理性的博弈方可以运用逆推归纳法，因此对于原博弈具有唯一纳什均衡（如囚徒困境博因此对于

48、原博弈具有唯一纳什均衡（如囚徒困境博因此对于原博弈具有唯一纳什均衡（如囚徒困境博因此对于原博弈具有唯一纳什均衡（如囚徒困境博弈）的有限次重复博弈，重复博弈结局尚无法摆脱弈）的有限次重复博弈，重复博弈结局尚无法摆脱弈）的有限次重复博弈，重复博弈结局尚无法摆脱弈）的有限次重复博弈，重复博弈结局尚无法摆脱囚徒困境；囚徒困境；囚徒困境；囚徒困境；（2 2 2 2）但是对于原博弈具有多个纳什均衡的有限次重）但是对于原博弈具有多个纳什均衡的有限次重）但是对于原博弈具有多个纳什均衡的有限次重）但是对于原博弈具有多个纳什均衡的有限次重复博弈，根据民间定理可以设计出具有可信威胁的复博弈，根据民间定理可以设计出具

49、有可信威胁的复博弈，根据民间定理可以设计出具有可信威胁的复博弈，根据民间定理可以设计出具有可信威胁的触发策略，达到帕累托最优的博弈结局。触发策略，达到帕累托最优的博弈结局。触发策略，达到帕累托最优的博弈结局。触发策略，达到帕累托最优的博弈结局。本讲稿第四十三页，共八十一页第三节第三节 无限次重复博弈无限次重复博弈l l在本节的在本节的无限次重复博弈无限次重复博弈中，由于无法运用逆中，由于无法运用逆推归纳法，因此对于原博弈具有唯一纳什均衡推归纳法，因此对于原博弈具有唯一纳什均衡（如囚徒困境博弈）的无限次重复博弈，考虑（如囚徒困境博弈）的无限次重复博弈，考虑到到时间的价值时间的价值后，也可以设计出

50、具有可信威胁后，也可以设计出具有可信威胁的触发策略，摆脱囚徒困境，达到帕累托最优的触发策略，摆脱囚徒困境，达到帕累托最优的博弈结局。的博弈结局。本讲稿第四十四页，共八十一页4.3.1 4.3.1 几个概念几个概念l l无限次重复博弈求解存在的无限次重复博弈求解存在的无限次重复博弈求解存在的无限次重复博弈求解存在的问题问题问题问题：（：（：（：（1 1 1 1）由于不存在）由于不存在）由于不存在）由于不存在最后一个阶段，无法运用逆推归纳法求解；（最后一个阶段，无法运用逆推归纳法求解；（最后一个阶段，无法运用逆推归纳法求解；（最后一个阶段，无法运用逆推归纳法求解；（2 2 2 2）如）如）如）如果