博弈论课件4-重复博弈.ppt

1、第四章 重复博弈,前言,重复博弈不是基本博弈的简单叠加，必须把重复博弈过程作为整体进行研究 大多数重复博弈是静态博弈的重复，而重复博弈又是一个动态的过程，属于动态博弈的范畴，前两章的分析是本章的基础,主要内容,4.1 重复博弈引论 4.2 有限次重复博弈 4.3 无限次重复博弈,4.1 重复博弈引论,4.1.1 为什么研究重复博弈 4.1.2 基本概念,生活中的重复博弈 你到菜场去买菜，当你担心上当受骗而犹豫不决时，卖菜的摊主便会对你说:“你放心好了，我天天在这里卖菜，不会骗你的，如果菜不好你回来找我！”他强调自己“天天”在这里卖菜，你通常便会放下心来，与之成交。因为他的这句话翻译成经济学的语

2、言就是“我跟你是重复博弈”! 而一次性的买卖往往发生在双方以后不再有买卖机会的时候，特点是尽量谋取暴利并且带欺骗性，比如车站、码头、旅游景点的东西往往质次价高，其原因就在于买卖双方很少有“重复博弈”的机会。,在公共汽车上，两个陌生人会为一个座位争吵，因为彼此知道，这是一次性博弈，吵过了谁也不会再见到谁，因此谁也不肯在嘴上吃亏；可如果他们相互认识，就会相互谦让，因为他们知道，二者以后还会有碰面甚至交往的可能。两个朋友因为什么事情发生了争吵，如果不想彻底决裂，通常都会在争吵中留有余地，因为二人日后还要“重复博弈”。,4.1.1 为什么研究重复博弈,长期反复合作与竞争关系的存在 例：两企业的长期竞争

3、，长期协议，回头客 长期关系比短期关系更加复杂，考虑当前也要兼顾未来 一般动态博弈环环相扣；长期关系中，经济活动各个阶段之间的相互独立性 例：回头客信誉、信任,4.1.2 基本概念,重复博弈的定义同样结构的博弈重复多次，其中每次博弈称为“阶段博弈”。 重复博弈的分类有限次重复博弈、无限次重复博弈、随机结束的重复博弈。 有限次重复博弈：给定一个基本博弈G（可以是静态博弈，也可以是动态博弈），重复进行T次G，并且在每次重复G之前各博弈方都能观察到以前博弈的结果，这样的博弈过程称为“G的T次重复博弈”，记为G(T)。而G则称为G(T)的“原博弈”。G(T)中的每次重复称为G(T)的一个“阶段”。 注

4、意：重复博弈与一般动态博弈的区别，每个阶段都有得益，每个阶段的博弈方和博弈内容都相同,4.1.2 基本概念,无限次重复博弈：一个基本博弈G一直重复博弈下去的博弈，用 表示。 如果某个重复博弈没有可以预见的结束时间，各博弈方主观上认为博弈会不断进行下去，就可以看作是无限重复博弈。 随机结束的重复博弈：重复的次数虽然有限，但重复的次数或博弈结束的时间却是不确定的。,策略在每个阶段（即每次重复），针对每种情况（以前阶段的结果）如何行为的计划。 子博弈从某个阶段（不包括第一阶段）开始，包括此后所有的重复博弈部分。仍然可以应用逆推归纳法来分析。 均衡路径由每个阶段博弈方的行为组合串联而成。重复博弈的路径

5、数目： 。 重复博弈使博弈有了更多的可能，分析重复博弈就是要在这些路径中找出具有稳定性的均衡路径，并分析它们的效率意义。,4.1.2 基本概念,4.1.2 基本概念,重复博弈的得益总得益、平均得益 重复博弈中的博弈方的行为、策略选择不可能只考虑本阶段的得益，而必须兼顾其它阶段的得益，或者说会考虑整个重复博弈过程的总体情况。 1、总得益：博弈方各次重复得益的总和 2、平均得益：总得益除以重复次数 贴现系数：,4.1.2 基本概念,无限次重复博弈时,4.1.2 基本概念,随机停止和贴现率 将典型的随机结束重复博弈理解成在进行一个重复博弈时，每次都通过抽签来决定是否停止重复，假设抽到 停止重复的概率

