运筹学思想方法及应用 ch5 博弈论的思想方法及其应用

第五章博弈论的思想方法及其应用

运筹学OperationalResearch要想在现代社会做一个有文化的人，你必须对博弈论有一个大致了解.——诺贝尔经济学奖获得者

PaulSamuelson博弈论（TheGamesTheory)是运筹学学科的一个重要分支。具有竞争或对抗性质的行为称为博弈行为，在这类行为中，参与斗争或竞争的各方各自具有不同的目标和利益，为了达到各自的目的，各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最合理的方案。博弈论就是研究博弈行为中，斗争各方是否存在最合理的行动方案，以及如何找到这个合理方案的理论和方法。5.1博弈论的基本概念5.2矩阵博弈的纯策略5.3矩阵博弈的混合策略5.4矩阵博弈求解方法5.5纳什均衡5.6合作博弈与效益分配5.7动态博弈与承诺行动5.8应用举例附录博弈论与诺贝尔经济学奖5.1博弈论的基本概念5.1博弈论的基本概念1944年，数学家冯·诺伊曼(J.von-Neumann)和经济学家摩根施特恩（O.Morgenstern）写成了《博弈论与经济行为》一书，这是博弈论这一分支的经典之作.该书不仅建立了博弈论的严格的公理化体系，而且对大量的经济活动进行了深入的分析，奠定了博弈论的基础.

5.1博弈论的基本概念5.1博弈论的基本概念5.1博弈论的基本概念博弈论是矛盾和合作的规范研究，是系统研究决策主体的行为发生直接相互作用情况下的决策以及这种决策均衡的理论.也就是说，当一个决策主体的选择受到其他决策主体选择的影响，并且它的决策也影响其他决策主体的决策时的合理选择问题.博弈论思想的主要特征是各参与人所实施的行为方案（策略）相互依存，各方在冲突或合作后所实现的得失结果不仅取决于自己所采用的行为方案，同时也依赖于其他参与人所采用的行为方案，它是各参与人行为方案组合的函数.在现实生活中，经常可以看到一些具有对抗和竞争性的现象，如体育比赛、军事斗争中双方兵力的对抗，各公司企业之间的经济谈判以及为争夺市场而进行的竞争等等。在竞争过程中，各方为了达到自己的目标和利益，必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案，也就是说要研究采取对抗其他竞争者的策略。从数学角度来说，博弈论就是研究竞争行为中的竞争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。5.1博弈论的基本概念博弈论认为：人是理性的，即人人都会在约束条件下最大化自身的利益；人们在交往合作中有冲突，行为互相影响，而且信息不对称.5.1博弈论的基本概念5.1博弈论的基本概念囚徒困境问题甲和乙两个小偷联手作案，因私入民宅被警方抓住但未获证据。警方将两人分别置于两间房间分开审讯，政策是若一人招供但另一人未招，则招者立即被释放，未招者判入狱10年；若二人都招，则两人各判刑8年；若两人都不招，则未获证据但因私入民宅各拘留1年。将这些数据列出，如下：

5.1博弈论的基本概念囚徒困境博弈尽管甲不知道乙是否招供，但他认为自己选“招”最好，因而甲会选择“招”，乙也同样会选择“招”，结果各判8年；但若两人都不招，结果是每人只被判1年，但在“人是理性的，即人人都会在约束条件下最大化自身的利益”的基本假设下，这种结果是不会出现的.5.1博弈论的基本概念甲和乙是参与博弈的人，称为“局中人”.表中每一个小方格内的数字被称为局中人的支付，其中左边的数字代表甲的支付，右边的是乙的支付.表中的双变量矩阵称为博弈支付矩阵.局中人所选择的战略构成的组合（招,招）被称为博弈均衡.这个组合中前后两个战略分别表示甲和乙所选择的战略.5.1博弈论的基本概念如果甲和乙在决策时抛掉谨慎，加入一定的“疯狂”，不约而同地采取“不招”的策略，其结果是每人只被判1年.显然，这对甲、乙二人来说，比他们采取理性策略的结果“好”.

5.1博弈论的基本概念5.1博弈论的基本概念商家价格战

出售同类产品的商家之间本来可以通过共同将价格维持在高位而获利，但实际上却是相互杀价，结果都赚不到钱.当一些商家共谋将价格抬高，消费者实际上不用着急，因为商家联合维持高价的垄断行为一般不会持久，可以等待垄断的自身崩溃，价格就会掉下来.5.1博弈论的基本概念博弈论有三个基本假设：参与人是理性的；他们有这些理性的共同知识；他们知道博弈规则.任何一个博弈问题都包含如下三个要素：局中人、策略和支付函数.5.1博弈论的基本概念（1）局中人(Players)在一场具有竞争性的决策中，有制定对付对手的行动与方案权，并有权作出决策的参加者称为局中人，如囚徒困境问题中的甲和乙.局中人可理解为那些利益完全一致的集体或集团，局中人是有理智、聪明的，并有行动决定权的.我们称只有两个局中人的博弈现象为两人博弈;而多于两个局中人的博弈称为多人博弈.在多人博弈中，局中人之间允许合作的称为结盟博弈，不允许合作的称为不结盟博弈.

