第四章：重复博弈

1,第四章重复博弈,本章介绍基本博弈重复进行构成的重复博弈。虽然形式上是基本博弈的重复进行，但重复博弈中博弈方的行为和博弈结果却不一定是基本博弈的简单重复，因为博弈方对于博弈会重复进行的意识，会使他们对利益的判断发生变化，从而使他们在重复博弈过程中的行为选择受到影响。这意味着不能把重复博弈当作基本博弈的简单叠加，必须把整个重复博弈过程作为整体进行研究。,2,重复博弈,大多数重复博弈是静态博弈的重复，而重复博弈又是一个动态的过程，属于动态博弈的范畴。因此重复博弈与静态博弈和动态博弈都有关系。,3,本章分三节,4.1重复博弈引论4.2有限次重复博弈4.3无限次重复博弈,4,4.1重复博弈引论,4.1.1为何研究重复博弈两家企业在一个市场上的传长期竞争；两个企业遵守一份为期10年协议方面的契约；商业中的回头客等等。由于长期合作，通过报复、制裁、威胁等手段的相互约束行为，追求共同的目标，考虑当前利益兼顾将来的利益。长期关系可以理解为博弈阶段较多，时间跨度较大的一般动态博弈。诚信、信任4.1.2基本概念,5,4.1.1为何研究重复博弈,经济中的长期关系人们的预见性未来利益对当前行为的制约长期合同、回头客、常客和一次性买卖的区别有无确定的结束时间长期关系与短期关系前面讨论的都是社会经济活动中短期一次性合作或竞争关系，但社会经济活动中除了短期一次性关系以外，还存在许多长期反复的合作和竞争关系。如商业活动中的回头客。长期关系与短期关系之间的差别不只是时间跨度长短的数量问题，而是有重要性质的差别。在长期关系中，人们在考虑当前利益的同时，需要兼顾未来利益。,6,“冲突”何以能产生合作，就是因为重复博弈的存在,瑞典皇家科学院2005年10月10日在斯德哥尔摩宣布，将2005年的诺贝尔经济学奖授予以色列希伯莱大学的罗伯特奥曼（RobertJ.Aumann）和美国马里兰大学的托马斯谢林（ThomasC.Schelling），以表彰他们“通过博弈论分析，促进了人们对冲突和合作的理解”。为此，他们获得1000万瑞典克朗（约合130万美元）的奖金。从约翰纳什开始，在博弈论这座金矿中淘到诺贝尔经济学奖的有数十位之多，与博弈论领域相关的基础研究，据说已经是第五次折桂了。瑞典皇家科学院在授奖时说，罗伯特奥曼第一次对重复博弈进行了全面正式分析。他们认为，“重复博弈的理论促进了我们对合作先决条件的理解，阐明了包括商业协会、犯罪组织在内的许多机构进行磋商和国际贸易协定的理由”。,7,4.1.2基本概念,有限次重复博弈：给定一个基本博弈G（可以是静态博弈，也可以是动态博弈），重复进行T次G，并且在每次重复G之前各博弈方都能观察到以前博弈的结果，这样的博弈过程称为“G的T次重复博弈”，记为G(T)。而G则称为G(T)的“原博弈”。G(T)中的每次重复称为G(T)的一个“阶段”。无限次重复博弈：一个基本博弈G一直重复博弈下去的博弈，记为G()策略：博弈方在每个阶段针对每种情况如何行为的计划子博弈：从某个阶段（不包括第一阶段）开始，包括此后所有的重复博弈部分均衡路径：由每个阶段博弈方的行为组合串联而成,8,2.重复博弈的策略、子博弈和均衡路径(1)重复博弈的策略重复博弈中每个博弈方在每个阶段都必须进行策略选择，因此博弈方的一个策略就是在每次重复时,针对其前面阶段所有可能的情况如何进行行动的计划。(2)重复博弈的子博弈重复博弈的子博弈就是从某个阶段（除第一阶段以外）开始，包括此后所有阶段的重复博弈部分。重复博弈的子博弈要么仍然是重复博弈，只是重复的次数较少，要么就是原博弈。(3)重复博弈的均衡路径重复博弈的路径是由每个阶段博弈方的行动组合串联而成的。而且对应前一阶段的每一种结果，下一阶段都有原博弈全部策略组合数那么多种可能的结果，如原博弈有m种策略组合，那么重复两次就有m2条博弈路径，重复T次就有mT条博弈路径，因此在重博弈中，博弈方在重复博弈中的策略空间要远远大于在每个阶段博弈中的策略空间，重复博弈的路径数往往是很大的，常常可以产生一些意想不到的均衡路径。,9,3重复博弈的得益方法之一是计算重复博弈的”总得益”,即博弈方各次重复得益的总和；另一种方法是计算各阶段的“平均得益”，即总得益除以重复次数。,10,重复博弈的总得益,11,重复博弈的平均得益,随机停止和贴现率,12,4.2有限次重复博弈,4.2.1两人零和博弈的有限次重复博弈4.2.2唯一纯策略纳什均衡博弈的有限次重复博弈4.2.3多个纯策略纳什均衡博弈的有限次重复博弈4.2.4有限次重复博弈的民间定理,13,4.2.1两人零和博弈的有限次重复博弈,零和博弈是严格竞争的，重复博弈并不改变这一点。以零和博弈为原博弈的有限次重复博弈与猜硬币博弈的有限次重复博弈一样，博弈方的正确策略是重复一次性博弈中的纳什均衡策略。,以猜硬币博弈为原博弈的有限次重复博弈中，每个博弈方的惟一正确的策略是在每次重复时都采用一次性博弈的纳什均衡策略，即各以0.5的概率随机选正面和反面的混合策略。重复博弈的结果是双方的平均期望得益和期望总得益都为0。,14,4.2.2两人零和博弈的无限次重复博弈,两人零和博弈无限次重复的所有阶段都不可能发生合作，博弈方会一直重复原博弈的混合策略纳什均衡,两人零和博弈的无限次重复与有限次重复博弈的结果并不会有什么不同：因为重复次数的无限增加也不能改变原博弈中博弈方之间在利益上的对立关系，也不会创造出潜在的合作利益，因此在这种博弈的无限次重复博弈中，博弈方仍然是每次重复都根据当时的最大利益行为，采用原博弈的混合策略纳什均衡。,两人零和博弈无限次重复博弈会不会发生合作？,15,4.2.2唯一纯策略纳什均衡博弈的有限次重复博弈,定理：设原博弈G有唯一的纯策略纳什均衡,则对任意整数T，重复博弈G(T)有唯一的子博弈完美纳什均衡，即各博弈方每个阶段都采用G的纳什均衡策略。各博弈方在G(T)中的总得益为在G中得益的T倍，平均得益的与原博弈G中的得益。,16,有限次重复削价竞争博弈,有唯一纯策略纳什均衡（70，70）有限次重复的结果仍然是（低价，低价）,17,4.4多个纯策略纳什均衡的重复博弈,原博弈存在两个纯策略纳什均衡（M,M），（L,L）以及混合策略纳什均衡。,18,4.4.1多个纯策略纳什均衡的有限次重复博弈,重复2次,触发策略：两博弈方先试探合作，一旦发现对方不合作则也用不合作报复博弈方1：第一次选H；如第一次结果为(H,H)，则第二次选M，否则选L。博弈方2：同博弈方1,19,如果重复n次，结论相似。采用触发策略实现比较好的结果，子博弈完美纳什均衡路径为：除了最后一次外，每次都采用（H，H），最后一次采用（M，M）。当重复次数较多时，平均得益接近于一次性博弈中（H，H）的得益（5，5）。,20,在上面的分析中，我们发现触发策略重复是一种非常重要的机制，采用这种策略就意味着对将来策略选择所作的可信的威胁或承诺可以影响到当前阶段的行动选择。但如果仔细分析，不难发现上述触发策略也可能存在值得推敲的问题，就是报复机制的可信性。惩罚别人也惩罚自己！,关于“触发策略”的讨论,21,其实，并不是每个重复博弈的触发策略都有可信性问题，触发策略在很多情况下是非常可信的。,可以证明，双方的上述触发策略组合（H，H），（M，M）构成该重复博弈的一个子博弈精炼纳什均衡，而且双方的触发策略中的报复都是可信的。,22,在博弈理论中，有两个著名的策略：1.触发策略（Triggerstrategies）。2.“一报还一报”策略：也就是若你采取不合作策略，我也采取不合作策略，但是如果你采取了合作策略，我也采取合作策略。这叫，或者称为“针锋相对”，英文叫Tit-for-Tat。,23,一报还一报的策略是这样的：第一次博弈采用合作的策略，以后每一步都跟随对方上一步的策略，你上一次合作，我这一次就合作，你上一次不合作，我这一次就不合作。也就是说，一报还一报的策略实行了“胡萝卜加大棒”的原则。它永远不先背叛对方，从这个意义上来说它是“善意的”。它会在下一轮中对对手的前一次合作给予回报,哪怕以前这个对手曾经背叛过它，从这个意义上来说它是“宽容的”。但它会采取背叛的行动来惩罚对手前一次的背叛，从这个意义上来说它又是“可激怒的”。而且，它的策略极为简单，对手一望便知其用意何在，从这个意义来说它又是“简单明了的”。“一报还一报”策略的优越性向我们充分展示了一个纯粹自利的人何以会选择善，只因为合作是自我利益最大化的一种必要手段。,24,美国密执安大学的罗伯特埃克斯罗德(RobertAxerold)曾经主持过一次计算机比赛，看谁写出来的程序能够赢。参加者有政治学家、数学家、经济学家、社会学家，他们都详细研究过囚徒困境。获胜者是加拿大多伦多大学的罗伯布（AnatolRapoport）写的“一报还一报”(Tit-for-Tat)策略。,25,两市场博弈的重复博弈（重复一次）,纯策略纳什均衡：(A,B)和(A,B)，对应得益为（1，4）和（4，1）混合策略纳什均衡：分别以1/2的概率随机在A或B中选择，双方得益为1/4（3410）2,两市场博弈的重复博弈,26,两市场博弈的重复博弈（重复两次）,(A,B)+(A,B)OR(B,A)+(B,A)(1,4)OR(4,1)连续两次采用混合策略(2,2)(A,B)+(B,A)OR(B,A)+(A,B)(2.5,2.5)轮换策略一次纯策略+一次混合策略(1.5,3)OR(3,1.5),27,重复博弈不同策略、均衡及一次性博弈得益比较,不同策略组合、均衡得益图示,28,重复博弈不同策略、均衡及一次性博弈得益比较,不同策略组合、均衡得益图示,轮换策略结果比较好，但与最佳结果（A，A）还有一定差距。本博弈不能实现最佳结果原因，是因为这个两次重复博弈没有运用触发策略的条件或者说机会。,29,两市场博弈的重复博弈（重复三次）,如果两市场重复3次，则博弈结果会得到进一步改善，关键是在两次重复博弈时没有条件运用触发策略，在3次以上的重复博弈中有了运用的条件。,厂商1：第一阶段选A；如果第一阶段结果是（A，A），则第二阶段选A，如果第一阶段结果是（A，B），则第二阶段选B；第三阶段无条件选B。厂商2：第一阶段选A，第二阶段无条件选B，如果第一阶段结果是（A，A），则第三阶段选A；如果第一阶段结果是（B，A），则第三阶段选B。,30,两市场博弈的重复博弈（重复三次）,其中第二阶段、第三阶段本身就是纳什均衡，因此不会有哪一方愿单独偏离。第一阶段的策略组合虽然并不是原博弈的纳什均衡，但由于有后面阶段利益的制约作用，但它作为3次重复博弈的第一次博弈的策略组合具有稳定性。,该子博弈完美纳什均衡的平均得益为（314）/32.67，大于其他任何子博弈完美纳什均衡的平均得益，因此从总体效率的意义上，这个带触发策略的子博弈完美纳什均衡是众多子博弈完美纳什均衡中效率最高的。,31,两市场博弈的重复博弈（重复101次）,厂商1触发策略：前99次选A；但从其中的第二次开始，一旦发现哪次的结果不是（A，A），则改为B并坚持到底，最后两次重复与3次重复博弈的后两次重复的策略相同。厂商2触发策略：同厂商1,每阶段的平均得益：（99*3+1+4）/101=2.99非常接近效率最高的得益（3,3）,32,由上面两个重复博弈例子的分析可以看出，当原博弈有多个纯策略纳什均衡时，有限次重复博弈存在许多效率差异很大的子博弈完美纳什均衡，并且可以通过设计包含报复机制的触发策略，来实现效率较高的均衡，得到一次性博弈中无法实现的潜在合作利益。而提高效率和发掘潜在利益可能性和程度，则主要决定于运用特定策略的条件，采用的策略，以及重复博弈的次数。由此，我们得到如下的“无名氏定理”（FolkTheorem）。在阐述“无名氏定理”之前，我们再介绍几个关于得益的概念。,有限重复博弈的“无名氏定理”（FolkTheorem）,33,设wi为博弈方i在一次性博弈中最差的均衡得益，用w记各博弈方的wi构成的得益数组。无论其他博弈方行为如何，一博弈方在某个博弈中自己采取某种特定的策略，能够最低限度保证得到的得益称为“保留得益”（ReservationPayoff）或“个体理性得益”（IndividualRationalityPayoff）。博弈中所有纯策略组合得益的凸组合（ConvexCombination）即纯策略得益的加权平均（权重数非负且总和为1）数组称为“可实现得益”（FeasiblePayoff）。,34,有了这几个得益概念，我们就可以给出次数较多的有限次重复博弈的“无名氏定理”：有限重复博弈“无名氏定理”：设原博弈G为一个完全信息的静态博弈，原博弈G的一次性博弈均衡得益数组优于w，那么在该博弈的多次重复中，所有不小于个体理性得益的可实现得益，都至少有一个子博弈完美纳什均衡的极限的平均得益来实现他们。,35,下面以两市场博弈的重复博弈为例来说明该定理。,在两市场博弈中，两个博弈方最差的均衡得益都是1，因此构成得益数组w=（1，1）；只要采取A策略，两个博弈方都至少得到1以上的得益，因此1就是这两个博弈方的个体理性得益；该博弈中的可实现得益就是下图中由（0，0），（1，4）、（3，3）和（4，1）四点连成边界线围起来的整个阴影部分面积中点坐标。很显然，该博弈的一次性博弈中显然存在均衡得益数组优于w，满足民间定理的条件，因此所有不小于个体理性得益的可实现得益，即图中（1，1）、（1，4）、（3，3）和（4，1）四点连成边界线所围阴影部分面积中点对应的双方得益，都有子博弈完美纳什均衡或这种均衡的极限来实现它。,36,4.2.4有限次重复博弈的民间定理,个体理性得益：不管其它博弈方的行为如何，一博弈方在某个博弈中只要自己采取某种特定的策略，最低限度保证能获得的得益可实现得益：博弈中所有纯策略组合得益的加权平均数组定理：设原博弈的一次性博弈有均衡得益数组优于w，那么在该博弈的多次重复中所有不小于个体理性得益的可实现得益，都至少有一个子博弈完美纳什均衡的极限的平均得益来实现它们,37,例如（4，1）和（1，4）可用每次采用原博弈同一个纳什均衡的子博弈完美纳什均衡来实现，这两点连线上的点可用原博弈两个纯策略纳什均衡的某种组合来实现，（3，3）可用重复次数不断增加前述触发策略构成的子博弈完美纳什均衡的极限实现等。,w,38,在所有可实现得益或优于w=（1，1）的可实现得益中，只有处于（1，4）与（3，3）和（3，3）与（4，1）两条连线上，包括这三点本身的可实现得益有较重要的意义，因为它们代表了帕累托效率意义上最有效率的均衡得益。无名氏定理的关键意义正是在于保证这些得益有一定次数重复博弈的子博弈完美纳什均衡的平均得益可以实现或逼近它们。,w,39,通过上面几个例子的分析我们发现，在一次性博弈和有限次重复中都无法实现的囚徒困境博弈中的合作关系，在无限次重复博弈的情况下是可以实现的。而且在有限次重复博弈中只有在原博弈有多个纯策略纳什均衡的情况下才会存在的合作，在无限重复博弈的情况下只要原博弈有一个纳什均衡就可能存在。于是，我们又得到无限次重复博弈的无名氏定理。,二、无限重复博弈的“无名氏定理”,40,两寡头削价竞争博弈,4.3.2唯一纯策略纳什均衡的无限次重复博弈,该博弈一次性博弈均衡是都采用低价，是囚徒困境型博弈,厂商1,厂商2,41,无限次重复两寡头削价博弈,“触发策略”（冷酷策略）：第一阶段采用H，如果前t-1阶段的结果都是(H,H)，则继续采用H，否则采用L。,如果博弈方2在第一阶段采用L，总得益现值为：,如果博弈方2第一阶段采用H，总得益现值为：,博弈方2会采用H策，否则会采用L策，即此时，博弈方2对博弈方1触发策略的最佳反应是第一阶段采用H。,42,由于从第二阶段开始的无限次重复博弈，与从第一阶段开始的无限次重复博弈是完全相同的，因此博弈方第二阶段的选择必然也是H，第三阶段也同样。依次类推。,因为重复博弈的子博弈就是重复一定次数之后的全部重复博弈过程，因此无限次重复博弈的子博弈还是无限次重复博弈。由于前述两博弈方的触发策略在所有子博弈中都仍然构成相同的触发策略，因此必然也是这些子博弈的纳什均衡，从而上述触发策略组合构成整个无限次重复博弈的子博弈完美纳什均衡，其均衡路径为两博弈方每阶段都选择H。,只要博弈方1采用前述触发策略、那么博弈方2的最优选择就始终是H。当然，如果博弈方1偏离H，博弈方2也必须用L来报复。因此博弈方2对博弈方1触发策略的完整反应策略是同样的触发策略。这就证明了双方都采取上述触发策略是一个纳什均衡。,43,两寡头削价竞争无限次重复博弈的民间定理,44,在上述两寡头头削价竞争模型的无限次重复博弈中，纳什均衡的得益数组为(1，1)，所有可实现得益构成图412中由(1，1)、(0，5)、(4，4)利(5，0)四点连成边界线围成的整个阴影部分面积中点的坐标。无限次重复博弈的民间定理应用到该博弈中意味着，由图412中竖线条阴影部分中点的坐标对应的双方数组，在该博弈的无限次重复博弈中，都有无限次重复博弈的子博弈完美纳什均衡的平均得益来实现它们。,45,在无限次重复古诺模型中，当贴现率满足一定条件时，两厂商采用下列触发策略构成一个子博弈完美纳什均衡：,厂商2不突破突破,在第一阶段生产垄断产量的一半1.5；在第t阶段，如果前t-1阶段结果都是(1.5,1.5)，则继续生产1.5，否则生产古诺产量2。,应用：无限次重复古诺模型,在无限次重复古诺模型中，当贴现率满足一定条件时，两厂商采用下列触发策略构成一个子博弈完美纳什均衡：,46,设厂商1已采用该触发策略，若厂商2也采用该触发策略，则每期得益4.5，无限次重复博弈总得益的现值为：,厂商2不突破突破,如果厂商2偏离上述触发策略，则他在第一阶段所选产量应为给定厂商1产量为1.5时，自己的最大利润产量，即满足：,解得，此时利润为5.0625，高于触发策略第一阶段得益4.5。,47,结论:在时，双方都采用上述触发策略是一条子博弈完美纳什均衡路径；当时，偏离是厂商2对厂商1的触发策略的最佳反应。为什么贴现系数的大小会得出两种不同情况？后一种情况说明未来得益折算成现在值的贴现系数太小，即博弈方太不看重未来利益时，他就会只顾为自己捞取更多的眼前利益，不会为长期利益打算，也不会害怕对方在未来阶段的报复，在这种情况下无限次重复博弈也不能提高原博弈的效率。前一种情况则刚好相反，由于贴现系数较大，因此对厂商2来说未来利益是足够重要的，他不会为了一次性的眼前利益而激怒对方，导致自己的未来利益、长期利益受到损失。,48,现实生活中，市场上的寡头企业往往有许多个，而不仅有两个：假定是有n个企业时，要n个企业都坚持触发战略，则贴现因子要满足：当时，。这说明当有许多企业时，除非未来的利益相当大，才会使所有企业放弃短期利益去获取长远利益。但贴现因子等于1在现实中几乎是可能的。故许多企业就会选择只顾眼前不顾长远的背叛行为。这就意味着，企业越多，合作越困难，这与现实状况是非常吻合的。,49,参与人不固定的重复博弈,重复博弈时，厂商不敢以劣货欺人在经济学或管理学中使用“信誉”这样一个不好解释的概念，但在博弈论中却在某些假设之下“逻辑地”证明了。所谓“信誉”，无非对自己行为的预期为什么买于“坐贾”而非“行商”？为什么车站旁边的劣质品那么多？企业存在的一个原因是创造一个“长期参与人”，因其考虑长期利益而遵章守纪、态度积极,50,厂商策略：第一次生产高质量产品，继续生产高质量产品。如果上一次生产了低质量产品，之后永远生产低质量产品。消费者策略：第一个消费者选择购买，只要厂商不曾生产过低质量产品，随后的消费者继续购买；如果厂商曾经生产过低质量产品，之后的消费者不再购买。,厂商策略是最优的：,51,厂商不生产低质量产品消费者：预期是高质量时，才购买。消费者预期不曾生产过低质量产品的厂商将继续生产高质量产品，所以购买是最优的；如果厂商曾经生产过低质量产品，消费者预期厂商将继续生产低质量产品，所以不购买是最优的。,52,4.3.4有效工