高等运筹第十一讲（刘巍）大连海事大学

高等运筹学大连海事大学刘巍目录第一篇运筹学发展历史第二篇运筹学中的数学规划第三篇运筹学中的组合优化第四篇运筹学中的随机优化第五篇运筹学中的博弈论第六篇运筹学中管理科学第七篇运筹学中智能计算第八篇运筹学发展势态第四篇运筹学中的博弈论第十四章

非合作博弈第十五章

合作博弈及其它博弈问题4从田忌赛马谈起5古代中国的运筹典故

齐王赛马（田忌赛马）

孙膑(约公元前380-432),孙武的后世子孙,战国中期著名军事家,担任齐国将领田忌的军师.

孙膑的“斗马术”是我国古代运筹思想中争取总体最优的脍炙人口的著名范例.

6齐王-田忌赛马:

孙膑曾在齐国将领田忌手下当门客。田忌常和齐威王（公元前356—320年在位）及诸公子以赛马。田忌的马有上、中、下三等；齐王的马也有上、中、下三等，但每一等都比田忌同等的马好，于是田忌屡赛屡输。7田忌赛马齐威王

田忌得意洋洋垂头丧气第一次8田忌赛马

这次他俩又下了1000两黄金的赌注，田忌一筹莫展。就在这时，孙膑对田忌说：“您尽管同他赛，我有办法让您赢。”比赛又开始了!9齐威王

田忌目瞪口呆转败为胜第二次10齐王令出上马，孙膑让田忌先出下马，给齐王舒舒服服、轻而易举地赢了第一场；然后齐王令出中马，孙膑让田忌出上马，经过激烈比赛，田忌的马赢了；最后齐王出下马，孙膑让田忌出中马，田忌的马又赢了。3场比赛，田忌以2：1取胜，“卒得王千金”。

齐王

田忌上下√×上中√×中下√×11

田忌反败为胜，使齐王大为惊讶。于是田忌向齐王推荐孙膑。齐王准奏，任命孙膑为军师。此后孙膑屡建战绩。而“田忌赛马”则成为脍炙人口的一个故事。

成为军事上一条重要的用兵规律,即要善于用局部的牺牲去换取全局的胜利,从而达到以弱胜强的目的.他的基本思想是不强求一局的得失,而争取全盘的胜利.12“田忌赛马”是典型的对策思想的成功运用！博奕论是一门内容广泛且复杂的学科，不仅是经济学，政治学、军事、外交、国际关系、公共选择等，都涉及到博奕论

13博弈论的定义“博弈论是研究决策主体的行为发生直接相互作用时候的决策以及这种决策的均衡问题的”也就是说，当一个主体，好比说一个人或一个企业的选择受到其他人、其他企业选择的影响，而且反过来影响到其他人、其他企业选择时的决策问题和均衡问题。所以在这个意义上说，博弃论又称为“对策论”.博弈论可以解释一些经济和社会现象，比如家电的价格战、民航业的价格战、国家之间的军备竞赛、“劣币逐良币”等等现象。现代博弈论(亦称对策论)起源于20世纪初，以策梅洛、博雷尔和冯·诺依曼等人的工作为代表。二次世界大战为博弈论的应用提供了广泛的背景，加快了博弈论体系的形成。冯·诺伊曼和摩根斯顿在1944年合著的《博弈论与经济行为》完善了博弈论的数学理论，使之系统化和公理化。此外，纳什等人也对博弈论做出了重大贡献，奠定了非合作博弈的基础。博弈论的研究对象与社会、政治、军事、经济、科学、技术等很多领域都有密切关系和广泛应用，一直是运筹学及相关领域的重要研究热点。15

