几个不错的博弈和决策的例题

An example of decision-making by backward induction

Consider an unemployed person who will be able to work for ten more years t = 1,2,...,10. Suppose that each year in which she remains unemployed, she may be offered a 'good' job that pays $100, or a 'bad' job that pays $44, with equal probability (50/50). Once she accepts a job, she will remain in that job for the rest of the ten years. (Assume for simplicity that she cares only about her monetary earnings, and that she values earnings at different times equally, i.e., the interest rate is zero.)

Should this person accept bad jobs? To answer this question, we can reason backwards from time t = 10.

* At time 10, the value of accepting a good job is $100; the value of accepting a bad job is $44; the value of rejecting the job that is available is zero. Therefore, if she is still unemployed in the last period, she should accept whatever job she is offered at that time.
* At time 9, the value of accepting a good job is $200 (because that job will last for two years); the value of accepting a bad job is 2*$44 = $88. The value of rejecting a job offer is $0 now, plus the value of waiting for the next job offer, which will either be $44 with 50% probability or $100 with 50% probability, for an average ('expected') value of 0.5*($100+$44) = $72. Therefore regardless of whether the job available at time 9 is good or bad, it is better to accept that offer than wait for a better one.
* At time 8, the value of accepting a good job is $300 (it will last for three years); the value of accepting a bad job is 3*$44 = $132. The value of rejecting a job offer is $0 now, plus the value of waiting for a job offer at time 9. Since we have already concluded that offers at time 9 should be accepted, the expected value of waiting for a job offer at time 9 is 0.5*($200+$88) = $144. Therefore at time 8, it is more valuable to wait for the next offer than to accept a bad job.

It can be verified by continuing to work backwards that bad offers should only be accepted if one is still unemployed at times 9 or 10; they should be rejected at all times up to t = 8. The intuition is that if one expects to work in a job for a long time, this makes it more valuable to be picky about what job to accept.

A dynamic optimization problem of this kind is called an optimal stopping problem, because the issue at hand is when to stop waiting for a better offer. Search theory is the field of microeconomics that applies problems of this type to contexts like shopping, job search, and marriage.--http://en.wikipedia.org/wiki/Backward_induction

逆向归纳法是求解动态博弈的具有演绎性质的方法，然而在蜈蚣博弈（罗森塔尔于1981年提出）之中由它得到的纳什均衡解因不合理，违反直觉而被认为是一个悖论。本文通过引进新的合作性的均衡解概念，使该悖论得到消解。合作性均衡是博弈参与人通过讨价还价这样的“言语行为”在“交流”中得以实现的，而由逆向归纳法得到的完美纳什均衡是在“沉默”中实现的。合作性的均衡所实现的是交流合理性，它能够使所有博弈参与人的支付都得到提高。 --http://www.cqvip.com/qk/92803X/200512/20890844.html

在图中，博弈从左到右进行，横向连杆代表合作策略，向下的连杆代表不合作策略。每个人下面对应的括号代表相应的人采取不合作策略，博弈结束后，各自的收益，括号内左边的数字代表A的收益，右边代表B的收益。如果一开始A就选择了不合作，则两人各得1的收益，而A如果选择合作，则轮到B选择，B如果选择不合作，则A收益为0，B的收益为3，如果B选择合作，则博弈继续进行下去。

可以看到每次合作后总收益在不断增加，合作每继续一次总收益增加1，如第一个括号中总收益为1＋1＝2，第二个括号为0＋3＝3，第二个括号则为2＋2＝4。这样一直下去，直到最后两人都得到10的收益，总体效益最大。遗憾的是这个圆满结局很难达到！

大家注意，在上图中最后一步由B选择时，B选择合作的收益为10，选择不合作的收益为11。根据理性人假设，B将选择不合作，而这时A的收益仅为8。A考虑到B在最后一步将选择不合作，因此他在前一步将选择不合作，因为这样他的收益为9，比8高。B也考虑到了这一点，所以他也要抢先A一步采取不合作策略……如此推论下去，最后的结论是：在第一步A将选择不合作，此时各自的收益为1！这个结论是令人悲伤的。

