第三讲 动态博弈与逆向归纳法.ppt

1、趣味博弈论,杨驭云 华南师范大学南海校区,第三讲 动态博弈与逆向归纳法,动态博弈,博弈的本质在于各参与者的决策相互依存，这种相互作用或者互动通过两种方式体现出来。,第一种方式：参与者同时行动或者虽非同时行动，但后行动者并不知道先行动者的选择。比如石头、剪刀、布，还有囚徒困境。 这一类博弈称为静态博弈。,第二种方式：参与者的行动有先后顺序，后行动者可以观察到先行动者做了什么选择，先行动者的选择影响后行动者的选择空间。 此类博弈称为动态博弈。,21支旗游戏,美国哥伦比亚广播公司的电视真人秀节目Survivor （幸存者）中有这样一个游戏： 地面插着21支旗，两个人轮流移走这些旗。每个人在轮到自己时

2、可以选择移走1支、2支或3支旗。拿走最后1支旗的人获胜，无论这支旗是最后1支，还是2支或3支中的一支。,请大家两两配对来玩这个游戏，轮流充当先行者。时间为10分钟。,你是跟着感觉走来玩这个游戏吗？,你是否发现越玩到后面、剩下的旗越少的时候就越清晰地知道自己正确的策略是什么？,那就让我们向前展望、倒后推理，即面向未来，思考现在，站在未来的立场来确定现在的最优行动。,倒数第二步，你必须留给对方4支旗。,倒数第三步，你必须留给对方8支旗。,依此类推，你必须依次给对方留下12、16、20支旗来确保取胜。,所以，在这个游戏中，先行者能确保取胜。 但如果游戏开始时是20支旗，那么后行者能确保取胜。,这是一

3、个典型的完全完美信息动态博弈。 完全信息：每个参与者的策略集合及收益函数均为博弈各方的共同知识。 完美信息：每个参与者都知道先前行动的参与者采取了什么策略。,序贯理性：每个参与者在其每一个决策时点上都将重新优化自己的选择，并且会把自己将来会重新优化其选择这一点也纳入当前的优化决策当中。 在序贯理性下不会有“后悔”出现。 “每个参与者是序贯理性的”是博弈的共同知识。,序贯理性,逆向归纳法：按与博弈进行顺序相反的方向逐一找出每个参与者在其所有决策时点上的最优策略选择，直到第一个决策时点为止。 “每个参与者是序贯理性的”是逆向归纳法的基础。,逆向归纳法,索马里海盗人力资源部招聘启事,你忍心蜗居在不到

4、10平米的小屋里吗？你忍心看着自己的女友和你奋斗一辈子还供不起一套房吗？你忍心看着父母缩衣节食把仅有的一点养老金帮你还房贷吗？ 这里才是实现你梦想的地方。加入我们，待遇从优，装备齐全，食宿全免，一条大裤衩，一双人字拖，一把AK47，800美元底薪+提成，全天移动式海景套房，多劳多得。只要大干一票，在大都市买楼不再是梦想；干两票，跻身上层社会，直接与奥巴马对话不再是距离。别再犹豫了，给你一片海域，换你一生奇迹！,海盗分金,有10名海盗抢得了100块金子，并打算瓜分这些战利品。这是一些讲民主的海盗，也就是遵循少数服从多数原则，他们按照习惯的方式进行分配：最厉害的一名海盗提出分配方案，然后所有的海盗

5、包括提出方案本人就此方案进行表决。如果半数以上（含半数）的海盗赞同这一方案，那么这一方案就获得通过并按照这一方案进行战利品的分配；否则，提出方案的海盗将被扔进海里喂鲨鱼，然后剩余海盗中最厉害的海盗又重复上述过程。,假设：没有两名海盗是同等厉害的；这些金块不能再分，也不允许几名海盗共有1块金子。 那么，最厉害的一名海盗应该提出什么样的分配方案呢？,考虑到分析的便利，这里按照这些海盗能力的差异给他们编上序号。最怯懦的海盗为1号海盗，次怯懦的海盗为2号海盗，依此类推，最厉害的海盗为10号海盗。,海盗们基于三个因素来做决定：首先，自己要能存活下来；其次，自己得到的利益最大化；最后，在所有其它条件相同的

6、情况下，优先选择把别人扔进海里。,这些海盗残酷的分配规则给人的第一印象是：最厉害的那名海盗是个多么不幸的人啊！因为作为头一个提出方案的人，仅仅能活下来的机会都微乎其微：即使他自己一分不要，把金子全部送给另外9人，那些人可能也不赞同他的分配方案，那么他只有死路一条！,真的是这样吗？,任何一个海盗想让自己的方案获得通过的关键是事先考虑清楚“继承者”的分配方案是什么，然后拉拢“继承者”分配方案中最不得意的人们，争取用最小的代价获取最大收益。 因此，推理过程应该是从后向前，因为越往后策略越容易看清。,分析的出发点应该是博弈进行到只剩两名海盗，即1号和2号的时候。这时最厉害的海盗是2号，而他的最佳分配方

