四章重复博弈

1、第四章节 重复博弈何为“重复博弈”？l重复博弈是指基本博弈重复进行构成的博弈过程。重复博弈中每个阶段中的博弈方、可选策略、规则和得益都是相同的-是特殊的动态博弈；形式上是基本博弈的重复进行，但博弈方的行为和博弈结果不一定是基本博弈的简单重复，因为博弈方对于博弈会重复进行的意识，会使他们对利益的判断发送变化，从而使他们在重复博弈过程不同阶段的行为选择受到影响。可信度：子博弈完美性仍是判断均衡是否稳定可靠的重要判断依据4.1 引论4.1.1 为什么研究重复博弈4.1.2 基本概念分类：有限次重复博弈，无限次重复博弈给定一个基本博弈（可以静态，也可以动态），重复进行了次，并且在每次重复之前，各博弈方

2、都能观察到以前博弈的结果，这样的博弈过程称为“的次重复博弈”，记为。而称为的“原博弈”。中的每次重复称为的一个“阶段”。理论上，重复博弈可以无限制进行下去，不一定经过一定次数重复以后就必须结束。如果一个基本博弈一直重复下去，这样的重复博弈就是“无限次重复博弈”，记为。无限次重复博弈的基本博弈也称为“原博弈”。无限次重复博弈是有无限个阶段的动态博弈。重复博弈的次数虽然有限，但重复的次数或博弈结束的时间不确定，这种重复博弈中博弈方的行为选择与确定结束时间的有限次重复博弈很不同，与无限次重复博弈很相似，甚至可以通过某种方式与无限次重复博弈统一起来。这种重复博弈可以称为“随机结束的重复博弈”。策略、子

3、博弈和均衡路径l策略：博弈方的一个策略就是在每个阶段（即每次重复），针对每种情况（以前阶段的结果）如何行动的计划。l子博弈：重复博弈的子博弈就是从某个阶段（不包括第一阶段）开始，包括此后所有阶段的重复博弈部分。l路径：-子博弈完美纳什均衡，以逆推归纳法（逆向归纳法）为核心的子博弈完美纳什均衡分析及相关结论，可以推广到重复博弈中。-重复博弈的路径是由每个阶段博弈方的行动组合串联而成的。因为对应前一阶段的每种结果，下一阶段都有原博弈全部策略组合数那么多种可能的结果。原博弈有种策略组合，那么重复两次就有条博弈路径，重复次就有条博弈路径。重复博弈的得益（支付）任何博弈中博弈方策略选择的依据都是得益的大

4、小。计算重复博弈的“总得益”。计算各阶段的“平均得益”。时间有先后，引入贴现系数无限次重复博弈：无限次重复博弈有时也写作在考虑贴现因素的情况下，重复博弈的平均得益与不考虑贴现因素时的平均得益，必然也有所不同。通常可以用下列方式定义平均得益。如果一常数作为重复博弈（有限次重复或无限次重复）各个阶段的得益，能产生与得益序列，相同的现值，则称为，的“平均得益”。有限次重复博弈不一定考虑贴现问题。无限次重复博弈必然要考虑贴现问题。由于无限次重复博弈每阶段得益都是时，现值为，而每阶段得益为，时，无限次重复博弈的得益现值是，因此令这就是计算无限次重复博弈平均得益的公式。随机停止和贴现率典型的随机结束重复博

5、弈可以理解为在进行一个重复博弈时，每次都通过抽签来决定是否停止重复，如果抽到停止重复的概率为，则抽到重复下去的概率为。设某博弈方在此博弈中的阶段得益为，利率为，因为在每一次博弈以后能继续下一次重复的可能性是，因此第二阶段的期望得益为，进一步，第三阶段的期望得益为，故该博弈方在重复博弈中期望得益的现值为：其中最后一个等式是通过令得到的。把这个与前面纯粹考虑时间价值的贴现率统一起来，我们就把已知概率的随机停止重复博弈与无限次重复博弈统一起来了。随机停止重复博弈问题可以当作无限次重复博弈来进行分析。4.2 有限次重复博弈4.2.1 两人零和博弈的有限次重复博弈重复零和博弈不会创造出新的利益。合作的可

6、能性根本不存在。即使双方都知道还要重复进行许多次基本博弈，也不会改变它们在当前阶段博弈中的行动方式，不可能变得（哪怕是暂时的）合作和顾及对方的利益。所有以零和博弈为原博弈的有限次重复博弈，博弈方的正确策略都是重复一次性博弈中的纳什均衡策略。推广：非零和或多个博弈方，博弈方的利益严格对立，没有纯策略纳什均衡的其他严格竞争博弈中。在以这些博弈作为原博弈构成的有限次重复博弈中，惟一的子博弈完美纳什均衡就是所有博弈方都始终采用原博弈的混合策略纳什均衡策略。例：有限次重复猜硬币博弈l各博弈方的正确策略就是在每次重复中都采用一次性博弈中的纳什均衡策略。4.2.2 惟一纯策略纳什均衡博弈的有限次重复博弈在有