不难看出，在该博弈的推理过程中，运用的是逆推法。从逻辑推理来看，逆推法是严密的，但结论是不合理的。因为一开始就停止的策略A、B均只能获取1，而采取合作性策略有可能均获取10，当然A一开始采取合作性策略有可能获得0，但1或者0与10相比实在是很小。直觉告诉我们采取“合作”策略是好的。而从逻辑的角度看，A一开始应选择“不合作”的策略。人们在博弈中的真实行动“偏离”了运用逆推法关于博弈的理论预测，造成二者间的矛盾和不一致，这就是蜈蚣博弈的悖论。
A------B------A------B------A------B------A------B------A------A------B------(10,10)
|******|******|******|******|******|******|
(1,1)**(0,3)**(2,2)**(8,8)**(7,10)*(9,9)**(8,11)--http://www.changhai.org/forum/article_load.php?fid=6&aid=1168864387

介绍一个经典案例。


5个海盗抢得100枚金币后，讨论如何进行公正分配。他们商定的分配原则是：
（1）抽签确定各人的分配顺序号码（1，2，3，4，5）；
（2）由抽到1号签的海盗提出分配方案，然后5人进行表决，如果方案得到超过半数的人同意，就按照他的方案进行分配，否则就将1号扔进大海喂鲨鱼；
（3）如果1号被扔进大海，则由2号提出分配方案，然后由剩余的4人进行表决，当且仅当超过半数的人同意时，才会按照他的提案进行分配，否则也将被扔入大海；
（4）依此类推。这里假设每一个海盗都是绝顶聪明而理性，他们都能够进行严密的逻辑推理，并能很理智地判断自身的得失，即能够在保住性命的前提下得到最多的金币。同时还假设每一轮表决后的结果都能顺利得到执行，那么抽到1号的海盗应该提出怎样的分配方案才能使自己既不被扔进海里，又可以得到更多的金币呢？


此题公认的标准答案是：1号海盗分给3号1枚金币，4号或5号2枚金币，自己则独得97枚金币，即分配方案为（97，0，1，2，0）或（97，0，1，0，2）。现来看如下各人的理性分析：


首先从5号海盗开始，因为他是最安全的，没有被扔下大海的风险，因此他的策略也最为简单，即最好前面的人全都死光光，那么他就可以独得这100枚金币了。


接下来看4号，他的生存机会完全取决于前面还有人存活着，因为如果1号到3号的海盗全都喂了鲨鱼，那么在只剩4号与5号的情况下，不管4号提出怎样的分配方案，5号一定都会投反对票来让4号去喂鲨鱼，以独吞全部的金币。哪怕4号为了保命而讨好5号，提出（0，100）这样的方案让5号独占金币，但是5号还有可能觉得留着4号有危险，而投票反对以让其喂鲨鱼。因此理性的4号是不应该冒这样的风险，把存活的希望寄托在5号的随机选择上的，他惟有支持3号才能绝对保证自身的性命。


再来看3号，他经过上述的逻辑推理之后，就会提出（100，0，0）这样的分配方案，因为他知道4号哪怕一无所获，也还是会无条件的支持他而投赞成票的，那么再加上自己的1票就可以使他稳获这100金币了。
但是，2号也经过推理得知了3号的分配方案，那么他就会提出（98，0，1，1）的方案。因为这个方案相对于3号的分配方案，4号和5号至少可以获得1枚金币，理性的4号和5号自然会觉得此方案对他们来说更有利而支持2号，不希望2号出局而由3号来进行分配。这样，2号就可以屁颠屁颠的拿走98枚金币了。


不幸的是，1号海盗更不是省油的灯，经过一番推理之后也洞悉了2号的分配方案。他将采取的策略是放弃2号，而给3号1枚金币，同时给4号或5号2枚金币，即提出（97，0，1，2，0）或（97，0，1，0，2）的分配方案。由于1号的分配方案对于3号与4号或5号来说，相比2号的方案可以获得更多的利益，那么他们将会投票支持1号，再加上1号自身的1票，97枚金币就可轻松落入1号的腰包了。







最后通牒博弈中理性的困境

有这样一个博弈：

