《重复博弈博弈论》PPT课件.ppt

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