第9讲博弈论重复博弈

1、蔡树66162）科技楼14062 为什么现实生活中并不总是出现“囚徒困境”？3重复博弈4重复博弈引论为何研究重复博弈 经济中的长期关系 人们的预见性 未来利益对当前行为的制约 长期合同、回头客、长客和一次性买卖的区别 有无确定的结束时间5无限次重复博弈：一个基本博弈G一直重复博弈下去的博弈 G() 策略：博弈方在每个阶段针对每种情况如何行为的计划子博弈：从某个阶段（不包括第一阶段）开始，包括此后所有的重复博弈部分均衡路径：由每个阶段博弈方的行为组合串联而成6重复博弈和无名氏定理 重复十次 （1）两人同时选好十次策略 （2）两人一次博弈接一次博弈，10次 （3）一人先选

2、一人后选，10次图图2-27 囚徒困境问题囚徒困境问题坦白抵赖坦白-8，-80，-10抵赖-10, 0-1,-1囚徒囚徒2囚徒囚徒17重复博弈和无名氏定理 重复博弈(repeated game)的定义 指同样结构的博弈重复多次，其中的每次博弈称为“阶段博弈(stage game)”。 如两个多次犯罪的“囚徒问题”。 由于动态博弈是相机行动，反映到重复博弈中，就是可以使自己在某个阶段的博弈选择依赖于其他参与人过去的行动历史。8重复博弈与策略空间的扩展 如囚徒困境的重复博弈的一个策略可以是：“如果这次你选择了坦白，我下次将选择坦白；如果你这次选择了抵赖，我下次将选择抵赖” 。 因此，参与人在重复博

3、弈中的策略空间远远大于和复杂于在每个阶段博弈中的策略空间。假定上属博弈重复多次或无限次；那么，每个参与人有多个可以选择的战略：仅举几例：All-D: 不论过去什么发生，总是选择不合作；All-C: 不论过去什么发生，总是选择合作；合作-不合作交替进行；tit-for-tat: 从合作开始，之后每次选择对方前一阶段的行动；trigger strategies: 从合作开始，一直到有一方不合作，然后永远选择不合作。910 两个均衡11均衡： （进入，合谋）为什么实际上还是有很多会选择（进入，斗争）？12重复博弈和无名氏定理 如此一直倒推回去，我们得到这个博弈的唯一子博弈精炼均衡是在位者在每一个市场

4、上都选择默许，进入者在每一个市场上选择进入。 这就是所谓的“连锁店悖论”(chain-store paradox, Selten,1978) 因为实际生活中，进入者和在位者在每个市场都斗得你死我活13有限次重复博弈定理 令G是阶段博弈，G(T)是G重复T次的重复博弈(T)。如果G有唯一的纳什均衡，重复博弈G(T)的唯一子博弈精炼纳什均衡结果是: 阶段博弈G的纳什均衡重复T次（即每个阶段博弈出现的都是一次性博弈的均衡结果）。 只要博弈的重复次数是有限的，重复本身并不改变囚徒困境的均衡结果。 条件： “唯一性”：如果纳什均衡不是唯一的，那会怎么样？ 有限性：如果博弈重复无限次，那会怎么样？ 时间性

5、：如果每次博弈的收益受到时间（贴现率、利率、风险、通货膨胀）的影响 ，那会怎么样？14多个均衡的重复博弈 (H,H)是“合作”，但不是NE NE为（M,M）(L,L) 纯策略=动作 混合策略=? 条件策略(H|M,M|H, L|L) 其他策略15多个均衡的重复博弈 两阶段博弈 (HH,HH)仍然不是NE1617等价于一次博弈 HH是均衡，所以没有人愿意偏离18 如果背叛，今天的收益加1，但是明天的收益减2（合作的收益为3，背叛的收益为1）19眼前利益与长远利益欺骗的短期收益信誉的长期收益时间20 当博弈有多个纳什均衡时，参与人可以使用不同的纳什均衡惩罚前面阶段的不合作行为或奖励第一阶段的合作行