　　两人分一笔总量固定的钱，比如100元。方法是：一人提出方案，另外一人表决。如果表决的人同意，那么就按提出的方案来分；如果不同意的话，两人将一无所得。比如A提方案，B表决。如果A提的方案是70∶30，即A得70元，B得30元。如果B接受，则A得70元，B得30元；如果B不同意，则两人将什么都得不到。



　　A提方案时要猜测B的反应，A会这样想：根据理性人的假定，A无论提出什么方案给B——除了将所有100元留给自己而一点不给B留这样极端的情况，B 只有接受，因为B接受了还有所得，而不接受将一无所获——当然此时A也将一无所获。此时理性的A的方案可以是：留给B一点点比如1分钱，而将99.99元归为己有，即方案是：99.99∶0.01。B接受了还会有0.01元，而不接受，将什么也没有。

　　这是根据理性人的假定的结果，而实际则不是这个结果。英国博弈论专家宾莫做了实验，发现提方案者倾向于提50∶50，而接受者会倾向于：如果给他的少于30%，他将拒绝；多于30%，则不拒绝。

　　这个博弈反映的是“人是理性的”这样的假定在某些时候存在着与实际不符的情况。

　　理论的假定与实际不符的另外一个例子是“彩票问题”。--http://blog.sina.com.cn/s/blog_53735c9d0100bo6q.html


高成本 低成本
默许 阻挠 默许 阻挠
进入 40,50 -10,0 30,100 -10,140
不进入 0,300 0,300 0,400 0,400