6、为p，则抽到重复下去的概率为1-p，设某博弈方在此博弈中的阶段得益为 ，利率为 ，则该博弈方在重复博弈中期望得益的现值为：,把已知概率的随机停止重复博弈与无限次重复博弈统一起来，随机停止重复博弈问题可以当作无限次重复博弈来进行分析。,4.2 有限次重复博弈,4.2.1 两人零和博弈的有限次重复博弈 4.2.2 惟一纯策略纳什均衡的有限次重复博弈 4.2.3 多个纯策略纳什均衡的有限次重复博弈 4.2.4 有限次重复博弈的无名氏定理,4.2.1 两人零和博弈的有限次重复博弈,猜硬币博弈 零和博弈是严格竞争的，重复博弈并不改变这一点。 重复零和博弈不会创造出新的利益。,4.2.1 两人零和博弈的有

7、限次重复博弈,以零和博弈为原博弈的有限次重复博弈与猜硬币博弈的有限次重复博弈一样，博弈方的正确策略是重复一次性博弈中的纳什均衡策略。 可用逆推归纳法来证明 可以推广到非零和或多个博弈方，但博弈方的利益严格对立，没有纯策略纳什均衡的其他严格竞争博弈中 产生原因：利益关系严格对立，矛盾不可调和,4.2.2 惟一纯策略纳什均衡的有限次重复博弈,情形一：惟一纯策略纳什均衡是帕累托效率意义上的最佳策略组合 情形二：原博弈惟一的均衡没有达到帕累托效率，存在通过合作进一步提高效率的可能性，例如：囚徒困境博弈,4.2.2 惟一纯策略纳什均衡的有限次重复博弈,有限次重复的囚徒困境博弈 假定进行两次重复博弈，双方

8、看到第一次博弈的结果后再进行第二次博弈，最后得益是两阶段各自得益的和。 用逆推归纳法，先分析第二阶段，再分析第一阶段。,第二阶段,第一阶段,4.2.2 惟一纯策略纳什均衡的有限次重复博弈,一般结论：原博弈有惟一的纯策略纳什均衡的博弈，则有限次重复博弈的惟一均衡即各博弈方在每阶段（每次重复博弈）中都采用原博弈的纳什均衡策略。 原因：不存在不可信的威胁或承诺，是子博弈完美纳什均衡，虽然存在潜在的合作利益，但合作有确定的期限，。 定理：设原博弈G有惟一的纯策略纳什均衡,则对任意整数T，重复博弈 G(T)有唯一的子博弈完美纳什均衡，即各博弈方每个阶段都采用G的纳什均衡策略。各博弈方在G(T)中的总得益

9、为在G中得益的T倍，平均得益等于原博弈G中的得益。,4.2.2 惟一纯策略纳什均衡的有限次重复博弈,有限次重复削价竞争博弈,有唯一纯策略纳什均衡 （70，70）有限次重复的结果仍然是 （低价，低价） 同理：有限次重复古诺模型,4.2.2 惟一纯策略纳什均衡的有限次重复博弈,重复囚徒困境悖论和连锁店悖论 理论和实践的直觉矛盾，现实中寡头之间的价格战问题并不十分普遍，重复次数较大的实验研究的结果（重复200次的囚徒困境） 泽尔腾(1978)，“连锁店悖论”（导论中的先来后到博弈），实际中对开头几个市场的进入者不计代价的打击 问题的症结与蜈蚣博弈类似，在于在较多阶段的动态博弈中逆推归纳法的适用性,4

10、.2.2 惟一纯策略纳什均衡的有限次重复博弈,其他的解释： 虽然博弈次数有限，但是我们不知道具体是多少，类似一个无限次数的重复博弈类似于无限（例如：人的生命） 即使我们知道准确的结束合作关系的时间，比如劳动合同常常有明确的时间期限，但我们并不是从上班第一天就开始偷懒，是因为面对足够长的合同期，偷懒被开除而损失如此长期的一笔工资收益是不划算的。所以，员工仍采取了合作的态度，但是的确可以发现，随着终止合同离开雇主的日期越来越近，员工的努力程度在打折扣有限次博弈开始起作用了 这个有限博弈中的合作或对抗会给你进入另外一个博弈带来影响,必须考虑自己的表现，例如到其他企业工作,4.2.3 多个纯策略纳什均

