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

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

非合作博弈第十九章

合作博弈与合作的演化4博弈论（GameTheory)

5从田忌赛马谈起6古代中国的运筹典故

齐王赛马（田忌赛马）

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

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

7齐王-田忌赛马:

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

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

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

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

齐王

田忌上下√×上中√×中下√×12

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

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

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

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

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

乙

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

-8,-80,-10-10,0-1,-121

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

22

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

23

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

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

乙

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

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

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

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

例子1商家价格战

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

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

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

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

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

乙修不修修甲不修

1,1-1,33,-10,032

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

33

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

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

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

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

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

37类似的例子还有：

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

禁鸣喇叭一方面是为了控制城市噪声污染，另一方面是基于以下的博弈论原因。见表3，当汽车司机可以鸣喇叭时，可能为汽车超速抢行提供条件。但当大家都抢行时，城市交通拥挤加重，反而都难以顺利通行，获得低支付（2,2)。39

表3交通博弈

司机2

缓行抢行缓行司机1

抢行

8,81,99,12,240

但当对方缓行时，自己抢行会占便宜，获得支付9。这个博弈中，“缓行”是劣战略，剔除后得到“剔除劣战略后的占优战略均衡”（抢行,抢行），这不是一个好的均衡。当禁止鸣喇叭时，司机为了避免造成交通事故，只得缓行，从而得到好的结果（缓行,缓行）。41

1.智猪博弈

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

智猪博弈

小猪按等待按大猪等待

5,14,49,-10,043

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

2.例子

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

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

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

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

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

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

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

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

48

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

乙

LMRU

甲

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

1,14,21,32,31,22,150

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

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

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

1/2

图1

商业位置博弈

··53

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

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

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

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

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

57

图2

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

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

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

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

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

称B的这种行动为“承诺行动”，它使原来不可置信的威胁变为可以置信。这时，A就不得不相信B一定要开发写字楼的威胁了，于是放弃开发写字楼的计划，让B如愿以偿单独开发写字楼。B不仅未向C支付2百万元，反而净赚1百万。我们可以运用“承诺行动”的原理来分析许多经济及军事现象。63

例子10项羽的“破釜沉舟”。例子11韩信赵国之战，“置之死地而后生”。例子12欧共体在空中客车与波音公司的竞争中对空中客车公司的战略性补贴。

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

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

未补贴时的博弈

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

-10,-10100,00,1000,066

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

有补贴时的博弈

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

-10,10100,00,1200,068

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

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

五、混合战略博弈70

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

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

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

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

73

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

例子15田忌赛马新编

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

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

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

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

78

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

在《三国演义》中，曹操在赤壁大战中一败涂地，率残兵败将向许都方向逃窜。诸葛亮命关羽率兵在途中阻截曹军。当时，第一批拦截大军是赵云率领的，第二批拦截大军是张飞带队的，第三批才是关羽率部伏击。由于曹军兵多将广，前二批伏击军不能逮住曹操，只是抢劫一些军械马匹之类。79

待曹军冲过赵云、张飞两道关后，进入关羽的伏击地带。但是，当时关羽与曹操相遇的地方有两条道，一条是华容道，除此外还有另一条道。诸葛亮令关羽伏兵于华容道，并且要求关羽在华容道上点燃树枝冒出烟雾引曹操到来。当时关羽不解，问诸葛亮，“如果在伏兵之处点火，岂不令曹兵看见而改走另一条道逃脱？”诸荀亮叫关羽不要再问，只如此照办即可。80

当曹操冲破赵云、张飞的阻截后，来到华容道前，看见华容道上静悄悄的，但有烟火萦绕。曹操大笑道：“孔明以为我会上他的当，故意叫人在华容道上点火让我走另一条道，而他却伏兵于这条道上好逮住我呢！我偏不上他的当！”于是，曹操令大军径直上华容道上而去，结果与关羽大军撞个正着。81