博弈论是一门十分有趣但理论上又是十分艰深的学问，我们用一些大家能够凭直观或简单分析就能把握的例子为大家介绍博弈论的基本概念及应用，以引起大家对这门目前已成为热门科学的兴趣和获得初步的了解。这些例子也是我们在日常生活中经常所遇到的问题或观察到的现象，通过博弈论，我们能够更加深刻地理解它们。第十四章非合作博弈截至目前，博弈论体系中最为完善的组成部分是零和博弈，其在应用方面最著名的例子是冷战时期美国和原苏联之间的军备竞赛以及著名的核遏制战略。1994年诺贝尔经济学奖得主纳什在20世纪50年代初奠定了非合作博弈的基础，对非合作博弈论体系的建立做出了重大贡献。事实上，因在”非合作博弈论中开创性的均衡分析”方面的杰出贡献，泽尔腾、海萨尼与纳什同时获得1994年诺贝尔经济学奖，他们的贡献涵盖了具有完全或不完全信息的静态、动态博弈的均衡分析理论。17

1.囚徒困境两个小偷甲和乙联手作案，私入民宅被警方逮住但未获证据。警方将两人分别置于两间房间分开审讯，政策是若一人招供但另一人未招，则招者立即被释放，未招者判入狱10年；若二人都招则两人各判刑8年;若两人都不招则未获证据但因私入民宅各拘留1年。一、什么是博弈论：18Prisoner’sDilemma19表1囚徒困境博弈

乙

招不招招甲不招（问题1：甲、乙如何选择？）

-8,-80,-10-10,0-1,-120

尽管甲不知乙是否招供，但他认为自己选“招”最好，因而甲会选择“招”，乙也同样会选择“招”，结果各判8年；但若两人都不招，结果是两人只被判1年，但这种结果是不会出现的。我们可以运用“剔除劣战略”的方法来获得这样的结果。

21

甲或乙可以作出的选择被称为“战略”，如“招”或“不招”都是战略。

22

对甲来说，尽管他不知道乙是选择了“招”还是“不招”，他发现他自己选择“招”都是比选择“不招”为好的。因此，“不招”是相对于“招”的劣战略，他不会选择劣战略。所以，甲会选择“招”。同样，根据对称性，乙也会选择“招”，结果是甲乙两人都“招”。23

甲和乙是参与博弈的人，称为“局中人”。表1中每一个小方格内的数字被称为局中人的支付，其中左边的数字代表甲的支付，右边的是乙的支付。表1中的双变量矩阵称为博弈支付矩阵。局中人所选择的战略构成的组合（招,招）被称为博弈均衡。这个组合中前后两个战略分别表示甲和乙所选择的战略。24表1囚徒困境博弈

乙

招不招招甲不招-8,-80,-10-10,0-1,-125

甲和乙都不会选择劣战略“不招”，称为“剔除劣战略的占优战略均衡”。其中“招”是占优于(优于)“不招”的占优战略。

我们可以利用这个道理来分析日常生活中的许多不合作现象。26

2.生活中的“囚徒困境”例子

例子1商家价格战

出售同类产品的商家之间本来可以通过共同将价格维持在高位而获利，但实际上却是相互杀价，结果都赚不到钱。当一些商家共谋将价格抬高，消费者实际上不用着急，因为商家联合维持高价的垄断行为一般不会持久，可以等待垄断的自身崩溃，价格就会掉下来。27

譬如，2000年我国几家生产彩电的大厂商合谋将彩电价格维持高位，他们搞了一个“彩电厂家价格自律联盟”，并在深圳举行了由多家彩电厂商首脑参加的“彩电厂商自律联盟高峰会议”。当时，国家有关部门还未出台相关的反垄断法律，对于这种在发达国家明显属于违法行为的所谓“自律联盟”，国家在法律上暂时还是无能为力的。寡头厂商在光天化日之下进行价格合谋，并且还通过媒体大肆炒作，这在发达国家是不可思议的。28

但是，尽管政府当时无力制止这种事情，公众也不必担心彩电价格会上涨。这是因为，“彩电厂商自律联盟”只不过是一种“囚徒困境”，彩电价格不会上涨。在高峰会议之后不到二周，国内彩电价格不是上涨而是一路下跌。这是因为厂商们都有这样一种心态：无论其他厂商是否降价，我自己降价是有利于自己的市场份额扩大的。

