重复博弈博弈论课件.ppt

1、重 复 博 弈,重复博弈,动态博弈的类型 序贯博弈sequential game 每一个阶段的博弈结构是不同的，即从后一个决策结开始的子博弈不同于从前一个决策结开始的子博弈。或者说，同样结构的博弈只出现一次。 重复博弈repeated game 是指同样结构的博弈重复多次，其中的每次博弈称为“阶段博弈”。如“囚徒困境”中小偷每次作案后判刑释放后又作案。 分为有限次重复博弈与无限次重复博弈,重 复 博 弈,人们之间的长期关系与短期关系之间有重要 的性质差别,人们在对待与其有长期关系的 人与对待那些以后不再交往的人可能会有非 常不同的行为。短期难以形成某种默契或合作关系，而长期可以通过报复、制裁的

2、威胁来相互约束各方的行动。,有限次重复博弈,定义 给定一个博弈G，重复进行T次G，并且在每次重复之前各参与人都能观察到以前博弈的结果，这样的博弈过程称为G的一个“T次重复博弈”，记为G(T)。而G则称为G(T)的原博弈。 G(T)中的每次重复称为G(T)的一个阶段。,几点说明,子博弈 动态博弈中的子博弈及SPNE在重复博弈中适用 策略 路径 重复博弈使博弈结果有了更多的可能，如果原博弈有n条路径，重复两次博弈则有n2条路径，重复T次就有nT条路径 支付,特别说明：重复博弈中的支付,在有限次博弈中，每一次的博弈都有一组结果即支付组合，因此重复博弈中各参与人的支付应该是他们每阶段支付相加的“总支付

3、”（无限次重复支付的计算要更复杂一些） 用每阶段的平均支付来进行比较各阶段重复博弈和各种均衡效率 如果博弈次数少，重复时间较近，无需引用贴现系数 如果博弈次数较多，重复时间较长，可以引进贴现系数，未来支付折算成当前支付,有 限 重 复 博 弈,有限重复博弈简单地说就是阶段博弈实施有限次(T次)。如我们考虑T2。考虑下列博弈：,有 限 重 复 博 弈,它有一个Nash 均衡(U,L),假设博弈进行两次, 两阶段重复博弈中每个参与人的得益相当于 各个阶段得益之和(或者平均数),考虑到贴现 因子,再一次借助于逆向归纳法, 第二阶段 唯一的Nash均衡为(U,L),得益向量为(1,1),所 得的贴现值

4、为(,),有 限 重 复 博 弈,由此在第一阶段相当于 博弈:,该博弈有唯一的Nash均衡(U,L),因此我们得到唯 一的子博弈完美Nash均衡:(U,L),(U,L),有限次重复猜硬币博弈,猜硬币博弈是一个零和博弈，重复零和博弈不会创造出任何新的利益（因为每个阶段博弈总是一方赢一方输，总支付还是为零和）。 因此双方合作的可能性根本不存在，即使双方都知道还要进行重复许多次这样的博弈也不会改变他们在当前的阶段博弈中的行为方式，即他们不可能变得合作和顾及对方的利益。,有限次重复猜硬币博弈,所以，以猜硬币博弈作为原博弈的重复博弈中，每个博弈方唯一正确的选择是在每次重复时都采用一次性博弈中所采用的NE

5、，即以0.5的概率随机选择正面和反面的混合策略，双方每次重复的期望值和期望总支付为零。 注意的是，所有以零和博弈为原博弈的重复博弈，与上述问题都有相同的结论，即都采用一次性博弈中的纳什均衡策略。,有限次重复囚徒困境的博弈,如果Policeman给这两个囚徒两次机会，即重复两次原博弈，其结果（即他俩关押的年限）会是怎样？ 两博弈先进行第一次博弈后，双方都看到最后结果，然后再进行第二次博弈。 用逆推归纳法求解 先求第二阶段博弈的解仍是原博弈的解（坦白，坦白）支付组合为（-5，-5） 再回到第一阶段。由于双方都知道后一阶段的结果即（-5，-5），因此此时双方都知道整个两次重复博弈的结果，双方的最终支

