(完全信息静态博弈).ppt

,邢立宁 国防科技大学五院管理系 Email：xinglining04gfkd.mtn 联系电话完全信息静态博弈,“要想在现代社会做一个有文化的人，你必须对博弈论有一个大致了解” 保罗萨缪尔森,理解博弈的标准式表达和Nash均衡的概念，掌握两人有限零和博弈。,引言 举例 博弈的标准式表述 纳什均衡求法 混合战略纳什均衡 应用,博弈：是指个人或组织在一定的环境条件下，以一定的规则进行决策并从中取得相应结果的过程。 博弈论（Game Theory）： 研究博弈参与者在利益冲突 条件下进行决策的理论。,完全信息博弈： 各博弈方都完全了解所有博弈方各种情况下的支付 不完全信息博弈 至少部分博弈方不完全了解其他博弈方支付情况的博弈,完全信息与不完全信息,完美信息博弈 每个轮到行为的博弈方对博弈的进程完全了解的博弈 不完美信息博弈 至少某些博弈方在轮到行动时不完全了解此前全部博弈的进程的博弈,完美信息与不完美信息,完美博弈,不完美博弈,静态博弈是指： 所有博弈方同时或可看作同时选择策略的博弈 田忌赛马、猜硬币、古诺模型 动态博弈是指： 各博弈方的选择和行动又先后次序且后选择、后行动的博弈方在自己选择、行动之前可以看到其他博弈方的选择和行动 弈棋、市场进入、领导追随型市场结构,静态博弈与动态博弈,Prisoners Dilemma,博弈方： 囚犯1、2 可选策略：坦白与不坦白 几乎同时决策 所得利益： 若一个坦白一个不坦白，坦白放人，不坦白被判8年； 若两人同时不坦白各被判1年； 若两人同时坦白各判5年。,不坦白 坦白,不坦白 坦白,囚犯2,囚犯1,完全信息博弈是指每个参与人对其他参与人的策略空间及支付函数有准确认识的博弈。 静态博弈是指所有博弈方同时或可看作同时选择策略的博弈。 完全信息静态博弈是指各博弈方同时决策，且所有博弈方对各方支付都了解的博弈。 完全信息静态博弈是非合作博弈最基本的类型。,完全信息静态博弈 有两层含义： 完全信息的 静态的,例如： 1. guess coin 2. prisoners dilemma 3. boxed pigs 4. Chicken game 5. 石头剪子布的博弈 6. 田忌赛马 7 . 无限策略博弈(古诺博弈),优势策略,又称占优策略,或者上策. 即不管其他博弈方选择什么策略，一博弈方的某个策略给他带来的支付始终高于其他的策略，至少不低于其他策略的策略。 占优均衡：一个博弈的某个策略组合中的所有策略都是各个博弈方各自的上策，必然是该博弈比较稳定的结果。 例如:囚徒困境博弈,如果无论其他参与人选择什么策略，策略 都是参与人i的强最佳应对，那么 就称为优势策略。这意味着无论别人选择什么策略， 都使参与人i的支付最大化。,对于许多从未接触过博弈的人来说囚徒困境看起来既荒谬又不现实 如果在你看来结果是不正确的，你应该意识到，模型的主要用处通常就是引起困惑。困惑是你的模型与你摄像的有所不同的标志你遗漏了对于你所期望但却并未得到的结果来说必不可少的东西。此时，要么是你最初的想法有问题，要么是你的模型有错误。发现这类错误便是建模过程中的收获。这种收获虽然略带痛苦，但却是真实的。拒绝接受出乎意料的结论就是拒绝逻辑。,在许多不同的情况中，我们都能发现囚徒困境的影子，其中包括寡头定价、拍卖出价、推销员的努力、政治上的讨价还价和军备竞赛等。一旦你观察到在冲突中两败俱伤的情况时，你的第一想法就应是囚徒困境。,寡头2,寡头2,斯特恩巴赫是费城的一个家庭保健医生，她很奇怪为什么辉瑞公司的五位不同推销员重复上门到她的诊所推销同样的止痛药Betra及Celebrex。她在储藏室里一个像冰箱一样大的柜子里已经装满了Betra和Celebrex，她说，“众多的推销员重复同样的产品，没有任何新意，实在是离奇。” 长达十年的招聘狂潮使制药业的推销员人数增加到90000，为原来人数的三倍。制药业人士笃信：只要推销员与医生推销一种药越频繁，医生越有可能多开此药。 据统计，2003年制药业在推销员工上花费120多亿美元，在药物广告商花费为27.6亿美元。根据联邦政府的报告，美国国内在处方药上的支出激增14%，达到1610亿美元。,尽管如此，没有任何一家制药商愿意第一个党方面裁军、葛兰素史克公司的推销员队伍是如此的壮大：它只需要七天就可以联系到美国80%以上的医生。“这有必要吗？”葛兰素史克的CEO加涅尔说：“应该说是没有必要，但是如果我的竞争对手能而我做不到，我们就处于劣势。者的确是以最坏可能的方式进行的军备竞赛。” “拥有众多的推销员不是竞争优势的源泉”，默克公司的主席和CEO吉尔马丁补充说。他说只制药商通过发现新药来获得优势。然而，默克公司2001年起在美国已增加了1500名推销员，使得总数达到约7000人。,重复剔除的占优策略均衡,依赖于小猪的策略：若小猪选“等待”，大猪的最优策略是“按”；若小猪选“按”，大猪的最优策略为“等待”。因此，不能用上述占优策略找出均衡。 可能的均衡是什么呢？若小猪是理性的，他只会选“等待”，因为“等待”严格优于“按”。假定大猪知道小猪是理性的，则会预测到小猪的选择；此时，大猪的最优选择只能是“按”。因此，（按，等待）是该博弈唯一的均衡。,找出上述均衡的思路是：先找出某个参与人的劣策略（假定存在），把它剔除，重新构造一个不包含已剔除策略的新博弈；然后再剔除新博弈中某个参与人的劣策略；直至剩下一个唯一的策略组合。该策略组合就是博弈的均衡解，称为“重复剔除的占优策略均衡”。上例中，先剔除小猪的劣策略“按”，在新博弈中，小猪只有“等待”一个策略，大猪仍有两个策略，但“等待”是它的劣策略，剔除它，就剩下唯一的策略组合（按，待待）。,例：找出下列博弈的重复剔除的占优策略均衡,数学界的梵高“疯子天才”纳什,美丽心灵故事的原型是数学家小约翰-福布斯-纳什。英俊而又十分古怪的纳什早年就作出了惊人的数学发现，开始享有国际声誉。但纳什出众的直觉受到了精神分裂症的困扰，使他向学术上最高层次进军的辉煌历程发生了巨大改变。面对这个曾经击毁了许多人的挑战，纳什在深爱着的妻子艾丽西亚的相助下，毫不畏惧，顽强抗争。经过了几十年艰难努力，他终于战胜了这个不幸，并于1994年获得诺贝尔奖。这是一个真人真事的传奇故事，今天纳什继续在他的领域中耕耘着。,纳什对博弈论的贡献有两个方面，一是合作博弈理论中的讨价还价模型，称为纳什讨价还价解(Nash bargaining solution)；二是非合作博弈论方面，这是他的主贡献所在。 纳什对非合作博弈的主要贡献是他在1950年和1951年的两篇论文中在非常一般的意义上定义了非合作博弈及其均衡解，并证明了均衡解的存在。这样，他便奠定了非合作博弈论的基础。纳什所定义的均衡称为“纳什均衡”, 已成为经济学中的专家术语。,纳什均衡是什么意思呢？假设有n个人参与博弈，给定其他人战略的条件下，每个人选择自己的最优战略(个人最优可能依赖于也可能不依赖于其他人的战略)，所有参与人选择的战略一起构成一个战略组合，这种战略组合由所有参与人的最优战略组成，也就是说，给定别人战略的情况下，没有任何单个参与人有积极性选择其他战略，从而没任何人有积极性打破这种均衡。用句不太褒义的话来说，纳什均衡是一种“僵局”：给定别人不动的情况下，没有人有兴趣动。,1.2 举例,一、囚徒困境（prisoners dilemma）,二、智猪博弈,智猪博弈用通俗话来形容就是“枪打出头鸟”。一个很常见的现象就是在企业中，不论国企还是民企或是外企，在企业内部总会存在各种各样的小团体。套用组织行为学的专业术语来说就是存在各种非正式组织。而每一个团体都代表了一部分人的利益，因此不可避免地会产生冲突。 每个团体都会推选出各自的代言人。这些代言人是为集体利益（如争取加薪或增加福利等）作出积极行动的领头人。但我们这时会发现，被推选为代言人的总是那些胸无城府、意气用事的人。,群体活动的最大受益者“小猪”们则永远躲在幕后。活动成功了，他们可以毫发无伤地优先分到一杯羹；如果失败了，他们也可以发表一通与我无关，我是受害者之类的演讲，让“大猪”成为永远的牺牲者。从另一个角度来看，懂得智猪博弈对于个人并非是件坏事。 实际上，作为一个有理性的人，谁都不愿意甘冒风险而为他人带来好处。如果是这种情况，智猪博弈便无法形成。在智猪博弈的模型中，要摆脱大家都无法生存的困境，就要让双方的期望值不同，然后由一方作出现象上的让步。实际上，让步的这一方，只是在表面上看起来是谦让了。,股份公司中，股东承担着监督经理的职能，但股东中有大股东和小股东之分，他们从监督中得到的收益并不一样。大股东监督经理需要搜集得到的好处显然多于小股东。大股东类似“大猪”，小股东类似“小猪”。纳什均衡是，大股东担当起搜集信息，监督经理的责任，小股东则搭大股东的便车。 股票市场上炒股票也是如此。股市上有大户，也有小户，大户类似“大猪”，小户类似“小猪”。对小户而言，“跟大户”是最优选择，而大户则必须自己搜集信息，进行分析。 市场中大企业与小企业之间的关系。进行研究开发，为新产品做广告，对大企业是值得的，对小企业则得不偿失。可能的情况是，小企业把精力花在模仿上，或等待大企业用广告打开市场后出售廉价产品。,公共产品的提供。村里住两户人家，一户富，一户穷，有一条路年久失修。这时候，富户一般会承担起个修路的责任，穷户则很少这样干，因为富户家常常是高朋满座，坐车坐轿的都来，而穷户家只是自己穿着破鞋走路，路修好了他走起来舒服，路修不好他也无所谓。 改革中也有类似的情况。同样的改革带给一部分人的好处可能比另一部分人大多得多。这时候，前一部分人比后一部分人更有积极性改革，改革往往就是由这些“大猪”推动的。如改革能创造出更多的“大猪”来，改革的速度就会加快。,三、性别战,这个博弈中，有两个纳什均衡：(足球，足球)，(芭蕾，芭蕾)。就是说，给定一个方去足球场，另一方也会去足球场；类似地，给定一方去看芭蕾，另一方也会去看芭蕾。那么，究竟哪一个纳什均衡会实际发生？我们不知道。实际生活中，也许是这一次看见优势(first-mover advantage)，比如说，若男的买票，两个就会出在足球场，若女的买票，两人就会在芭蕾舞厅。,四、市场进入阻挠,这个博弈也有两个纳什均衡，即(进入，默许)，(不进入，斗争)。为什么(进入，默许)是纳什均衡?因为给定进入者进入，在位者选择默许时得50单位利润，选择斗争时得不到利润，所以，最优战略是默许。类似地，给定在位者选择默许，进入者的最优战略就是进入。尽管在进入者选择不进入时，默许和斗争对在位者是一个意思，只有当在位者选择斗争时，不进入才是进入者的最优选择，所以，(不进入，斗争)是一个纳什均衡，而(不进入，默许)不是一个纳什均衡。,存在两个纳什均衡的博弈：,此时不存在占优策略,左下格和右上格为纳什均衡,实是哪个均衡呢？无法确定，取决于哪家厂商先行动,如果两家厂商分别采取不同的专长策略，利润就会更高。厂商1的战略取决于厂商2的战略；厂商2的战略取决于厂商1的战略。没加厂商都会力争首先宣布有新发动机的车型！,1.3 博弈的标准式表述,在博弈的标准式表述中，一般包括如下基本要素；博弈的参与者；博弈方可选择的全部行为或策略的集合；针对所有参与者可能选择的策略组合，每一个参与者获得的收益。为了便于分析，通常要对各博弈方从1到n排序，设其中任一个参与者的序号为i，令 代表参与者i的策略空间，其中任一个特定的策略记为 ，则。令 表示每一个参与者选定一个策略形成的策略组合，令 表示第i个参与者的收益函数， 表示参与者选择 策略时第i个参与者的收益。将上述内容综合起来，可以对博弈进行如下定义。 定义7.1 在一个n人博弈的标准式表述中，参与者的策略空间分别为 ，收益函数分别为 ，则 表示此博弈。,石头、剪子、布,石 头,剪 子,布,博弈方2,石 头,剪 子,布,博 弈 方 1,划拳博弈,1.4 纳什均衡求法,定义7.2 在博弈 中，如果策略组合 中任一博弈方i的策略 都是对其余比一方的策略组合 的最佳对略，也即 对任意都成立，则称 为G的一个“纳什均衡”。 纳什均衡有强弱之分，以上是弱纳什均衡，也是最常用的纳什均衡概念。强纳什均衡是指每个博弈方对于对手的策略有唯一的最佳反应，即 为严格纳什均衡，当且仅当对所有i，所有其他 ，均有,（一）两人有限零和博弈模型 如果用 和 表示两人有限零和博弈的两个局中人，并设他们的策略集分别为 ， 。由于在任一举止中领个局中人得失之和总是等于零，也就是说如果对于局势 ，局中人 的收入为 ，则局中人的收入为 。局中人 的支付矩阵可记作 根据局中人 的支付矩阵A，结合博弈的一般式表述 ，我们可将这种博弈记作,（二）最优纯策略与纳什均衡 例7-1 设有两人有限零和博弈 ，其中局中人 的支付如表7-2所示。 的最大收入是8，但是如果 采取策略 ，而 采取 ，则 非但没有得到8，反而损失5。同理，如果 为得到最大收入而采取 ，则 会采取 ，而 损失3。对 来讲， 对应的最坏收入分别是 （0，-5，1），这些最坏收入中最好收入是1。同理，局中人 的各个策略 对应的最坏结果就是表7-2中每列的最大元素（3，8，4，1），其中 的最好收入是-1。 这局博弈中两个局中人最坏情况下最好的结果的绝对值相等， 分别是 和 的最优纯决策，称局势 为 的鞍点。,表7-2 支付表,定义7.3 对于博弈 ，如果 则称支付元素 对应的 分别为局中人 和 的最优纯策略，称局势 为博弈G的鞍点，称v为博弈G的博弈值。 两人有限博弈存在鞍点的虫咬条件是支付矩阵中存在一个元素 ，使对于一切 ，总有 这个结论说明，若能在支付表A中找到一个元素 ，它既是所在行最小元素，又是所在列最大元素，则 就是博弈G的鞍点， 分别为局中人 和 的最优纯策略。 例如博弈 ，其中 。由于 既是所在行最小元素又是所在列最大元素，因此博弈的鞍点即纳什均衡为 ， 和 分别是局中人 和 的最优纯策略。,（三）最优混合策略与纳什均衡 设博弈 ，令 分别为局中人 和 在各自的策略集 和 中选择策略 和 的概率，则称 分别为局中人 和 的一个混合策略。称 为局中人 的期望所得， 为 的期望所得，而 为博弈的混合局势。 又记 分别为局中人 和 的混合策略集合。,定义7.4 如果 ，则称 分别为局中人 和 的最优混合策略，称 为G的最优混合局势，称 为博弈方 的期望所得。 最优混合局势 构成了混合意义上的纳什均衡，任何一方单独背离这个局势，则它的期望所得将不会优于最优混合局势下的所得。 （四）最优混合策略的求解方法 博弈 有混合意义下的解的充要条件是：存在 及数 满足下列两个不等式组：,为了求解上述不等式组，可将它们变为线性规划而求出博弈G的最有混合策略。不妨设 。令 ，则不等式组（1）等价于下面的线性规划： 同理，令 ，问题（2）就变为线性规划（4）：,例7-2 市场竞争模型。假设某产品市场有两家超级公司相互竞争，超级公司A有三个广告策略，超级公司B也有三个广告策略。已知当双方采取不同的广告策略时，A方所占市场份额增加的百分数如表7-3： 表7-3 A方所占市场份额增加的百分数 由于该产品市场上只有两家公司，因此公司A增加的份额即为公司B减少的份额，这是一个两人有限零和博弈模型。由于 ，知该模型不存在最优纯策略，一次把此问题表示成线性规划模型，并用单纯性法求解。先求B的最优策略为 ，博弈值为v，令,则B问题的线性规划模型为,加入松弛变量 ，用单纯形法求得最优单纯形表如下：,因此，局中人B的最优混合策略,因为局中人A最优混合策略与局中人B最优混合策略互相为对偶变量，所以从上面最优单纯形表中可得 ，局中人A的最优混合策略为 。,例7-3 市场进入阻挠博弈。一种市场上存在一个垄断企业，另一个企业希望进入这一市场，垄断者为了保持自己的地位需要对进入者进行阻挠。在这种博弈中，进入者有两种策略可以选择；“进入”与“不进入”；垄断者也有两种策略：“容忍”与“反击”。他们的支付函数用以下双变量矩阵表示，如图7-4所示。 显然这不是一个两个人有限零和博弈，不能利用鞍点存在准则进行求解。但根据纳什均衡的定义，可以很容易判断出，这个博弈有两个纯策略纳什均衡点，即（进入，容忍）与（不进入，反击）。,例7-4 产量决策的古诺模型。古诺模型是博弈论中最经典的例子。 生产同质产品的两个企业同时选择各自的产量，单位成本均为常数c。市场需求决定价格 。为了求解其中的纳什均衡，需要求得每个局中人对另一个局中人策略的最优反应。对于局中人1来说，他的利润为 对 求导可得到利润最大化的一阶条件为 这一函数决定了面对局中人2的每种策略 时局中人1的最优反应，称之为局中人1的最优反应函数。类似的，可得到局中人2利润最大化的一阶条件（局中人2的最优反应函数） 联立两式，求解得到纳什均衡,通过简单计算可知，如果市场上只有一个垄断厂商，则他的产量是 ，利润为 。这里的双人古诺竞争中总利润为 ，显然小于垄断利润。因此，对这两个厂商来说，存在着帕累托改进的可能。事实上，如果每个厂商都自我约束，降低产量到 ，则每个人都可以得到更好的结局，平分垄断利润，各自得到 。但这一结局之所以不是纳什均衡，是因为双方都会有单方面改变策略的动机（任一局中人针对对方 的最优反应是， 即增加产量会获利），两厂商都这样想也就出现了纳什均衡的结局。一次，古