曹操为何进了孔明的圈套呢？这里的道理是这样的：孔明知道曹操是聪明人，而聪明人见华容道上有烟火会认为华容道上有伏兵，于是会避开华容道而走另一条路。如果孔明令关羽在另一条路等着，曹操就被逮住了。但是，曹操不仅聪明，而且还聪明过人，他也知道孔明的如此盘算来诱他上钩，他偏不上当，知道点火的华容道上无人，孔明的队伍在另一条道上呢！于是他选择走华容道。82

但是，依《三国演义》作者罗贯中的逻辑，孔明总是比曹操计高一筹，按博弈论的术语来说，就是孔明的理性程度要比曹操高上一阶。孔明也知道曹操知道孔明的打算，于是令关羽正好在点火的华容道上等着曹操。《三国演义》中的这个故事很可能是作者编造的，因为在《三国志》中并无这一情节。这里，罗贯中假设了曹操在智力上比孔明差一些，才有华容道上被关羽抓住，要不是关羽旧情难忘，曹操就死无葬身之地了。83

但是，如果我们不假定曹操比孔明要笨一些，而是相反假定曹操与孔明一样聪明，则曹操又知道孔明知道曹操知道孔明的打算，曹操就会知道关羽在华容道上等着他呢？此时曹操就避开华容道走另一条路。但是，这还没有完，因为若孔明知道曹操知道孔明知道……。显然，最终的结果是曹操与孔明玩混合战略博弈，曹操随机地以1/2的概率选择走华容道和另一条路，孔明也以1/2的概率令关羽守华容道或另一条路。84

于是，《三国演义》中的这一情节就应作如下改写：

诸葛亮抛出一枚硬币，决定关羽是守华容道呢还是另一条道……，而曹操也掷出一枚硬币，决定是走华容道呢还是走另一条路。平均看来，曹操有1/2的概率逃脱，而关羽也只有1/2的概率抓住曹操。如果说关羽在华容道上抓住了曹操，则纯属偶然、并非孔明比曹操计高一筹所致！85

博弈论中涉及到的生活中的各种经济学道理是十分多而有趣的。这里因时间关系还有许多有趣的例子没有为大家介绍，各位有机会可以通过其它的著作了解到博弈论深遂的道理及其在经济分析中的应用，希望大家能通过这种学习能对博弈论有更深入的认识。

八、总结第二十三章合作博弈熊、狼、狐狸一起抓了一只兔子，民主协商如何分配。狐狸对熊说：平均分只能各得1/3，这样吧，我们俩联合起来，平分如何？熊要答应，狼急了，于是狐狸对狼说：怎么样，我和熊联合起来可以让你什么也得不到，我可以和你合作，不过我要3/4。狼感激的点头，熊琢磨过味来，对狼说：别听那个两面三刀的，和我合作，我给你1/3。狐狸见势不妙，对狼说：别，我给你2/3，我只要1/3。狼成了抢手货，正得意，没留神狐狸和熊又开始嘀咕起来，有再次把自己晾在一边的不妙趋势，连忙钻去继续讨价还价。结果呢？在本世纪初，19位世界博弈论领域的权威学者接受采访，回答同样的5个问题，并对博弈论研究领域未来发展前景做出预测181.有多位学者一致认为合作博弈论在20世纪被忽视或者应该得到更多重视。经典合作博弈主要关注多个局中人之间的联盟形成方式及联盟效用分配方案，即多人结盟合作博弈的解，在20世纪中叶有过较多的研究，提出了一些重要的多人结盟合作博弈的解概念。目前多人合作博弈的发展明显滞后于多人非合作博弈，经典合作博弈论的突出特征是局中人的完全理性假设以及理论体系的不完善，因而“合作博弈让人们苦恼很长时间”。合作博弈的概念及其表示

合作博弈最重要的两个概念是联盟和分配。每个参与者从联盟中分配的收益正好是各种联盟形式的最大总收益,每个参与者从联盟中分配到的收益不小于单独经营所得收益。合作博弈的基本形式是联盟博弈,它隐含的假设是存在一个在参与者之间可以自由流动的交换媒介(如货币),每个参与者的效用与它是线性相关的。这些博弈被称为“单边支付”博弈,或可转移效用(TransferableUtility,TU)博弈。合作博弈的概念及其表示