6、付肯定就是在本阶段的双方支付基础上各加上-5，博弈结果仍是（坦白，坦白）支付组合（-10，-10）,有限次重复囚徒困境的博弈,第一阶段,不坦白 坦白,不坦白 坦白,囚犯2,囚犯1,-6，-6 -13，-5,-5，-13 -10，-10,第二阶段,两次重复囚徒困境的等价博弈,有限次重复囚徒困境的博弈,从结果上看，两次重复囚徒的困境相当于独立地进行两次一次性的囚徒的困境博弈，然后把两个独立博弈的支付相加。 这个结果具有一般意义。 在有限次重复博弈中，如果原博弈存在唯一的纯策略NE，则有限次重复博弈的唯一的均衡解就是各博弈方在每阶段中都采用原博弈的NE。 因为每个阶段NE都是SPNE，即不存在不可信

7、的威胁和许诺，因此重复博弈的解也是SPNE。,定理,设原博弈G有唯一的纯策略NE，则对任意正整数T，重复博弈G(T)有唯一的SPNE，即各博弈方每个阶段采用原博弈G的纳什均衡策略。各博弈方在G(T)中的总支付为在原博弈G中支付的T倍，平均每阶段支付等于原博弈G中的支付。 注意1 可以用逆推归纳法证明该定理。 注意2 该定理说明了，所有具有唯一NE的静态博弈构成的重复博弈，它们和零和博弈一样，都是原博弈的一次性博弈的简单重复和支付相加。,有限次重复削价竞争博弈,高价 低价,高价 低价,寡头2,寡头1,类似的，有限次的古诺特重复博弈问题也有相同的结论。,重复囚徒困境悖论,有限次重复博弈并不能摆脱囚

8、徒的困境的低效率均衡。 这与人们的直觉经验并不完全一致，因为根据这种结论寡头之间的价格战应该是随时都在发生的，但现实中的寡头的价格战却没有这么普遍。 此外，在重复囚徒的困境博弈的大量实验研究中，重复次数较大时的实验结果通常也与上述理论结论，包含合作的情况比较普遍。,设有如下市场进入博弈,连锁店悖论(Selten 1978),连锁店悖论(Selten),假定同样的市场有20个(可以理解为在位者有20个联锁店), 进入者每次进人一个市场,博弈就成了20次的重复博弈。 两个理性的博弈方之间得子博弈完美均衡的结果为进入者在每一市场选择进入，而在位者总是选择默许。 但现实中的类似问题和理论结论不符。 从

9、一个市场看，在位者的最优选择是默许，但因为有20个市场要保护，为了防止进入者进入其他19个市场，应该选择斗争，通过示范效应从而独享19个市场的利益。总体上合算。,有限次的囚徒困境博弈和连锁店悖论问题与之前的蜈蚣博弈类似，问题的症结在于在较多阶段的动态博弈中逆向归纳法的适用性。,有两个NE博弈的重复博弈,如果构成重复博弈的原博弈有多于一个的纯策略NE，其结果如何？ 这时重复博弈就可能有多个SPNE路径，重复次数越多，这种路径也越多，并且会出现在原博弈中并非均衡的策略组合在重复博弈中却构成其SPNE的一个部分情况。 导致这个结果的原因是，当阶段博弈（原博弈）有多个NE时，参与人可以使用不同的NE惩

10、罚第一阶段的不合作行为或奖励第一阶段的合作行为，而这一点在阶段博弈只有唯一NE时办不到。,三 价 博 弈 的 重 复 博 弈,其中H表示高价，M表示中价 L表示低价。该博弈有两个 Nash均衡： (M,M) 和(L,L)。 策略组合 ： ( H，H) 对双方 最有利, 但不是Nash 均衡。 两次重复博弈情况会有变化 吗？,三 价 博 弈 的 重 复 博 弈,两次重复博弈共有99=81 种纯策略组合(路径),这时,子 博弈完美有多个,但重要的 是:存在在第一阶段取(H,H) 的子博弈完美纳什均衡路径。,触发策略（trigger strategy）,首次试探合作，一旦发觉对方不合作则也用不合作相