7、案一目了然：100块金子全归他一人所有，1号海盗什么也得不到。 为什么呢？,现在加上3号海盗。 1号海盗知道：如果3号的方案被否决，那么最后只剩两个海盗，而1号将肯定一无所获；另外，3号也明白1号了解形势。因此，只要3号的分配方案给1号一点儿甜头使他不至于空手而归，那么不论3号提出什么样的分配方案，1号都将投赞成票，因此3号需要分出尽可能少的一点儿金子来收买1号海盗。,那么，3号海盗会提出什么样的分配方案呢？,答案是：3号海盗分得99块金子，2号海盗一无所获，1号海盗分得1块金子。,4号海盗的策略也差不多。他需要有半数以上的支持票，因此同3号一样也需要再找一人做同谋。他可以给同谋的最低贿赂是1

8、块金子，在这里，他可以用这块金子来收买2号海盗。因为如果4号被否决而3号得以通过，则2号将一无所获。,因此，4号的分配方案就是：99块金子归自己，2号得1块金子，1号和3号什么也得不到。,5号海盗的策略略有不同。他需要收买另外两名海盗，因此至少得用两块金子来贿赂才能使自己的方案得到采纳。他的分配方案应该是： 98块金子归自己，1块金子给3号，1块金子给1号。,这一分析过程可以按照上述思路继续进行下去。每个分配方案都是唯一确定的，它可以让提出这个方案的海盗获得尽可能多的金子，同时保证该方案肯定能获得通过。,10号海盗提出的方案将是：96块金子归自己所有，其他编号为偶数的海盗各得1块金子，而编号为

9、奇数的海盗什么也得不到。,如果海盗的人数变成了100人，金子仍然是100块。那么，最厉害的海盗，也就是编号100的海盗，他的方案应该是什么呢？,100号海盗提出的方案将是：51块金子归自己所有，其他编号为偶数的海盗各得1块金子，而编号为奇数的海盗什么也得不到。,如果海盗的人数变成了200人，金子仍然是100块。那么，最厉害的海盗，也就是编号200的海盗，他的方案应该是什么呢？,所有偶数号的海盗将各得1块金子，而所有奇数号的海盗将一无所获。,如果海盗人数为201人呢？,201号海盗的分配方案是：给1到199号的所有奇数号海盗每人一块金子，自己则一块也不要。虽然分不到金子，至少保证了自己不会被扔进

10、海里喂鲨鱼。,如果海盗人数为202人呢？,202号海盗同样别无选择，只能1块金子都不要了，他必须把这100块金子全部用来收买100名海盗，而且这100名海盗还必须是那些按照201号方案将一无所获的人。由于这样的海盗有101名，因此202号的方案将不再是唯一的，因为贿赂方案有101种。,如果海盗人数为203人呢？,203号海盗必须获得102张赞成票，但他显然没有足够的金子去收买101名同伙。因此，无论提出什么样的分配方案，他都注定会被扔进大海喂鲨鱼。 悲催啊！,如果海盗人数为204人呢？,204号海盗知道，203号为了能保住性命，就必须避免由他自己来提出分配方案这样一种局面，因此不管204号提出

11、什么样的方案，203号都一定会投赞成票。这样，204号海盗总算可以拣到一条命：他可以得到他自己的1票、203号的1票以及另外100名被收买的海盗的赞成票，刚好达到保命所需的一半票数。获得金子的海盗，就是根据202号方案肯定一无所获的那100名海盗，即1到199号的所有奇数号海盗。,如果海盗人数为205人呢？,205号海盗没有那么走运了。他不能指望203号和204号支持他的方案，因为如果他们投票反对205号方案，就可以看到205号被扔进海里，而他们自己的性命却仍然能够保全。这样，无论205号海盗提出什么方案都活不了命。,206号海盗的命运也是这样。他肯定可以得到205号的支持，但这不足以救他一命

12、。,同样，207号海盗需要104张赞成票，除了他收买的100张赞成票以及他自己的1张赞成票之外，他还需3张赞成票才能免于一死。他可以获得205号和206号的支持，但还差1张票却是无论如何也弄不到了，因此207号海盗的命运也是被扔进大海里。,可是，208号海盗却又时来运转了。他需要104张赞成票，而205、206、207都会支持他，加上他自己一票及收买的100票，他得以过关保命。获得他贿赂的必定属于那些根据204号方案肯定将一无所获的人，候选人包括2到200号中所有偶数号的数，以及201、202、203、204号。,现在，出现了一条新的并在此之后会持续有效的规律：那些方案能过关的海盗的分配方案全