7、惟一纯策略纳什均衡的博弈中，博弈方之间的利益关系不再是始终对立的，而是有很大一致性甚至完全一致。在以这样的博弈为原博弈的有限次重复博弈中，博弈方的行动和博弈结果会不会发生质的变化？如果原博弈惟一的纯策略纳什均衡本身就是帕累托意义上的最佳策略组合，那么因为符合所有博弈方的利益，因此，有限次重复显然不会改变博弈方的行动方式。分析：原博弈惟一的纳什均衡没有达到帕累托效率，因此存在通过合作进一步提高效率的潜在可能性的囚徒困境式的博弈，在有限次重复博弈中能不能实现合作和提高效率呢？有限次重复博弈的囚徒困境两次重复博弈等价于图4.2一般结论（1）在有限次重复博弈中，如果原博弈存在唯一的纯策略纳什均衡策略组

8、合，则有限次重复博弈的唯一的均衡解即各博弈方在每阶段中都采用原博弈的纳什均衡； （2）由于在这样的双方策略下，均衡路径中的每个阶段都不存在任何不可信的威胁或许诺，因此这种均衡是子博弈完美纳什均衡。（3）在一个博弈中的每个博弈方的所有得益上各自加上相同的数值不会改变博弈原来的均衡定理 设原博弈G有惟一的纯策略纳什均衡，则对任意正整数T，重复博弈G(T)有惟一的子博弈完美纳什均衡，即各博弈方每个阶段都采用G的纳什均衡策略。各博弈方在G(T)中的总得益为在G中得益的T倍，平均得益等于原博弈G中的得益。定理 设原博弈有惟一的纯策略纳什均衡，则对任意正整数，重复博弈有惟一的子博弈完美纳什均衡，即各博弈方

9、每个阶段都采用的纳什均衡策略。各博弈方在中的总得益为在中得益的倍，平均得益等于原博弈中的得益。有限次重复削价竞争博弈例：石油输出国组织的困境l（1）某些成员国的石油资源已趋枯竭；l（2）不少非石油输出国组织成员国加入石油市场；l（3）石油输出国组织成员之间地位的不平衡；l（4）有些国家由于政治、经济、军事等方面的原因造成资金、财政紧张；重复囚徒困境悖论和连锁店悖论（1）与直觉的差异（2）连锁店悖论（Selten，1978）泽尔腾一个在个市场都开设有连锁店的企业，对于各个市场的竞争者是否应该加以打击排斥？由于个市场的竞争者一般不会同时进入竞争，如果忽略各个市场环境、竞争者不同等方面的微小差异，这

10、个问题对上述连锁企业来说相当于一个次重复的重复博弈。较多阶段的动态博弈总结：l第一类是由零和博弈构成的，不存在纯策略NE；第二类是唯一的纯策略纳什么均衡的静态博弈构成的。l共性：重复博弈本质上只不过是原博弈的简单重复，重复博弈每个阶段采取的策略就是原博弈中所采取的策略，在零和博弈的情况下是同样的混合策略NE，在后一种情况下则是纯策略NE;l重复博弈并不能给博弈方带来比一次博弈更好的结果，每阶段的平均得益与一次性博弈的得益相同。例：如果T次重复齐威王田忌赛马，双方在该重复博弈中的策略是什么？博弈结果如何？l特点：此博弈是混合博弈NE的严格竞争零和博弈，对一方有利的策略组合总是对另一方不利，没有一

11、个策略组合双方同时愿意接受。4.2.3 多个纯策略纳什均衡博弈的有限次重复博弈三价博弈的重复博弈触发策略trigger strategy：首先试探合作，一旦发觉对方不合作，则也用不合作相报复的策略。冷酷策略grim strategy触发策略的进一步讨论不计前嫌担心报复两市场博弈的重复博弈轮换策略：双方轮流去两个不同市场的策略。博弈论走向了“语言时代”？经济学与语言4.2.4 有限次重复博弈的无名氏定理（folk theorem）民间定理，民歌定理首先，记为博弈方在一次性博弈中最差的均衡得益（支付），用表示各博弈方的构成的得益数组。其次，不管其他博弈方的行为如何，一博弈方在某个博弈中只要自己采取

12、某种特定的策略，最低限度保证能获得的得益称为“个体理性得益”（individual rationality payoff）或“保留得益”（reservation payoff）。第三，博弈中所有纯策略组合得益的加权平均（权数非负且总和为1）数组称为“可实现得益”（feasible payoff）。有限重复博弈的无名氏定理设原博弈的一次性博弈有均衡得益数组优于，那么在该博弈的多次重复中，所有不小于个人理性得益的可实现得益，都至少有一个子博弈完美纳什均衡的极限的平均得益来实现它们。无名氏定理的关键意义：保证这些得益有一定次数重复博弈的子博弈完美纳什均衡的平均得益可以实现或逼近它们。有助于在重复博弈