29例子2为什么政府要负责修建公共设施，因为私人没有积极性出资修建公共设施

设想有两户相居为邻的农家，十分需要有一条好路从居住地通往公路。修一条路的成本为4，每个农家从修好的好路上获得的好处为3。如果两户居民共同出资联合修路，并平均分摊修路成本，则每户居民获得净的好处（支付）为3-4/2=1；当只有一户人家单独出资修路时，修路的居民获得的支付为3-4=-1（亏损），“搭便车”不出资但仍然可以使用修好的路的另一户人家获得支付3-0=3，见表2。30表2修路博弈

乙修不修修甲不修

1,1-1,33,-10,031

我们看到，对甲和乙两家居民来说，“修路”都是劣战略，因而他们都不会出资修路。这里，为了解决这条新路的建设问题，需要政府强制性地分别向每家征税2单位，然后投入4单位资金修好这条对大家都有好处的路，并使两家居民的生活水平都得到改善。

32

这就是我们看到的为什么大多数路、桥等公共设施都是由政府出资修建的原因。同样的道理，国防、教育、社会保障，环境卫生等都由政府承担资金投入，私人一般没有积极性承担这方面服务的积极性和能力。33

例子3苏格兰的草地为什么消失了？公共资源经常被过度利用的原因。

在18世纪以前，英国苏格兰地区有大量的草地，其产权没有界定，属公共资源，大家都可以自由地在那里放牧。草地属于“可再生资源”，如果限制放牧的数量，没有被牛羊吃掉的剩余草皮还会重新长出大面积草场，但如果不限制放牧规模，过多的牛羊将草吃得一光二净，则今后不会再有新草生长出来，草场就会消失。34

由于草地的产权没有界定，政府也没有对放牧作出规模限制，每家牧民都会如此盘算：如果其他牧民不约束自己的放牧规模，让自己的牛羊过多地到草地上吃草，那么，我自己一家约束自己的放牧规模规模对保护草场的贡献是微乎其微的，不会使草场免于破坏；相反，我也加入过度放牧的行列，至少在草场消失之前还会获得一部分短期的收益。35

如果其他牧民约束放牧规模，我单独一家人过度放牧不会破坏广褒的牧场，但自己却获得了高额的收益。因此，任何一位牧民的结论都会是：无论其他牧民是否过度放牧，我选择“约束自己的放牧规模”都是劣战略，从而被剔除。大家最终都会选择过度放牧，结果导致草地消失，生态破坏。

36类似的例子还有：

渤海中的鱼愈来愈少了，工业化中的大气及河流污染，森林植被的破坏等。解决公共资源过度利用的出路是政府制订相应的规制政策加强管理，如我国政府规定海洋捕鱼中，每年有一段时间的“休渔期”，此时禁止捕鱼，让小鱼苗安安静静地生长，大鱼好好地产卵，并对鱼网的网眼大小作出规定，禁用过小网眼的捕网打鱼，保护幼鱼的生存。又如在三峡库区，为了保护库区水体环境，关闭了前些年泛滥成灾的许多小造纸厂等。37

1.智猪博弈

猪圈中有一头大猪和一头小猪，在猪圈的一端设有一个按钮，每按一下，位于猪圈另一端的食槽中就会有10单位的猪食进槽，但每按一下按钮会耗去相当于2单位猪食的成本。如果大猪先到食槽，则大猪吃到9单位食物，小猪仅能吃到1单位食物；如果两猪同时到食槽，则大猪吃7单位，小猪吃3单位食物；如果小猪先到，大猪吃6单位而小猪吃4单位食物。表4给出这个博弈的支付矩阵。二、智猪博弈：对诸多经济现象的解释38表4

智猪博弈

小猪按等待按大猪等待

5,14,49,-10,039