5.1博弈论的基本概念（2）策略(Strategies)在一局博弈中，每个局中人都有一套可供选择的指导自始至终如何行动的方案，以求争取较好的结果，我们称此行动方案为这个局中人的一个策略，而把这个局中人的策略全体称为这个局中人的策略集.在一局博弈中，各个局中人选定的策略构成的一个策略组，称之为一个局势.如果在一局博弈中，各个局中人只有有限的策略，我们称之为有限博弈；否则称为无限博弈.5.1博弈论的基本概念（3）支付函数(PayoffFunction)在一局博弈结束后，对每个局中人来说，其结果不外乎是赢（得）或输（失）.显然，这种输赢局势是随局中人所选取的策略组的变化而变化的，局中人选定一个策略组，必然对应着一个博弈结果.因此，我们可以用一个函数来表示输赢（或得失）.将这个函数称之为支付函数.对应所有策略组的支付函数的各个取值可以用一个矩阵来表示，称之为支付矩阵.5.1博弈论的基本概念对于一个博弈问题，如果在每一个局势中，全体局中人的得失相加都是零，则称此博弈为零和博弈，否则称为非零和博弈.5.1博弈论的基本概念博弈中有关局中人的策略集、支付函数等构成了博弈的信息.按照局中人对信息掌握的情况，可分为完全信息博弈和不完全信息博弈。按照局中人采取行动的次序，当局中人同时采取行动或在互相保密情况下采取行动，称这种情况为静态博弈.如果局中人采取行动有先后，后采取行动的人可以观察到前面人采取的行动，则属于动态博弈。按照局中人是否结盟情况，还可以将博弈分为结盟博弈与不结盟博弈.5.1博弈论的基本概念5.1博弈论的基本概念二人有限零和博弈

在众多博弈模型中，占有重要地位的是二人有限零和博弈，即在博弈只有两个局中人，各自的策略集只含有限个策略，每局中两个局中人的得失总和为零（即一个局中人的赢得恰为另一个局中人所输掉的值），这类博弈又称为矩阵博弈.5.1博弈论的基本概念5.1博弈论的基本概念【例5.1】田忌赛马战国时期（自公元前475周元王元年起，至公元前221年秦始皇吞并六国建立中国第一个统一的多民族的中央集权的封建国家为止，是我国历史上的战国时期）齐王与田忌赛马.双方约定：每人从自己的上、中、下三个等级的马中，各选出一匹马参赛，每一场比赛各出一匹马，一共比三场，每匹马只能参加一场比赛，每场比赛后输者要付给赢者一千金.就同级的马而言，齐王的马都比田忌的马强.解

在本问题中局中人为齐王和田忌。以马出场的顺序而言，齐王有六种博弈策略.例如先用上等马，再用中等马，最后下等马，以（上、中、下）表示之.同样，田忌也有六种博弈策略，即两位局中人的策略集都含有六个策略.

可以用表5.2表示齐王的支付.5.1博弈论的基本概念5.1博弈论的基本概念表5.25.1博弈论的基本概念将表5.2中的数字表成矩阵称为齐王的赢得矩阵.

这个博弈问题是一个二人有限零和博弈问题.形势显然对田忌不利.但是田忌的谋士孙膑建议，每场比赛前要齐王报他要出哪匹马.孙膑让田忌的下等马对齐王的上等马，用中等马对齐王的下等马，用上等马对齐王的中等马.结果反而赢了齐王一千金，这是一个典型的博弈问题.它表明在博弈问题中，局中人必须运用智慧，保守自己的秘密并设法获得对方的情报，采取恰当的策略方能取得较好的结果.5.1博弈论的基本概念本节知识要点

1.博弈论研究的问题

2.博弈论思想的主要特征

3.博弈论的基本概念

4.博弈论有三个基本假设

5.博弈论的分类

5.1博弈论的基本概念5.2矩阵博弈的纯策略局中人Ⅰ从

中选一个策略

，同时局中人Ⅱ从

中选一个策略

，这样就构成一个局势

对应于策略集

和，一共有

个局势.在局势

下局中人Ⅰ的赢得记为，则局中人Ⅰ在m个策略下的赢得构成一个矩阵.5.2矩阵博弈的纯策略用Ⅰ，Ⅱ分别表示两个局中人，设局中人Ⅰ有m个策略；局中人Ⅱ有n个策略；其策略集分别表示为，5.2矩阵博弈的纯策略称为局中人Ⅰ的赢得矩阵.

由于对策是零和的，

表示在同一局势下局中人Ⅱ的赢得，故局中人Ⅱ的赢得矩阵为记这个博弈为

矩阵博弈的数学模型为：，其中5.2矩阵博弈的纯策略5.2矩阵博弈的纯策略在矩阵博弈中要讨论的问题是：各局中人应该如何选择自己的策略，使自己在博弈中获得最好的结果.下面用一个例子说明.5.2矩阵博弈的纯策略【例5.2】设矩阵博弈局中人Ⅰ，Ⅱ应如何选择自己的策略，以保证自己在博弈中取得有利的地位？解:

对局中人Ⅰ而言，他的最大的收益是8，他理所当然地会选择策略，同时，他希望局中人Ⅱ选择策略。但是局中人Ⅱ发现，如果局中人Ⅰ采取策略，他不会愚蠢地选择以致失去8。反之，他会选择，这样他仅失去1。然而，当局中人Ⅱ选择时，局中人Ⅰ就会选择，这样做比选择有利，可使收益由1增加到3。这时，局中人Ⅰ、Ⅱ都不愿再改变选择，因为如果局中人Ⅱ改变选择，失去的不是3，而是5或4，如果局中人Ⅰ改变选择，其得到的不是3，而是1或2。显然，这种状态是一种平衡状态。5.2矩阵博弈的纯策略对应于策略，局中人Ⅰ的赢得由5降到3，然后又由3升到4；对应于策略，局中人Ⅰ的支付由1上升到3，然后又由3下降到2.中间这个数3，从第二行看来它形成一个凹槽，从第二列看它形成一个凸脊，正像一个马鞍形，点3处于马鞍的中心.5.2矩阵博弈的纯策略上面解题的数学方法为：对局中人Ⅰ来讲，先对矩阵A的每行元素取最小值：再从这些最小值中取最大值：。也就是说，局中人Ⅰ采取悲观主义原则，从最坏的情况中，取得的最好结果是3，这时，他应采取的策略是，不论局中人Ⅱ采取什么策略，都可以保证赢得不会少于3.5.2矩阵博弈的纯策略5.2矩阵博弈的纯策略注意到矩阵A中的元素反号后是局中人Ⅱ的赢得，故局中人Ⅱ采取悲观主义原则时，应先对矩阵A的每一列元素中取出最大值：再从这些最大值中取最小值：。因此，局中人Ⅱ应采取策略，则不论局中人Ⅰ采取什么策略，最大损失不会大于3。5.2矩阵博弈的纯策略因此，局中人Ⅰ、Ⅱ只有分别采取、时才是他们的最优策略。为了与后面的概念相区别，我们称、分别为局中人Ⅰ、Ⅱ的最优纯策略，而局势称为博弈的解，或博弈的纳什均衡。5.2矩阵博弈的纯策略一般地，对最优纯策略及纯策略意义下的纳什均衡有如下定义：考虑矩阵博弈如果成立等式则分别称为局中人Ⅰ、Ⅱ的最优纯策略，对应的策略组合即局势称为矩阵博弈在纯策略意义下的纳什均衡。数值称为矩阵博弈的值。【例5.3】

设矩阵博弈，其中5.2矩阵博弈的纯策略求解纳什均衡与博弈的值。解对局中人Ⅰ，先对矩阵A的每行求最小值，得到，再求其最大值得到3，即对局中人Ⅱ，先对矩阵A的每行求最大值，得到，再求其最大值得到3，即从而所以，该博弈的纳什均衡为，博弈的值.可以看出：满足不等式

将这个结论推广，我们给出如下定理：5.2矩阵博弈的纯策略5.2矩阵博弈的纯策略

矩阵博弈在纯策略意义下有纳什均衡的充分必要条件是：存在策略，使得或，定理5.15.2矩阵博弈的纯策略设矩阵博弈，其中

求解纳什均衡与博弈的值.【例5.4】解对局中人Ⅰ，先对矩阵A的每行求最小值，得到，再求其最大值得到5，即.

对局中人Ⅱ，先对矩阵A的每列求最大值，得到，再求其最小值得到5，即从而

所以，局势都是博弈的纳什均衡，博弈值。5.2矩阵博弈的纯策略本节知识要点

1.矩阵博弈的数学模型

2.博弈的纳什均衡

3.矩阵博弈在纯策略意义下有纳什均衡的充分必要条件5.3矩阵博弈的混合策略

5.3矩阵博弈的混合策略上节讨论了在纯策略意义下有纳什均衡的矩阵博弈问题。但是，并非所有的矩阵博弈在纯策略意义下都有纳什均衡。例如本章的齐王赛马的博弈在纯策略下没有纳什均衡。因为所以在齐王赛马的博弈中，双方都没有最优纯策略，从而在纯策略意义下就没有纳什均衡。5.3矩阵博弈的混合策略【例5.5】

设矩阵博弈，其中解

故此博弈不存在鞍点，从而双方都没有最优纯策略。5.3矩阵博弈的混合策略此时，我们可以设想局中人随机地取纯策略来进行博弈。例如，局中人Ⅰ以概率选取纯策略，以概率选取纯策略；局中人Ⅱ以概率选取纯策略，以概率选取纯策略。于是，对局中人Ⅰ来说，他的赢得可用期望值来描述：5.3矩阵博弈的混合策略由上式可以看出，当时，即局中人Ⅰ以概率选取纯策略时，其期望值至少是4，但不能保证期望值超过4，这是因为局中人Ⅱ取时，即以概率选取纯策略时，可以控制局中人Ⅰ的赢得不会超过4.

5.3矩阵博弈的混合策略从上述分析可以看出，每个局中人决策时，不是决定用哪一个纯策略，而是决定用多大概率选择每一个纯策略。