11、衡的有限次重复博弈,三价博弈的两次重复博弈,博弈方1：第一次选H；如第一次结果为(H,H)，则第二次选M，否则选L 博弈方2：同博弈方1 两次重复的路径：第一阶段（H，H），第二阶段（M，M） 触发策略：两博弈方先试探合作，一旦发现对方不合作则也用不合作报复 多次重复的触发策略，平均得益接近于一次性博弈,+3,+1,两市场博弈的重复博弈（重复两次）,(A,B)+(A,B) OR (B,A)+(B,A)(1,4)(4,1) 连续两次采用混合策略(2,2) 轮换策略(A,B)+(B,A) OR (B,A)+(A,B)(2.5,2.5) 一次纯策略+一次混合策略(1.5,3)(3,1.5),两个纯策

12、略NE 一个混合策略NE,平均得益,重复博弈不同策略、均衡及一次性博弈得益比较 三次重复可以运用触发策略，重复次数增多，博弈的结果会得到改善,两市场博弈的重复博弈（重复两次）,有限次重复博弈的民间定理,当原博弈有多个纯策略纳什均衡时，有限次重复博弈有许多效率差异很大的子博弈完美纳什均衡，可以通过设计特定的策略，主要是包含报复机制的触发策略，实现效率较高的均衡，充分发掘一次性博弈中无法实现的潜在合作利益。 有限次重复博弈民间定理 设原博弈的一次性博弈有均衡得益数组优于w，那么在该博弈的多次重复中，所有不小于个体理性得益的可实现得益，都至少有一个子博弈完美纳什均衡的极限的平均得益来实现它们。,有限

13、次重复博弈的民间定理,最差均衡得益数组,帕累托 效率最大,触发策略,原博弈纯策略均衡的组合,4.3 无限次重复博弈,4.3.1 两人零和博弈的无限次重复博弈 4.3.2 惟一纯策略纳什均衡的有限次重复博弈 4.3.3 无限次重复古诺模型 4.3.4 有效工资率,4.3.1 两人零和博弈的无限次重复博弈,两人零和博弈无限次重复的所有阶段都不可能发生合作，博弈方会一直重复原博弈的混合策略纳什均衡 可以用类似逆推归纳法的方法进行分析 可以推广到更多博弈方、非零和的其他严格竞争博弈的无限次重复博弈中,4.3.2 惟一纯策略纳什均衡的无限次重复博弈,囚徒困境式博弈的无限次重复两寡头削价竞争,触发策略：第

14、一阶段采用H，如果前t-1阶段的结果都是(H,H)，则继续采用H，否则采用L。（先试图合作，如发现对方不合作，则以后永远报复），如果博弈方2采用L，总得益现值为： 如果博弈方2采用H，总得益现值为： 因此当 时，此触发策略纳什均衡策略。,4.3.2 惟一纯策略纳什均衡的无限次重复博弈,无限次重复博弈民间定理（弗里德曼，1971） 书上P193图形,4.3.3 无限次重复古诺模型,假定： ，边际成本都为2。 在无限次重复古诺模型中，当贴现率 满足一定条件时，两厂商采用下列触发策略构成一个子博弈完美纳什均衡： 在第一阶段生产垄断产量的一半1.5；在第 t 阶段，如果前 t-1 阶段结果都是(1.5

15、,1.5)，则继续生产1.5，否则生产古诺产量2。,支持垄断产量的条件,设厂商1已采用该触发策略，若厂商2也采用该触发策略，则每期得益4.5，无限次重复博弈总得益的现值为： 如果厂商2偏离上述触发策略，则他在第一阶段所选产量应为给定厂商1产量为1.5时，自己的最大利润产量，即满足： 解得 ，此时利润为5.0625，高于触发策略第一阶段得益4.5。,4.3.3 无限次重复古诺模型,但从第二阶段开始，厂商1将报复性地永远采用古诺产量2，这样厂商2也被迫永远采用古诺产量，从此得利润4。因此，无限次重复博弈第一阶段偏离的情况下总得益的现值为： 当 上述策略是厂商2对厂商1的同样触发策略的最佳反应，否则

