重 复 博 弈 博弈论课件.ppt

重复博弈,重复博弈,动态博弈的类型序贯博弈sequentialgame每一个阶段的博弈结构是不同的，即从后一个决策结开始的子博弈不同于从前一个决策结开始的子博弈。或者说，同样结构的博弈只出现一次。重复博弈repeatedgame是指同样结构的博弈重复多次，其中的每次博弈称为“阶段博弈”。如“囚徒困境”中小偷每次作案后判刑释放后又作案。分为有限次重复博弈与无限次重复博弈,重复博弈,人们之间的长期关系与短期关系之间有重要的性质差别,人们在对待与其有长期关系的人与对待那些以后不再交往的人可能会有非常不同的行为。短期难以形成某种默契或合作关系，而长期可以通过报复、制裁的威胁来相互约束各方的行动。,有限次重复博弈,定义给定一个博弈G，重复进行T次G，并且在每次重复之前各参与人都能观察到以前博弈的结果，这样的博弈过程称为G的一个“T次重复博弈”，记为G(T)。而G则称为G(T)的原博弈。G(T)中的每次重复称为G(T)的一个阶段。,几点说明,子博弈动态博弈中的子博弈及SPNE在重复博弈中适用策略路径重复博弈使博弈结果有了更多的可能，如果原博弈有n条路径，重复两次博弈则有n2条路径，重复T次就有nT条路径支付,特别说明：重复博弈中的支付,在有限次博弈中，每一次的博弈都有一组结果即支付组合，因此重复博弈中各参与人的支付应该是他们每阶段支付相加的“总支付”（无限次重复支付的计算要更复杂一些）用每阶段的平均支付来进行比较各阶段重复博弈和各种均衡效率如果博弈次数少，重复时间较近，无需引用贴现系数如果博弈次数较多，重复时间较长，可以引进贴现系数，未来支付折算成当前支付,有限重复博弈,有限重复博弈简单地说就是阶段博弈实施有限次(T次)。如我们考虑T2。考虑下列博弈：,有限重复博弈,它有一个Nash均衡(U,L),假设博弈进行两次,两阶段重复博弈中每个参与人的得益相当于各个阶段得益之和(或者平均数),考虑到贴现因子,再一次借助于逆向归纳法,第二阶段唯一的Nash均衡为(U,L),得益向量为(1,1),所得的贴现值为(,),有限重复博弈,由此在第一阶段相当于博弈:,该博弈有唯一的Nash均衡(U,L),因此我们得到唯一的子博弈完美Nash均衡:(U,L),(U,L),有限次重复猜硬币博弈,猜硬币博弈是一个零和博弈，重复零和博弈不会创造出任何新的利益（因为每个阶段博弈总是一方赢一方输，总支付还是为零和）。因此双方合作的可能性根本不存在，即使双方都知道还要进行重复许多次这样的博弈也不会改变他们在当前的阶段博弈中的行为方式，即他们不可能变得合作和顾及对方的利益。,有限次重复猜硬币博弈,所以，以猜硬币博弈作为原博弈的重复博弈中，每个博弈方唯一正确的选择是在每次重复时都采用一次性博弈中所采用的NE，即以0.5的概率随机选择正面和反面的混合策略，双方每次重复的期望值和期望总支付为零。注意的是，所有以零和博弈为原博弈的重复博弈，与上述问题都有相同的结论，即都采用一次性博弈中的纳什均衡策略。,有限次重复囚徒困境的博弈,如果Policeman给这两个囚徒两次机会，即重复两次原博弈，其结果（即他俩关押的年限）会是怎样？两博弈先进行第一次博弈后，双方都看到最后结果，然后再进行第二次博弈。用逆推归纳法求解先求第二阶段博弈的解仍是原博弈的解（坦白，坦白）支付组合为（-5，-5）再回到第一阶段。由于双方都知道后一阶段的结果即（-5，-5），因此此时双方都知道整个两次重复博弈的结果，双方的最终支付肯定就是在本阶段的双方支付基础上各加上-5，博弈结果仍是（坦白，坦白）支付组合（-10，-10）,有限次重复囚徒困境的博弈,第一阶段,不坦白坦白,不坦白坦白,囚犯2,囚犯1,-6，-6-13，-5,-5，-13-10，-10,第二阶段,两次重复囚徒困境的等价博弈,有限次重复囚徒困境的博弈,从结果上看，两次重复囚徒的困境相当于独立地进行两次一次性的囚徒的困境博弈，然后把两个独立博弈的支付相加。这个结果具有一般意义。在有限次重复博弈中，如果原博弈存在唯一的纯策略NE，则有限次重复博弈的唯一的均衡解就是各博弈方在每阶段中都采用原博弈的NE。因为每个阶段NE都是SPNE，即不存在不可信的威胁和许诺，因此重复博弈的解也是SPNE。,定理,设原博弈G有唯一的纯策略NE，则对任意正整数T，重复博弈G(T)有唯一的SPNE，即各博弈方每个阶段采用原博弈G的纳什均衡策略。各博弈方在G(T)中的总支付为在原博弈G中支付的T倍，平均每阶段支付等于原博弈G中的支付。注意1可以用逆推归纳法证明该定理。注意2该定理说明了，所有具有唯一NE的静态博弈构成的重复博弈，它们和零和博弈一样，都是原博弈的一次性博弈的简单重复和支付相加。,有限次重复削价竞争博弈,高价低价,高价低价,寡头2,寡头1,类似的，有限次的古诺特重复博弈问题也有相同的结论。,重复囚徒困境悖论,有限次重复博弈并不能摆脱囚徒的困境的低效率均衡。这与人们的直觉经验并不完全一致，因为根据这种结论寡头之间的价格战应该是随时都在发生的，但现实中的寡头的价格战却没有这么普遍。此外，在重复囚徒的困境博弈的大量实验研究中，重复次数较大时的实验结果通常也与上述理论结论，包含合作的情况比较普遍。,设有如下市场进入博弈,连锁店悖论(Selten1978),连锁店悖论(Selten),假定同样的市场有20个(可以理解为在位者有20个联锁店),进入者每次进人一个市场,博弈就成了20次的重复博弈。两个理性的博弈方之间得子博弈完美均衡的结果为进入者在每一市场选择进入，而在位者总是选择默许。但现实中的类似问题和理论结论不符。从一个市场看，在位者的最优选择是默许，但因为有20个市场要保护，为了防止进入者进入其他19个市场，应该选择斗争，通过示范效应从而独享19个市场的利益。总体上合算。,有限次的囚徒困境博弈和连锁店悖论问题与之前的蜈蚣博弈类似，问题的症结在于在较多阶段的动态博弈中逆向归纳法的适用性。,有两个NE博弈的重复博弈,如果构成重复博弈的原博弈有多于一个的纯策略NE，其结果如何？这时重复博弈就可能有多个SPNE路径，重复次数越多，这种路径也越多，并且会出现在原博弈中并非均衡的策略组合在重复博弈中却构成其SPNE的一个部分情况。导致这个结果的原因是，当阶段博弈（原博弈）有多个NE时，参与人可以使用不同的NE惩罚第一阶段的不合作行为或奖励第一阶段的合作行为，而这一点在阶段博弈只有唯一NE时办不到。,三价博弈的重复博弈,其中H表示高价，M表示中价L表示低价。该博弈有两个Nash均衡：(M,M)和(L,L)。策略组合：(H，H)对双方最有利,但不是Nash均衡。两次重复博弈情况会有变化吗？,三价博弈的重复博弈,两次重复博弈共有99=81种纯策略组合(路径),这时,子博弈完美有多个,但重要的是:存在在第一阶段取(H,H)的子博弈完美纳什均衡路径。,触发策略（triggerstrategy）,首次试探合作，一旦发觉对方不合作则也用不合作相报复的策略，称作触发策略触发策略是一个完整的计划，假定博弈方一旦设定了这样的策略就会坚持到底，因此其中的报复是可信的，因此所构成的威胁都是子博弈完美的。触发策略是重复博弈中实现合作和提高均衡效率的关键机制，是重复博弈分析的重要“构件”之一。有的地方也称作冷酷战略（grimstrategy）,三价博弈的重复博弈,双方的策略是:博弈方1:第一次选H,如果第一次结果为(H,H),则第二次选择M;如果第一次结果为其它任何组合,则第二次选L。(触发策略)博弈方2的策略与博弈方1相同。在双方的上述策略组合下,两次重复博弈的路径一定为第一阶段(H,H),第二阶段(M,M)。如果上述博弈是进行n次,仍可采用“触发策略”实现比较好的结果。,博弈方1:第一次选H,如果第一次结果为(H,H),则第二次选择M;如果第一次结果为其它任何组合,则第二次选L。(触发策略)博弈方2的策略与博弈方1相同。,两次重复的等价一次性博弈,三价博弈重复n次，结论类似。运用触发策略，子博弈完美纳什均衡的路径为，除了最后一次重复以外，每次都采用（H,H），最后一次重复采用原博弈的纳什均衡（M,M）,当重复次数较多时，平均支付接近于一次性博弈的支付（5，5）,触发策略可信性问题,触发策略在重复博弈的分析中有非常重要的作用,但上例中的触发策略也存在可信性的问题,因为参与人在报复对方的偏离时,自己也会受到损失,故也可能是未偏离的一方不计前嫌,在第二阶段与对方共同采用M,这对他自己也是有利的。,触发策略可信性问题,实际上,触发策略中的报复机制的可信性是一个很复杂的问题,会受到相互预期等很多复杂因素的影响。例如，未偏离的一方并不想报复偏离的一方，而偏离的一方却因为害怕报复而采用L,结果心慈手软的未偏离一方再次遭受损失，这种可能性的存在会使得报复机制实施的可能性增加。此外，考虑策略的制定者和执行者分离的情况，执行者会严格执行决策者指令的情况等等。,触发策略可信性问题,触发策略可信的情况,博弈方1:第一次选H,如果第一次结果为(H,H),则第二次选择M;否则采用P博弈方2:第一次选H,如果第一次结果为(H,H),则第二次选择M;否则采用Q,HMLPQ,HMLPQ,博弈方1,博弈方2,两市场博弈的重复博弈,如两个厂商同时面临市场机会A和B,得益如下表:表中得益意味着市场A较大但开发程度很低,市场B较小但开发程度高,这个博弈的两个纯策略Nash均衡和一个混合策略的Nash均衡的结果都不很理想。,两市场博弈的重复博弈,如果该博弈重复两次双方会采用什么策略?这时有多种子博弈完美的均衡路径,但双方均采用“轮流策略”是比较好的。,两市场博弈及其重复博弈各均衡的平均得益,两市场博弈的重复博弈,考虑两市场博弈重复三次，一些有条件策略（几次重复中各次选择的完整计划）可以构成子博弈完美纳什均衡，并且这些策略可能包含某些重复中策略组合不是纳什均衡。如策略如下：厂商1：第一阶段选A；如果第一阶段结果是（A,A），则第二阶段选A；否则第二阶段选B；第三阶段无条件选B厂商2：第一阶段选A；第二阶段无条件选B；如果第一阶段结果是（A,A）则第三阶段选A；否则选B,上述战略的解释:对于厂商1：若厂商2在第一阶段未偏离，则在第二阶段奖励厂商2，此时支付为（1，4）；若厂商2在第一阶段偏离，则在第二阶段惩罚厂商2，此时支付为（0，0）因此，如果厂商2在第一阶段偏离，可以多的1(4-3)，但在第二个阶段少的4（4-0）则三阶段博弈的路径为（A,A）（A,B）（B,A）,它是一条子博弈完美纳什均衡路径。各方的平均得益为：(3+1+4)/3=2.67,进一步，把三次重复两市场博弈推广到任意有限次，例如101次，这是厂商1的策略是在前99次都选A，但一旦发现那次结果出现了(A,B)，则改选B坚持到底，最后两次与三次重复的后两次一样；厂商二的策略也是前99次都选A,但一旦发现那次结果出现了(B,A)，则改选B坚持到底，最后两次与三次重复的后两次一样这也是子博弈完美纳什均衡，双方平均得益为（99*3+1+4）/101=2.99,当原博弈有多个纯战略纳什均衡时，有限次重复博弈有许多效率差异很大的子博弈完美纳什均衡，并且可以通过设计特定的策略，主要是包含报复机制的触发策略，实现效率较高的均衡，充分发掘一次性博弈中无法实现的潜在合作利益。,有限次重复博弈的无名氏(Folk)定理,用wi记博奕方i在一次性博弈中最差的均衡得益,w=(w1,w2,wn),不管其他方的行为如何,一个博弈方在某个博弈中只要采取某种特定的策略,最低限度保证能获得的得益称为“个体理性得益”或“保留得益”博弈中所有纯策略组合的的加权平均(凸组合)数组称为“可实现得益”,有限次重复博弈的无名氏(Folk)定理,有限次重复博弈的无名氏定理:设原博弈的一次性博弈有均衡得益组合优于w,那么在该博弈的多次重复中,所有不小于个体理性得益的可实现得益,都至少有一个子博弈完美的Nash均衡的极限的平均得益来实现他们。,两市场博弈有限次重复的无名氏定理,帕累托前沿,无限次重复博弈,前面已经看到:在有限次重复博弈中,如果G有多重Nash均衡可能存在这样子博弈完美:对任意的t(a-c)2/8，但随后阶段的利润流为c=(a-c)2/9(a-c)2/8,无限次重复古诺模型,如果下列条件满足，企业i没有积极性偏离合作均衡。解上述条件的结论：如果默契合作是一个精炼均衡结果说明如果未来得益折算成现值得系数太小，博弈方不太看重未来得益，他只顾及捞取更多的眼前利益；而如果贴现系数较大，未来利益足够重要，则双方采用冷酷战略是均衡的。,无限次重复古诺模型,当时上述触发策略不是无限重复博弈的子博弈纳什均衡，但也不是说两企业就只能在每阶段选择古诺产量，实现较差的低效率的纳什均衡得益。虽然较小时远期利益的重要性不足以维持qm/2低产量，但远期利益还是存在的，很可能会促使各厂商的产量维持在古诺产量和垄断产量之间，设这个产量为q*,无限次重复古诺模型,在第一阶段生产q*；在第t阶段，如果t-1阶段的结果是（q*,q*），则继续生产q*，否则生产古诺产量qc设*为每个企业产量都是q*时企业i的利润，d为当另一个企业生产q*而企业i生产短期最优产量时企业i的利润，若下列条件满足，则企业i没有积极性偏离q*,无限次重复古诺模型,不同的能支持不同的q*。当接近于9/17时q*接近于qm/2,当接近于0时q*接近于古诺产量；当09/17时qm/2q*ei对任意playeri都成立,而足够接近1，那么无限次重复博弈G(,)中一定存在一个子博弈完美的纳什均衡路径能实现各players平均支付为(x1xn)。在无限次重复博弈中，如果参与人有足够的耐心，那么，任何满足个人理性的可行的支付向量都可以通过一个特定的子博弈精炼均衡得到,囚徒1的支付值,囚徒2的支付值,阴影面积中的任意一个坐标点都是一个可行支付向量。,Nash威胁点Nashthreatpoint(e1,e2,en),保留支付reservationpayoff:参与人i的保留支付是指无论其它参与人如何行动，参与人i能够保证得到的最大支付；它意味着即使其它参与人试图给参与人i最大惩罚时，参与人i至少能保证得到的支付。通常以i表示参与人i的保留支付。,阶段博弈囚徒困境中i=ei=-8；阶段博弈古诺模型中i=0，而ei=(a-c)2/9，iei。,个体理性支付individuallyrationalpayoffs即大于保留支付的支付。这个概念的涵义是，如果要一个参与人在无限次重复博弈中有任何兴趣“合作”的话，他从“合作”中得到的支付不应该小于他的保留支付。,Fudenberg&Maskin于1986年证明，无名氏定理中的(e1,e2,en)可以用(1,2,n)代替。,例如阶段博弈市场开发中(e1,e2)=(1,4)或(4,1)或(2,2)（混合策略NE），但(1,2)=(1，1)。,0,甲的AV,乙的AV,1,2,3,4,1,2,3,4,红阴影是民间定理，绿阴影是Fudenberg&Maskin证明的结论。就是说每一个个体理性支付向量都可以在完美均衡中达到。,古诺特重复博弈模型的可行支付集合,(c1c2),m,m,加大惩罚力度和提高合作水平,如果有更严厉的