一般地，设矩阵博弈，其中5.3矩阵博弈的混合策略则将纯策略集合对应的概率向量分别称为局中人Ⅰ与Ⅱ的混合策略，这里是局中人Ⅰ选取的概率，是局中人Ⅱ选取的概率，显然，纯策略可以看成是混合策略的一种特殊情况。又称数学期望为局中人Ⅰ的赢得，为局中人Ⅱ的赢得，而称为混合局势。5.3矩阵博弈的混合策略对给定博弈，称为博弈的混合扩充，其中为局中人Ⅰ的所有混合策略集；为局中人Ⅱ的所有混合策略集。5.3矩阵博弈的混合策略在混合扩充博弈中，局中人Ⅰ选取某种混合策略时，必定要想到局中人Ⅱ会针对性选取一种策略，使其期望赢得最小，于是局中人Ⅰ的目标就是寻求一种以概率选取的策略，使局中人Ⅱ不论采取何种策略时，都能使自己的期望赢得中最小的尽可能大，即局中人Ⅰ想找到一个最大的数，使其在以概率选取策略时，对局中人Ⅱ的每种策略都有(5.1)

我们称为局中人Ⅰ的最优混合策略，简称最优策略。5.3矩阵博弈的混合策略同理，局中人Ⅱ也想以概率寻找最优策略，使局中人Ⅰ不论采取何种策略时，都能使自己的期望损失中最大的尽可能小，即局中人Ⅱ想找到一个最小的数，使其在以概率选取策略时，对局中人Ⅰ的每种策略都有（5.2）

我们称为局中人Ⅱ的最优策略.5.3矩阵博弈的混合策略可以证明，在任何一个给定的二人零和博弈中，对局中人Ⅰ和Ⅱ分别存在最优策略和，以及和，使得式（5.1）和（5.2）成立，且，我们称为博弈的值，而混合局势称为在混合策略意义下的一个纳什均衡。5.3矩阵博弈的混合策略定理5.2

设，则为的纳什均衡的充要条件是：存在数，使得是线性不等式组

的解，是线性不等式组5.3矩阵博弈的混合策略定理5.2表明，局中人Ⅰ的期望赢得至少为，局中人Ⅱ的期望损失至多为，且；如果局中人Ⅰ选用其最优策略，但局中人Ⅱ未选用其最优策略，则局中人Ⅰ的期望赢得将高于；同样，如果局中人Ⅱ选用其最优策略而局中人Ⅰ未选用其最优策略，则局中人Ⅱ的期望损失会低于.当局中人都采用其最优策略时，则可以达到某种程度的平衡，即混合策略意义下的纳什均衡.5.3矩阵博弈的混合策略定理5.3

任何一个给定的二人零和博弈一定存在混合策略下的纳什均衡。定理5.4

设为二人零和博弈在混合策略下的一个纳什均衡，，则（1）若，则；（2）若，则；（3）若，则；（4）若，则。本节知识要点

1.矩阵博弈的混合扩充

2.混合策略意义下的纳什均衡

3.定理5.2---定理5.45.4矩阵博弈求解方法

5.4矩阵博弈求解方法1.代数解法【例5.6】求例5.1中齐王与田忌各自的最优混合策略及博弈的值。解齐王的赢得矩阵

5.4矩阵博弈求解方法由于它没有鞍点，不存在纯策略解，由定理5.2可得到两组不等式：（5.3）

（5.4）

5.4矩阵博弈求解方法这里，每个均大于零，换言之，每个纯策略都可能被局中人选取。由定理5.3与定理5.4知，式（5.4）和（5.3）都应当取等号，将不等式组求解转化成线性方程组求解。将所有式子相加，便得：

由及其故得。代入其他各式解得5.4矩阵博弈求解方法齐王的最优策略是；田忌的最优策略是。博弈值。即比赛的双方都很聪明，有理智，总的结果是齐王赢一千金。5.4矩阵博弈求解方法2.图解法

用平面直角坐标图解的方法来求出双方的最优策略。【例5.7】

用图解法求解例5.5的博弈问题。解支付矩阵先考虑局中人Ⅰ：如果局中人Ⅱ取纯策略，则局中人Ⅰ赢得的期望值为如果局中人Ⅱ取纯策略，则局中人Ⅰ赢得的期望值为

5.4矩阵博弈求解方法现以策略和所取概率值和为横坐标，赢得为纵坐标，分别画出局中人Ⅱ取策略和时，局中人Ⅰ所能获得的赢得的变动直线l1和l2。如图5.4矩阵博弈求解方法这里注意到显然，只有以直线l1和l2的交点M处相应的概率值分别取策略和，才是局中人Ⅰ所选取的最优混合策略，这时，局中人Ⅰ的赢得总是，而不论局中人Ⅱ选择何种混合策略，由图知所以局中人Ⅰ的最优混合策略为显然，只有以直线l1和l2的交点M处相应的概率值分别取策略和，才是局中人Ⅰ所选取的最优混合策略，这时，局中人Ⅰ的赢得总是，而不论局中人Ⅱ选择何种混合策略，由图知