16、偏离是最佳反应。,4.3.3 无限次重复古诺模型,低水平的合作 加大惩罚力度和提高合作水平 例子：石油输出国组织（OPEC）,4.3.3 无限次重复古诺模型,4.3.4 有效工资率（Efficiency Wages）,模型设定： 首先厂商选择工资率为 ，然后工人选择接受或拒绝。如果拒绝，则他作个体户得到收入 小于 ，如果接受 ，则工人选择努力工作（负效用 ）还是偷懒（无负效用）。 厂商只能看到产量高低，高产量为 ，低产量0。 工人努力工作时一定是高产量 ，不努力时却并不一定是0，而是高产量 的概率为 ，低产量0的概率为 。 工人努力工作时，厂商得益为 ，工人得益为 ； 工人偷懒时，厂商期望得益

17、为 ，工人得益为 。,触发策略：,厂商在第一阶段给工资率 ，在第t阶段，如果前面t-1阶段结果都是 则继续给 ，否则从此永远是 。 工人的策略是如果 则接受，否则宁愿作个体户得到 ，并在以前各期结果都是 和当前工资率为 时努力工作，否则偷懒。 设厂商已采用上述触发策略。由于 ，工人接受工作是最佳反应。用 记工人努力工作时无限次重复博弈得益的现值，则 即,用 记工人选偷懒时无限重复博弈得益的现值，则： 即 因此当 即 时，努力是工人的最佳选择。 反过来，设工人已采用上述触发策略。若厂商给的工资率满足上式条件，并且威胁一旦产量降低就解雇工人，则各阶段的得益为 ，无限次重复博弈得益现值为 。若不愿给

18、 ，则解雇工人，以后得益为0。因此只要 ，厂商选择前述触发策略就是最佳反应。,4.3.4 有效工资率（Efficiency Wages）,综上所述，在满足 的条件下，双方的触发策略构成一个纳什均衡。而上述两式实际上意味着 即工人努力的产出扣除努力负效用后的剩余，必须不小于工人作个体户的收入即机会成本，加上一定比例的取决于努力负效用、贴现系数和偷懒可能得高产量概率的附加部分。 最后这个不等式正是存在有效工资率，工作激励有效的基本条件。,4.3.4 有效工资率（Efficiency Wages）,罗伯特阿克谢罗德（Robert Axelord）竞赛实验,罗伯特阿克谢罗德，1943年出生于芝加哥，曾

19、就读于芝加哥大学和耶鲁大学，现在是密歇根大学政治学教授。1980年，为了研究合作问题，他组织了一次关于囚徒困境的不同策略的比赛。 阿克谢罗德在开始研究合作之前，设定了两个前提： 1、每个人都是自私的； 2、没有任何权威干预每个人的决策。 也就是说，个人可以完全按照自己利益最大化的企图进行决策。 在此前提下，合作要研究的问题是： 第一、人为什么要合作； 第二、人什么时候是合作的，什么时候又是不合作的； 第三、如何使别人与你合作。,罗伯特阿克谢罗德（Robert Axelord）竞赛实验,在研究的过程中，他组织了一场计算机模拟竞赛，竞赛的思路非常简单：任何想参加这个计算机竞赛的人都扮演“囚徒困境”

20、案例中一个囚犯的角色，他们开始玩“囚徒困境”的游戏，每个人都要在合作与背叛之间做出选择。关键问题在于，他们不只玩一遍这个游戏，而是一遍一遍地玩上200次，这就是所谓的“重复的囚徒困境”，于是这就更逼真地反映了日常人际关系。 首先由14个人参与实验，每两个人为一组，进行重复200次的博弈，博弈记分规则为：如果都合作，每方计2分，都对抗每方计0分，一方合作一方对抗则合作者计-1分而对抗者记4分。然后再重新分组，直到两两比赛过。,罗伯特阿克谢罗德（Robert Axelord）竞赛实验,试验的结果使教授大为吃惊，因为竞赛的冠军获得者-多伦多大学的数学教授阿纳托拉帕波特所采取的策略一点都不高深，而是非