6、为。 从而迫使大家合作21人们为什么会做好事（合作）？因为有明天的回报，或者避免明天的惩罚。人的理性就在于，为了将来更大的利益，可以牺牲眼前利益。大部分的小孩和动物，一般就做不到这一点。今天欺骗的收获今天欺骗的收获 合作后的收获（承诺）合作后的收获（承诺） 欺骗后的收获（威胁）欺骗后的收获（威胁）教训：在发展关系的时候，承诺合作后的收益以及威胁欺骗的惩罚，教训：在发展关系的时候，承诺合作后的收益以及威胁欺骗的惩罚， 有时能够激励今天良好行为的发生。有时能够激励今天良好行为的发生。 而这种行为，有助于创建一个好的未来！而这种行为，有助于创建一个好的未来！22先别急着吃棉花糖 有三只青蛙在河中的一

7、片叶子上顺水漂流。其中一只想跳到河里。在叶子上还剩几只青蛙？ 吃掉棉花糖等于吃掉未来! http:/ 美国的斯坦福大学曾进行过一个著名的棉花糖实验。在这个实验里，把小孩子单独留在房间里，并给他们一人一块棉花糖，让他们选择是要马上吃掉棉花糖，还是等待十五分钟。如果愿意等，就可以再多得一块棉花糖作为奖赏。研究结果发现，为了获得奖赏，能够抗拒眼前棉花糖的诱惑而等待十五分钟的小孩，长大以后，普遍都比那些马上吃掉棉花糖的小孩们更成功 23无限次重复博弈图图2-27 囚徒困境问题囚徒困境问题坦白抵赖坦白-8，-80，-10抵赖-10, 0-1,-1囚徒囚徒2囚徒囚徒124 首先，（一直坦白，一直坦白）可以

8、是一个均衡 有没有其他的均衡？ 也即：有没有其他的策略，当双方都采用该策略之后，就没有人反悔去用其他策略？ 如果你知道对方会一直坦白，那么你的最佳应对是一直坦白 T,T,T,T, T,T,T,T,25 考虑下列所谓的“冷酷策略”(grim strategies): 开始时选择抵赖； 选择抵赖直到有一方选择了坦白，然后永远选择坦白。重复博弈和无名氏定理图图2-27 囚徒困境问题囚徒困境问题坦白抵赖坦白-8，-80，-10抵赖-10, 0-1,-1囚徒囚徒2囚徒囚徒126 D,D,D,D,D,D, D,D,D,D,D,D, T,T,T,. T,D,T,D,T,. T,D,D,D,D, D,T,T,

9、T,T,.27重复博弈和无名氏定理 首先证明冷酷策略是一个纳什均衡 回顾一下，所谓纳什均衡，就是这样的一个状态，对于任意一个参与人，给定其他参与人选择纳什均衡策略，该参与人都无法偏离纳什均衡策略。 因此，证明囚徒问题中冷酷策略是一个纳什均衡的方法是：给定其中任意一个参与人坚持“冷酷战略”，另外一个参与人的最优选择也是坚持冷酷战略。28 如果i在博弈的某个阶段首先选择了坦白，在该阶段得到0单位的支付，优于选择抵赖得到的-1。 但这个机会主义行为将触发他的伙伴选择“永远坦白”的惩罚，因此i随后每个阶段的支付都是-8。（-1是奖励，-8是惩罚） 因此，如果下列条件满足，给定对手没有选择坦白，i将不会

