博弈论第五章重复搏弈(RepeatedGames).ppt

第五章 重复搏弈(Repeated Games),本章介绍基本博弈重复进行构成的重复博弈。虽然形式上是基本博弈的重复进行，但重复博弈中博弈方的行为和博弈结果却不一定是基本博弈的简单重复，因为博弈方对于博弈会重复进行的意识，会使他们对利益的判断发生变化，从而使他们在重复博弈过程中的行为选择受到影响。这意味着不能把重复博弈当作基本博弈的简单叠加，必须把整个重复博弈过程作为整体进行研究。,一、有限次重复博弈 二、无限次重复博弈 三、参与人不固定时的重复博弈 四、应用举例,信息集 挺好用 见下图,在每一个重复博弈中，有一个实施许多遍的组件博弈有时候称作阶段博弈。,博弈中的盈利是每个阶段的盈利之和,重复博弈,重复博弈：指同样结构的博弈重复多次，其中的每次博弈称为“阶段博弈”。如囚徒困境。 重复博弈类型： 有限次重复博弈 无限次重复博弈 随机结束的重复博弈,重复博弈,重复博弈的特征： 1、阶段博弈之间没有“物质上”的联系，即前一阶段的博弈不改变后一阶段的结构 ； 2、所有参与人都观测到博弈过去的历史； 3、参与人的总支付是所有阶段博弈支付的贴现值之和或加权平均均值。 贴现因子：下一期的一单位支付在这一期的价值。 注意：在每个阶段，参与人可同时行动，也可不同时行动。,重复博弈,因为其他参与人过去的历史总是可以观测到的，因此，一个参与人可以使自己在某个阶段博弈的选择依赖于其他参与人过去的行动历史，因此，参与人在重复博弈中的战略空间远远大于和复杂于每一阶段的战略空间，这意味着，重复博弈可能带来一些“额外”的均衡结果。 影响重复博弈均衡结果的主要因素是博弈重复的次数和信息的完备性。 博弈重复的次数的重要性来源于参与人在短期利益和长远利益之间的权衡。 信息的完备性：当一个参与人的支付函数不为其他参与人知道时，该参与人可能有积极性建立一个“好”的声誉以换取长远利益。,重复博弈的要素,策略、子博弈、均衡路径 支付（得益） 贴现系数 有限次重复博弈 无限次重复博弈,重复博弈,随机停止与贴现率： 设停止重复的概率为p，继续重复的概率为1p。,定义：令G=A1, A2,An; u1, u2,un)表示n个局中人的完全信息博弈，对G重复若干次，称G为阶段博弈。 给定阶段博弈G，令G(T)表示G 实施T（T为大于1的整数）次的重复博弈。在某次阶段博弈开始之前，所有已采取过的前面阶段的行动都可以观察到。局中人在G(T)的盈利函数或效用简单的为来自T个阶段博弈盈利现时值之和。,有限重复博弈,定理：如果阶段博弈G有唯一的Nash均衡，那么对任意有限次T，重复博弈G(T)有唯一的子博弈完美结局：在每一阶段取G的Nash均衡策略。 注1：定理中要求的唯一Nash均衡可以是混合策略均衡。如猜谜游戏。 注2：阶段博弈G可以不是静态的，假如阶段博弈G是完全且完美信息动态博弈时，且具有唯一的“逆向归纳”结局，那么G(T)有唯一的子博弈完美结局。,当阶段博弈具有唯一的Nash均衡时,举例,有限次重复博弈：寡头市场的削价竞争 连锁店悖论：,寡头市场的削价竞争,这个博弈的纳什均衡是什么？ 假定博弈共进行10次，结果会如何？ 为什么会出现这个结果？,高价,企业乙,企业甲,低价,高价,低价,价格大战中的囚徒困境,逆向归纳法 假定现在是第十次，结果和一次博弈一样。第九次，即倒数第二次，局中人已经很清楚，最后一次博弈对方肯定要实行低价，因此，现在如何对他施行好心都不会在下一次得到好报，所以，理性人的“我”没有理由实施高价使对方获益。依次类推。,高价,企业乙,企业甲,低价,高价,低价,连锁店悖论,进入者,进入,不进入,在位者,默许,斗争,默许,(-10，0),（0，300),(0,300),(40,50),x,x,在位者,斗争,假定同样的市场上有20个（可以理解为在位者有20个连锁店），进入者每次进入一个市场，博弈就变成了20次重复博弈。 假定进入者进入第1个市场，在位者应该如何反应呢？,结论：不存在纯战略纳什均衡和存在惟一的纯战略纳什均衡，作为原博弈构成的有限次重复博弈，共同特点是重复博弈本质上不过是原博弈的简单重复，重复博弈的子博弈完美纳什均衡就是每次重复采用原博弈的纳什均衡。,多个纯战略纳什均衡博弈的有限次重复博弈,考虑下面的三价博弈： 该博弈存在两个纯战略纳什均衡（M，M）和（L，L）。显然一次博弈的结果效率不是最高的，因此有帕雷托改进的余地。,多个纯战略纳什均衡博弈的有限次重复博弈,现在考虑该博弈重复进行的情况。如果这个博弈重复进行两次： 两次重复博弈的纯战略路径：9981 子博弈完美纳什均衡路径：两阶段都采用原博弈同一个纯战略纳什均衡，或者轮流采用不同纯战略纳什均衡，或者两次都采用混合战略纳什均衡，或者混合战略和纯战略轮流采用。,多个纯战略纳什均衡博弈的有限次重复博弈,在这些子博弈完美纳什均衡路径中，确实存在第一阶段采用（H，H）的子博弈完美纳什均衡。 双方的战略是： 局中人1：第一次选H；如第一次结果为（H，H），则第二次选M，如第一次结果为任何其它战略组合，则第二次选L。 局中人2：同局中人1。,多个纯战略纳什均衡博弈的有限次重复博弈,此战略组合的两次重复博弈的路径：第一阶段（H，H），第二阶段（M，M），此为一个子博弈完美纳什均衡路径。 证明： 第二阶段是一个原博弈的纳什均衡，因此不可能有哪一方会愿意单独偏离； 第一阶段的（H，H）虽然不是原博弈的纳什均衡，一方单独偏离，采用M能增加1单位得益，但这样的话，在第二阶段至少要损失2单位得益，因为对方采用的“有报复机制”的战略。偏离（H，H）得不偿失，合理的选择是坚持H。,多个纯战略纳什均衡博弈的有限次重复博弈,总结： 触发战略（Trigger Strategy），首先试探合作，一旦发现对方不合作，则也用不合作相报复的战略。 触发战略是重复博弈中实现合作和提高均衡效率的关键机制，是重复博弈分析的重要“构件”之一。 在触发战略中，第二阶段的选择实际上是一种条件选择。,多个纯战略纳什均衡博弈的有限次重复博弈,当第一阶段结果为（H,H）时，第二阶段必为（M,M）；当第一阶段结果为其它8种结果是，第二阶段必为（L，L）。 把上面的分析加到原博弈得到下面的博弈，该博弈的纳什均衡为（H，H）,多个纯战略纳什均衡博弈的有限次重复博弈,如果此博弈重复多次，一般地说n次，仍然可以采用触发战略得到较好的结果：子博弈完美纳什均衡路径为，除了最后一次重复外，每次都采用（H，H），最后一次重复采用原博弈的纳什均衡（M，M）。当重复的次数较多时，平均得益接近于一次性博弈中的（H，H）的得益（5，5）。,结论：如果阶段博弈G=A1, A2,An; u1, u2,un)具有多重Nash均衡，那么可能（但不必）存在重复博弈G(T)的子博弈完美均衡结局，其中对于任意的tT，在t阶段的结局并不是G的Nash均衡。,多个纯战略纳什均衡博弈的有限次重复博弈,多个纯战略纳什均衡博弈的有限次重复博弈,触发战略的可信性问题 从合作开始，一直到有一方不合作，然后永远选择不合作。,无限次重复博弈,无限次重复博弈与有限重复博弈的区别： 无限次重复博弈没有结束重复的确定时间。在有限次重复博弈中，存在最后一次重复正是破坏重复博弈中局中人利益和行为的相互制约关系，使重复博弈无法实现更高效率均衡的关键问题。 无限次重复博弈不能忽视不同时间得益的价值差异和贴现问题，必须考虑后一期得益的贴现系数，对局中人和博弈均衡的分析必须以平均得益或总得益的现值为根据。 无限次重复博弈与有限次重复博弈的共同点：试图“合作”和惩罚“不合作”是实现理想均衡的关键，是构造高效率均衡战略的核心构件。,无限次重复博弈,一个男孩被视为傻瓜，因为每当别人拿一枚1角硬币和5分硬币让他选的时候，他总是选5分的，有一个人觉得奇怪，就问他：“为什么你不拿1角钱的？”，男孩小声回答：“假若我拿了1角钱的硬币，下次他们就不会拿钱让我选了。”,无限次重复博弈,两人零和博弈的无限次重复博弈： 所有阶段都不可能发生合作，局中人会一直重复原博弈的混合战略纳什均衡。,惟一纯战略纳什均衡博弈的无限次重复博弈,原博弈惟一的纳什均衡本身是帕雷托效率意义上最佳战略组合，符合各局中人最大利益：采用原博弈的纯战略纳什均衡本身是各局中人能实现的最好结果，符合所有局中人的利益，因此，不管是重复有限次还是无限次，不会和一次性博弈有区别。 惟一的纳什均衡不是效率最高的战略组合，存在潜在合作利益的囚徒困境博弈：,惟一纯战略纳什均衡博弈的无限次重复博弈,无限次重复囚徒困境： 囚徒困境博弈重复无穷次，结果如何？ 证明得出，如果参与人有足够的耐心，（抵赖，抵赖）是一个子博弈精练纳什均衡结果）。 触发战略 （1）开始选择抵赖； （2）选择抵赖一直到有一方选择了坦白，然后永远选择坦白。,囚徒A,囚徒 B,坦白,抵赖,坦白,抵赖,无限次重复博弈使其走出了囚徒困境，背后的原因是： 如果博弈重复无穷次而且每个人有足够的耐心，任何短期机会主义行为的所得都是微不足道的，参与人有积极性为自己建立一个乐于合作的声誉，同时也有积极性惩罚对方的机会主义的行为。,两寡头价格竞争博弈： 一次性博弈的惟一纯战略纳什均衡（L，L），双方的得益（1，1）,局中人2,局中人1,H,L,H,L,无限次重复囚徒困境,触发战略：第一阶段采用H，在第t阶段，如果前t1阶段的结果都是（H，H），则继续采用H，否则采用L。 结论：在不同时期得益的贴现因素 较大时，双方采用上述战略构成无限次重复博弈的一个子博弈完美纳什均衡。,无限次重复囚徒困境,局中人2： 如第一阶段选L， 如第一阶段采用H，下一阶段也采用H，一直下去,无限次重复囚徒困境,无限次重复古诺模型:垄断合作,假定： ， 边际成本都为2。 在无限次重复古诺模型中，当贴现率 满足一定条件时，两厂商采用下列触发策略构成一个子博弈完美纳什均衡： 在第一阶段生产垄断产量的一半1.5；在第 t 阶段，如果前 t-1 阶段结果都是(1.5,1.5)，则继续生产1.5，否则生产古诺产量2。,设厂商1已采用该触发策略，若厂商2也采用该触发策略，则每期得益4.5，无限次重复博弈总得益的现值为： 如果厂商2偏离上述触发策略，则他在第一阶段所选产量应为给定厂商1产量为1.5时，自己的最大利润产量，即满足： 解得 ，此时利润为5.0625，高于触发策略第一阶段得益4.5。,但从第二阶段开始，厂商1将报复性地永远采用古诺产量2，这样厂商2也被迫永远采用古诺产量，从此得利润4。因此，无限次重复博弈第一阶段偏离的情况下总得益的现值为： 当 上述策略是厂商2对厂商1的同样触发策略的最佳反应，否则偏离是最佳反应。,无限次重复古诺模型：低水平合作,触发战略：在第一阶段生产q*（该产量位于qm/2和qc之间）；在第t阶段，如果前t1阶段的结果都是（q*,q*），则继续生产q*，否则生产古诺产量qc2。 分析： 双方都采用触发战略时均衡路径为每阶段都是（q*,q*），两厂商的得益都为,无限次重复古诺模型：低水平合作,假设厂商1已采用触发战略，如果厂商2也采用触发战略，则其得益是 无限次重复博弈的现在值为,无限次重复古诺模型：低水平合作,如果厂商2在第一阶段偏离，并根据厂商1的产量q*决定自己该阶段最大利润产量，则该产量必须满足,但是从第二阶段开始，因为厂