11、报复的策略，称作触发策略 触发策略是一个完整的计划，假定博弈方一旦设定了这样的策略就会坚持到底，因此其中的报复是可信的，因此所构成的威胁都是子博弈完美的。 触发策略是重复博弈中实现合作和提高均衡效率的关键机制，是重复博弈分析的重要“构件”之一。 有的地方也称作冷酷战略（grim strategy）,三 价 博 弈 的 重 复 博 弈,双方的策略是: 博弈方1:第一次选H,如果第一次结果为(H,H),则第二次选择M;如果第一次结果为其它任何组合,则第二次选L。(触发策略) 博弈方2的策略与博弈方1相同。 在双方的上述策略组合下,两次重复博弈的路径一定为第一阶段(H,H),第二阶段(M,M)。 如

12、果上述博弈是进行n次,仍可采用“触发策略”实现比较好的结果。,博弈方1:第一次选H,如果第一次结果为(H,H),则第二次选择M;如果第一次结果为其它任何组合,则第二次选L。(触发策略) 博弈方2的策略与博弈方1相同。,两次重复的等价一次性博弈,三价博弈重复n次，结论类似。 运用触发策略，子博弈完美纳什均衡的路径为，除了最后一次重复以外，每次都采用（H,H），最后一次重复采用原博弈的纳什均衡（M,M）,当重复次数较多时，平均支付接近于一次性博弈的支付（5，5）,触发策略可信性问题,触发策略在重复博弈的分析中有非常重要的作用,但上例中的触发策略也存在可信性的问题,因为参与人在报复对方的偏离时,自己

13、也会受到损失,故也可能是未偏离的一方不计前嫌,在第二阶段与对方共同采用M,这对他自己也是有利的。,触发策略可信性问题,实际上,触发策略中的报复机制的可信性是一个很复杂的问题,会受到相互预期等很多复杂因素的影响。 例如，未偏离的一方并不想报复偏离的一方，而偏离的一方却因为害怕报复而采用L,结果心慈手软的未偏离一方再次遭受损失，这种可能性的存在会使得报复机制实施的可能性增加。 此外，考虑策略的制定者和执行者分离的情况，执行者会严格执行决策者指令的情况等等。,触发策略可信性问题,触发策略可信的情况,博弈方1:第一次选H,如果第一次结果为(H,H),则第二次选择M;否则采用P 博弈方2:第一次选H,如

14、果第一次结果为(H,H),则第二次选择M;否则采用Q,H M L P Q,H M L P Q,博弈方1,博弈方2,两市场博弈的重复博弈,如两个厂商同时面临市场机会A和B,得益如下表: 表中得益意味着市场A较大但开发程度很低,市场B较小 但开发程度高,这个博弈的两个纯策略Nash均衡和一个混合策略的Nash 均衡的结果都不很理想。,两市场博弈的重复博弈,如果该博弈重复两次双方会采用什么策略?这时有多种子博弈完美的均衡路径,但双方均采用“轮流策略”是比较好的。,两市场博弈及其重复博弈各均衡的平均得益,两市场博弈的重复博弈,考虑两市场博弈重复三次，一些有条件策略（几次重复中各次选择的完整计划）可以构

15、成子博弈完美纳什均衡，并且这些策略可能包含某些重复中策略组合不是纳什均衡。如策略如下： 厂商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,

16、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,当原博弈有多个纯战略纳什均衡时，有限次重复博弈有许多效率差异很大的子博弈完美纳什均衡，并且可以通过设计特定的策略，主要是

17、包含报复机制的触发策略，实现效率较高的均衡，充分发掘一次性博弈中无法实现的潜在合作利益。,有限次重复博弈的无名氏(Folk)定理,用wi记博奕方i在一次性博弈中最差的均衡得益, w=(w1,w2,wn), 不管其他方的行为如何,一个博弈方在某个博弈中只要采取某种特定的策略,最低限度保证能获得的得益称为“个体理性得益”或“保留得益” 博弈中所有纯策略组合的的加权平均(凸组合)数组称为“可实现得益”,有限次重复博弈的无名氏(Folk)定理,有限次重复博弈的无名氏定理:设原博弈的一次性博弈有均衡得益组合优于w,那么在该博弈的多次重复中,所有不小于个体理性得益的可实现得益,都至少有一个子博弈完美的Na