10、选择坦白0( 8)( 8).1 ( 1)( 1). 这个不等式是否正确？有限和无限的不同，希尔伯特旅馆的故事29另外一种计算方法0( 1)( 1 ( 8)( 1 ( 8).177. 这个策略为什么不适用于两阶段（有限）重复博弈？0( 1)( 1 ( 8)17 因为有逆向归纳法：大家在第二阶段肯定都坦白，也即，第二阶段肯定是-8，不会有-10( 1)( 8( 8)10 30 所以，无限很重要 给你100万，你愿意今天要这个钱还是明天（10年后）要这个钱？Why？ 今天的钱并不等于明天的钱：利率 明天的钱并不等于今天的钱：贴现率31贴现率将未来资产折算成现值(present value)的利率，一

11、般是用当时零风险的利率来当作贴现率，但并不是绝对。举个例子：贴现率为10%，明年的100块在今年就相当于100/（1+10%）=90.909090.块钱，到了去年就是100/（1+10%）*（1+10%），也就是说，今年用90.909090.块可以买到的东西相当于明年100块可以买到的东西。 今天投资100万元的项目，将来如能收回200万，也不能证明此项投资一定有效。因为如果这回收的200万要等50年之后，今天衡量的价值就远低于100万。这是由于如果利率是3%，100万元存银行，50年内得到的利息也将达338万元（利率为2%的话，50年的利息为169万元）。所以50年后回收200万的投资与存银

12、行得利息相比不值得去做。 贴现率：将来的钱现在花，把将来的钱借给现在利率：现在的钱存起来将来花，把现在的钱借给将来32考虑贴现因子的重复博弈 设a为贴现因子（假定两人贴现因子相同）。贴现因子=1/（1+贴现率） 如果i在博弈的某个阶段首先选择了坦白，在该阶段得到0单位的支付，优于选择抵赖得到的-1。 但这个机会主义行为将触发他的伙伴选择“永远坦白”的惩罚，因此i随后每个阶段的支付都是-8。 因此，如果下列条件满足，给定对手没有选择坦白，i将不会选择坦白.) 1() 1(1.) 8() 8(022aaaaaaa1118即33230( 1)( 1 ( 8)( 1 ( 8).1777.117 ()1

13、aaaaaaaa q a 1/8q a太小，则将来的钱根本不管用，将来不值得期待（有未来，但是更期待今天）q 因此，冷酷战略是一个纳什均衡。34重复博弈和无名氏定理 该策略是否是子博弈精炼均衡？ 因为博弈重复无限次，从任何一个阶段开始的子博弈与这个博弈的结构完全相同。 在冷酷战略均衡下，子博弈可以分为两类：在类型a，没有任何参与人曾经坦白；在类型b，至少有一个参与人曾经坦白。35重复博弈和无名氏定理 在类型a中，我们已经证明，冷酷战略在a类型子博弈中构成纳什均衡； 在b类子博弈中，根据冷酷战略，参与人只是重复单阶段博弈的纳什均衡，因此也是子博弈的纳什均衡。 因此，如果a 1/8，冷酷战略是无限

14、次囚徒博弈的一个子博弈精炼纳什均衡。36重复博弈和无名氏定理 该博弈还有许多其他子博弈精炼均衡。 各期都坦白，是另一个子博弈精炼纳什均衡 子博弈精炼均衡的多重性是无限次重复博弈的普遍问题。37更多例子 无限次重复古诺模型 支持垄断产量的条件：P194-195 低水平的合作：P195-197 加大惩罚力度和提高合作水平：P197-199 复杂的现实（OPEC）：P199-200 工资：P200-2053839Axelrod (1984)qTit-for-tat 是成功率最高的战略4041惩罚与合作 Abreu(1986)：最大合作战略是使用最严厉的可信惩罚（the strongest credi

15、ble punishment); 维护合作并不需要无限期的惩罚；只要惩罚期足够长就可以了； 萝卜加大棒（stick and carrot): 从合作开始，一直合作直到：如果有任何一方在t期不合作，在t+1期，前期合作者选择“不合作”来实施惩罚，前期不合作者选择合作；如果该合作的没有合作或者该惩罚的没有惩罚，在t+2期继续按照上述t+1期的策略规定博弈；否则，合作恢复。42 仁：人不犯我，我不犯人仁：人不犯我，我不犯人 怒：以眼还眼，以手还手怒：以眼还眼，以手还手 即：（君子报仇，十年不晚）即：（君子报仇，十年不晚） 恕：宽恕对方，宽以待人恕：宽恕对方，宽以待人 信：说到做到信：说到做到43概率

16、问题有可能有限，有可能无限明天是否继续是一个概率事件什么情况？人们也是倾向于合作如果没有明天，今天就会为非作歹如果没有明天，今天就会为非作歹如果有无限多明天，作恶不惩罚，今天就会为非作歹如果有无限多明天，作恶不惩罚，今天就会为非作歹如果有无限多明天，作恶会惩罚，今天就会合作如果有无限多明天，作恶会惩罚，今天就会合作如果明天有可能或者，也有可能挂掉，作恶会惩罚，则今天有可能合如果明天有可能或者，也有可能挂掉，作恶会惩罚，则今天有可能合作，合作的可能性看明天挂掉的概率和作恶惩罚的力度作，合作的可能性看明天挂掉的概率和作恶惩罚的力度44不可信的惩罚：垄断厂家客户商家不购买购买诚实欺骗（5，5）（1，

17、7）（0，0）45不确定性下的最优处罚 在确定的情况下，惩罚越严厉，越有助于合作。因为均衡情况下，欺骗从来不会发生，所以惩罚实际上是没有成本的。 但在不确定的情况下，即使每个人都选择合作，“坏结果”也会出现。如果坏结果总是触发惩罚，就会冤枉好人，过重的惩罚反到导致不合作；但如果总是原谅，合作也不会发生。46家族企业的困境；“杀熟” 如果惩罚对惩罚者本身的损害太大，惩罚就是不可信的。这与投鼠忌器是一个道理，你讨厌老鼠，但是你没有办法，因为你心疼那个盘子，那个器皿。投鼠忌器在我们企业内部很多环节都会发生，导致惩罚不可信，所以对方就不会太注重信誉。家族成员有时候比非家族成员更不可信任，更不守规矩，就

18、是这个道理。 朋友专门骗朋友，是“杀熟”。问题也与惩罚的不可信有关。47长期参与人与不固定的短期参与人 最简单的例子是厂家与消费者之间的博弈：每个消费者一般只购买一次，而厂家重复出售产品给众多的消费者。 此时，只要消费者足够多，并且每个消费者能观察到前一个消费者购买的产品的质量，合作仍然可以出现。48产品质量博弈产品质量博弈购买不购买高质量低质量1，1-1，20，00，049社会规范：集体抵制 Boycott: 每个人都应该诚实；都有责任惩罚骗过人的人；不参与惩罚的人应该受到惩罚；如：假定A在t期欺骗了B，C在t+1期就不应该与B合作，否则，D在t+2期就不应该与C合作；如果C在t+1期与B合

19、作，而D在t+2期又与C合作，F在t+3期就不应该与D合作，如此等等； （美国对不参与伊拉克战争的国家的态度）；50敌友规则 开始把所有的人当朋友；t期的朋友关系继续保持到t+1期，当只当他在t期不曾骗过任何人并不曾与你的敌人合作； 朋友的朋友是朋友； 朋友的敌人是敌人； 敌人的朋友是敌人； 敌人的敌人未必是朋友。51传统社会的个人信誉传统社会的个人信誉q在传统社会，人们常年生活在封闭的村庄，村民之间彼此非常熟悉，欺骗行为很容易识别，人们之间的口头交流足以使任何欺骗行为广为而知，每个人的历史都存储在别人的脑海里，对欺骗行为的惩罚即使不能施加于欺骗者本人，也可以通过家庭成员而实现，前面讲的四个条件基本是可以得到满足。因此，即使没有法律，村民之间也可以建立起高度的信任，欺骗行为很少发生。计算机中的博弈（大作业） 调研博弈在计算机中的应用情况，给出自己