在无限重复中，行为规则可以用自动机来代表，于是不同行为规则的 相争，便成了机器与机器的角斗。假设甲和乙玩无限重复的囚犯博奕。甲相信《美德的起源》一书作者的教导，认定仁厚忠恕既高尚又有效，于是 以它为策略。乙信奉理性流氓主义，崇尚实力和实利，于是以流氓主义为策略。这样，二人间的博弈，就可以看作恕道机器与流氓机器的争斗。根 据上一贴中列出的框图，我们可以推演出各个回合双方的行为如下：第一回合，甲仁厚玩合作H，乙宰客玩欺骗D； 第二回合，甲报复玩欺骗D，乙仍然宰客玩欺骗D；第三回合，甲仍报复玩欺骗D，乙发现甲并非傻客，于是玩合作H； 第四回合，甲原谅乙，玩合作H；乙却因甲上次不合作，回头玩欺骗D宰客； ⋯⋯ 如此等等。采用我们上贴里的报偿表，整个结果序列如下图所示： 循 环 循 环 循 环 ┌———┐ ┌———┐ ┌———┐ ↓ ↓ ↓ ↓ ↓ ↓ 行为：甲 H D D H D D H D D 乙 D D H D D H D D H 报偿：甲 0 2 6 0 2 6 0 2 6 乙 6 2 0 6 2 0 6 2 0 ⋯⋯ 请注意，此序列呈现一个有趣的规律：就是每三个一组，不断循环重复。于是我们很容易算出，博弈各方平均每个回合的报偿有多少 只要 取相继三个回合，作个简单平均就够了。甲得到（0＋2＋6）／ 3 ＝ 2．67，乙得到（6＋2＋0）／ 3＝2．67。显然，两者平分秋色， 不相上下，谁也不比谁差，谁也不比谁强。这种循环重复并不是特例。可以证明，有限自动机玩无限重复博弈， 其结果最终都会变成循环重复序列。于是，利用类似的办法，我们可以针对上贴中列出的七种策略，算出每一对策略相博所产生的的平均报偿。这 些报偿可以写成一个7×7博奕矩阵，如下表所示（其中一些略去了小数，这不影响下面的讨论）： 乙 傻客 恶棍 冷血 恕道 侠义 流氓 摇摆 ·－－－－－－－－－－－－－－－－－－－－－－－－－－－· 傻客｜4，4｜0，6｜4，4｜4，4｜4，4｜0，6｜0，6｜ ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜恶棍｜6，0｜②，②｜2，2｜2，2｜2，2｜3，1｜2，2｜ ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜冷血｜4，4｜2，2｜④，④｜④，④｜2，2｜3，1｜2，2｜ ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜恕道｜4，4｜2，2｜④，④｜④，④｜3，3｜2，2｜2，2｜ 甲 ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜侠义｜4，4｜2，2｜2，2｜3，3｜2，2｜2，2｜2，2｜ ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜流氓｜6，0｜1，3｜1，3｜2，2｜2，2｜④，④｜2，4｜ ｜－－－＋－－－＋－－－＋－－－＋－－－＋－－－＋－－－｜摇摆｜6，0｜2，2｜2，2｜2，2｜2，2｜4，2｜③，③｜ ·－－－－－－－－－－－－－－－－－－－－－－－－－－－· 上面这个表里面，有带圈数字的格子都是平衡点。比如，乙玩恶棍策 略时，甲无论玩什么，都不比当恶棍带来的好处更多，顶多不致受损而已。因此，甲乙双方都当恶棍，次次都玩欺骗，便是重复囚犯博奕的平衡点之 一，此时各方的报偿与一次性博奕相同，都是2。观察一下上面这个表，我们会发现它有多个平衡点。非重复博弈中的 均衡点，恶棍对恶棍，双方永远玩欺骗，仍然是无限重复博弈的均衡点。无条件合作的傻客策略，仍然不是重复博弈的均衡点 理性的人，决不 会当傻客。 更重要的是，重复博弈引进了许多新的平衡点，其中有不少平衡点，可以实现合作报偿(4,4)。 这包括恕道策略对恕道策略，恕道策略对冷血 策略，冷血策略对冷血策略，流氓策略对流氓策略等，都可以维持双方的合作。以流氓对流氓为例：第一回合，双方耍流氓互宰，发现对方不是好 惹的之后，双方转入合作心态，此后一直维持合作，这样无限次重复，其平均报偿都是4。 事实上，存在这无穷多对有限自动机策略，可以成为无限重复博弈的 平衡点，并同时实现双方的合作。这就是有名的“大众定理(Folk Theorem)”， 又译作“无名氏定理”。它之得名，是由于重复博弈促进合作的思想，早就有很多人提出，以致无法追溯到其原创者，于是以“无名氏”名之。 大众定理说明了行为规则的多样性：有无穷多种行为规则可以支持合作行为。在正常的平衡状态中，可观察到的行为可以完全相同的，此即博 弈双方相互合作，不玩欺骗。但其背后的行为规则却可能大不相同 合作，可以是由于双方都信奉仁厚的恕道主义，也可能是因为双方都是理性 流氓，还可能是因为双方都一冷血报复作威胁。这些行为规则上的区别，在正常的平衡状态中，是看不出来的，只有在非正常情况下，或在与外人 的交往中，才会表现出来。为说明此点，设想有两个相互隔离的社会：一个形成了理性流氓式的 行为规则，一个形成仁厚恕道的行为规则，他们各自内部都能维持相互合作，这形成了社会的正常状态。外人但凭观察这两个社会中人们的正常行 为，看不出他们有什么区别。现在假设两个社会打破隔离，相互接触，会产生甚么情况？ 两套行为规则间会出现激烈的冲突！ 初次接触，流氓主义者将把对方当傻客，大宰其客。恕道主义者假设对方是好人，选择合作，只是在吃了亏之后，才以回宰其客相回报。流氓 主义者见对方回宰，以为对方也是跟自己一样的流氓，于是转向合作心态，同时预期对方也选择合作。但恕道主义者根据“以直报怨”的原则，仍然 以宰客回报对方上次的欺骗。流氓主义者一看对方不合作，怒从心起，于是报之以宰客，如此循环往复，双方永远无法达成合作。 行为规则的冲突，类似于人文学科里常说的文化冲突。由于行为规则反映了人们对各自行为的稳定预期，一些博弈论者把不同的行为规则解释 为不同的文化信仰，应当是不无道理的。我觉得，重复博弈理论，为我们科学理解许多文化现象，打开了大门。 正是由于行为规则本身的多样性和复杂性，所以我对成朴文章中过分 抬高“一报还一报（tit for tat）”单一规则，将之推崇为美德的起源，始终抱有疑虑