合作博弈的结果必须是一个帕累托改进，博弈双方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受损害。合作博弈研究人们达成合作时如何分配合作得到的收益，即收益分配问题。合作博弈采取的是一种合作的方式，合作之所以能够增进双方的利益，就是因为合作博弈能够产生一种合作剩余。至于合作剩余在博弈各方之间如何分配，取决于博弈各方的力量对比和制度设计。因此，合作剩余的分配既是合作的结果，又是达成合作的条件。合作博弈的核心问题是参与人如何结盟以及如何重新分配结盟的支付。下面首先分析结盟的概念。与结盟相关联的就是特征函数。合作博弈强调群体理性

(grouprationality)群体理性的含义是：从一个群体整体角度，研究策略的选择，使得整体效用最大.字典中合作的含义指“为共同目的而一起行动”合作博弈的含义与非合作博弈相比，需要一个描述集体理性的效用函数。纳什认为(1951)，可利用纳什均衡这一基本概念（非合作博弈的理论基础），通过参与人间讨价还价过程，达成合作的实现。在协议集(bargainingsets)理论中对此进行了描述。合作博弈的含义可传递效用(transferableutility)为描述n人合作博弈，通常假设合作博弈具有可传递效用简单地说，该效用就像货币一样，可以在各参与人之间自由转让定义8.1.1

在n人博弈中，参与人集用表示，N的任意子集S称为一个联盟（coalition）

空集Φ和全集N也可以看成是一个联盟，当然单点集也是一个联盟。合作博弈的特征函数合作博弈的特征函数(characteristicfunction)是指，对于每一个联盟(coalition)S(S为N的任意一个子集)，指定一个函数v(S)，用以描述联盟S无需求助于S之外的参与人(N\S)所能得到的可传递效用的总量合作博弈的特征函数特征函数满足v(φ)=0对于满足对于S∩T=φ的联盟，若成立v(S∪T)≥v(S)+v(T)则称v

是超可加的(superadditive)关于特征函数的一些深入讨论此处从略合作博弈的各种解概念，就是基于特征函数进行的。合作的分配记一个合作博弈为{N,v(S),SN}一个分配(payoffallocation)就是一个向量x

=(xi),iN分量xi

可以被解释为合作结果对参与人i的效用分配水平。可行分配说一个分配对于联盟S是可行的(feasibleforacoalitionS)当且仅当核心的定义说联盟S能改进一个分配x，当且仅当v(S)>Σi∈S

xi当且仅当x是可行的，且不存在联盟能改进x

时，才说分配x在合作博弈的核心(core)中，即x在核心中的充要条件是核心的定义一般来说，核心是一个集合。可能结果是（具体实例从略）：无穷集，唯一集，空集。核心的理解是，如果合作博弈的一个可行分配x不在核心中，那就存在一个联盟S,该联盟中的参与人可通过更好地合作，并在他们之间分配价值v(S)，使得该分配结果严格优于x。Shapley值合作博弈的核心可能结果可能是空的或非常之大，这限制了核心作为合作博弈的解的应用我们希望导出一个具有普遍意义的解概念Shapley值是其中重要的解概念之一Shapley公理Shapley提出了看上去比较合理的几个公理假设在这些假设下，Shapley证明了任何合作博弈(N,v)存在唯一的Shapley值。可作为合作分配的一个解概念。Shapley值参与人集合N的一个置换(permutation)，是任一函数π：N

N，使得对于N中的每个j,N中恰好存在一个i,使得π(i)=j（π是单射，又是满射）给定上述置换π和任一联盟博弈v,令πv为满足πv

（{π(i)|i∈S}）=v(S),S为N的任一子集的联盟博弈。Shapley值Shapley公理1（对称性）对于合作博弈(N,v),在任一参与人的置换映射π(i)

