《大连海事大学-刘巍-高等运筹第十一讲》由会员分享，可在线阅读，更多相关《大连海事大学-刘巍-高等运筹第十一讲（223页珍藏版）》请在金锄头文库上搜索。
1、高等运筹学,大连海事大学 刘巍,目录,第一篇 运筹学发展历史 第二篇 运筹学中的数学规划 第三篇 运筹学中的组合优化 第四篇 运筹学中的随机优化 第五篇 运筹学中的博弈论 第六篇 运筹学中管理科学 第七篇 运筹学中智能计算 第八篇 运筹学发展势态,第四篇 运筹学中的博弈论,第十八章 非合作博弈 第十九章 合作博弈与合作的演化,4,博弈论（Game Theory),5,从田忌赛马谈起,6,古代中国的运筹典故,齐王赛马（田忌赛马） 孙膑(约公元前380-432),孙武的后世子孙,战国中期著名军事家,担任齐国将领田忌的军师. 孙膑的“斗马术”是我国古代运筹思想中争取总体最优的脍炙人口的著名范例.,7
2、,齐王-田忌赛马 :,孙膑曾在齐国将领田忌手下当门客。田忌常和齐威王（公元前356320年在位）及诸公子以赛马。田忌的马有上、中、下三等；齐王的马也有上、中、下三等，但每一等都比田忌同等的马好，于是田忌屡赛屡输。,8,田忌赛马,齐威王,田忌,得意洋洋,垂头丧气,第一次,9,田忌赛马,这次他俩又下了1000两黄金的赌注，田忌一筹莫展。就在这时，孙膑对田忌说：“您尽管同他赛，我有办法让您赢。” 比赛又开始了!,10,齐威王,田忌,目瞪口呆,转败为胜,第二次,11,齐王令出上马，孙膑让田忌先出下马，给齐王舒舒服服、轻而易举地赢了第一场；然后齐王令出中马，孙膑让田忌出上马，经过激烈比赛，田忌的马赢了；
3、最后齐王出下马，孙膑让田忌出中马，田忌的马又赢了。3场比赛，田忌以2：1取胜，“卒得王千金”。,12,田忌反败为胜，使齐王大为惊讶。于是田忌向齐王推荐孙膑。齐王准奏，任命孙膑为军师。此后孙膑屡建战绩。而“田忌赛马”则成为脍炙人口的一个故事。,成为军事上一条重要的用兵规律,即要善于用局部的牺牲去换取全局的胜利,从而达到以弱胜强的目的.他的基本思想是不强求一局的得失,而争取全盘的胜利.,13,“田忌赛马” 是典型的对策思想的成功运用！ 博奕论是一门内容广泛且复杂的学科，不仅是经济学，政治学、军事、外交、国际关系、公共选择等，都涉及到博奕论,14,博弈论的定义,“博弈论是研究决策主体的行为发生直接相
4、互作用时候的决策以及这种决策的均衡问题的”也就是说，当一个主体，好比说一个人或一个企业的选择受到其他人、其他企业选择的影响，而且反过来影响到其他人、其他企业选择时的决策问题和均衡问题。所以在这个意义上说，博弃论又称为“对策论”.,博弈论可以解释一些经济和社会现象，比如家电的价格战、民航业的价格战、国家之间的军备竞赛、“劣币逐良币”等等现象。,现代博弈论(亦称对策论)起源于20世纪初，以策梅洛、博雷尔和冯诺依曼等人的工作为代表。二次世界大战为博弈论的应用提供了广泛的背景，加快了博弈论体系的形成。冯诺伊曼和摩根斯顿在1944年合著的博弈论与经济行为完善了博弈论的数学理论，使之系统化和公理化。此外，
5、纳什等人也对博弈论做出了重大贡献，奠定了非合作博弈的基础。博弈论的研究对象与社会、政治、军事、经济、科学、技术等很多领域都有密切关系和广泛应用，一直是运筹学及相关领域的重要研究热点。,16,博弈论是一门十分有趣但理论上又是十分艰深的学问，我今天打算用一些大家能够凭直观或简单分析就能把握的例子为大家介绍博弈论的基本概念及应用，以引起大家对这门目前已成为热门科学的兴趣和获得初步的了解。这些例子也是我们在日常生活中经常所遇到的问题或观察到的现象，通过博弈论，我们能够更加深刻地理解它们。,第二十三章 非合作博弈,截至目前，博弈论体系中最为完善的组成部分是零和博弈，其在应用方面最著名的例子是冷战时期美国
6、和原苏联之间的军备竞赛以及著名的核遏制战略。1994年诺贝尔经济学奖得主纳什在20世纪50年代初奠定了非合作博弈的基础，对非合作博弈论体系的建立做出了重大贡献。事实上，因在”非合作博弈论中开创性的均衡分析”方面的杰出贡献，泽尔腾、海萨尼与纳什同时获得1994年诺贝尔经济学奖，他们的贡献涵盖了具有完全或不完全信息的静态、动态博弈的均衡分析理论。,18,1. 囚徒困境 两个小偷甲和乙联手作案，私入民宅被警方逮住但未获证据。警方将两人分别置于两间房间分开审讯，政策是若一人招供但另一人未招，则招者立即被释放，未招者判入狱10年；若二人都招则两人各判刑8年;若两人都 不招则未获证据但因私入民宅 各拘留1
7、年。,一、什么是博弈论：,19,Prisoners Dilemma,20,表1 囚徒困境博弈 乙 招 不招 招 甲 不招 （问题1：甲、乙如何选择？）,21,尽管甲不知乙是否招供，但他认为自己选“招”最好，因而甲会选择“招”，乙也同样会选择“招”，结果各判8年；但若两人都不招，结果是两人只被判1年，但这种结果是不会出现的。 我们可以运用“剔除劣战 略”的方法来获得这样的结果。,22,甲或乙可以作出的选择被称为“战略”，如“招”或“不招”都是战略。,23,对甲来说 ，尽管他不 知道乙是选择了“招”还是“不招”，他发现他自己选择“招”都是比选择“不招”为好的。因此，“不招”是相对于“招”的劣战略，
8、他不会选择劣战略。所以，甲会选择“招”。 同样，根据对称性，乙也会选择“招”，结果是甲乙两人都“招”。,24,甲和乙是参与博弈的人，称为“局中人”。表1中每一个小方格内的数字被称为局中人的支付，其中左边的数字代表甲的支付，右边的是乙的支付。表1中的双变量矩阵称为博弈支付矩阵。 局中人所选择的战略构成的组合（招,招）被称为博弈均衡。这个组合中前后两个战略分别表示甲和乙所选择的战略。,25,表1 囚徒困境博弈 乙 招 不招 招 甲 不招,26,甲和乙都不会选择劣战略“不招”，称为“剔除劣战略的占优战略均衡”。其中“招”是占优于(优于)“不招”的占优战略。 我们可以利用这个道理来分析日常生活中的许多
9、不合作现象。,27,2. 生活中的“囚徒困境”例子,例子1 商家价格战 出售同类产品的商家之间本来可以通过共同将价格维持在高位而获利，但实际上却是相互杀价，结果都赚不到钱。 当一些商家共谋将价格抬高，消费者实际上不用着急，因为商家联合维持高价的垄断行为一般不会持久，可以等待垄断的自身崩溃，价格就会掉下来。,28,譬如，2000年我国几家生产彩电的大厂商合谋将彩电价格维持高位，他们搞了一个“彩电厂家价格自律联盟”，并在深圳举行了由多家彩电厂商首脑参加的“彩电厂商自律联盟高峰会议”。当时，国家有关部门还未出台相关的反垄断法律，对于这种在发达国家明显属于违法行为的所谓“自律联盟”，国家在法律上暂时还
10、是无能为力的。寡头厂商在光天化日之下进行价格合谋，并且还通过媒体大肆炒作，这在发达国家是不可思议的。,29,但是，尽管政府当时无力制止这种事情，公众也不必担心彩电价格会上涨。这是因为，“彩电厂商自律联盟”只不过是一种“囚徒困境”，彩电价格不会上涨。在高峰会议之后不到二周，国内彩电价格不是上涨而是一路下跌。这是因为厂商们都有这样一种心态：无论其他厂商是否降价，我自己降价是有利于自己的市场份额扩大的。,30,例子2 为什么政府要负责修建公共设施，因 为私人没有积极性出资修建公共设施 设想有两户相居为邻的农家，十分需要有一条好路从居住地通往公路。修一条路的成本为4，每个农家从修好的好路上获得的好处为
11、3。如果两户居民共同出资联合修路，并平均分摊修路成本，则每户居民获得净的好处（支付）为3-4/2=1；当只有一户人家单独出资修路时，修路的居民获得的支付为3-4=-1（亏损）， “搭便车”不出资但仍然可以使用修好的路的另一户人家获得支付3-0=3，见表2。,31,表2 修路博弈 乙 修 不修 修 甲 不修,32,我们看到，对甲和乙两家居民来说，“修路”都是劣战略，因而他们都不会出资修路。 这里，为了解决这条新路的建设问题，需要政府强制性地分别向每家征税2单位，然后投入4单位资金修好这条对大家都有好处的路，并使两家居民的生活水平都得到改善。,33,这就是我们看到的为什么大多数路、桥等公共设施都是
12、由政府出资修建的原因。 同样的道理，国防、教育、社会保障，环境卫生等都由政府承担资金投入，私人一般没有积极性承担这方面服务的积极性和能力。,34,例子3 苏格兰的草地为什么消失了？公共资源经常被过度利用的原因。 在18世纪以前，英国苏格兰地区有大量的草地，其产权没有界定，属公共资源，大家都可以自由地在那里放牧。草地属于“可再生资源”，如果限制放牧的数量，没有被牛羊吃掉的剩余草皮还会重新长出大面积草场，但如果不限制放牧规模，过多的牛羊将草吃得一光二净，则今后不会再有新草生长出来，草场就会消失。,35,由于草地的产权没有界定，政府也没有对放牧作出规模限制，每家牧民都会如此盘算：如果其他牧民不约束自
13、己的放牧规模，让自己的牛羊过多地到草地上吃草，那么，我自己一家约束自己的放牧规模规模对保护草场的贡献是微乎其微的，不会使草场免于破坏；相反，我也加入过度放牧的行列，至少在草场消失之前还会获得一部分短期的收益。,36,如果其他牧民约束放牧规模，我单独一家人过度放牧不会破坏广褒的牧场，但自己却获得了高额的收益。因此，任何一位牧民的结论都会是：无论其他牧民是否过度放牧，我选择“约束自己的放牧规模”都是劣战略，从而被剔除。大家最终都会选择过度放牧，结果导致草地消失，生态破坏。,37,类似的例子还有： 渤海中的鱼愈来愈少了，工业化中的大气及河流污染，森林植被的破坏等。解决公共资源过度利用的出路是政府制订
14、相应的规制政策加强管理，如我国政府规定海洋捕鱼中，每年有一段时间的“休渔期”，此时禁止捕鱼，让小鱼苗安安静静地生长，大鱼好好地产卵，并对鱼网的网眼大小作出规定，禁用过小网眼的捕网打鱼，保护幼鱼的生存。又如在三峡库区，为了保护库区水体环境，关闭了前些年泛滥成灾的许多小造纸厂等。,38,例子4 为什么在城市中心道路上禁止汽 车鸣喇叭？ 禁鸣喇叭一方面是为了控制城市噪声污染，另一方面是基于以下的博弈论原因。见表3，当汽车司机可以鸣喇叭时，可能为汽车超速抢行提供条件。但当大家都抢行时，城市交通拥挤加重，反而都难以顺利通行，获得低支付（2,2)。,39,表3 交通博弈 司机2 缓行 抢行 缓行 司机1
15、抢行,40,但当对方缓行时，自己抢行会占便宜，获得支付9。 这个博弈中，“缓行”是劣战略，剔除后得到“剔除劣战略后的占优战略均衡”（抢行,抢行），这不是一个好的均衡。当禁止鸣喇叭时，司机为了避免造成交通事故，只得缓行，从而得到好的结果（缓行,缓行）。,41,1. 智猪博弈 猪圈中有一头大猪和一头小猪，在猪圈的一端设有一个按钮，每按一下，位于猪圈另一端的食槽中就会有10单位的猪食进槽，但每按一下按钮会耗去相当于2单位猪食的成本。如果大猪先到食槽，则大猪吃到9单位食物，小猪仅能吃到1单位食物；如果两猪同时到食槽，则大猪吃7单位，小猪吃3单位食物；如果小猪先到，大猪吃6单位而小猪吃4单位食物。表4给
16、出这个博弈的支付矩阵。,二、智猪博弈：对诸多经济现象的解释,42,表4 智猪博弈 小猪 按 等待 按 大猪 等待,43,这个博弈没有“剔除劣战略均衡”，因为大猪没有劣战略。 但是，小猪有一个劣战略“按”，因为无论大猪作何选择，小猪选择“等待”是比选择“按”更好一些的战略。 所以，小猪会剔除“按”，而选择“等待”；大猪知道小猪会选择“等待”，从而自己选择“按”，所以，可以预料博弈的结果是(按,等待）。这称为“重复剔除劣战略的占优战略均衡”，其中小猪的战略“等待”占优于战略“按”，而给定小猪剔除了劣战略“按”后，大猪的战略“按”又占优于战略“等待”。,44,2. 例子,在经济生活中，有许多“智猪博弈”的例子。 例子6 股市博弈
