重复博弈的详细介绍.ppt

重复博弈,主要内容：一、有限次重复博弈二、无限次重复博弈与无名氏定理三、重复博弈的社会学含义,例子1-越战战场上的潜规则 一名新兵刚上战场，老兵按住他：别乱开枪！新兵问：为什么？老兵对其解释：曾有一段时间，双方打得不可开交，结果大家都躲着，屎尿都撒在猫耳洞里，由于猫耳洞很潮湿，人呆在里面很难受，导致有人耳朵都发了霉，最后是谁也打不着谁，自己却活受罪。此后，便慢慢达成默契：我出来你不开枪，你出来我也不开枪。,例子2 一个男孩被视为傻瓜，因为每当别人拿一枚1块硬币和5分硬币让他选的时候，他总是选5分的，有一个人觉得奇怪，就问他：“为什么你不拿1块钱的？”，男孩小声回答：“假若我拿了1块钱的硬币，下次他们就不会再拿钱让我选了。”,威胁和承诺的重要性：以上两个例子带给我们什么启发？,问题1 在相互联系紧密的人际关系中，人们普遍比较注意礼节、道德，因为合作和协调对大家都有好处；但是，我们又常常见到这样的消息：在公共汽车上，两个陌生人会为一个座位争吵，为什么会发生这种事情？原因何在？,问题2 在“囚徒困境”这一例子中，博弈的参与人为了追求自身利益的最大化，而陷入了个人理性与集体理性的冲突中，导致最优的结果未能出现，即合作没有产生。如果我们假定博弈可以多次重复进行，结果是否会发生变化？是否会出现合作的局面？,动态博弈中涉及的一个重要问题是，博弈过程中威胁和承诺如何影响博弈的进程。重复博弈所关心的议题也与之相似：（1）将来可信的威胁或承诺如何影响到当前的行动？（2）在一次博弈中无法实现的均衡，在重复博弈中能否实现？,一、有限次重复博弈,考察下列博弈,该博弈存在唯一的Nash均衡，即（U，L）。同时注意到，该博弈还存在一个高效均衡（D，R），高效均衡对应着一种合作行为。为什么高效的均衡不是纳什均衡？如何保证这一高效均衡能够实现？,两次重复博弈的博弈树,假设将上述博弈重复两次，那么第二次博弈开始时，第一次博弈的结果可视为已知。,第二阶段,第一阶段,第一阶段,运用逆推归纳法，可以发现上述重复博弈的子博弈精炼Nash均衡为：在每次博弈中，参与人1都选择U，参与人2都选择L。这说明：在两次重复博弈中，高效的均衡仍无法实现。,同样可证明：在n阶段重复博弈(即博弈重复n次且每次博弈开始时，前面博弈的结果都已知)中，高效的均衡同样无法实现。,有限重复博弈定义,定义：对于给定的阶段博弈G，令G(T)表示G重复进行T次的有限重复博弈，并且在下一次博弈开始前，所有之前博弈的进程均可被观测到。,有限重复博弈的战略、子博弈与支付,战略：重复博弈环境下，参与人的战略非常复杂。一般地，我们定义参与人的一个战略是在博弈的每个阶段针对之前的博弈历史而制定的行动计划；子博弈：子博弈要么仍然是重复博弈，要么是原博弈；,有限重复博弈的战略、子博弈与支付,参与人的支付：是所有阶段博弈支付的贴现值之和，或者加权平均值。注意：在重复博弈中，阶段博弈可能是静态博弈，也可能是动态博弈，因此，重复博弈可能是完美信息重复博弈和不完美信息重复博弈。此处我们仅讨论完美信息重复博弈。,假定在位者在不同的市场上有20家连锁店，进入者试图进入这些市场。如果进入者进入了每一个市场，此时博弈就变成了20次重复博弈。当进入者进入第1个市场时，在位者应该如何反应呢？猜想：杀鸡儆猴的效应,连锁店悖论,单阶段博弈矩阵,进入者,支付,在位者,纳什均衡为：在位者在每一个市场选择默许，进入者在每一个市场选择进入。,单阶段扩展式博弈,阶段博弈的子博弈精炼纳什均衡为：在位者在每一个市场选择默许，进入者在每一个市场选择进入。,重复博弈的子博弈精炼纳什均衡：在位者在每一个市场选择默许，进入者在每一个市场选择进入。,定理：,如果阶段博弈G有唯一的Nash均衡，则对任意有限的T，重复博弈G(T)有唯一的子博弈精炼解，即G的Nash均衡结果在每一个阶段重复进行。,问题：囚徒困境中的囚徒有可能实现高效的均衡吗？,考察下列博弈,存在多重纳什均衡的情形,单阶段Nash均衡：(L1,L2)和(R1,R2)；合作均衡：（M1，M2）；问题：合作均衡能否出现？,现在假设博弈重复两次，可以根据以下原则构造均衡：由第一阶段的结果，预测第二阶段的均衡。例如：若第一阶段出现(M1,M2)(即出现合作)，则第二阶段为(R1,R2)(即“好的纳什均衡”)；若第一阶段没有出现(M1,M2),则第二阶段为(L1,L2)(即“差的纳什均衡”)。,冷酷战略（grim strategies）,也称触发战略；以囚徒困境为例：开始选择抵赖，而且一直选择抵赖直到有一方选择了坦白，然后永远选择坦白；这意味着：一旦哪个参与人选择了坦白，就触发了惩罚的扳机。,根据上述原则，可构造如下战略：,S1：第一阶段选择M1；如果第一阶段结果为(M1，M2)，则下一阶段选R1；否则选择L1。S2：第一阶段选择M2；如果第一阶段结果为(M1，M2)，则下一阶段选R2；否则选择L2。,根据上述战略，博弈可表示为：,这意味着，合作可以在第一阶段达到。这一结论说明，对将来行动所作的可信威胁或承诺可以影响到当前的行动。问题：没有考虑贴现率。,二、无限次重复博弈与无名氏定理,定义：给定一阶段博弈G，令 表示相应的无限次重复博弈，其中G将无限次的重复进行，且参与人的贴现率为。对每个t，之前t-1次阶段博弈的结果在t阶段开始进行前都可以被观测到，每个参与人在 中的收益都是该参与人在无限次的阶段博弈中所得收益的贴现值。,在有限次重复博弈G(T)中，由第t+1阶段开始的一个子博弈为G、进行T-t次的重复博弈，可表示为G(T-t)。在无限次重复博弈 中，由 t+1 阶段开始的每个子博弈都等同于初始博弈。和在有限情况下相似，博弈 到 t 阶段为止有多少不同的可能进行过程，就有多少从 t+1 阶段开始的子博弈。,考虑如下无限次重复博弈：,对于阶段博弈为上述博弈的有限次重复博弈，合作不可能形成。但对于无限次重复博弈，在一定的贴现率下，合作有可能形成。,构造如下触发策略：,S1：第i阶段选择D；如果第i阶段结果为(D，R)，则下一阶段选D；否则以后一直选择U。S2：第i阶段选择R；如果第i阶段结果为(D，R)，则下一阶段选R；否则以后一直选择L。,贴现率的求解：,所以,可以证明：在一定的贴现率下，上述触发策略构成Nash均衡；,可行收益,一组收益 为阶段博弈G的可行收益，如果它们是G的纯战略收益的凸组合，即纯战略收益的加权平均，权重非负且和为1。前述阶段博弈的可行收益集合如下图所示。,阴影部分为上述博弈的可行收益区间,平均收益,给定贴现率，无限的收益序列 的平均收益为,所以,故,无限次重复博弈的无名氏定理：,令G为一个n人阶段博弈，令 为G的 一个Nash均衡下的收益，且用 表 示G的其它任何可行收益，表示可行收益的 集合。若存在 则存在贴现率，使无限重复博弈 存在一个子博弈精炼Nash均衡，其平均收益可达到。,子博弈精炼Nash均衡的可行收益区间,无名氏定理的一个解释,在无限次重复博弈中，如果参与人具有足够的耐心（只要满足一定的条件），那么任何满足个人理性的可行收益向量都可以通过一个特定的子博弈精炼Nash均衡得到。,无名氏定理举例,该博弈中唯一的纳什均衡为（U，L），两个局中人在此均衡下的收益都是1；所以，只要无限次重复博弈中参与人可行的平均单期收益不小于1，这样的收益就是一个可能的均衡收益。这说明，无限次重复博弈能够导致帕累托改进。,三、重复博弈的社会学含义,罗伯特爱克斯罗德(政治科学家)对合作问题进行了实验性研究，他组织了一场计算机竞赛。这个竞赛的思路非常简单：任何想参加这个竞赛的人都扮演“囚徒困境”案例中的一个囚犯，他们把自己的战略编入计算机程序，然后他们的程序会被成双成对地融入不同的组合，分好组以后，参与者就开始玩“囚徒困境”的游戏。他们每个人都要在合作与背叛之间做出选择，并且游戏重复多次。,竞赛的第一个回合交上来的14个程序中包含了各种复杂的战略。但使爱克斯罗德和其他人深为吃惊的是，竞赛的桂冠属于其中最简单的战略：一报还一报(Tit for Tat)。这是多伦多大学心理学家阿纳托拉帕波特提交上来的战略。一报还一报战略：它总是以合作开局，但从此以后就采取以其人之道还治其人之身的战略。也就是说，一报还一报的战略实行了胡萝卜加大棒的原则。,一报还一报战略：永远不先背叛对方，从这个意义上来说它是“善意的”。一报还一报战略：会在下一轮中对对手的前一次合作给予回报（哪怕以前这个对手曾经背叛过它），从这个意义上来说它是宽容的。一报还一报战略：会采取背叛的行动来惩罚对手前一次的背叛，从这个意义上来说它又是“强硬的”。一报还一报战略：简单明了，对手一看便知其用意何在。,一报还一报战略的特征,为了验证上述结果的合理性，爱克斯罗德又举行了第二轮竞赛，特别邀请了更多的人，看看能否从一报还一报战略那儿将桂冠夺过来。这次有62个程序参加了竞赛，结果是一报还一报又一次夺魁。竞赛的结论无可争议地证明，具备以下特点的人，将总会是赢家：（1）本性善良；（2）品格宽厚；（3）不失强硬；（4）处事干练，原则简单明了。,一报还一报战略的胜利对人类和其他生物的合作行为的形成具有深刻地含义。爱克斯罗德在合作进化一书中指出，一报还一报战略能导致社会各个领域的合作，包括在最无指望的环境中的合作。典型的例子就是越战中自发产生的“自己活，也让他人活”的原则：只要对方不开枪伤人，我也不开枪。,一报还一报自然界的例子,真菌从地下的石头中汲取养分，为海藻提供了食物，而海藻反过来又为真菌提供了光合作用；金蚁合欢树为一种蚂蚁提供了食物，而这种蚂蚁反过来又保护了该树；无花果树的花是黄蜂的食物，而黄蜂反过来又为无花果树传授花粉，将树种撒向四处。,一报还一报的社会学含义,共同演化会使一报还一报的合作风格在这个诚信缺失的社会蔚然成风。假设少数采取一报还一报战略的人在社会上通过突变而产生了。那么，只要这些个体能互相遇见，并在今后的相逢中形成利害关系，他们就会开始形成小型的合作关系。,一旦发生了这种情况，他们就能影响周围那些不讲信用、不懂合作的人。这样，参与合作的人数就会增多。很快，一报还一报式的合作就会最终占上风。一旦建立了这种机制，相互合作的个体就能生存下去。如果不太合作的类型想侵犯和利用他们的善意，一报还一报政策强硬的一面就会狠狠地惩罚他们，让他们无法扩散影响。,