《重复博弈》PPT课件.ppt

第四章 重复博弈 1. 基本概念 n重复博弈：给定一个基本博弈G（可以 是静态博弈，也可以是动态博弈）， 重复进行T次G，并且在每次重复G之前 各博弈方都能观察到以前博弈的结果 ，这样的博弈过程称为“G的T次重复 博弈”，记为G(T)。而G则称为G(T)的 “原博弈”。G(T)中的每次重复称为 G(T)的一个“阶段”。 2.为何研究重复博弈 （1）两家企业在一个市场上的传长期竞争；两个 企业遵守一份为期10年协议方面的契约；商业中 的回头客等等。 （2）由于长期合作，通过报复、制裁、威胁等手 段的相互约束行为，追求共同的目标，考虑当前 利益兼顾将来的利益。 （3）长期关系可以理解为博弈阶段较多，时间跨 度较大的一般动态博弈。诚信、信任 3. 序贯博弈与重复博弈 n序贯博弈(sequential game)：参与人在前一个 决策点的选择决定后续子博弈的结构，因此， 从后一个决策点开始的子博弈不同于从前一个 决策点开始的子博弈，或者说，同样结构的子 博弈只出现一次； n重复博弈(repeated game)：同样结构的博弈 重复多次，其中的每次博弈被称为“阶段博弈” (stage game)。 4. 重复博弈的三个特征 n阶段博弈之间没有物质上的联系，也就 是说，前一阶段的博弈不改变后一阶段 的结构； n所有参与人能观察到博弈过去的历史； n参与人的总支付（报酬）是所有阶段博 弈支付的贴现值之和； n(1) 重复博弈的策略 n重复博弈中每个博弈方在每个阶段都必须进行 策略选择，因此博弈方的一个策略就是在每次 重复时, 针对其前面阶段所有可能的情况如何 进行行动的计划。 n(2) 重复博弈的子博弈 重复博弈的子博弈就是从某个阶段（除第一 阶段以外）开始，包括此后所有阶段的重复博 弈部分。重复博弈的子博弈要么仍然是重复博 弈，只是重复的次数较少，要么就是原博弈。 5. 重复博弈的策略、子博弈和均衡路径 n(3) 重复博弈的均衡路径 n重复博弈的路径是由每个阶段博弈方的行动组 合串联而成的。而且对应前一阶段的每一种结 果，下一阶段都有原博弈全部策略组合数那么 多种可能的结果，如原博弈有m种策略组合， 那么重复两次就有m2条博弈路径，重复T次就有 mT条博弈路径，因此在重博弈中，博弈方在重 复博弈中的策略空间要远远大于在每个阶段博 弈中的策略空间，重复博弈的路径数往往是很 大的，常常可以产生一些意想不到的均衡路径 。 6重复博弈的支付 n方法之一是计算重复博弈的”总支付”,即博弈方各次 重复支付的总和； n另一种方法是计算各阶段的“平均支付”，即总支付除 以重复次数。 7.重复博弈和信誉问题 n如果博弈不是一次性的，而是重复进行的，参 与人过去行动的历史是可以观察到的，参与人 就可以将自己的选择依赖于其他人之前的行动 ，因而有了更多的战略可以选择，均衡结果可 能与一次博弈大不相同。 n重复博弈理论的最大贡献是对人们之间的合作 行为提供了理性解释；在囚徒困境中，一次博 弈的唯一均衡是不合作（即坦白）。但如果博 弈无限重复，合作就可能出现。 8. 关于重复博弈的一般化讨论 n重复博弈可用于研究人们长期之间相互 作用关系 n重复博弈的基本思想是，一个参与者将 会考虑自己当前的行为对其他参与者未 来行为的影响， 旨在阐释人们的合作、 报复和威胁等现象。 基本思想 n重复博弈的基本思想可以用两个人重复 进行“囚徒困境”博弈来阐述. n在一次性博弈中，囚徒困境具有唯一的 纳什均衡，即每个局中人都选择不合作 （即坦白，记作D),(D, D) 是唯一的结果 n尽管如此, 每个参与者如果选择合作C， 则状况将得到改善。 基本思想 n只要博弈是重复进行的，那么合作对双 方来说就是有吸引力的。 n每个人都相信背叛行为将会使合作终止 ，所导致的长期损失超过了短期收益。 n可用于解释社会行为规范。 9.有限重复博弈和无限重复博 弈 n根据博弈重复次数划分 n两种情形的结果是截然不同的 10. 囚徒困境博弈 合作不合作 合作不合作 -1，-1-10，0 0，-10-8，-8 局中人 1 局中人 2 重复博弈与战略空间的扩展 n假定上属博弈重复多次或无限次；那么，每个参与人 有多个可以选择的战略：仅举几例： nAll-D: 不论过去什么发生，总是选择不合作； nAll-C: 不论过去什么发生，总是选择合作； n合作-不合作交替进行； ntit-for-tat: 从合作开始，之后每次选择对方前一阶段的 行动； ntrigger (grim) strategy: 从合作开始，一直到有一方不 合作，然后永远选择不合作。 “囚徒困境”的一般表示 合作 不合作 合作不合作 T，TS，R R，SP，P 满足：RTPS; (S+R) U2 (TFT | TFT) 有无其他更有吸引力的策略 (TFT, TFT) 考虑另外一种情形:在第L回合偏离1次 （Deviate once in some round L，记作DEV1L). DEV1L: TFT 直至第 L回合. 采取 D 一次. 重新选择 C ，然后再回到TFT 局中人2有没有动机采取 DEV1L? (TFT, TFT) 1: C C C C C C C 2: C C C C C C C 0 1 2 L L+1 L+2 L+3 (TFT, DEV1L)1: C C C C D C C 2: C C C D C C C 阿克塞洛德 Axelrod (1984) nTit-for-tat 是成功率最高的战略 Robert Axelrod (The Evolution of Cooperation作者) 邀请提供重复 200次“囚徒困境”(依出招历史决定偏离或合作) 的动态策略： 1. 第一回合对14个策略加随机策略配对，发现TFT表现最好。 前八名均具“善意”(nice) 特性：在前面几回合中，都不是第一 个偏离合作，不是太富于竞争性 (not too competitive)。 不“宽恕”(not forgiving) 的策略 (像trigger strategy)：只 排到第七名。 Axelrod的研究 n狡猾 (sneaky) 的策略 (像TFT但采10% 机率偏离)：只排到第十二名。 n试探 (sophisticated) 策略：先偏离 以试探对手反应机制，依估计对手型态 的机率决定偏离或合作：只排到第十名 。 n随机 (random) 策略表现最差。 n但是，何种策略会成功不只由本身特性 决定，也由对手策略决定。 2. 第二回合对62个策略加随机策略配对，参加者均知第一次比赛 结果，有很多策略针对TFT而来。不再固定200次互动，而是每 次均有0.99机会继续下去，必须追踪共63x63=3969个结果。 以善意来区分：前15名有14个策略具善意，垫底15名有14个 策略不具善意。 nAxelrod 认为参赛者有两面向的考虑：“Be nice and forgiving”，也有人会设法利用这 种特性获利 “If others are nice and forgiving, it pays to try to take advantage of them”。但这种投机策略只落 到27及46名，因为对手最后会惩罚这种策略。 n在具善意的策略中可依响应偏离的速度来区 分，立即响应者为报复型 (retaliatory)。因 为会遇到试探型策略，延迟报复者会被剥削 (exploited)：报复型策略表现不差。 结果是具non-exploitability 的 TFT表现最好，tit-for-two-tats 只得到第24名，随机策略仍最差。 n3. 第三回合用演化博弈 (evolutionary game)来模拟这 些策略的消长，报酬高者后代也成比例增加，来看“优 胜劣汰”: n 第二回合表现最差的十余个策略在五代之后逐渐 灭绝，原中间名次者大体存活，而高名次者比例升高 ，最后达到共存的生态 (ecology)，这些策略在行动上 已无法分辨。 n 投机者刚开始获利，但被剥削者灭绝后，只遇到 会报复的对手，也因此灭绝。例如第二回合第八名 (前 15名中唯一非具善意的策略)，当猎物灭绝后也随之灭 绝。 Trigger strategy n如果未来足够重要，精炼纳什均衡： n结果发现 Tit-for-Tat (TFT) 的平均表现最好，虽然在各个赛局中 也给对方不错的报酬(双赢)。Axelrod认为TFT具有优势是因为符 合以下原则： n “nice, provocable, forgiving and clear. ” 最好的决策原则是 n “Dont be envious. Dont be the first to defect. Reciprocate both cooperation and defection. Dont be too clever.“ n有的策略 (nasty) 过份想占对手便宜，造成互不信任；有的策略 (nice) 又过于一厢情愿，反为对手利用。长期来说均非适当策略 。 n TFT的缺点：对手一偏离就立刻报复，一旦在执行过程中“意 外错误”，就会造成误解和互相报复无止境。 n nicer, more forgiving ? 合作的条件 n如果下列条件满足，合作就是均衡结果 ： 解释 nR-T可以理解为不合作的诱惑； nR-P是合作的剩余（利益）； n条件说明： n给定未来的重要程度，不合作的一次性诱惑 （R-T）相对于合作带来的利益（R-P）越小 ，合作的可能性越大； n给定不合作的诱惑和合作带来的利益，未来 越重要，合作的可能性越大； 行为的信息传递 n假如欺骗两次才被发现： 含义 n欺骗行为越难以被发现，欺骗发生的可 能性越大；或者说，合作越困难； n在前面的例子，R=0, T=-1, P=-8. 如果 欺骗一次就被发现，只要 合作就会出现；而如果欺骗两次才被发现 ，只有当 时，合作才可能出现； n一般地，欺骗行为越不容易被发现，合 作越困难。 惩罚与合作 nAbreu(1986)：最大合作战略是使用最严厉的 可信的惩罚； n维护合作并不需要无限期的惩罚；只要惩罚期 足够长就可以了； n胡萝卜加大棒（stick and carrot): 从合作开始，一直 合作直到：如果有任何一方在t期不合作，在t+1期， 前期合作者选择“不合作”来实施惩罚，前期不合作者 选择合作；如果该合作的没有合作或者该惩罚的没有 惩罚，在t+2期继续按照上述t+1期的战略规定博弈； 否则，合作恢复。 不可信的惩罚：垄断厂家 客户 商家 不购买 购买 诚实 欺骗 （5，5） （1，7） （0，0） 多重交易关系与合作行为 合作不合作 合作不合作 3，3-1，4 4，-10，0 合作不合作 合作不合作 5，50，9 9，04，4 交易关系I交易关系II 合作条件 n在交易关系I中，合作要求 n在交易关系II中，合作要求 n如果两种交易在同样的两个人之间进行，只 要 ，两 种交易中都会合作； n设想实的 ，那么如果两种交易 发生在不同的人之间，合作只出现在市场I ，不会出现于市场II。但如果两人之间同时 存在两种交易，合作存在于两个市场。 社会关系与合作行为 n更一般地讲，市场交易常常镶嵌在复杂 的社会关系中。这种关系可以提高交易 的合作程度。这也是人们愿意发展社会 关系的原因。 举例 n在交易关系II中，假定除了这一交易外， 当事人双方之间还存在另外的社会关系 ，这一社会关系对每一方的现值是V。如 果交易中出现欺骗，这一价值就不存在 。合作条件为： 应用 n家庭血缘关系； n朋友关系； n同学关系； n老乡关系（保姆市场）； 家族企业的困境 n如果惩罚对惩罚者本身的损害太大，惩 罚就是不可信的。这与投鼠忌器是一个 道理，你讨厌老鼠，但是你没有办法， 因为你心疼那个盘子，那个器皿。投鼠 忌器在我们企业内部很多环节都会发生 ，导致惩罚不可信，所以对方就不会太 注重信誉。家族成员有时候比非家族成 员更不可信任，更不守规矩，就是这个 道理。 第三方实施的惩罚 n前面假定了固定的一对参与人进行重复博弈， 对不合作的惩罚是由“受害人”本人实施的。 n但更经常的情况是参与人不固定的情况。此时 ，惩罚要由第三方实施。 n问题是第三方惩罚欺骗别人的同时，自己可能 失去合作带来的好处。 长期参与人与不固定的短期参与人 n最简单的例子是厂家与消费者之间的博 弈：每个消费者一般只购买一次，而厂 家重复出售产品给众多的消费者。 n此时，只要消费者足够多，并且每个消 费者能观察到前一个消费者购买的产品 的质量，合作仍然可以出现。 产品质量博弈 购买 不购买 高质量低质量 1，1-1，2 0，00，0 Klein-Leffler Model n如果 ，下列战略组合构成一个精炼纳 什均衡：厂家开始生产高质量；继续生产高质 量，除非曾经生产过低质量；如果上一期生产 了低质量，之后永远生产低质量；消费者：第 一个消费者购买；只要低质量事件没有发生过 ，之后的消费者继续购买；但一旦发现低质量 ，之后的消费者不再购买； n结果：（购买，高质量） 社团内的博弈 B H EG F A C D 社团内的博弈 B H EG F A C D 第三方惩罚问题 n如果A欺骗了B，其他成员是否应该惩罚A ？ n如果C惩罚A，C就失去了与A合作的机会 ，C为什么要替B惩罚A？ 社会规范：集体抵制 n联合抵制: 每个人都应该诚实；都有责任 惩罚骗过人的人；不参与惩罚的人应该 受到惩罚；如：假定A在t期欺骗了B，C 在t+1期就不应该与B合作，否则，D在 t+2期就不应该与C合作；如果C在t+1期 与B合作，而D在t+2期又与C合作，F在 t+3期就不应该与D合作，如此等等； 敌友规则 n开始把所有的人当朋友；t期的朋友关系继续保 持到t+1期，当只当他在t期不曾骗过任何人并 不曾与你的敌人合作； n朋友的朋友是朋友； n朋友的敌人是敌人； n敌人的朋友是敌人； n敌人的敌人未必是朋友。 精炼纳什均衡 n如果每