下，分配结果应保持不变，即有φπ(i)(πv)=φi(v)公理1表明：一个参与人在博弈中的角色才是唯一的，而不是他在集合N中的特定名字或标号。Shapley值Shapley值说一个联盟R是合作博弈v的一个载体(carrier)，如果v(S∩R)=v(S),S是N的任意子集若R是v的一个载体，那么所有不在R中的参与人称为v的“多余人(dummies)”，因为他们进入任何联盟都不会改变该联盟的价值。Shapley值公理2（载体公理），对于合作博弈v和博弈的任一联盟R,若R是v的一个载体，则公理3（线性性）对于任意两个合作博弈v,w,满足0≤p≤1的任意p，以及N中的任一参与人i,均有Shapley值在上述3个公理假设下，Shapely证明了，存在唯一的一个映射φ,称为Shapley值，为Shapley值若v是超可加性的，则Shapely值从φi(v)≥v({i}),i∈N看，一定是个人理性的。因为超可加性意味着Shapley值供应链协调供应链是围绕核心企业，通过对信息流、物流、资金流的控制，从采购原材料开始，制成中间产品以及最终产品，最后由销售网络把产品送到消费者手中的将供应商、制造商、分销商、零售商、直到最终用户连成一个整体的功能网链结构模式。最简单的供应链包括一个供应商（Supplier）和一个分销商（Retailer）,供应商确定批发价格,分销商决定订货量。批发价格契约回购价格契约批发价格契约

供应商的参数与决策变量：：供应商的制造成本；供应商的缺货损失费；供应商对分销商的批发价格。分销商的参数与决策变量：：分销商的分销成本；分销商的缺货损失费；剩余产品的价值；分销商的固定零售价格；分销商的决策订货量。市场参数：：市场随机需求；：的分布函数；：的密度函数；：的数学期望。令＋，＋。如果订货量为，则期望销售量为：

有。批发价格契约则期望剩余存货为：。则期望缺货量为：。因此，分销商的收益函数为：

供应商的收益函数为：

则供应链的整体利润为：

批发价格契约整个供应链作为一个整体,进行最优化的集成决策，最优订货量满足的一阶条件。由此，从供应链整体最优化的角度，得到最优订货量满足：订货量是分销商的决策变量，分销商的决策是使最大化。利用关于的一阶条件，得到分销商的最优决策：批发价格契约

是从供应链整体角度的最优订货量,符合整体理性;是分销商从个体角度的最优订货量,符合个体理性.如果,则整体利益与个体利益就是协调的。能够等于吗?

显然有，供应商的批发价格不可能低于其生产成本，因此，不可能等于,即批发价格不能协调整个供应链。回购价格契约回购价格契约是指供应商为鼓励分销商订货，对分销商剩余的产品以回购价格回收，降低分销商多订货的风险。回购价格契约条件下，分销商的收益函数为：

如果供应商决定批发价格和回购价格，使分销商的收益正比于整个供应链的收益，例如使，则分销商的最优化策略也是供应链整体的最优策略。回购价格契约由，得到供应商的契约设计如下，如此设计的契约就可以协调整个供应链：因此,回购契约能够协调整个供应链，供应商可以通过任意分配供应链的整体利润。成本分担在现实生活和经济管理活动中，经常遇到这种情况：一些人或者经济组织为了实现各自的目标，大家或者部分成员联合起来，进行共同投资，以实现各自的目标，又降低各自所负担的公共投资的费用。这就是费用分担问题。大家能否实现合作，费用分担是否合理是关键。下面通过两个例题说明如何解决费用分担问题。成本分担例在一个地区有一个公共服务机构，如自来水场、有线电视网等，如图中O所示。三个乡镇（图中的所示）需要连接到这个公共服务机构。乡镇与服务机构之间、乡镇与乡镇之间的连接路线造价为边的权。问如何构建这个连接网络并分配建设费用？O1110998成本分担解：这显然是一个最小支撑树的构建和建设成本分担问题。、、分别连接到O的建设成本为C()＝9，C()＝10，C()＝11;将、连接到O的最小树的建设成本（最小支撑树的长度）为C(，)＝17，同样，C(，)＝18，C(，)＝11；将3个顶点连接到O的最小树的建设成本（最小支撑树的长度）C(，，)＝18。设、、分别承担的建设费用为,则建设费用的分配应该满足:

有无限个向量满足上式，每个向量都可以作为一个建设费用的分配方案。成本分担

核心集合：

核仁：

Shapley值：除了合作博弈的方法，在现实生活中还有一些符合惯常约定、经常被采用且大家也觉得基本合理的分配方法，如资源占用费用分担法和费用增量法。成本分担资源占用费用分担法是按照每个参与人对公共资源的使用来分摊费用，占用公共资源多，则分摊费用即大，否则，即小。最小费用最小网络如下：189

为3个参与人公用，费用9在3个参与人之间分配；为2个参与人公用，费用8在2个参与人之间分配；为自用，费用1由自己承担。因此，按照资源占用费用分担法，费用分担向量：。成本分担费用增量法是按照合作所增加的总量按照一定的比例在参与人之间进行分配的一种方法。例如，如果3个参与人都不进行合作，则需要承担的费用分别是9、10、11，比例是。如果3个参与人进行合作，则总的建设费用是18。将总建设费用18按照比例在3个参与人之间进行分配，则3个参与人分别承担的费用是：

分析发现：根本就不在核心中，因为和会形成一个联盟，反对这样一个分配，承担的费用太小。哥本哈根气候峰会博弈哥本哈根气候峰会博弈由美国、日本、澳大利亚等国组成的“伞形集团”和欧盟的代表也分别发言，表示愿意为应对气候变化提供“合适份额”的资金，并希望会议能达成一份有约束性的协议非洲国家集团、阿拉伯国家集团、最不发达国家集团和小岛国集团的代表在会上分别发言，呼吁发达国家立即为那些最易受影响的国家提供帮助，强调发展中国家有继续发展的正当权利等，要求会议达成一份长期的有约束性的协议，同时也指出一些国家不应该利用气候变化问题推行贸易保护主义。代表“77国集团和中国”发言的苏丹高级外交官易卜拉欣说，发达国家应该正视自己的历史责任，做出严格的减排承诺，各方应该继续坚持《京都议定书》，根据“共同但有区别的责任”原则，达成一份长期的应对气候变化协议。二氧化碳排放最多的国家1中国

31亿吨

2美国

28亿吨

3印度

6.3亿

4俄罗斯4.7亿吨