21、常简单：一报还一报（以牙还牙）。也就是我们通常所说的“以其人之道，还治其人之身”。它的特点是：第一次对局采用合作的策略，以后每一步都紧紧跟随对方上一步的策略，你上一次合作，我这一次就合作，你上一次不合作，我这一次就不合作。 为了进一步验证第一轮游戏得到的结论，教授邀请了更多的人再做一次游戏。这时游戏进入了第二轮。第二次爱克斯罗德征集到了62个程序，同样也附加上他自己的随机程序，又进行了一次竞赛。结果，第一名的仍是针锋相对策略。,罗伯特阿克谢罗德（Robert Axelord）竞赛实验,这个如此简单的策略之所以反复赢得竞赛，是因为它奉行了针锋相对的(tit-for-tat)法则，说白了就是一报还

22、一报，即“人不犯我，我不犯人；人若犯我，我必犯人”，但它坚持“有理、有利、有节”的尺度，并且用以下有规律可供遵循的行为将对手纳入长期合作的轨道上来： 第一，善良的，即从不首先背叛； 第二，可激怒的，对于对方的背叛行为一定要报复，不能总是合作； 第三，宽容的，不能人家一次背叛，你就没完没了地报复，以后人家只要改为合作，你也要合作； 第四，易于察觉的，即逻辑清晰，使对手能够很轻易地发现你采取策略的规律，并且领会你的意图。,罗伯特阿克谢罗德（Robert Axelord）竞赛实验,而输掉这个竞赛的策略，总是在上述四个方面做得不够好。比如竞赛者的脾气过于好，总是“以德报怨”，结果就被狡猾之徒反复地占便

23、宜；有些竞赛者不够宽容，别人背叛一次他就不与对方再次合作，从而使合作关系永久性断绝；还有一些竞赛者太“精于算计”，总是试图通过取巧来占别人的便宜，这种人在与“好脾气者”的博弈中虽然大占便宜，但与“不宽容者”的博弈中往往搬起石头砸自己的脚，而从最后的总分来看，他的“小聪明”总是得不偿失。,针锋相对策略的优越性向我们充分展示了一个纯粹自利的人何以会选择善，只因为合作是自我利益最大化的一种必要手段。 比如在爱情中的重复博弈原则应该是：善意而不是恶意地对待恋人；宽容而不是尖刻地对待恋人，关键是能够彼此宽容，既宽容对方的缺点；强硬而不是软弱地对待恋人，就是要在我永远爱你的善意的前提下，做到有爱必报，有恨

24、也必报，以眼还眼，以牙还牙，以其人之道，还治其人之身，比如对恋人与其他异性的亲热行为，要有极其强烈的敏感与斩钉截铁地回报；简单明了而不是山环水绕地对待恋人，在博弈中过分复杂的策略使得对手难于理解，无所适从，因而难以建立稳定的合作关系，明晰的个性、简练的作风和坦诚的态度倒是制胜的要诀。,重庆谈判中共产党的方针针锋相对,1945年抗日战争胜利后，为避免内战、争取和平，中国共产党同国民党政府在重庆进行了为期43天的和平谈判，史称“重庆谈判”。 谈判之前，蒋介石就让阎锡山入侵上党地区，以此先发制人，扼守抢夺平津、独占华北的交通要道，保持长江与北方之间的陆上联系。当时国共之前的军事摩擦已经出现。 8月25日，即毛泽东电复蒋介石将亲自赴重庆谈判的当天，对即将返回上党前线的刘伯承、邓小平说：“你们回到前方去，放手打就是了。不要担心我在重庆的安全问题，你们打得越好，我越安全，谈得越好。别的办法是没有的。” 刘、邓回到上党，在上党战役的动员报告中指出：“我们立足于打，不放弃有利条件的谈判。只有打得好，才能谈得好。”,重庆谈判中共产党的方针针锋相对,就这样，国共和谈在边打边谈中进行