18、sh均衡的极限的平均得益来实现他们。,两市场博弈有限次重复的无名氏定理,帕累托前沿,无 限 次 重 复 博 弈,前面已经看到: 在有限次重复博弈中,如果G有多重Nash均衡可能存在这样子 博弈完美: 对 任意的tT,阶段博弈的结局不是G的Nash均 衡,而对无限重复博弈来说,即使阶段博弈G只 有唯一的Nash均衡,也可能存在类似的子博弈 完美。,无 限 次 重 复 博 弈,无限次重复博弈和有限次重复博弈的区别 对有限次重复博弈的分析可知，存在最后一次重复正是破坏重复博弈中博弈方利益和行为的相互制约关系，使重复博弈无法实现更高效率均衡的关键问题。 无限次重复博弈不能忽视不同时间得益的价值差异和贴

19、现问题，必须考虑后一期得益折算成前一期的贴现系数，对博弈方选择和博弈均衡的分析必须以平均得益或总得益的现在值为依据。,无 限 次 重 复 博 弈,如果囚徒的困境实施一次或有限次,则两个囚徒“总是坦白”构成了子博弈完美均衡，但如果 该博弈不断重复地实施，而每存在博弈前可以 看到以前各次所采取的行动 ,就可以认为是无 限重复博弈(这里的“无 限”可以理解为不固 定次数)。,无限次重复博弈,定义 给定一博弈G，无限次重复进行G博弈的过程称为G的无限次重复博弈，记为G(,)，其中是各博弈方支付（即未来所得利益）共同的贴现系数。并且，对任意的t，在进行第t阶段（第t次重复）博弈之前，所有博弈方都能看到前

20、t-1阶段博弈的结果。各博弈方在G(,)中的支付等于各阶段支付的现在值。,无限次重复博弈,给定贴现系数，若无限次重复博弈一路径的某博弈方各阶段支付为1，2，则该博弈方在该无限次重复博弈中的“总支付”为各阶段博弈中支付的“现值”： 总支付现值=1+ 2+ 23 + =t-1t -（1） 如果有一个常数，它是无限次重复博弈中每一轮次博弈的平均支付，则 总支付现值= + + 2 + = /(1- ) -（2） 让（1）、（2）两式相等，则每轮平均支付为 = (1- ) t-1t,= t-1 t,t =1,01,当 0，行动短视化，时间视野往往局限于本期、近期；,当 1，参与人有远见，他充分意识到他

21、现期的行动决策将通过其他参与人的反应影响到 他未来的收益，因而试图跨期协调其行动决策。,总支付现值=1+ 2+ 23 + ,无限次重复博弈,尽管阶段博弈中唯一的NE是不合作的(坦白， 坦白)，在有限次重复时，唯一的子博弈完美NE 还是在每个阶段都(坦白，坦白)，可是在无限次 重复（在可预见的将来不会结束）进行的情况下， 只要参与人有足够的耐心(即足够接近1)，每个 阶段的行动组合为(不坦白，不坦白) 将形成一条 子博弈完美NE的路径。,无限次重复囚徒困境博弈,无限次重复囚徒困境博弈,考虑参与人的冷酷（触发）战略：在第一阶段选择不坦白，且在之后的任意阶段t，如果之前的（t-1）阶段的结果是双方都

22、不坦白，则继续选择不坦白，否则从t阶段开始永远选择坦白。,不坦白 坦白,不坦白 坦白,囚犯2,囚犯1,第一阶段坦白：贴现值之和为,0 + (-8) + 2(-8) + 3(-8) + = -8 / (1 ),不坦白的现值 -1 / (1 - ),招认的现值 -8 / (1 ), 1/8,这说明，当且仅当 1/8，给定对方的触发策 略并且对方没有首先选择坦白，自己也不会首 先坦白。,无限次重复囚徒困境博弈,无限次重复囚徒困境博弈,假定1首先选择了坦白，并且按照冷酷策略一旦选择坦白将永远选择坦白，那么不论为多少，2有积极性坚持坦白以惩罚1 的不合作行为。 子博弈可以划分为两类：类型1，没有任何参与

23、人曾经坦白；类型2，至少有一个参与人曾经坦白 如果 1/8（参与人有足够的耐心），冷酷战略是无限次囚徒博弈的一个子博弈精炼纳什均衡。每一阶段的均衡结果是（不坦白，不坦白）,无限次重复囚徒困境博弈,如果博弈重复无穷次且每个人有足够的耐心，任何短期的机会主义行为的所得都是微不足道的，参与人有积极性为自己建立一个乐于合作的声誉，同时也有积极性惩罚对方的机会主义行为。,古诺产量:qc =(a-c)/3 ； 古诺利润:c=(a-c)2/9,垄断产量:qm/2=(a-c)/4; 垄断利润: m/2=(a-c)2/8,不合作,合作,无限次重复古诺模型,无限次重复古诺模型,首先选择生产qi=qm/2;继续选择

