纳什定理与零和游戏.ppt

第二章 零和游戏与纳什定理,赵国洪,优势策略,每个参与人都有优势策略的情况下，优势策略均衡是非常合乎逻辑的。 假如你有一个优势策略，你可以选择采用，并且知道你的对手若是有一个优势策略他也会照办；同样，假如你有一个劣势策略，你应该避免采用，并且知道你的对手若是有一个劣势策略他也会规避。,不是所有博弈都有优势策略。实际上，优势策略只是博弈论的一种特例。,零和游戏游戏者有输有赢，但整个游戏的总成绩永远为零。 博弈的过程就是一个零和游戏：博弈当中的参与者，其利益可能严格对立，一人所得永远等于另一人所失。,零和游戏,拉封丹寓言狐狸与狼的零和博弈 一天晚上，狐狸踱步来到了水井旁，低头俯身看到井底的月亮圆圆的，它认为这是块大奶酪。两只吊桶一上一下交替打水上来，这只饿得发昏的狐狸顾不得那么多，它跨进一 只水桶下到了井底，另一只水桶升到了井面。 下得井来，它才明白这圆月是吃不得的，自己已铸成大错，处境十分地不利，长期下去就只有等死了。如果没有另一个饥饿的替死鬼来打这月亮的主意，以同样的方式，落得同样悲惨的下场把它从眼下窘迫的境地换出来，它怎能指望活着回到地面上去呢？,零和游戏,拉封丹寓言狐狸与狼的零和博弈 两天两夜过去了，没有一只动物光顾水井，时间一分一秒地流逝，银色的上弦月出现了。沮丧的狐狸正无计可施时，刚好一只口渴的狼途经此地，狐狸不禁喜上眉梢，它对狼抬 起头打着招呼道： “喂，伙计，我免费招待你一顿美餐你看怎么样？你看到这个了吗？”它指着井底的月亮对狼说，“这可是块十分好吃的干酪，这是森林之神福纳用奶牛伊娥的奶做出来的，假如神王朱庇特病了，只要尝到这美味可口的食物都会胃口顿开。我已吃掉了这奶酪的那一半，剩下这半也够你吃一顿的了。就请委屈你钻到我特意为你准备好的桶里下到井里来吧。” 狐狸尽量把故事编得天衣无缝，这只狼可是个笨蛋，居然中了它的奸计。狼下到井里， 它的重量使狐狸升到了井口，这只被困两天的狐狸终于得救了。,零和游戏,“无毒不丈夫”也是零和博弈所致 著名经济学家茅于轼曾说：“在市场经济之前，人类自利是妨碍别人的，是损人利己的。”他举例说，”过去的帝王与将相就是这样一种博弈，他可以剥削你，抄你的家；你可以造他的反，夺他的天下。一方得利，一方受损，那是零和博弈。事实上也正是因为这种零和博弈反复上演，才使中国历史的每一页都充满了阴谋与血腥，并且使无毒不狠非丈夫的文化观念深入到每一个中国人的意识中。“,零和游戏,纳什定理案例房地产开发博弈,假定： 广州市的房地产市场需求有限，、两个开发商都想开发一定规模的房地产，但是市场对房地产的需求只能满足一个房地产的开发量； 而且，每个开发商必须一次性开发这一定规模的房地产才能获利。,在这种情况下，和都不存在一种策略完全优于另一种策略，也不存在一个策略完全劣于另一个策略。因为， 如果选择开发，则的最优策略是不开发； 如果选择不开发，则的最优策略是开发； 类似地， 如果选择开发，则的最优策略是不开发； 如果选择不开发，则的最优策略是开发。,案例房地产开发博弈,根据纳什均衡含义：给定你的策略，我的策略是最好的策略；给定我的策略，你的策略也是你最好的策略。即双方在对方给定的策略下不愿意调整自己的策略。,开发商博弈的纳什均衡点不止一个，而是两个： 要么A选择开发，B不开发； 要么A选择不开发，B选择开发。 在这种情况下，A与B都不存在优势策略，也就是A和B不可能只要选择某一个策略而不考虑对方的所选择的策略。 在有两个或两个以上纳什均衡点的博弈中，其最后结果难以预测。我们无法知道，最后结果是A开发，B不开发还是A不开发，B开发。,案例夫妻博弈,丈夫和妻子商量晚上的活动。丈夫喜欢看拳击，而妻子喜欢欣赏歌剧。但两人都希望在一起度过夜晚。 这个“夫妻博弈”有两个纳什均衡点：(歌剧，歌剧)，(拳击，拳击)。 有两个或两个以上纳什均衡点的博弈中，其最后结果难以预测。在“夫妻博弈”中，我们无法知道，最后结果是一同欣赏歌剧还是一起去看拳击。,假定华农只有一名警察，他要负责全校的治安。华农只有一个小偷，要实施偷盗。 东区有一家士多，三角市有一家银行。 因为分身乏术，警察一次只能在一个地方巡逻；而小偷也只能去一个地方。 假定银行需要保护的财产价格为2万元，酒馆的财产价格为1万元。若警察在某地进行巡逻，而小偷也选择了去该地，就会被警察抓住；若警察没有巡逻的地方而小偷去了，则小偷偷盗成功。 警察怎么巡逻才能使效果最好？,零和游戏警察与小偷,“警察抓小偷”，站着的那个代表警察，蹲着并被抓着头发的代表小偷，这个雕像代表了佛罗伦萨政府打击犯罪的决心。,一个明显的做法是，警察对银行进行巡逻，这样，可以保住2万元的财产。可是，假如小偷去了酒馆，偷窃一定成功。这种做法是警察的最好做法吗？有没有对这种策略改进的措施？ 警察的一个最好的做法是，警察抽签决定去银行还是酒馆。因为银行的价值是酒馆的两倍，所以用两个签代表银行，比如如果抽到1、2号签去银行，抽到3号签去酒馆。这样警察有2/3的机会去银行进行巡逻，1/3的机会去酒馆。 而小偷的最优选择是：以同样抽签的办法决定去银行还是去酒馆偷盗，只是抽到1、2号签去酒馆，抽到3号签去银行，那么，小偷有l/3的机会去银行，2/3的机会去酒馆。,零和游戏警察与小偷,21世纪经典建筑之中国银行总行大厦,英国的酒馆,警察与小偷之间的博弈，所选策略应当是随机的，不能让对方知道自己的策略，哪怕是“倾向性”的策略。 当博弈是零和博弈时，即一方所得是另外一方的所失时，对于任何一方来说，此时不可能有纯策略的占优策略。,零和游戏警察与小偷,在博弈论中，可以选择出某个策略的纳什均衡，这个策略叫做纯策略。纯策略的纳什均衡只是博弈的一种特例。 所谓纯策略是指参与者在他的策略空间中选取惟一确定的策略。纯策略是参与者一次性选取的，并且坚持他选取的策略。 所谓混合策略是指参与者采取的不是惟一的策略，而是其策略空间上的概率分布。混合策略是参与者在各种备选策略中采取随机方式选取的。这就是纳什于1950年证明了的纳什定理。而这个博弈没有纯策略纳什均衡点，而有混合策略均衡点。,纳什定理与混合策略,最常见混和策略就是猜硬币游戏。比如在足球比赛开场，裁判将手中的硬币让双方队长猜正反面。由于硬币落下是正是反是随机的，概率都是1/2。那么，猜硬币游戏的参与者都是1/2的概率择正与反，这时博弈达到混和策略纳什均衡。,纳什定理与混合策略,“剪、布、锤”就不存在纯策略均衡，对每个小孩来说，自己采取出“剪”、“布”还是“锤”的策略应当是随机的。因此，每个小孩的最优混合策略是采取每个策略的可能性是l3。在这样的博弈中，每个小孩各取三个策略的13是纳什均衡。,纳什定理与混合策略,两个不到十岁的小男孩，一起玩的时候发生争执，两人商量用剪刀、石头、布，谁赢就听谁的。下面是他们的对话： 甲说：“喂，咱们俩是好兄弟，非要分出胜负就太伤和气了。待会儿咱们都出剪刀就算了事了，好不？” 乙说：“没问题，好兄弟嘛！ ” 他们说话的时候一脸的纯真。 结果甲出的是石头，乙出的是布。,纳什定理与混合策略,也许孩子们的想法只是单纯到希望赢。而往往单纯的想法却能折射人性的本质。假如甲真的按照自己的说法出了剪刀，而乙却出了布，那岂不是聪明反被聪明误。 也许你也置身于这样的怪圈，每个人都再设自己的圈套，让你往里钻，而解脱的方式，就是识破并将计就计。然而出乎意料的是，并不是所有人的圈套你都能看透，这个时候往往就是那没有心计、不设圈套的人撞上了大运。 人还是简单一点，单纯一点，互相信任一点，当这个世界谁都分不出真假是非的时候，这样的世界该是多么可怕啊！为了明天的美好，让我们简单的生活！,零和游戏,有两个经济学家，在马路上散步，便讨论经济问题甲经济学家看见了一堆狗屎，思索着对乙经济学家说。你吃了这堆狗屎吧，我给你100万块钱。乙经济学家犹豫了一会儿，但是还是经受不住诱惑，吃了那堆狗屎，当然，作为条件，甲经济学家给了他100万块钱。 过了一会儿，乙经济学家也看见了一堆狗屎，就对甲经济学家说：你吃了这堆狗屎吧，我也给你100万块钱。甲经济学家犹豫了一会儿，但是还是经受不住诱惑，吃了那堆狗屎当然，作为条件，乙经济学家把甲给他的 100万还了回去。 故事还没有完。 走着走着，乙经济学家忽然缓过神来了，对甲说不对阿，我们谁也没有挣到钱，却吃了两对狗屎。甲也换过神了，思考了一会儿说：可是，我们创造了200万的GNP阿！,零和游戏,“零和游戏”之所以广受关注，主要是因为人们发现，在社会的方方面面都有与“零和游戏”类似的局面，胜利者的光荣后面往往隐藏着失败者的辛酸和苦涩。 但20世纪以来，“零和游戏”观念正逐渐被“非零和游戏”即“负和”或“正和”观念所取代。 “负和游戏”指，一方虽赢但付出了惨重的代价，得不偿失，可谓没有赢家。 赢家所得比输家所失多，或者没有输家，结果为“双赢”或“多赢”，称为“正和”。,零和游戏,有人认为，双赢只不过是把负面隐藏到我们不能观及的地方而已也就是把危害转让到与自己利益无关的地方。 “我们谁也没有挣到钱，却吃了两对狗屎。” 甲之所以给乙钱,是因为甲看见乙吃狗屎感到了快乐.所以他们各吃了一堆狗屎,都没得到钱,但是都感到了一次快乐。,零和游戏,公司年饭抽奖，老板提出，今年特别奖不用抽签而是用玩游戏的方式来决定。 游戏规则：大家围成一圈同时跟老板猜拳，猜赢老板或是平手的人可以参予比赛，猜输的就没有参赛资格。参赛者一直猜到剩下最后一个就是赢家而获得该奖项。 如果你是该公司的员工，你如何增大你拿奖的概率？ 立刻跟两位同事商量：三个人合作，得到奖项大家平分。 大家讲好第一次大家都出不一样的。至少确定第一回合之后，接着还会剩下两个人能够参予这个游戏。,位置博弈,麦当劳和肯德基为什么总是相邻设店?,位置博弈,他们为什么总喜欢贴身撕杀?,位置博弈,假设有条完全笔直的公路，连接城市A到城市B之间的交通。这条公路上每天行驶着大量的车辆，并且车流量在公路上是均匀分布的。假设麦当劳和肯德基要在这条公路上选择一个位置，招揽来往车辆。 一个合乎逻辑的假定：通常情况下，车辆总是乐意到距自己最近的快餐店购买食物。,从资源的最佳配置来看，麦当劳、肯德基应该分别开在1/4、3/4处是最优。在这种均匀散布的情况下，每家快餐店所有拥有的客户从距离最近的城市到两家快餐店的中心为止，因此都拥有1/2的顾客量，同时对于开车的人们总体来说，这种策略的选择，车辆到快餐店的总的距离最短。,位置博弈,肯德基与麦当劳都是百年老店，自然是精明之至，从经济学上就是具有经济理性，总是希望自己的生意尽可能地红火，至于其他人的生意的好坏则与己无关。 出于这种理性，肯德基肯定会想到：如果将店铺从3/4点处向左移一点，将从麦当劳抢夺走部分顾客，这对于肯德基单方面来说无疑是一个好主意。 当然麦当劳也不甘示弱，作为一个“理性人”，麦当劳自然也应该想到将自己的店铺从1/4点处向右移动以争取更多的顾客。,不难想象，双方博弈的结果将使他们的店铺设置在l/2中点附近达到纳什均衡状态，甲乙两人相依为邻且相安无事地做起快餐生意。 即使不是两家快餐店，而是很多家快餐店，也很容易分析得到结果：这些快餐店仍然会在1/2处设店达到纳什均衡。,位置博弈,同样的道理，如果地段的繁华等其他原因在一条路上上都可以认为到处相同的话，没有一个商家会将自己安置于某条路的一头，只要条件许可，超市将几乎趋向于相依为邻，这种现象完全可以看作公正的市场竞争的合理结果。这就是很多城市商业中心形成的原理，在博弈论中称为位置博弈。,大部分电视台总是将最精彩的节目放在相同的时间段，甚至有些时候是在相同时间段播放类似的节目，比如你播“快乐大本营”，我就播“超级总动员”；你播“玫瑰有约”，我就播“单身男女”。人都说文人相轻，电视台也是这么相煎太急。,游戏：微软面试的智力题,这是一道微软用来测试应聘者的试题。它主要考察受训者的逻辑思维和判断能力，同时也给受训者一些关于问题解决方法上的启示。 游戏规则和程序 1.有两个房间，一间房里有三盏灯，另一间房有分别控制着三盏灯的三个开关；这两个房间是分隔开的，从一间里不能看到另一间的情况。 2.现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。 3.有什么办法呢？,游戏：微软面试的智力题,答案 1.先走进有开关的房间，将三个开关编号为a、b、c。 2.将开关a 打开5分钟，然后关闭，然后打开b； 3.然后走到另一个房间，即可辨别出正亮着的灯是由b 开关控制的。再用手摸另两个灯泡 ，发热的是由开关a 控制的，另一个就一定是开关c了。,趣味智力题,题：你让工人为你工作天，给工人的回报是一根金条。金条平分成相连的段，你必须在每天结束时给他们一段金条，如果只许你两次把金条弄断，你如何给你的工人付费？,答案：两次弄断就应分成三份，把金条分成、和三份。这样，第天我就可以给他；第天我给他，让他找回我；第天我就再给他，加上原先的就是；第天我给他那块，让他找回那两块和的金条；第天，再给他；第天和第天一样；第天给他找回的那个。,一道真正难倒亿人的智力题,5个囚犯，按1-5号分别在装有100颗绿豆的麻袋抓绿豆，规定每人至少抓一颗，而抓得最多和最少的人将被处死，而且，他们之间不能交流，但在抓的时候，可以摸出剩下的豆子数。问他们中谁的存活几率最大？ 提示： 1，他们都是很聪明的人 2，他们的原则是先求保命，再去多杀人 3，100颗不必都分完 4，若有重复的情况，则也算最大或最小，一并处死,这是微软的面试题。,一道真正难倒亿人的智力题,因为他们五个人分一百颗绿豆 中位数是20颗，他们都是很聪明