5德国4.3亿吨哥本哈根气候峰会博弈1发达国家欧、美、日为代表2发展中国家中、印、巴西、印尼3气候敏感国家和贫穷国家图瓦卢、马尔代夫、斐济等太平洋小岛国；非洲各国的立场中国，到2020年单位国内生产总值二氧化碳排放比2005年下降40％－45％美国将在哥本哈根气候变化大会上承诺2020年温室气体排放量在2005年基础上减少17％。英国：承诺到2020年和2050年分别减排2005年的34%和80%，各国立场欧盟：通过包括气候与能源一揽子计划和各种能效措施，无条件承诺到2020年较1990年减排20%以上。同时承诺抬高减排幅度至30%，前提是各工业化国家同意相当水平的减排力度，同时发展中国家做出重大贡献，共同促成国际条约的签署。挪威：首个承诺到2020年较1990年减排40%的国家，这与发展中国家要求富裕发达国家做出的减诺幅度一致。同时还承诺在2030年前成为“碳中立国”。各国立场巴西：承诺到2020年自主减排38%至42%。巴西国家气候变化计划涵盖了目标远大的林业发展措施，包括到2017年将森林非法砍伐面积减少70%，该数据最近被更新为到2020年减少80%。印度尼西亚：承诺自愿使用国家预算到2020年减排26%。印尼总统尤多约诺同时承诺，如果国际提供资金援助，能源和林业部门将减少41%的碳排放量。韩国：无条件承诺到2012年较2005年水平减排4%。这是在韩国今年提出的三种可能情境中最宏伟的一个目标。墨西哥：2008年气候变化特别项目包括86个阻碍碳排放量增长的具体目标。目前年碳排放量约为7亿吨，目标到2012年前减少5千万吨。俄罗斯：承诺到2020年较1990年减排20%至25%，之前做出的承诺是减排10%至15%。澳大利亚承诺到2020年较2000减排25%，前提是哥本哈根大会上能达成宏伟的全球减排目标哥本哈根气候峰会博弈中国代表团的烦躁可能有三个原因。1中国的减排计划似乎正在招致越来越多的质疑。中国的计划初看上去很美，但是一经推敲，人们便不难发现，中国的"减排计划"其实是一个"增排计划"。如果中国的国民生产总值在二零零五年至二零二零之间能够实现百分之八以上的经济增长，同时实现排放强度减少百分之四十的目标，那末中国的排放总量实际上将增长一倍左右。中国已经是世界上最大的排放国，在其他主要排放大国决定减少排放的绝对量的同时，中国却提出这么一个增加排放的绝对量的计划，说起来不太理直气壮。这也是西方国家要求中国提高减排的事实基础。哥本哈根气候峰会博弈2中国的立场在发展中国家之间也备受争议。受温室效应影响最大、承受能力最弱的是那些最穷的发展中小国，尤其是那些受海平面上升威胁最大的小岛国。他们的代表在会议的第三天明确地提出，此次会议应该达成一个比《京都议定书》更为严厉的新协议。这个协议不仅应该对发达国家、也应该对像中国这样的发展中大国具有约束力。中国对这个方案马上提出了反对。中国的立场引起了这些国家的强烈不满，因此中国所期待的发展中国家用同一个声音说话的计划也就成了水中阁楼。哥本哈根气候峰会博弈3巴西这样的一些发展中国家的大国，在减排问题上所采取的立场比中国主动。这对中国的国际形像有不少负面影响。巴西政府在参加气候峰会前也提出了减排目标。根据京都议定书的规定，作为发展中国家，巴西本来也没有具有约束性的减排义务。但是巴西却自愿做出了绝对减排的承诺。无论是用排放总量、排放密度、人均排放等任何一个指标来衡量，巴西温室气体排放上的责任都要比中国要小得多。巴西与中国在这一重大国际问题上不同立场的对比，使得一向声言要做一个"负责任的大国"的中国在面子上很有些挂不住。定义8.1.1

在n人博弈中，参与人集用表示，N

的任意子集S

称为一个联盟（coalition）。

空集和全集N

也可以看成是一个联盟，当然单点集也是一个联盟。定义8.1.2

给定一个n人博弈，S

是一个联盟，是指S和的两人博弈中S

的最大效用，称为联盟S

的特征函数（characteristicfunction）。

规定。根据定义，表示参与人与全体其他人博弈时的最大效用值，表示为。在很多情况下，一个联盟能获得的支付依赖于其他参与人所采取的行动。有时被解释为联盟独立于联盟的行动可保证的最大支付。合作博弈的概念及其表示

合作对策的分类主要是根据特征函数的性质。下面根据特征函数的性质介绍几类特殊的合作对策。如果仅与的个数有关，则称作对称博弈。如果，则称作常和博弈。如果，则称作简单博弈。例如，在投票博弈中，每个参与人的权重，

如果，则称作凸博弈。例8.1设有一个3人合作对策，每个参与人各有两个纯策略。当三人不合作时，其支付见下表。假设采用最稳妥策略，即最坏情况下选择最好，求合作博弈的支付函数合作博弈的概念及其表示解：用表示一个联盟，表示联盟中参与人的个数。当＝0，自然，有。当＝1，有3个，以为例。当，则。的策略集合，策略组合。与进行如下矩阵对策：合作博弈的概念及其表示

上述矩阵对策没有纯策略，的混合策略是，的混合策略是。的均衡值是。故。同理，可以求出。当＝2，有3个，以为例。当，则。的策略集合,

策略组合。与进行如下矩阵对策：合作博弈的概念及其表示上述矩阵对策有纯策略，的均衡值是。故。同理，可以求出。当＝3，有1个，，最大的联盟。的策略空间。有。至此特征函数的值已全部求出。合作博弈的概念及其表示