24、qi直到有一个企业选择qi不等于qm/2，然后永远选择qc 给定企业j坚持冷酷战略，如果企业i坚持合作，它每期的利润为 m/2=(a-c)2/8 ； 如果企业i选择短期最优产量qi=(a-c)3/8，当期的利润为d=(a-c)2 9/64(a-c)2 /8 ， 但随后阶段的利润流为c=(a-c)2 /9(a-c)2 /8,无限次重复古诺模型,如果下列条件满足，企业i没有积极性偏离合作均衡。 解上述条件的 结论：如果 默契合作是一个精炼均衡结果 说明如果未来得益折算成现值得系数太小，博弈方不太看重未来得益，他只顾及捞取更多的眼前利益；而如果贴现系数 较大，未来利益足够重要，则双方采用冷酷战略是均

25、衡的。,无限次重复古诺模型,当 时上述触发策略不是无限重复博弈的子博弈纳什均衡，但也不是说 两企业就只能在每阶段选择古诺产量，实现较差的低效率的纳什均衡得益。 虽然 较小时远期利益的重要性不足以维持 qm/2 低产量，但远期利益还是存在的，很可能会促使各厂商的产量维持在古诺产量和垄断产量之间， 设这个产量为q*,无限次重复古诺模型,在第一阶段生产q*；在第t阶段，如果t-1阶段的结果是（q*,q*），则继续生产q*，否则生产古诺产量qc 设*为每个企业产量都是q*时企业i的利润，d 为当另一个企业生产q*而企业i生产短期最优产量时企业i的利润，若下列条件满足，则企业i没有积极性偏离q*,无限次

26、重复古诺模型,不同的 能支持不同的q* 。当接近于9/17时q*接近于qm/2,当 接近于0时q* 接近于古诺产量；当0 9/17时qm/2q*qc,可行支付向量feasible payoffs（可实现支付）:支付数组x=(x1，x2 、xn)称为可行支付向量，如果它是阶段博弈G的纯策略支付的凸组合(concave combination)(即xi是阶段博弈中参与人i的纯策 略支付的加权平均值，权数非负且和为1)。,可行支付向量。以“囚徒困境”为例,一个可行支付向量对应重复博弈的一条路径。,无限次重复博弈无名氏定理,囚徒1的支付值,囚 徒 2 的 支 付 值,阴影面积中的任意一个坐标 点都是一

27、个可行支付向量。,无限次重复博弈无名氏定理,设G是一个完全信息的静态博弈。用(e1,en)记G的一个纳什均衡的支付，用(x1xn)表示G的任意可实现支付，如果xiei对任意player i 都成立, 而足够接近1，那么无限次重复博弈G(,)中一定存在一个子博弈完美的纳什均衡路径能实现各players平均支付为(x1xn) 。 在无限次重复博弈中，如果参与人有足够的耐心，那么，任何满足个人理性的可行的支付向量都可以通过一个特定的子博弈精炼均衡得到,囚徒1的支付值,囚 徒 2 的 支 付 值,阴影面积中的任意一个坐标 点都是一个可行支付向量。,Nash 威胁点Nash threat point (

28、e1,e2, ,en),保留支付reservation payoff:参与人i的保留支付 是指无论其它参与人如何行动，参与人i能够保 证得到的最大支付；它意味着即使其它参与人 试图给参与人i最大惩罚时，参与人i至少能保证 得到的支付。通常以i表示参与人i的保留支付。,阶段博弈囚徒困境中i= ei =-8；阶段博弈古诺模 型中i= 0，而ei=(a-c)2/9， iei。,个体理性支付 individually rational payoffs 即大于保留支付的支付。 这个概念的涵义是，如果要一个参与人在无限次重复博弈中有任何兴趣“合作”的话，他从“合作”中得到的支付不应该小于他的保留支付。,Fudenberg & Maskin 于1986年证明，无名氏定 理中的(e1,e2, ,en)可以用(1,2