13、都是把金子用来收买100名同伙而自己一点都得不到，他们相隔的距离越来越远，而在他们之间的海盗则无论提什么样的方案都会被扔进大海，因此为了保命，他们必定会投票支持比他们厉害的海盗提出的任何分配方案。,得以避免葬身鱼腹的海盗包括：201、202、204、208、216、232、264、328、456号，也就是其号码等于200加上2的某一幂的海盗。,那么，哪些海盗是获得贿赂（1块金子）的人呢？,分配贿赂的方法不是唯一的，其中一种方法是让201号海盗把贿赂分给1到199号的所有奇数编号的海盗，让202号分给2到200号的所有偶数编号的海盗，然后是让204号贿赂奇数编号的海盗，208号贿赂偶数编号的海盗

14、，依此类推，也就是轮流贿赂奇数编号和偶数编号的海盗。,如果表决的规则是必须超过半数赞同时才通过分配方案，假设是5名海盗和100块金子。5号海盗应该提出什么样的分配方案呢？,蜈蚣博弈悖论,悖论，是一种逻辑矛盾，它指这样一个命题：由它的真可以推出它的假；相反，由它的假又可以推出它的真。,理发师悖论,小城里的理发师放出豪言：“我帮且只帮城里所有不自己刮脸的人刮脸”。 理发师该给自己刮脸吗？,蜈蚣博弈是由罗森塞尔（Rosenthal ）在1981年提出的一个完全完美信息条件下的动态博弈问题。由于这个博弈的扩展形式很像一条蜈蚣，因此被称为“蜈蚣博弈”。,两个参与者A、B轮流进行策略选择，可供选择的策略有

15、“合作”和“不合作”两种。当出现“不合作”时，博弈结束。 规则是：A、B两次决策为一组，进行至第n组时，若A决策结束，则A、B的收益都是n；若B决策结束，则A得n-1，B得n+2。 假定A先选，然后是B，接着是A，如此交替进行。另外，A、B之间的博弈次数为有限次，比如198次。若双方始终选择“合作”，则最后A、B的收益都是100。,A、B该如何进行策略选择呢？,当A决策时，他考虑博弈的最后一步即第198步。B在“合作”和“不合作”之间作出选择时，因“合作”给B带来100的收益，而“不合作”带来101的收益，根据“理性人”的假定，B会选择“不合作”。,但是，要经过第197步才到第198步。在第1

16、97步，A考虑到B在第198步时会选择“不合作”，此时他的最优策略是“不合作”“不合作”的收益99大于“合作”的收益98。 因此，在第197步时A会选择“不合作”。,同样，要经过第196步才到第197步。在第196步时，B考虑到A在第197步时会选择“不合作”，此时他的最优策略是“不合作”“不合作”的收益100大于“合作”的收益99。 因此，在第196步时B会选择“不合作”。,如此推论下去，最后的结论是：在第1步时A将选择“不合作”，博弈结束，此时双方的收益均为1。 这个结果是令人悲伤的。,从逻辑推理来看，逆向归纳法是严密的，但结论是违反直觉的。 直觉告诉我们，一开始就采取“不合作”的策略获取

17、的收益只能为1，而采取“合作”策略有可能获取的收益为100，因此A应采取“合作”的策略。而从逻辑的角度，一开始A就应采取“不合作”的策略。,有实验经济学家做过蜈蚣博弈的实验，实验的结果显示不会出现一开始选择“不合作”策略而使双方获得收益1的情况。参与者都会自动选择合作性策略，从而走向合作。 人们在博弈中的真实行动“偏离”了运用逆向归纳法关于博弈的理论预测，造成二者间的矛盾和不一致，这就是蜈蚣博弈的悖论。,逆向归纳法在逻辑上是严密的，然而它存在着“困境”，蜈蚣博弈悖论恰好反映了这种“困境” 。,蜈蚣博弈悖论的产生其实是源于逆向归纳法的适用范围问题，即逆向归纳法只是在一定的条件下和一定的范围内有效

18、，忽略了这一点笼统去谈论逆向归纳法的有效性不是科学的研究思路。,第一，从逆向归纳法的适用范围来看，应当避免在较长阶段的动态博弈中使用逆向归纳法。博弈的阶段数不同，博弈方的策略选择会有很大的差异。,以下象棋为例说明这个问题。下象棋是一种完全完美信息动态博弈，而且博弈阶段和路径数量是有限的，但由于象棋博弈的路径数量很大、分支选择很多，即使用最先进的电子计算机也无法在短时间内找出每步的最优决策，因此不可能有人一开始就用逆向归纳法下棋。但是实践却表明，下棋人往往在象棋博弈的局部阶段，即在有限步数、有限选择的范围内局部地使用逆向归纳法。正因为如此，才有“下一步看三步”的说法。,又如，在蜈蚣博弈中，如果蜈蚣博弈的阶段数大大减少，比如说只有6步，那么开始时合作的