重复博弈

第四章重复博弈本章主要内容：1重复博弈的概念；2作为一种特殊的动态博弈，有限次和无限次重复博弈的子博弈完美纳什均衡的求解方法；3无限次重复博弈古诺模型和效率工资模型。本章主要结论（民间定理）：由于参与者在重复博弈中具有了长期利益，可以通过在后面阶段中采取的报复策略使得威胁变得可信，从而摆脱静态博弈中“追求自身利益最大化”导致的囚徒困境，实现长期合作的结局。第一节几个概念重复博弈的概念有限次重复博弈的概念4.1.1重复博弈的概念1由简单的静态博弈（或动态博弈）的有限次（或无限次）重复进行构成的。2每一阶段博弈方、策略集合、规则和得益都相同。3包括：有限次重复博弈和无限次重复博弈4例子：多场决胜负的体育比赛（有限次）两寡头市场上两个厂商之间的竞争（无限次）商场与顾客交易定义：给定一个博弈G，重复进行T次G，并且在每次重复之前各博弈方都能观察到以前博弈的结果，称为G的一个“T次重复博弈”，记为G(T)。其中，G成为G(T)的原博弈。每次重复称为G(T)的一个阶段。4.1.2有限次重复博弈的概念4.1.2有限次重复博弈的概念几个概念：1子博弈：从某一阶段（不包括第一阶段）开始，包含以后所有阶段的原重复博弈的一部分。2策略：博弈方在每个阶段针对每种情况如何行动的计划（注：在每一阶段之前，博弈方是可以观察到以前博弈的结果的）。3路径：是每个阶段博弈结果（原博弈的一个策略组合）连接而成。对于具有n个策略组合的原博弈，重复T次的路径数为nT，重复博弈的求解即找出具有稳定性的均衡路径。4得益：不同于一般的动态博弈，重复博弈的得益为各个阶段得益的加总。考虑到时间的价值，需要引进“贴现系数”将未来的得益折算成当期得益的价值。4.1.2有限次重复博弈的概念第二节有限次重复博弈有限次重复的猜硬币博弈——原博弈为零和博弈有限次重复的囚徒困境博弈——原博弈有唯一的纯策略纳什均衡有多个纳什均衡的重复博弈的策略设计——触发策略有多个纳什均衡重复博弈的得益范围——民间定理在零和博弈中，双方不存在合作的可能性，因此在长期进行的重复博弈中，子博弈完美纳什均衡由各个阶段原博弈的纳什均衡构成（例，在猜硬币博弈中以0.5的概率选择正面或者反面，即采取混合策略）。实际上，所有以零和博弈为原博弈所构成的重复博弈与猜硬币博弈构成的重复博弈一样，各博弈方的正确策略就是在每次重复中都采用一次性博弈中的纳什均衡策略。4.2.1有限次重复的猜硬币博弈4.2.2有限次重复的囚徒困境博弈图4－1囚徒困境求解思路：对于有限次重复囚徒困境博弈，根据动态博弈的逆推归纳法可以求解。－5，－50，－8－8，0－1，－1坦白不坦白坦白不坦白4.2.2有限次重复的囚徒困境博弈以两阶段（以该博弈作为原博弈G重复两次）为例：分析最后一阶段，子博弈即为原博弈，唯一的均衡为（－5，－5）；分析第一阶段，将最后阶段的收益（－5）添加到第一阶段的矩阵中，即：此时，博弈的纳什均衡仍是（坦白，坦白）。坦白不坦白坦白不坦白－10，－10－5，－13－13，－5－6，－6结论：在有限次重复博弈G(T)中，如果原博弈G存在唯一的纯策略纳什均衡组合，则重复博弈的唯一的子博弈完美纳什均衡解为各博弈方在每阶段都采取的原博弈纳什均衡策略。含义：在原博弈具有唯一均衡的有限次重复博弈中，由于完全理性的博弈方具有“共同知识”的分析推理能力，因此在从最后阶段开始的逆推过程中，仍然无法摆脱囚徒困境。4.2.2有限次重复的囚徒困境博弈4.2.2有限次重复的囚徒困境博弈如果原博弈存在唯一的纯策略纳什均衡组合，则有限次重复博弈的唯一的均衡解即各博弈方在每阶段（即每次重复）中都采用原博弈的纳什均衡策略。由于在这样的双方策略下，均衡路径中的每个阶段都不存在不可信的威胁或许诺，因此这种均衡是子博弈完美纳什均衡。4.2.2有限次重复的囚徒困境博弈定理设原博弈G有唯一的纯策略纳什均衡，则对任意正整数T，重复博弈G（T）有唯一的子博弈完美的解，即各博弈方每个阶段都采用G的纳什均衡策略。各博弈方在G（T）中的总得益为在G中得益的T倍，平均每阶段得益等于原博弈G中的得益。4.2.3有两个纳什均衡的重复博弈例两个厂商1和2，同时面临两个市场机会A和B。假设每个厂商都只有能力选择一市场发展，即他们的可选择策略都是A或B，其得益矩阵如图所示。此博弈具有2个纯策略纳什均衡（1，4）、（4，1）和混合策略纳什均衡概率（0.5，0.5）。ABAB3，31，44，10，0图4－2两厂商差别市场博弈考虑三次重复博弈各策略组合子博弈纳什均衡路径：1.由原博弈的纳什均衡组合而成的路径，如采取轮换策略（在上述的协调博弈中，双方轮换采取纯纳什均衡策略，路径为(A,B)，(B,A)，(A,B)…..不考虑时间的价值（贴现系数），每阶段的平均得益为（4＋1）/2＝2.5，高于混合策略的得益2。2.触发策略，博弈方首先采取合作行为，如果发现对方没有进行合作，那么在后续阶段的博弈中采取不合作策略进行惩罚。4.2.3有两个纳什均衡的重复博弈在图4－2中，触发策略的设计为：（1）博弈方1的策略是第一阶段合作A，如果发现对方采取B不合作，则第二阶段采取不合作的B策略惩罚，否则第二阶段继续合作；第三阶段无条件采取B策略。（惩罚放在第二阶段）（2）博弈方2的策略是第一阶段合作A，第二阶段无条件选B，如果第一阶段结果是（A，A），则第三阶段A；如果第一阶段结果是（B，A），则第三阶段选B。（惩罚放在第三阶段）（3）是一子博弈完美纳什均衡，双方每阶段的平均得益为（3+1+4）/3=2.67,效率较高。（4）如果增加博弈的重复次数到101次。若采用的触发策略是：博弈方1在前99次中都选A，但从其中的第二次开始，一旦发现4.2.3有两个纳什均衡的重复博弈4.2.3有两个纳什均衡的重复博弈那一次的结果不是（A，A），则改为B并坚持到底，最后两次重复与三次重复博弈后两次重复的策略相同；博弈方2：前99次选A，但从其中的第二次开始，一旦发现那一次的结果不是（A，A），则改为B并坚持到底，最后两次重复与三次重复博弈后两次重复的策略相同；双方的每阶段的平均得益是（99×3+1+4）/101=2.99,非常接近效率最高的得益（3，3）策略设计分析：（1）在博弈方1和2中，在第一阶段都采取了合作行为A，并针对对方的不合作行为B，都设计了在后续2个阶段采取不合作B的相应惩罚措施；（2）如果对方在第一阶段中采取了合作行为，在后续阶段的策略设计中要保证博弈结局具有稳健性。因此，针对第一阶段的合作行为，后续阶段的策略设计是为了实现双方的行动协调，以保证实现纳什均衡（B,A）或（A,B）。4.2.3有两个纳什均衡的重复博弈结果分析：子博弈路径（A,A)，（A,B），（B,A）为子博弈纳什均衡。因为后续两阶段的结局（A,B）和（B,A）为纳什均衡，而第一阶段的合作结局（A,A)是由于触发策略针对对方偏离合作的行为设计了后续两阶段都不合作的惩罚措施，其单方面偏离的路径（B,A）（B,B）（B,B）收益并不增加，因此不存在偏离的动机。4.2.3有两个纳什均衡的重复博弈问题的提出：由于具有多个纳什均衡的重复博弈可以设计多种策略，在双方缺乏沟通的情况下，结局具有不确定性。因此，这里讨论具有多个纳什均衡的重复博弈可以实现的收益范围。个体理性得益：不管对方采取何种行动，只要自己的行为合理就可以保证实现的收益。可实现得益：各纯策略组合得益的加权平均数组。注意：并非一定是均衡策略的组合得益，因此在图4－2中，（3，3）也是可实现得益。4.2.4民间定理4.2.4民间定理用wi记博弈方i在一次性博弈中最差的均衡得益，用w记各博弈方的wi构成的得益数组。结合“个体理性得益”和“可实现得益”，则有限但次数很多的重复博弈有如下民间定理：定理：将一次性博弈中最差的均衡得益数组记为w,如果原博弈G的一次性博弈有得益数组优于w，那么在有限次重复博弈G(T)中，所有个体理性得益和可实现得益都至少有一个子博弈完美纳什均衡来实现。在图4-2一次性博弈中，博弈方均衡得益分别为纯策略的得益（1，4）和混合策略的得益（2，2）,最差的均衡得益数组为w=(1,1)。图4-3民间定理4.2.4民间定理(1,4)(3,3)(1,1)(4,1)厂商2得益厂商1得益在图4-3中，通过不同得益的组合，阴影部分（包括连线）的得益都是可实现得益。民间定理揭示出：在有限次重复博弈中，可以通过设计触发策略来实现（或者逼近）阴影部分的得益。4.2.4民间定理定理分析：民间定理表明，在具有多个纳什均衡的有限次重复博弈中，通过设计具有可信威胁的触发策略（即在第一阶段采取合作行为，当对方不合作时通过在后续阶段采取相应的不合作策略进行惩罚；当对方合作时，在最后阶段采取一次性原博弈的纳什均衡策略作为稳定的结局。），可以使得博弈方在重复博弈的过程中具有了一定学习能力，从而达到博弈的帕累托前沿得益。4.2.4民间定理例（两人各三种可选策略）：LMRLMR图4－4多种策略博弈的重复博弈该博弈具有两个纯策略纳什均衡和一个混合策略纳什均衡，但是双方存在一个更好的得益（4，4）。对于二次重复博弈，根据民间定理可以设计一个触发策略来实现这个得益。1，15，00，00，54，40，00，00，03，34.2.4民间定理触发策略：博弈方1在第一阶段采取M策略，如果对方合作，则第二阶段采取R策略作为奖励；否则第二阶段采取L策略进行惩罚（注意(L,L)也是纳什均衡，因此具有稳定性）。博弈方2也采取同样策略。策略分析：如果任何一方在第一阶段偏离，仅仅多获得5－4＝1单位得益，而在第二阶段的得益（L,L）仅仅为1；如果在第一阶段合作，第二阶段的得益为3。因此双方不存在偏离该策略的动机。4.2.4民间定理例（双方各五种可选策略重复博弈）：LMRPQLMRPQ图4－5双方各五种可选策略重复博弈1,15,00,00,00,00,54,40,00,00,00,00,03,30,00,00,00,00,04,1/20,00,00,00,00,01/2,44.2.4民间定理该博弈具有4个纯策略纳什均衡，在二次重复博弈中，触发策略设计：第一阶段双方采取(M,M)策略，如果博弈方1偏离此策略，那么第二阶段采取(Q,Q)策略对博弈方1进行惩罚，对博弈方2进行奖励；同理，如果博弈方2偏离了此策略，那么采取(P,P)策略对博弈方2进行惩罚，对博弈方1进行奖励。如果双方都没有偏离，那么第二阶段采取具有较高收益的纳什均衡(R,R)策略。如果双方都偏离了此策略，第二阶段同样采取纳什均衡的(R,R)策略。4.2.4民间定理策略分析：与图4－4例子相比较，由于博弈的特殊结构，这个触发策略的设计对偏离行为和合作行为分别进行惩罚和奖励，因此策略具有很强的可信性。而在图4-4例子中，针对对方的偏离行为采取了（L,L）策略进行惩罚，但是惩罚对方的同时，自身的利益也受到了损害，因此可信性不强。4.2.4民间定理第三节无限次重复博弈在有限次重复博弈中，（1）由于完全理性的博弈方可以运用逆推归纳法，因此对于原博弈具有唯一纳什均衡（如囚徒困境博弈）的有限次重复博弈，重复博弈结局尚无法摆脱囚徒困境；（2）但是对于原博弈具有多个纳什均衡的有限次重复博弈，根据民间定理可以设计出具有可信威胁的触发策略，达到帕累托最优的博弈结局。第三节无限次重复博弈在本节的无限次重复博弈中，由于无法运用逆推归纳法，因此对于原博弈具有唯一纳什均衡（如囚徒困境博弈）的无限次重复博弈，考虑到时间的价值后，也可以设计出具有可信威胁的触发策略，摆脱囚徒困境，达到帕累托最优的博弈结局。4.3.1几个概念无限次重复博弈求解存在的问题：（1）由于不存在最后一个阶段，无法运用逆推归纳法求解；（2）如果不考虑时间的价值，在无限次重复加总过程中，几乎所有子博弈路径的总得益都为无穷大，因此无法比较不同路径的优劣。解决方法：考虑到时间的价值，人们更为注重近期的得益，引入贴现系数，将未来阶段的收益折算到当期阶段。这样在无限次重复博弈中，总收益值将是一个有限数，可以加以比较。