2014_第8章_对策论

北京科技大学经济管理学院1管理系统建模与优化第8章对策论——竞争、对抗、利益分配北京科技大学经济管理学院2博弈行为与博弈论第一节博弈论概述博弈论的概念北京科技大学经济管理学院3对博弈论的理解北京科技大学经济管理学院4博弈论与决策论北京科技大学经济管理学院5北京科技大学经济管理学院6博弈论的发展历史北京科技大学经济管理学院7博弈论的创立于发展北京科技大学经济管理学院8博弈论思想明确用于经济领域北京科技大学经济管理学院9北京科技大学经济管理学院10北京科技大学经济管理学院11纳什的生平约翰.纳什(JohnNash)于1928年在美国出生。当纳什申请普林斯顿大学研究院时，他的老师为他所写的推荐信只有一行字：“此人是天才”。(Thismanisagenius)。年仅二十二岁便取得普林斯顿大学数学博士学位。博士论文《非合作博弈》只有27页，发展并奠定了博弈论的数学基础。北京科技大学经济管理学院121951年在麻省理工任教，1957年与物理系学生艾莉西亚.拉德结婚，1959年患精神分裂症，多次进出精神病院，20多年后渐渐康复。1994年，与JohnC.Harsanyi和ReinhardSelten同获诺贝尔经济学奖。北京科技大学经济管理学院13从1994年至今，已有6项博弈论研究获得诺贝尔经济学奖北京科技大学经济管理学院14•2012年10月15日晚上7点，瑞典皇家科学院诺贝尔奖评审委员会宣布，2012年诺贝尔经济学奖授予哈佛大学教授埃尔文·罗斯及加州大学罗伊德·沙普利，以奖励他们在稳定配置理论及市场设计实践上所作出的贡献。•沙普利使用合作博弈方法来研究和对比不同的匹配方法，其关键在于保证配对是稳定的，也就是配对的双方都不会有更满意的其他选择。•罗斯则意识到了沙普利的理论和计算可让实践中重要市场的运作方式变得更清晰。他成功地通过系统性的实验室实验支持了前述结论。比如，他参与了一系列日常实践中的制度设计，帮助医生和医院、学生和学校、器官捐赠者和接受者之间进行配对。•评审委员会认为，尽管两位研究者的研究是独立完成的，但沙普利的基础理论与罗斯的实验性实践一经结合，已创造出一个繁荣的经济学研究领域，提升了多个市场的表现。今年的诺贝尔经济学奖因此授予经济工程领域的这一杰出实例。北京科技大学经济管理学院15北京科技大学经济管理学院16博弈的基本要素北京科技大学经济管理学院17北京科技大学经济管理学院18以儿童猜拳问题为例：对儿童甲来说，其支付矩阵（赢得矩阵）：局中人、策略集与支付规则构成了Game的基本内涵。A甲＝石剪布石01-1剪-101布1-10练习：写出田忌赛马问题的支付矩阵北京科技大学经济管理学院19战国时期，齐王提出要与田忌进行赛马。双方约定:•从各自的上、中、下三个等级的马中，各选一匹参赛；•每匹马均只能参赛一次，每一次比赛双方各出一匹马；每一次负者要付给胜者千金。•在同等级的马中，田忌的马不如齐王的马；而如果田忌的马比齐王的马高一等级，则田忌的马可取胜。讨论：混合零和博弈+信息不对称北京科技大学经济管理学院20博弈论的类型北京科技大学经济管理学院21北京科技大学经济管理学院22北京科技大学经济管理学院23北京科技大学经济管理学院24第二节矩阵对策一、二人零和对策[案例]（俾斯麦海的海空对抗，1943.2）此案例由O.G.Haywood于1954年解读。北京科技大学经济管理学院251943年，二战中的日本已处劣势，以新不列颠群岛拉包尔为基地的日本联合舰队，受命去支援被美军团团包围在新几内亚莱城的日军。此情报被美军获得，盟军统帅麦克阿瑟命令太平洋战区盟军空军司令Kenny将军，对日舰队实施空中打击。北京科技大学经济管理学院26俾斯麦海海空对抗示意图新几内亚莱城(被困日军)新不列颠群岛拉包尔(山本五十六的联合舰队)北航线(3天)天气恶劣南航线(3天)天气晴好Kenny的空军基地北京科技大学经济管理学院27局中人：Kenny将军、山本五十六大将Kenny策略集：S1={α1,α2}α1——重点侦察北线，α2——重点侦察南线。日舰队策略集：S2={β1,β2}β1——走北线，β2——走南线。北京科技大学经济管理学院28试分析双方的策略的选择。局Kenny日舰队天距有效轰炸势侦察航行气离天数1北线(α1)北线(β1)坏远2天2北线(α1)南线(β2)好近2天3南线(α2)北线(β1)坏远1天4南线(α2)南线(β2)好近3天北京科技大学经济管理学院29此例策略分析中的重要背景（特征）：•强对弱的对局，双方均清楚这一点；•双方将帅均为理智型；•基本信息双方共享；•一方损失即为另一方所得（即支付的代数和为0）。即这是一个二人零和对策。北京科技大学经济管理学院30案例中，盟军的支付（赢得）矩阵A为：盟军的理性考虑，在最少赢得中取最大；日军的理性考虑，在最多损失中取最小。A=(aij)2×2α1α2β1β22213=aij为策略对(αi,βj)中盟军的赢得北京科技大学经济管理学院31数学表达：盟军：首先作“行中取小”，即Min{aij}={2,1}j然后作“列中取大”，即结果，取策略α1，即重点搜索北线。Max[Min{aij}]=Max{2,1}=2ijiα1α2β1β22213北京科技大学经济管理学院32日军：首先作“列中取大”，即α1α2β1β22213Max{aij}={2,3}i然后作“行中取小”，即Min[Max{aij}]=Min{2,3}=2jij结果，取策略β1，即选择北航线。北京科技大学经济管理学院33此对策G的解为：(α1,β1)，此对策G的值为：V＝a11＝2。与此次海空对抗战役的实际情况一致。北京科技大学经济管理学院34一般：若二人零和对策G={S1,S2,A}中有则称G为具有鞍点的矩阵对策。MaxMin{aij}=MinMax{aij}=ai0j0……(*)ijji并称策略对(αi0,βj0)为纯策略解，相应的ai0j0称为此对策G的值。(*)式即为VonNeumann的“最大—最小定理”。鞍点北京科技大学经济管理学院35二、二人非零和对策1．[囚徒悖论]犯罪嫌疑人甲与乙，因已被警方获取一项犯罪证据而被拘留，并将受到判刑惩处。但法院对他们另一项犯罪的指控证据尚不足，有待他们的相互指证与坦白。北京科技大学经济管理学院36法院向分别关押的甲与乙指出：•依据第一项犯罪情节，甲、乙各判刑1年；•对第二项犯罪嫌疑，一方若坦白及揭发对方，而另一方拒不合作，则对合作方免去1年判刑并释放；不合作方则重判，判刑9年；•对第二项犯罪甲、乙均坦白并揭发对方，则二罪合计判刑，但减为7年。试分析甲、乙的策略。北京科技大学经济管理学院372．二人非零和对策：囚徒悖论中，策略集S甲={坦白(α1)，不坦白(α2)}S乙={坦白(β1)，不坦白(β2)}甲、乙的支付矩阵A、B分别为：A=α1α2β1β2-70-9-1B=β1β2α1α2-70-9-1由于在此矩阵对策中，局中人双方支付的代数和不为0，故称之为“二人非零和对策”。北京科技大学经济管理学院383．Nash均衡如果一个局势（或一个策略对）对每一个局中人的自利性都满足，即双方都认为自己选择的策略对已有利，则此局势（策略对）称为Nash均衡。北京科技大学经济管理学院39在“囚徒悖论”中，囚徒甲的分析是：如选α1，即坦白，则面临的支付是：-7（当乙也坦白）0（当乙不坦白）如选α2，即不坦白，则面临的支付是：-9（当乙坦白）-1（当乙不坦白）故甲的自利性策略是α1（坦白）。同理可得，乙的自利性策略是β1（坦白）。结果：囚徒悖论的Nash均衡是(α1,β1)。北京科技大学经济管理学院404．悖在何处？不难看出，若甲、乙同时拒不坦白，则第二项罪名无法量刑，甲、乙均只被判刑一年。即甲、乙的最佳选择应是(α2,β2)。“囚徒悖论”与社会伦理相悖。北京科技大学经济管理学院415．“囚徒悖论”所引发的思考•抓住模型的要点：⑴非零和对策，即非绝对对抗，存在妥协余地；⑵信息不沟通；⑶双方均为自利性导向。•如能沟通，则双方可获最优化结果。•对政治、经济某些情况有理论指导价值。其他的二人非零和博弈：情侣博弈北京科技大学经济管理学院42对纳什均衡的进一步理解北京科技大学经济管理学院43北京科技大学经济管理学院44其他的二人非零和博弈：中美知识产权问题引发的一次对抗局中人：中国与美国策略集：S美={惩罚(β1)，不惩罚(β2)}S中={报复(α1)，不报复(α2)}支付矩阵：（1996.5）试分析双方的策略选择。中国α1α2β1β2(-50,-50)(50,-150)(-150,50)(20,20)美国北京科技大学经济管理学院45分析：•这是一个二人非零和对策问题•(α1,β1)即美方惩罚，中方报复，是唯一的Nash均衡•双方的最佳选择应是(α2,β2)，即妥协，美方在中方让步下不执行惩罚；中方在美方取消惩罚的承诺下取消报复•途径：沟通与妥协（龙永图语：“谈判就是妥协”）其他的二人非零和博弈：智猪博弈北京科技大学经济管理学院46该问题的纳什均衡策略？北京科技大学经济管理学院47北京科技大学经济管理学院4849智猪博弈的思考•“小猪躺着大猪跑”的现象是由于故事中的游戏规则所导致的。规则的核心指标是：每次落下的食物数量和踏板与投食口之间的距离。50•改变方案一：减量方案。投食仅原来的一半分量。结果是小猪大猪都不去踩踏板了。小猪去踩，大猪将会把食物吃完；大猪去踩，小猪将也会把食物吃完。谁去踩踏板，就意味着为对方贡献食物，所以谁也不会有踩踏板的动力了。•但因为大猪和小猪的耐饿能力不一样，大猪有能力撑得更久，小猪会先被饿死（例如现在的房地产中介）。51•改变方案二：增量方案。投食为原来的一倍分量。结果是小猪、大猪都会去踩踏板。谁想吃，谁就会去踩踏板。反正对方不会一次把食物吃完。小猪和大猪相当于生活在物质相对丰富的“共产主义”社会，所以竞争意识却不会很强。•对于游戏规则的设计者来说，这个规则的成本相当高（每次提供双份的食物）；而且因为竞争不强烈，想让猪们去多踩踏板的效果并不好。52•改变方案三：减量加移位方案。投食仅原来的一半分量，但同时将投食口移到踏板附近。结果呢，小猪和大猪都在拼命地抢着踩踏板。等待者不得食，而多劳者多得。每次的收获刚好消费完。•对于游戏设计者，这是一个最好的方案。成本不高，但收获最大。北京科技大学经济管理学院53课堂练习北京科技大学经济管理学院54例8.2设有矩阵对策G=S1,S2,A，其中：S1=1,2,3,4，S2=1,2,3。213324213508A三、二人有限混合对策北京科技大学经济管理学院55北京科技大学经济管理学院56北京科技大学经济管理学院57纳什均衡的存在性•在一个有限个博弈者的博弈中，如果每个博弈者可选的纯策略个数是有限的，那么该博弈中总存在一个混合策略纳什均衡。（Nash1950年用Kakutani不动点定理进行了存在性证明）•纯策略纳什均衡可视为混合策略纳什均衡的特殊情况。•纳什均衡并不唯一存在。北京科技大学经济管理学院58混合策略纳什均衡的计算：以斗鸡（鹰鸽）博弈为例-100，-1001，-1-1,10,0北京科技大学经济管理学院59甲进退乙进退纯策略纳什均衡：（甲：进；乙：退）（甲：退；乙：进）其余局势均不稳定是否存在混合策略均衡？•定理：在一个N人博弈中，σ=（σ1,σ2,…σN）是一个混合策略组合，用Si表示博弈者i在其混合策略σi中使用的所有正概率纯策略的集合，那么σ构成一个混合策略纳什均衡的必要条件是：对于所有的i=1,2,…,N,对于所有的si，ui(si’,σ-i)=ui(si’,σ-i).北京科技大学经济管理学院60混合策略纳什均衡的计算方法：策略等值法•给定甲的混合策略，无论乙实行纯策略中的哪一种，乙的效用总是一样。否则，甲的混合策略就还存在改善的空间，即不是均衡策略。•x(-100)+(1-x)1=x(-1)+(1-x)0x=1/100北京科技大学经济管理学院61混合策略纳什均衡：（甲：1/100进；