13、中更好地把握机会，设计和运用高效率的策略，建立相互的默契和信任，从而争取实现更好的博弈结果。重复博弈往往也很难确定博弈结果究竟是哪一个子博弈完美纳什均衡。现实博弈的结果很大程度上取决于博弈方对重复博弈结构和性质的了解，以及博弈方的分析能力和相互信任等因素，特别是博弈方是否具有设计和实行轮换策略、触发策略的能力和默契。冷酷策略grim strategy：以囚徒困境博弈为例。(1) 一开始选择抵赖(2) 一直选择抵赖，除非某些参与人选择了坦白；如果某些参与人已经选择了坦白，那么就永远选择坦白针锋相对策略tit-for-tat(1) 开始时选择否认。(2) 此后，在第n期选择其他参与人在第n-1期选

14、择的行动。4.3 无限次重复博弈异：有限次：（1）存在最后一次博弈正是破坏重复博弈中博弈方利益和行为的相互制约关系，使重复博弈无法实现更高效率均衡的关键。（2）不一定考虑贴现问题无限次：（1）（2）对博弈方选择和博弈均衡的分析必须以平均得益或总得益的现值为依据。同：试图“合作”，惩罚“不合作”都是实现理想均衡的关键，是构造高效率均衡策略的核心构件。4.3.1 两人零和博弈的无限次重复博弈没有最后一个阶段，逆推法。先讨论无限次重复博弈的第阶段。显然，该阶段博弈方面临的仍然是一个无限次重复博弈两人零和博弈，博弈方的利益关系不会因为第阶段或前阶段的结果而有任何改变，仍然是严格对立的，因此在第阶段不会

15、合作。同理，第、也都不会合作。从重复博弈的第一个阶段开始就不可能合作。推广到更多博弈方、非零和的其他严格竞争博弈的无限次重复博弈。4.3.2 惟一纯策略纳什均衡博弈的无限次重复博弈原博弈有惟一纯策略纳什均衡的无限次重复博弈帕累托意义上最佳策略组合存在前在合作利益的囚徒困境式博弈囚徒困境式的无限次重复在囚徒困境式博弈的无限次重复博弈中，对双方有利的合作在子博弈完美纳什均衡中有可能存在，博弈可能会出现较理想的结果。分析：（L，L）无限次：触发策略，第一阶段采用H，如果前阶段的结果都是（H，H），则继续采用H，否则采用L。证明：在不同期得益的贴现因子较大时，双方采用上述策略构成无限次重复博弈的一个子

16、博弈完美纳什均衡。首先：双方采用上述触发策略是一个纳什均衡。假设博弈方1已采用了这种策略，然后证明在达到一定水平时，采用同样的触发策略是博弈方2的最佳反应策略。因为博弈方1和2是对称的，因此只要这个结论成立，就可以确定上述触发策略是两博弈方相互对对方策略的最佳反应，因此构成纳什均衡。由于与在某个阶段出现与（H，H）不同的结果以后，博弈方1将永远采用L，此时博弈方2也只有一直选择L。因此，博弈方2对博弈方1触发策略的最佳反应策略的后半部分与触发策略的后半部分是一样的。现在关键是确定博弈方2在第一阶段的最优选择。如果博弈方2采用L，那么在第一阶段能得到5，但以后引气博弈方1一直采用L的报复，自己也

17、只能一直采用L，得益将永远为1，总得益的现值为如果博弈方2采用H，则在第二阶段他将得到4，下一阶段又面临同样的选择。记为博弈方2在该重复博弈中每阶段都采用最佳选择的总得益现值，那么从第二阶段开始的无限次重复博弈因为与从第一阶段开始的只差一个阶段，因而在无限次重复时可看作相同的，其总得益的现值折算成第一阶段的得益为，因此第一阶段的最佳选择是H时，整个无限次重复博弈总得益的现值为或因此当即当时，博弈方会采用H，否则用L。由于从第二阶段开始的无限次重复博弈，与从第一阶段开始的无限次重复博弈是完全相同的，因此，博弈方第二阶段的选择必然也是H。第三阶段也同样。依此类推，只要博弈方1采用前述触发策略，那么

18、2的最优选择就始终是H。当然，如果1偏离H，2也必须用L来报复。因此，博弈方2对博弈方1触发策略的完整反应策略是同样的触发策略。这就证明了双方都采用上述触发策略是一个纳什均衡。重复博弈的子博弈还是无限次重复博弈。其实，在该囚徒困境博弈构成的无限次重复博弈中，子博弈完美纳什均衡路径不止上述一条，如两博弈方始终都选择原博弈的纳什均衡（L，L）就是其中之一。但后者的得益要差得多，因此双方合理的选择是触发策略而不是坚持原博弈的纳什均衡。无限次重复博弈的无名氏定理无限次重复博弈无名氏定理：设是一个完全信息的静态博弈。用记的纳什均衡的得益，用表示的任意可实现得益。如果对任意博弈方都成立，而足够接近1，那么无限次重复博弈中一定存在一个子博弈完美的纳什均衡，各博弈方的平均得益就是。弗里德曼（1971）这个定理称为无名氏定理是因为有限次重复博弈无名氏定理的关系。图4.12无限次重复古诺模型有效工资率例