之所以称为特征函数，是因为这个合作博弈的性质基本由决定。由此可见对合作博弈的重要性。定理设是参与人集合上的特征函数，则有如下的超可加性：对于联盟和，如果，则证明以最稳妥策略为例给出证明。用表示联盟的策略空间。合作博弈的概念及其表示

上式说明，特征函数只有满足超加性，才有形成新联盟的必要性。否则，如果一个合作博弈的特征函数不满足超可加性，那么，其成员没有动机形成联盟，已经形成的联盟将面临解散的威胁。定理3的逆命题也是正确的，即：是一个集合，是定义在上的一个非负实值函数。满足：，如果则存在一个上的合作博弈，使成为该合作博弈的特征函数。合作博弈的概念及其表示

对于合作博弈，特征函数满足超加性，自然有：根据上述不等式，特征函数分成两种类型：

类型1，满足。即大连盟的效用是每个参与人的效用之和。这说明通过联盟并没有创造新的合作剩余，联盟没有价值，这种联盟也不可能维持。这种对策称为非实质性对策，没有研究价值，不是本章研究的范畴。对于非实质性对策，有，如果。合作博弈的概念及其表示

类型2，满足。即大连盟的效用大于每个参与人的效用之和。这说明通过联盟创造了新的合作剩余，联盟有意义，这种联盟能否维持，取决于如何分配合作剩余，使每个参与人的支付都有改善。这种对策称为实质性对策，是本章研究的范畴。分配

所谓分配就是博弈的一个维向量集合，之所以是维向量，是由于每个参与人都要得到相应的分配。维的分配向量称为博弈的“解”。定义8.1.3

对于合作博弈，对每个参与人，给予一个实值参数，形成维向量且其满足：

则称是联盟的一个分配方案。分配

分配的定义中，是基于个人理性，合作中的收益不能小于非合作中的收益，反映了参与人的参与约束。如果，那么，参与人是不可能参加联盟的。是基于集体理性，每个参与人的分配之和不能超过集体剩余。另外若没有全部被分配，显然不是一个帕类托最优的分配方案，不会参与人所接受。分配

在例8.1分配中，分配显然不是一个，而是无限个，无限个分配形成一个分配集合。对于实质博弈，其分配总是有无限个。例如，对于实质博弈，由于存在无限个正向量，满足。显然如下的都是分配，其中。用表示一个博弈的所有分配方案组成的集合。分配定义8.1.4

设的两个分配和，是一个联盟。如果分配方案和满足（i），；（ii）。则称分配方案在上优超于，或称分配方案在上劣于，记为。如果分配方案在上优超于，则联盟会拒绝分配方案，方案得不到切实执行。因为从到，中的每个参与人的收益都得到改善，创造的剩余又足以满足他们在中的分配。分配在优超关系中，联盟的特征：1.单人联盟不可能有优超关系。2.全联盟上也不可能有优超关系。因此，如果在上有优超关系，则。3.优超关系是集合上的序关系，这种序关系一般情况下不具有传递性和反身性。4.对于相同的联盟，优超关系具有传递性，即，，则有。5.对于不同的联盟，优超关系不具有传递性。核心

尽管可行分配集合中有无限个分配，但实际上，有许多分配是不会被执行的，或者不可能被参与人所接受的。很显然，联盟的每一个成员都不偏好于劣分配方案，因此，真实可行的分配方案应该剔除劣分配方案。定义8.3.1

在一个人合作博弈中，全体优分配方案形成的集合称为博弈的核心(core)，记为。显然有。核心说明：

1.核心是中的一个闭凸集。

2.若，则将中的向量作为分配，既满足个人理性，又满足集体理性。

3.用核心作为博弈的解，其最大缺陷是可能是空集。核心定理8.3.1

分配方案在核心中的充要条件是：（i），，

(ii)。证明如果，满足（i）、(ii)，则不可能被优超，即。反证法，设存在，使。根据优超的定义，有:则有，矛盾。如果，不满足(ii)，则一定被优超，即。核心对于，存在联盟，有，则定义，定义，使得在中平均分配，在