所以局中人Ⅰ的最优混合策略为当局中人Ⅰ取策略时，局中人Ⅱ损失的期望值为：用同样的方法作图，得局中人Ⅱ的最优混合策略，博弈值。5.4矩阵博弈求解方法同理，考虑局中人取最优策略的情况，当局中人Ⅰ取策略时，局中人Ⅱ损失的期望值为：5.4矩阵博弈求解方法【例5.8】设给定一个矩阵博弈，其中

求其最优策略及博弈值。解

我们注意到矩阵的第2列各数大于第1列对应各数，也就是无论局中人Ⅰ选取什么策略，局中人Ⅱ选取策略的损失都比选取策略的损失要大，故局中人Ⅱ绝不会去选取策略，他可以把从策略集中删去，并把第2列从中删去，即局中人Ⅱ只要用到策略，，，所以只要考虑下列矩阵就可以了。3.优超法5.4矩阵博弈求解方法解

我们注意到矩阵的第2列各数大于第1列对应各数，也就是无论局中人Ⅰ选取什么策略，局中人Ⅱ选取策略的损失都比选取策略的损失要大，故局中人Ⅱ绝不会去选取策略，他可以把从策略集中删去，并把第2列从中删去，即局中人Ⅱ只要用到策略，，，所以只要考虑下列矩阵就可以了。

此时再抹去中第3列得5.4矩阵博弈求解方法从局中人Ⅰ看来，中第2行各元素比第3行对应各元素大，也就是无论局中人Ⅱ选取什么策略，局中人Ⅰ选取策略比选取策略有利，这样，局中人Ⅰ删去策略，同样可删去策略，得5.4矩阵博弈求解方法利用上例结果可得

局中人Ⅰ的最优混合策略；局中人Ⅱ的最优混合策略。以上降低支付矩阵维数的方法称为优超法。5.4矩阵博弈求解方法优超法一般描述如下：在支付矩阵中，如果第i行元素都不小于第k行对应各元素，即，，则称局中人Ⅰ的策略优超于策略，记为。这时局中人Ⅱ无论选取哪种策略，局中人Ⅰ选取总比选取好。那么可将第k行元素从支付矩阵中抹去，即将策略从策略集中删去；如果中的第j列各元素都不大于第k列对应的各元素，即，，则称局中人Ⅱ的策略优超于策略，记为。这时，局中人Ⅰ无论选取哪一种策略，局中人Ⅱ选取总比选取好。那么，可将第k列从中抹去，即将策略从策略集中删去。5.4矩阵博弈求解方法定理5.5

设矩阵博弈，其中，，。如果被其余纯策略中之一所优超，由可以得到一个新矩阵博弈，其中，则有（1）；（2）中局中人Ⅱ的最优策略就是中局中人Ⅱ的最优策略；（3）如果是中局中人Ⅰ的最优策略，则就是中局中人Ⅰ的最优策略。5.4矩阵博弈求解方法4.线性规划解法从定理5.2的表示形式可以看出，求解矩阵博弈混合策略意义下的纳什均衡问题可以用线性规划方法求解。因为求相当于解

（5.5）及（5.6）5.4矩阵博弈求解方法不妨设，引入新变量（5.5）化为线性规划（5.6）化为线性规划（5.7）（5.8）这两个线性规划的最优解都存在，而且最优值相等。5.4矩阵博弈求解方法【例5.9】设给定一个矩阵博弈，其中求其最优策略及博弈值。解

此博弈既无鞍点，又不能用优超法简化，可用线性规划求解。求解的线性不等式组为5.4矩阵博弈求解方法及5.4矩阵博弈求解方法故局中人Ⅰ的最优混合策略为所以局中人Ⅱ的最优混合策略为解得

同理，解得

本节知识要点

主要介绍矩阵博弈求解方法：

1.代数解法

2.图解法

3.优超法

4.线性规划方法5.4矩阵博弈求解方法5.5纳什均衡

5.5纳什均衡在二人零和博弈中，双方局中人寻求的最优解是一种纳什均衡。当达到这种均衡时，无论是纯策略解还是混合策略解，只要其他局中人不改变自己的策略，则任何一方单独改变自己的策略，只能带来收益或效用的减少。纳什均衡是一种策略组合，它是每个局中人的策略对其他局中人策略的最优反应。下面先给出个局中人博弈的标准式，然后给出相应的纳什均衡的定义。5.5纳什均衡1.博弈的标准式在有n个局中人的博弈中，设第i个局中人的策略集为.用表示每个局中人选定某一个策略时形成的局势.这里是相应于该局势的第i个局中人的支付函数，则称为博弈的标准式.设有，如果对其他局中人所有可能策略组成的局势均有不等式成立，则称是对的严格劣战略.5.5纳什均衡2.纳什均衡定义在有n个局中人的标准式博弈中，如果局势满足：对每一个局中人是至少不劣于他针对其他n-1个局中人所选策略的最优反应策略，则称局势是该博弈的一个纳什均衡。即对任意的，有

或是最优化问题

的解.