这个博弈没有“剔除劣战略均衡”，因为大猪没有劣战略。但是，小猪有一个劣战略“按”，因为无论大猪作何选择，小猪选择“等待”是比选择“按”更好一些的战略。所以，小猪会剔除“按”，而选择“等待”；大猪知道小猪会选择“等待”，从而自己选择“按”，所以，可以预料博弈的结果是(按,等待）。这称为“重复剔除劣战略的占优战略均衡”，其中小猪的战略“等待”占优于战略“按”，而给定小猪剔除了劣战略“按”后，大猪的战略“按”又占优于战略“等待”。40

2.例子

在经济生活中，有许多“智猪博弈”的例子。

例子6股市博弈在股票市场上，大户是大猪，他们要进行技术分析，收集信息、预测股价走势，但大量散户就是小猪。他们不会花成本去进行技术分析，而是跟着大户的投资战略进行股票买卖，即所谓“散户跟大户”的现象。

41例子7为何股份公司中的大股东才有投票权？

在股份公司中，大股东是大猪，他们要收集信息监督经理，因而拥有决定经理任免的投票权，而小股东是小猪，不会直接花精力去监督经理，因而没有投票权。42

例子8为什么中小企业不会花钱去开发新产品？

在技术创新市场上，大企业是大猪，它们投入大量资金进行技术创新，开发新产品，而中小企业是小猪，不会进行大规模技术创新，而是等待大企业的新产品形成新的市场后生产模仿大企业的新产品的产品去销售。43

例子9为什么只有大企业才会花巨额金钱打广告？

大企业是大猪，中小企业是小猪。大企业投入大量资金为产品打广告，中小企业等大企业的广告为产品打开销路形成市场后才生产类似产品进行销售。

44

表5给出的博弈中，甲和乙都没有劣战略，所以，不能通过重复剔除劣战略获得博弈结果。三、纳什均衡与商业中心区的形成45表5存在纳什均衡的博弈

乙

LMRU

甲

D（问题2：甲和乙分别会选择什么战略？）

1,14,21,32,31,22,146

当甲选“U”时，乙会选“R”；而当乙选“R”时，甲应该选“D”而不是“U”；但当甲选“D”时，乙会选“L”；给定乙选“L”，甲选“D”是最好的选择，他不会改变选择“D”；给定甲不改变选“D”，乙也不会改变其选择“L”。所以，可以预期（D,L）是甲乙最终完成的稳定的选择。47

称（D,L)为“纳什均衡”。纳什均衡是局中人战略选择上构成的一种“僵局”，给定其他局中人的选择不变，任何一个局中人的选择是最好的，他也不会改变其战略选择。剔除劣战略的占优战略均衡和重复剔除劣战略的占优战略均衡是纳什均衡，但相反的结论不成立。48

在城市街道上，我们常见到一些地段上的商店十分拥挤，构成一个繁荣的商业中心区，但另一些地段却十分冷僻，没什么商店。对于这种现象，我们可以运用纳什均衡的概念来加以解释。甲乙

1/2

图1

商业位置博弈

··49

见图1，有一个长度为1单位的街道，在街道两边均匀地分布着居民。现有两家商店决定在街道上确定经营位置。如果甲在街道中间位置1/2处设店，则乙的最好选择是紧靠甲的左边或右边设店。50

当乙在甲的右边紧靠甲设店时，其右边街道上的顾客都是乙的顾客；如果乙不是紧靠甲而是远离甲设店，则其顾客只是其右边街道的居民，不如它紧靠甲设店时多，因而在远离甲的位置设店是劣战略。所以给定甲在1/2处设店，乙在紧靠甲的左边或右边设店是最优的。反过来，给定乙在接近1/2处设店，甲的最优选择也是在1/2附近设店。这样，甲和乙挤在1/2处设店就是纳什均衡，这就是商业中心区的形成原理。51

如果局中人在进行行动选择时有先后顺序之分，这种博弈就被称为“动态博弈”。在图2中，有两个房地产开发商A和B分别决定在同一地段上开发一栋写字楼。由于市场需求有限，如果他们都开发，则在同一地段会有两栋写字楼，超过了市场对写字楼的需求，难以完全出售，空置房太多导致各自亏损1百万。

