博弈论(对策论).ppt

博 弈 论,杨文国 Y 2010. 03,博 弈 论,美藉匈牙利数学家冯诺依曼（John Von Neuman）和美藉奥地利经济学家摩根斯顿（Morgenstern）相识于普林斯顿大学，他们于1944年出版了经典著作博弈论与经济行为，为现代博弈论的发展奠定了基础。,美国的数学家、经济学家纳什（John Nash），美籍匈牙利经济学家海萨尼（John C. Harsanyi）和德国经济学家泽尔滕（R.Selten）因对博弈论的卓越贡献而获得1994年度的诺贝尔经济学家。,海萨尼,纳什,值得一提的是纳什，他发表奠定其在博弈论中重要地位的学术论文时，年仅22岁，被人称为“一个天才”。1959年，纳什被精神病医生诊断为“妄想性精神分裂”，饱受精神病折磨40余年。,泽尔滕,引子 概论 解的概念 矩阵对策的解法,矩阵对策方法的引子,乔家大院、乔致庸、疏通茶道、货通天下、汇通天下 开办茶票庄大德兴、老字号广盛源、金元宝、银冬瓜、保牌与摘牌之博弈 争取项目、项目资源组织,竞争博弈的矩阵对策问题 黄 钧、杨文国、付宏伟,引 子 软件厂商 vs 软件销费者,2006年7月15日报告：徐秋红,报告摘要,运用博弈论中的混合均衡理论对消费者购买了正版软件后，服从或不服从软件厂商的协议的行为进行了分析，并得出软件厂商可能会采取随机抽样的办法，检测消费者是否服从软件协议。 运用了以下理论： 纳什均衡 混合策略纳什均衡,纳什均衡,定义：是对应于完全信息静态博弈的一个重要均衡概念，由纳什（Nash，1950-1951）年首先提出。 意义：若其他参与人均采用均衡策略，则余下的这一参与人只有采用均衡策略才是最好的；或者说，对于每个参与人来说，没有一个参与人能够单方面的改变它的策略并获得更好的支付，以致它们将会理性的坚持自己的策略，这使得纳什均衡成为博弈的一致解概念。 结果：这种指定的策略组合可以叫做是“自动实施”的，稳定的结果。,美丽的心灵的影片中，“纳什”对这种均衡做了形象地描述,混合策略纳什均衡,在策略式博弈G=S1， ，Sn；u1， ，un中，设p*为一混合策略组合，如果 Ej（pi，p-i*）Ei（p*）成立，则称P*是一个混合策略纳什均衡(mixed strategy Nash equilibrium),软件厂商 vs 软件销费者 混合纳什均衡的问题,局中人：在这里我们假设“软件厂商”（局中人I）和“消费者”(局中人II)是两个独立的局中人，并都是“理智的”，即对每一局中人来说，不能存在侥幸心理； 策略：在消费者购买了软件后，即开始了软件厂商有两种策略抉择（检查和不检查消费者的使用情况，确认消费者是否严格履行软件购买协议的要求来使用此软件）；同时，消费者也有两种策略抉择（服从和不服从软件使用协议。服从将没有任何风险，不服从就可能在将来被软件厂商检查出来所面临的高额经济损失） 局势：由上面分析得出，每个局中人所出的不同策略将形成的策略组，即一个局势。在此软件厂商的全部局势集合为Si=检查，不检查，消费者的全部局势集合为 Sj=服从，不服从。,局势中赢得函数中参数设定,软件厂商进行检查未发现消费者违约，软件厂商的支付记为-1；消费者的支付记为0 软件厂商进行检查并发现消费者违约，由于多项环节的介入，软件厂商支付出软件销售额的4倍的成本，记为-4；在此，消费者将被惩罚64倍的软件价格的费用，记为-64 如果软件厂商不进行检查，消费者也没有违约，那么软件厂商付出的成本记为0，消费者的付出和收益记为0 如果软件厂商不进行检查，消费者不服从软件协议（即将软件又加载到其它计算机上或借给朋友），假定这种情况使得软件厂商损失为8倍的软件价格，而消费者的收益也是八倍的软件价格，分别记为-8和+8。,软件厂商与消费者的支付矩阵,求解混合策略纳什均衡,混合纳什均衡的随机性,在这个博弈中，参与人I的一个混合策略纳什均衡是：局中人I不检查的概率为8/9，则检查的概率为1/9；局中人II服从的概率为0.8，则不服从的概率为0.2。 当监管力度薄弱时，即不检查概率x8/9（或说检查的概率1-x1/9)时，局中人II选择服从协议。 因此，如果软件厂商（局中人I）检查的概率特别低或者特别高时，局中人II有唯一的最优反应。,混合策略纳什均衡是概率依赖于竞争对手的支付，而不依赖于局中人自己的支付,通过以上分析，如果有人认为，消费者预期如果他/她不服从软件协议并被检查到，将受到-64的惩罚，而降低了均衡中的不服从概率的理解是不尽然的。 事实上，变化的因素主要是检查的概率（打击盗版的力度）；也就是说，如果软件厂商经常检查，不服从协议的消费者的比例将减少；这样的持续过程，厂商会调整策略，即不检查成为一个更好的策略。因此，在动态的过程中，比例的长期平均近似于均衡概率。 因此，即使检查不是确定的，足够高的被查处的概率也威胁着消费者，至少在某种程度上威胁了。,结语：,本文的结论：在检查的背景下，随机抽样检查是实践中的方法，这样可以削减软件厂商的成本。因此，可以预测到未来软件厂家会采取随机抽样的方式，对最终用户的版权进行检测以达到打击盗版、推行正版，创造良好的市场竞争格局。 本文的不足：由于时间仓促，我没有对知名软件公司反盗版的实际数据进行统计分析，从而与混合均衡模型的结论作以比较；同时，没有引入更多的局中人，进行综合分析。今后有时间时，再充实文章的内容，进行详细的分析。 本文作者的希望：通过今天的演讲，起到“抛砖引玉”的作用，使大家更充分的认识到数学知识在生活中的广泛运用及其科学性；另外，结合本文的结论，也提起大家警惕，避免我们目前使用的非正规安装的软件被厂家发现，而带来经济损失。,一种奇特的美统治着数学王国，这种美不像艺术与自然之美那么相似，但其却深深地感染着人们的心灵，激起人们对数学的欣赏 -库默,概 论,名称 Game Theory 博奕论，对策论 发展历史 对策论模型 分 类 例 子,发 展 简 史,早期工作 1912年E.Zermelo 关于集合论在象棋对策中的应用 1921年E.Borel 引入最优策略 1928年J.V.Neumann证明了一些猜想 产生标志 1944年J.V.Neumann和O.Morgenstern对策论与经济行为 发展成熟 Nash均衡、经济博奕论、信息不对称对策和广义对策,概 念,具有竞争或对抗性质的行为，称为对策行为。 对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。 称具有对策行为的模型为对策模型或对策。,例：“齐王赛马”；“石头剪子布”,对策模型三个基本要素,局中人 两个或两个以上-决策者 策略集合 策略-决策 局势-状态 赢得函数（支付函数） 支付关于局势的函数-决策依据和标准,分 类,局中人 两人对策、多人对策 策略 有限对策、无限对策；合作对策、非合作对策 支付 零和对策、非零和对策 时间 单阶段对策、多阶段对策,矩 阵 对 策,在众多对策模型中占有重要地位的是二人有限零和对策，又称矩阵对策。 矩阵对策是到目前为止在理论研究和求解方法方面比较完善的一类对策，而且这类对策的研究思想和理论结果又是研究其它类型对策模型的基础。,例 子,两个参加者甲、乙各出示一枚硬币，在不让对方看见的情况下，将硬币放在桌子上，若两个硬币都呈正面或都呈反面则甲得1分，乙付出1分；若两个硬币一个呈正面另一个呈反面则乙得1分，甲付出1分。 局中人：甲、乙,矩 阵 对 策 的 解,例子 设定 最稳妥策略 性质 对策的解 例子,例子：,例1 我们称“石头剪子布”游戏是一个对策问题，设参加游戏的是甲、乙两人，他们的策略集合都是石头、剪子、布，也就是说他们在每一局比赛中都只能采取各自策略集合中的一个策略，如果我们再规定，赢得的一方得1分，输的那方得-1分。显然，这个问题是两人有限零和对策，即矩阵对策。 我们可以列出甲、乙两人在一局比赛中的各种局势下的赢输分数。因为这是零和对策，故只需知道甲、乙任何一方在各种局势下的分数，就能够知道对方的情况了。,甲乙两人在各种局势下的得分情况：,如把表中数字用矩阵形式表示，则有,例2、（齐王赛马）,战国时期，齐王要与大将田忌赛马，双方约定：从自己的上、中、下三个等级的马中各选出一匹进行比赛。每次比赛输者要付给赢者千金。就同等级的马而言，齐王的马都比田忌的强，他们俩人的策略集合都是，（上、中、下）、（上、下、中）、（中、上、下）、（中、下、上）、（下、上、中）、（下、中、上）并且可以知道，在每一局比赛结束时，齐王和田忌任何一方赢得的千金数恰是对方输丢的千金数。可见这是两人有限零和对策。即矩阵对策。,下表列出齐王在各种局势下赢得千金的数值，（表中-1表齐王输一千金）。,齐王的赢得矩阵：,一般情况，设两个局中人分别记为I、II，局中人I有m个策略1，2，m；局中人II有n个策略1，2，n。用S1表示局中人I的策略集合，S2表示局中人II的策略集合，即 1，2，m 1，2，n 称i为I的纯策略，j为II的纯策略，对于纯策略构成局势（i，j）称为纯局势。,设 定,两人有限零和对策 局中人：两个 策略集: 局势集： 支付函数： 矩阵表示（局中人I的赢得矩阵）：,A中的元素ij表示在纯局势（i，j）下局中人I得分，也表示在同一局势下，局中人II得分为-ij。 我们把矩阵对策记为 I，；s1，s2；A或s1，s2；A 矩阵对策模型给定后，各局中人面临的问题是：,如何选择对自己最为有利的纯策略，以谋取最大的赢得（或最少损失），这就是所谓矩阵对策的最优纯策略（最稳妥策略）。,矩阵对策的最优纯策略 (最稳妥策略),我们用一个例子来说明最稳妥策略的概念。,从A可看出，局中人I的最大赢得是9，要想得到这个赢得，他就得选择纯策略3。由于，假定局中人II也是理智的，他考虑到了局中人I打算出3的心理于是便准备以3对付之。使局中人不但得不到9，反而失掉10，局中人I当然也会猜到局中人II的这一心理，故想出4来对付，使局中人II得不到10而失掉6，所以，如果双方都不想冒险，都不存在侥幸心理，而是考虑到对方必然会设法使自己的所得最少这一点，就应该从各自可能出现的最不利的情形中选择一种最为有利的情形作为决策的依据，这就是所谓“理智行为”，也是对策双方实际上都能接受的一种稳妥方法。,例3中，局中人I分析出纯策略1，2，3，4可能带来的最少赢得（矩阵A中每行的最小元素）分别为： -8，-10，-3； max-8，2，-10，-3=2 在这些最少赢得（最不利的情形）中最好的结果（最有利的情形）是赢得为2。因此，局中人I只要以2参加对策，无论局中人II取什么样的纯策略，都能保证局中人I的收入不会少于2，而出其它纯策略，其收入都有可能小于2，甚至输给对方。,对局中人II来说，各纯策略1，2，3可能带来的对其最不利的结果（矩阵A中每列中最大元素）分别为： 9，6 min9，2，6=2 在这些最不利的结果中，最好的结果（输得最少）也是2，即局中人II只要选择纯策略2（无论局中人I采取什么纯策略，都能保持自己的支付不会多于2，而采取其它任何策略，都有可能使自己的所失多于2。,上面的分析表明，局中人I、II的“理智行为”分别是，选择纯策略2和2，这时局中人I的赢得值和局中人II的所失值的绝对值相等（都是2），局中人I是按最大最小原则。局中人II是按最小最大原则选择各自的纯策略，这对双方来说都是一种最为稳妥的行为，因此，2，2分别为局中人I、II的最优纯策略(最稳妥策略）。,于是我们引出矩阵对策解的概念：,性 质,均 衡 解,由定义可知，在矩阵对策中两个局中人都采取最优纯策略（如果最优纯策略存在）才是理智的行动。,例 子,实 例,例. 某单位采购员在秋天要决定冬季取暖用煤的贮量问题，已知在正常的冬季气温条件要耗煤15吨，在较暖与较冷的气温条件要消耗10吨和20吨，假定冬季时的煤价随天气寒冷程度而有所变化，在较暖、正常、较冷的气候条件下每吨煤价分别为10元、15元和20元，又设秋季时煤价为每吨10元，在没有关于当年冬季准确的气象预报的条件下，秋季贮煤多少吨，能使单位的支出最少？,实 例 之 求 解,解：这一贮量问题，可以看成是一个对策问题，把采购员当作局中人，他有三个策略，在秋天时买10吨、15吨与20吨，分别论为1、2、3。 把大自然看作局中人II（可以当作理智的局中人来处理），大自然（冬季气温）有三种策略，出现较暖的、正常的、与较冷的各季，分别记为1、2、3。,现在把该单位冬季取暖用煤实际费用（即秋季时的购煤费用与冬季不够时再补购的费用总和，作为局中人I的赢得，赢得矩阵如下 (较暖) (正常) (较冷) min 1(10顿) -100 -175 -300 -300 2(15顿) -150 -150 -250 -250 3(20顿) -200 -200 -200 -200 max -100 -150 -200,实 例 之 结 论,故对策解为（3，3），即秋季贮煤20吨合理 。 博弈论在项目管理中的应用。,一个博弈游戏引发的智慧思考,一个经典的博弈游戏,红黑游戏（分组） 得分规则,一个经典的博弈游戏,红黑游戏 过程规则,总共进行6轮竞赛，每次3分钟报出选择 第3、6轮各组分别讨论一次，每次5分钟 第三轮得分乘以2， 第六轮得分乘以5，,一个经典的博弈游戏,竞合博弈：红黑游戏 胜负规则,各队的得分视为各自企业的经营业绩 得正分多的队获胜,一个经典的博弈游戏,各组代表阐述：,你们如何预测其它组的选择结果 为什么你们组作出这样的选择 如果再给你一次机会，你会做何选择,一个经典的博弈游戏,红黑游戏 博弈矩阵,一个经典的博弈游戏,结果的反思：,都选择各自的最优策略，结果如何 是什么制约大家达成双赢,可口可乐与百事可乐的价格博弈,博弈矩阵,一个经典的博弈游戏,结果的再反思：,博弈并不仅仅在于理性的选择 拥有退一步的智慧才可能达成双赢 博弈无处不在，你在求赢的理性追求过程中，往往的结局是双输，博弈的双赢，需要理性中的智慧选择 中国市场的成熟标志在于“价格屠夫”的衰落,无论零和博弈还是非零和博弈，博弈论学科本身所包含的内容非常地丰富，在经济领域的应用也越来越广泛，希望大家在今后的学习和工作之中能够利用博弈论的思想对项目管理、物流工程等专业中所遇到的实际问题进行思考，以期得到很“理性的”解决。,结 语,要求与作业,对博弈论部分知识的要求 1 掌握矩阵对策模型及其最稳妥策略的求法； 2 知道非零和对策模型，并能进行考虑对手行为的决策； 对博弈论部分能力的要求 1 能够对实际问题，建立矩阵对策模型并求出其最稳妥策略； 2 能够对实际问题建立非零和对策模型，并能进行考虑对手行为的决策分析。,作 业,1 试求下述矩阵对策问题： B1 B2 B3 1 2 12