5.5纳什均衡纳什均衡是博弈论中最重要的概念。纳什证明了在任何非合作的有限博弈（指局中人个数有限、每个局中人的策略集中的策略个数有限）中，都存在至少一个纳什均衡。5.5纳什均衡【例5.10】设有二人博弈，各自的策略和支付值如表所示。表中的每个数对表示局中人采用策略，局中人采用策略时，局中人的支付为，局中人的支付为。求其纳什均衡解。5.5纳什均衡解先判别是否存在劣策略，若有将其删除。判别方法：比较A的第i个和第l个策略,如果有,而且其中至少有一个取“>”号，则称l为劣策略；比较B的第j个和第k个策略，如果有,其中至少有一个取“>”号，则称第k个策略为劣策略.5.5纳什均衡在本例中，是劣策略，将其删除得到

5.5纳什均衡由于纳什均衡是每个局中人策略对其他局中人策略的最优反应，对局中人A：当局中人B采用策略时，局中人A的最优反应是采取策略，支付为5，在5下面划横线；当局中人B采用策略时，局中人A的最优反应是采取策略支付为6，在6下面划横线；当局中人B采用策略时，局中人A的最优反应时采取策略.支付为4，在4下面划横线。5.5纳什均衡对局中人B：当局中人A采用策略时，局中人B的最优反应是采取策略，支付为6，在6下面划横线；当局中人A采用策略时，局中人B的最优反应是采取策略，支付为6，在6下面划横线.对支付值都划有横线的组合，即为所求的纳什均衡解.这种解法简称为划线法.由上表可知，本例的纳什均衡解为(4,6)，其对应的策略组合为.该局势是一种平衡局势.5.5纳什均衡【例5.11】以弱敌强博弈在战争史上，不乏以弱胜强的例子。例如在二战中的诺曼底登陆战的谋略策划中，盟军就面临以弱敌强的问题。盟军有两个可以选择的登陆目标地，一是多佛，二是诺曼底。德国守军在人数上超过了盟军，并且就军事进攻而言，在人数相同的情况下，攻方与守方相比会处于不利的情形。下面，将这种情形模型化。假设有一支军队准备进攻一座城市，它有军力两个师；守城军队有三个师。通往城市有甲、乙两条道路或方向。两军相遇时，人数居多的一方取胜，当两方人数相等时，守方获胜。并假定军队只能整师调动。5.5纳什均衡攻方战略：

a.两个师集中沿甲方向进攻；

b.兵分两路，一个师沿甲方向进攻，另一个师沿乙方向进攻；

c.两个师集中沿乙方向进攻。守方战略：

A.三个师集中守甲方向；

B.两个师守甲方向，一个师守乙方向；

C.一个师守甲方向，两个师守乙方向；

D.三个师集中守乙方向。5.5纳什均衡用“+”、“－”，分别表示胜和败，攻、守双方布阵结果见下表

5.5纳什均衡分析：进攻方无劣战略，但守方有劣战略，A劣于B，D劣于C，故守方不会采用战略A和D，剔除后的博弈变为：5.5纳什均衡攻方知道守方不会选A和D，他由此知道博弈变成上图所示。此时，攻方就有一个劣战略b，他剔除b后得到新的博弈：

此时，两方的形势是相同的，即攻方尽管开始在军力上劣于守方，但实际上它只要运用计谋，其获胜的可能与守方是相同的。5.5纳什均衡本节知识要点

1.n个局中人博弈的标准式

2.纳什均衡与纳什均衡解

3.求纳什均衡解的划线法

5.6合作博弈与效益分配5.6合作博弈与效益分配1.问题的提出

多人合作博弈中的效益分配或费用分摊问题与现实的经济活动有着密切的关系.最典型的例子有横向经济联合中的效益分配问题和资金重组过程中的利益分配；大气污染总量控制优化治理投资的费用分摊；联合兴建污水处理厂建设费用的分摊；联合投资企业破产以后所发生的债务如何进行分担等。这类问题由于涉及的资金数目较大，比较敏感，只有处理好才能够保证合作项目的成功.本节以三人合作经商为问题为例，介绍解决多人合作博弈中的效益分配或费用分摊问题的基本概念和方法.5.6合作博弈与效益分配设有A,B,C三人经商.若各人单干，则每人仅能获利1万元；若A,B合作,可获利7万元，A,C合作可获利5万元，B,C合作可获利4万元，三人合作可获利10万元。问三人合作时应如何合理分配10万元的利益。由此可见，有A参加的合作，获利最大，7+5=12；有B参加的合作，获利次之，7+4=11；有C参加的合作，获利最小，5+4=9.在合作中，A贡献最大，B次之，C最小。故在分配利益时，应考虑与贡献联系起来。具体如何分配，这类问题就是n人合作博弈问题.下面介绍n人合作博弈的一些概念，并建立该问题的数学模型。2.n人合作博弈与特征函数设有n个局中人的集合对任一子集定义一实函数满足条件：（1）表示空集;（2）当，