四、动态博弈与承诺行动52

当只有一家开发商在这个地段开发一栋写字楼时，它可以全部售出，赚得利润1百万。假定A先决策，B在看见A的决策后再决策是否开发写字楼。在图2中，用“博弈树”表示博弈过程。

53

图2

房地产开发博弈A不开发开发BB开发不开发开发不开发(-1,-1)(1,0)(0,1)(0,0)54

在其中每一条“路径”的末端用向量给出A和B的支付，称为支付向量。下面用“逆向归纳法”可以求解这个博弈。在B进行决策的2个“决策结”上，B在左边的决策结上选择“不开发”；而在右边的决策结上选择“开发”。即给定A开发，B就不开发；给定A不开发，B就开发。B应避免同时与A都选择开发而蒙受损失。55

在这种情况下，A在自己的决策结上当然选择“开发”，因为他预计当自己选择“开发”后，B会选择“不开发”，自己就净赚一百万。当B威胁A说：“不管你是否开发，我都会在这里开发写字楼。”倘若A将B的话当了真，A就不敢开发，让B单独开发写字楼占便宜。但是，B的威胁是“不可置信”的。当A不理会B的威胁而果断地开发出一栋写字楼时，B其实不会将事前的威胁付诸实施。因为“识时务者为俊杰”，在A已开发的情况下，B的最优决策是“不开发”而不是“开发”。56

但是，如果B在向A发出威胁的同时又当着A的面与第三者C打赌一定要在该地段上开发出一栋写字楼，否则输给C2百万元。B与C为此签定合同并加以公证有效。这时，博弈变成图3所示的动态博弈。57图3

承诺行动后房地产开发博弈A不开发开发BB开发不开发开发不开发(-1,-1)(1,-2)(0,1)(0,-2)58

称B的这种行动为“承诺行动”，它使原来不可置信的威胁变为可以置信。这时，A就不得不相信B一定要开发写字楼的威胁了，于是放弃开发写字楼的计划，让B如愿以偿单独开发写字楼。B不仅未向C支付2百万元，反而净赚1百万。我们可以运用“承诺行动”的原理来分析许多经济及军事现象。59例子10欧共体在空中客车与波音公司的竞争中对空中客车公司的战略性补贴。

欧共体为了打破美国波音公司对全球民航业的垄断，曾放弃欧洲传统的自由竞争精神而对与波音公司进行竞争的空中客车公司进行补贴。60

当双方都未获得政府的补贴时，两个公司都开发新型飞机会因市场饱和而亏损，但若一家公司开发而另一家公司不开发时，则开发的那家公司会获巨额利润，见表6。61表6

未补贴时的博弈

空中客车开发不开发开发波音不开发

-10,-10100,00,1000,062

此时有两个纳什均衡，即一家开发而另一家不开发。下面，考虑欧共体对空中客车进行补贴20个单位的情况。此时，当两家都开发时，空中客车仍然盈利10单位而不是亏损，博弈矩阵见表7。63表7

有补贴时的博弈

空中客车开发不开发开发波音不开发

-10,10100,00,1200,064

这时只有一个纳什均衡，即波音公司不开发和空中客车公司开发的均衡（不开发,开发），这有利于空中客车。在这里，欧共体对空中客车的补贴就是使空中客车一定要开发（无论波音是否开发）的威胁变得可置信的一种“承诺行动”。65

小孩玩的游戏“石头，剪子，布”，也是一种博弈。但是，这个博弈有一种有趣的特征，即给定一方的任何选择，另一方都有制胜对方的战略，所以，给定一方任何一个战略，对方都有制胜这个战略的战略，因而这个战略不是最优的。任何“纯战略”都不是最优的，纯战略是“石头，剪子，布”中的任何一个。

五、混合战略博弈66

但是，我们知道，玩这个游戏是总是以对方不易猜出的随机方式出招。事实上，可以通过数学证明，当双方都以每个战略按1/3的概率出招时，达成一种双方都不愿改变这种概率分布的局面。这被称为“混合战略纳什均衡”，而这种以随机方式选择纯战略的博弈被称为“混合战略博弈”。以混合战略博弈的概念，我们来看下面几个例子。67

例子14为什么一般人总是小错不断，大错不犯；偷税漏税的一般是中小企业，大企业会老老实实地交税？

税务部门不会对所有企业的交税情况每一次都去检查，因为这样做的成本太高，得不偿失。所以，税务部门总是随机地对企业的交税情况进行检查。68

企业也是随机地在交税与偷漏税之间进行选择。税收部门与企业间进行的是混合战略博弈。因为如果企业总是交税，税务部门就最好不检查；但给定不检查，企业就会偷漏税。所以，两者只有在随机地检查与不检查，企业随机地在偷漏税与交税之间选择，才会达成均衡。

69

对于大企业，因一旦偷税就数目巨大，所以，税务部门在随机检查时放在大企业上的可能性就大一些；而给定税务部门检查大企业的可能性较大，大企业偷漏税的行为就较少，否则就容易被逮个正着。所以，偷漏税较多的就是一些中小企业，大企业纳税的积极性较高。同样，大人物或有钱人纳税的积极性应较高，至于我国在过去一段时期有钱人反而不交税的现象主要源于制度不健全或已有的制度得不到贯彻所致。同样的道理，在犯罪或对错误的监督惩罚博弈中，也是混合博弈，人们可能总是大错不犯小错不断。70

例子11田忌赛马新编

春秋战国时期，齐威王常与旗下大将田忌赛马。规则是：每次赛三局，每一局齐威王与田忌各出一匹马比赛奔跑速度。每一局中的胜者赢败方一千斤铜。田忌有上、中、下三匹马，而齐威王也有上、中、下三匹马。每次比赛，第一局田忌出上马，齐威王也出上马；第二局田忌出中马，齐威王也出中马；第三局，田忌出下马，齐威王也出下马。齐威王的上马比田忌的上马好，齐威王的中马也比田忌的中马好，齐威王的下马还是比田忌的下马好。于是，每次比赛的结果都是田忌连输三局。71

田忌的谋士孙膑了解了田忌的困境后，就打听到这样一个消息：尽管齐威王的上、中、下三匹马都要比田忌的对应上、中、下三匹马好，但碰巧的是田忌的上马可胜齐威王的中马，田忌的中马可胜齐威王的下马。于是，孙膑为田忌献计：下一次比赛中第一局时田忌出下马对齐威王的上马输一局，第二局田忌出上马对齐威王的中马，第三局田忌出中马对齐威王的下马，这样可连赢两局，最后净胜一千斤铜。田忌依计而行，果真赢回一千斤铜。72

这个故事一般被很多人当作博弈论的例子来演绎，但实际上这个故事与博弈论中的假定是有差异的。博弈论会假定所有局中人都是理性的，不能假定一些局中人聪明而另一些局中人却是傻子。当田忌出下马时，齐威王最好的选择是出下马而不是上马。孙膑的计谋中假定齐威王是傻子，当田忌出下、上、中马时，他仍然按上、中、下马出，当然要输了。事实上，当田忌出下马时，齐威王应出下马，但齐威王出下马时，田忌不应出下马而是出中马，但此时齐威王又应出中马而不是下马了，……。这样，博弈不会有纯战略的均衡。73

两人只能玩混合战略博弈，齐威王分别以1/6随机的概率选择出上、中、下马的任一排列，田忌也如此。由于齐威王存在绝对优势，他平均看来仍然会赢田忌一千斤铜。

74

例子12如果曹操与诸葛亮一样聪明：三国演义中的华容道博弈

在《三国演义》中，曹操在赤壁大战中一败涂地，率残兵败将向许都方向逃窜。诸葛亮命关羽率兵在途中阻截曹军。当时，第一批拦截大军是赵云率领的，第二批拦截大军是张飞带队的，第三批才是关羽率部伏击