(称为超可加性)。我们把称为一个n人合作博弈(也称结盟；称为I的特征函数，它描述合作的效益。5.6合作博弈与效益分配5.6合作博弈与效益分配从（2）式可见，合作规模扩大，获益不会减少.使（2）式等式成立的博弈称为非本质的，因为这种合作没有带来任何效益；使（2）式严格不等式成立的博弈称为本质的，因为这种合作对局中人确实有利，对局中人有吸引力.博弈论重点讨论这种合作.5.6合作博弈与效益分配在3人经商问题中，5.6合作博弈与效益分配3.简单博弈

在博弈中，若对任意只取值0或1，则称为简单博弈。使的称为获胜结盟，使的称为失败结盟。5.6合作博弈与效益分配例如，在3人经商问题中

（1）若,，则此简单博弈记为.即三人合作获利1万元，单干或两两合作无获利.（2）若,，

，则此简单博弈记为.即有,两人参加获利1万元，其他合作无获利.（3）若，

，则此简单博弈记为.即有参加获利1万元，无参加则无获利.5.6合作博弈与效益分配4.总体合作所获利益的分配原则n人合作博弈的解是指对总体结盟所获利益的一个分配方案。若用表示局中人i从合作V中获得报酬，为一个分配方案，则至少应满足：（1）个体合理性：

，.即合作优于单干；（2）总体合理性：.解决n人合作博弈问题的任务，是如何获得一个合理的分配方案：5.6合作博弈与效益分配5.Shapley值1953年美国运筹学家夏普利（L.S.Shapley）采用逻辑建模方法研究了这一问题。首先，他归纳出了几条合理分配原则，即应当满足的基本性质（用公理形式表示），进而证明满足这些基本性质的合作对策是唯一存在的，从而妥善地解决了问题。

5.6合作博弈与效益分配（1）对称性原则每个局中人获得的分配与他被赋予的记号无关，设

为I的一个排列，则.其中为重排序后的特征函数，为重排后原局中i人的新编号。5.6合作博弈与效益分配（2）有效性原则

①若局中人对他所参加的任一合作都无贡献,则给他的分配应为0。即若任意

，则

②完全分配5.6合作博弈与效益分配（3）可加性原则对I上任意两个特征函数U与V，若此n个人同时进行两项互不影响的合作，则两项合作的分配也应互不影响，每人的分配额即两项合作单独进行时应分配数的和。满足上述三公理的称为Shapley值。5.6合作博弈与效益分配Shapley证明了：对任一n人合作博弈，Shapley值是唯一存在的，且

其中为集合S的元素个数，可看做这种贡献的权因子，可视为局中人i在合作S中所作的贡献.5.6合作博弈与效益分配Shapley值的分解算法：设，现有合作V：把合作V分解为简单博弈的线性组合系数可通过解方程组确定。这是一个函数恒等式，故对自变量的每个取值都应成立，其自变量为的各子集.5.6合作博弈与效益分配5.6合作博弈与效益分配把简单博弈表5.5中各行的数据代入式(5.9)，并求解，得：5.6合作博弈与效益分配解这个方程组，有5.6合作博弈与效益分配可知：

分别表示A,B,C单干时的效益；

分别表示A与B,A与C,B与C合作时新增效益；

表示A,B,C三人合作时新增的效益，这是因为从第7个方程看出

【注】不要求非负.5.6合作博弈与效益分配在分配时，对两人合作新增的效益应各分1/2，对三人合作新增效益应各分1/3，于是

而且5.6合作博弈与效益分配【例5.12】在3人经商问题中，根据所给条件代入系数公式可以求出从而所以由公式（5.11）有利益分配方案

5.6合作博弈与效益分配【例5.13】有三个位于某河流同侧的城市,从上游到下游依次为A,B,C，这三个城市的污水必须经处理后才能排入河中.A与B距离为20km,B与C距离38km，如图.设为污水流量Q(单位：),L为管道长度(km).建污水厂费用的经验公式为(单位：万元),而建管道费用的经验公式为(单位：万元).已知三城市的污水流量分别为，问应该怎样处理(单独设厂还是联合设厂)，才可使总开支最少？又每一城镇负担的费用应各为多少?5.6合作博弈与效益分配分析思路：合作可省钱→把省钱视作获利→计算获利的分配→导出费用的分担.同时注意到：由于河流的走向，只要是合作建厂，就不可能建在A处.同理，B与C合作建厂，也不可能建在B处.5.6合作博弈与效益分配值解

下面计算各种情况的建厂费用(以下单位费用均是万元，不再注明.计算时保留小数点后四位)：方案1：A,B,C各自建厂A自建厂的投资

B自建厂的投资

C自建厂的投资

方案2：A与B合作，在B处建厂；C单独建厂

A与B合作投资

C自建厂的投资

总费用为

5.6合作博弈与效益分配方案3：A与C合作，在C处建厂；B自建厂

A与C合作投资

B自建厂的投资

总费用为

方案4：B与C合作，在C处建厂；A自建厂

B与C合作投资

A自建厂的投资

总费用为

5.6合作博弈与效益分配方案5：A,B,C合作，在C处建厂

总费用为

综合上述，得到的最佳方案是：三城合作建厂.该方案实施的关键是如何分担费用：

在合作建厂的洽谈过程中，C城提出合作建厂费用按照污水量比例5:3:5分担，污水管道费用由A与B城分担；B城同意C城提出的合作建厂费用按照污水量比例分担，并提议由A城到B城的污水管道费用由A城承担，由B城到C城的污水管道费用由A与B城按污水量比例5:3分担；A城觉得他们的建议似乎合理.5.6合作博弈与效益分配A城承担的总费用

B城承担的总费用

C城承担的总费用

因此，A城自然不会同意B城、C城提出的方案.5.6合作博弈与效益分配为使合作成功，我们为他们提出一个合理分担费用的方案。由于三城合作建厂可节省现把三城合作建厂节省的钱作为获利，问题转化为如何合理分配节约出的万元。由于5.6合作博弈与效益分配5.6合作博弈与效益分配从而由公式(5.9)可把合作V分解为:代入公式(5.11)得A,B,C三个城市的获利分配方案为

城市A

城市B

城市C5.6合作博弈与效益分配从而得到参考决策：A,B,C三城市合作，在处投资建厂，A,B,C三城市的分担方案为(单位：万元)：

城市A

城市B

城市C注意：在对实际问题作最后决策的时候，还应考虑在城市C建厂的征地费用及产生的就业效益等.本节知识要点

1.n人合作博弈与特征函数

2.简单博弈及相关概念

3.总体合作所获利益的分配原则

4.Shapley值与合理分配原则

5.Shapley值的分解算法5.6合作博弈与效益分配5.7动态博弈与承诺行动5.7动态博弈与承诺行动

如果局中人在进行行动选择时有先后顺序之分，这种博弈就被称为动态博弈.【例5.14】有两个房地产开发商A和B分别决定在同一地段上开发一栋写字楼。由于市场需求有限，如果他们都开发，则在同一地段会有两栋写字楼，超过了市场对写字楼的需求，难以完全出售，空置房太多导致各自亏损100万.当只有一家开发商在这个地段开发一栋写字楼时，它可以全部售出，赚得利润100万.假定A先决策，B在看见A的决策后再决策是否开发写字楼.在图中，用“博弈树”表示博弈过程：5.7动态博弈与承诺行动5.7动态博弈与承诺行动在图5.5中每一条“路径”的末端用向量给出A和B的支付，称为支付向量.下面用“逆向归纳法”可以求解这个博弈.在B进行决策的两个“决策结”上，B在左边的决策结上选择“不开发”；而在右边的决策结上选择“开发”.即给定A开发，B就不开发；给定A不开发，B就开发.B应避免同时与A都选择开发而蒙受损失.在这种情况下，A在自己的决策结上当然选择“开发”，因为他预计当自己选择“开发”后，B会选择“不开发”，自己就净赚一百万.当B威胁A说：“不管你是否开发，我都会在这里开发写字楼.”倘若A将B的话当了真，A就不敢开发，让B单独开发写字楼占便宜.5.7动态博弈与承诺行动但是，B的威胁是“不可置信”的.当A不理会B的威胁而果断地开发出一栋写字楼时，B其实不会将事前的威胁付诸实施.因为“识时务者为俊杰”，在A已开发的情况下，B的最优决策是“不开发”而不是“开发”.但是，如果B在向A发出威胁的同时又当着A的面与第三者C打赌一定要在该地段上开发出一栋写字楼，否则输给C二百万元.B与C为此签定合同并加以公证有效.这时，博弈变成图5.6所示的动态博弈.5.7动态博弈与承诺行动5.7动态博弈与承诺行动称B的这种行动为“承诺行动”，它使原来不可置信的威胁变为可以置信.这时，A就不得不相信B一定要开发写字楼的威胁了，于是放弃开发写字楼的计划，让B如愿以偿单独开发写字楼。B不仅未向C支付2百万元，反而净赚1百万.我们可以运用“承诺行动”的原理来分析许多经济及军事现象.5.7动态博弈与承诺行动【例5.15】

欧共体在空中客车与波音公司的竞争中对空中客车公司的战略性补贴.欧共体为了打破美国波音公司对全球民航业的垄断，曾放弃欧洲传统的自由竞争精神而对与波音公司进行竞争的空中客车公司进行补贴.当双方都未获得政府的补贴时，两个公司都开发新型飞机会因市场饱和而亏损，但若一家公司开发而另一家公司不开发时，则开发的那家公司会获巨额利润.未补贴时的博弈矩阵为下表.此时有两个纳什均衡，即一家开发而另一家不开发.5.7动态博弈与承诺行动5.7动态博弈与承诺行动下面考虑欧共体对空中客车进行补贴20个货币单位的情况.此时，当两家都开发时，空中客车仍然盈利10货币单位而不是亏损，博弈矩阵为下表。这时只有一个纳什均衡，即波音公司不开发和空中客车公司开发的均衡（不开发,开发），这有利于空中客车。在这里，欧共体对空中客车的补贴就是使空中客车一定要开发（无论波音是否开发）的威胁变得可置信的一种“承诺行动”.5.7动态博弈与承诺行动5.8应用举例5.8应用举例1.俾斯麦海的海空对抗（1）相关背景资料：

1943年2月，第二次世界大战中的日本，在太平洋战区已处于明显的劣势.为扭转战局，日军统帅山本五十六统率下的一支舰队策划了一次军事行动：由集结地——南太平洋新不列颠群岛的拉包尔