《运筹学思想方法及应用》课件ch5 博弈论的思想方法及其应用.ppt

1、要想在现代社会做一个有文化的人，要想在现代社会做一个有文化的人，你必须对博弈论有一个大致了解你必须对博弈论有一个大致了解.诺贝尔经济学奖获得者 Paul Samuelson博弈论（博弈论（The Games Theory)The Games Theory)是运筹学学科的一个重是运筹学学科的一个重要分支。具有竞争或对抗性质的行为称为博弈行为，要分支。具有竞争或对抗性质的行为称为博弈行为，在这类行为中，参与斗争或竞争的各方各自具有不同在这类行为中，参与斗争或竞争的各方各自具有不同的目标和利益，为了达到各自的目的，各方必须考虑的目标和利益，为了达到各自的目的，各方必须考虑对手的各种可能的行动方案，并

2、力图选取对自己最为对手的各种可能的行动方案，并力图选取对自己最为有利或最合理的方案。有利或最合理的方案。博弈论就是研究博弈行为中，斗争各方是否存在最合博弈论就是研究博弈行为中，斗争各方是否存在最合理的行动方案，以及如何找到这个合理方案的理论和理的行动方案，以及如何找到这个合理方案的理论和方法。方法。5.1 博弈论的基本概念5.2 矩阵博弈的纯策略5.3 矩阵博弈的混合策略 5.4 矩阵博弈求解方法 5.5 纳什均衡 5.6 合作博弈与效益分配5.7 动态博弈与承诺行动 5.8 应用举例附录 博弈论与诺贝尔经济学奖5.1 博弈论的基本概念5.1 博弈论的基本概念1944年，数学家冯诺伊曼(J.v

3、on-Neumann)和经济学家摩根施特恩（O.Morgenstern）写成了博弈论与经济行为一书，这是博弈论这一分支的经典之作.该书不仅建立了博弈论的严格的公理化体系，而且对大量的经济活动进行了深入的分析，奠定了博弈论的基础.5.1 博弈论的基本概念5.1 博弈论的基本概念博弈论的基本概念5.1 博弈论的基本概念博弈论是矛盾和合作的规范研究，是系统研究决策主体的行为发生直接相互作用情况下的决策以及这种决策均衡的理论.也就是说，当一个决策主体的选择受到其他决策主体选择的影响，并且它的决策也影响其他决策主体的决策时的合理选择问题.博弈论思想的主要特征是各参与人所实施的行为方案（策略）相互依存，各

4、方在冲突或合作后所实现的得失结果不仅取决于自己所采用的行为方案，同时也依赖于其他参与人所采用的行为方案，它是各参与人行为方案组合的函数.在现实生活中，经常可以看到一些具有对抗和竞争性的现象，如体育比赛、军事斗争中双方兵力的对抗，各公司企业之间的经济谈判以及为争夺市场而进行的竞争等等。在竞争过程中，各方为了达到自己的目标和利益，必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案，也就是说要研究采取对抗其他竞争者的策略。从数学角度来说，博弈论就是研究竞争行为中的竞争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。5.1 博弈论的基本概念博弈论

5、认为：人是理性的，即人人都会在约束条件下最大化自身的利益；人们在交往合作中有冲突，行为互相影响，而且信息不对称.5.1 博弈论的基本概念5.1 博弈论的基本概念囚徒困境问题甲和乙两个小偷联手作案，因私入民宅被警方抓住但未获证据。警方将两人分别置于两间房间分开审讯，政策是若一人招供但另一人未招，则招者立即被释放，未招者判入狱10年；若二人都招，则两人各判刑8年；若两人都不招，则未获证据但因私入民宅各拘留1年。将这些数据列出，如下：5.1 博弈论的基本概念囚徒困境博弈囚徒困境博弈尽管甲不知道乙是否招供，但他认为自己选“招”最好，因而甲会选择“招”，乙也同样会选择“招”，结果各判8年；但若两人都不招

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

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

8、困境问题中的甲和乙.局中人可理解为那些利益完全一致的集体或集团，局中人是有理智、聪明的，并有行动决定权的.我们称只有两个局中人的博弈现象为两人博弈;而多于两个局中人的博弈称为多人博弈.在多人博弈中，局中人之间允许合作的称为结盟博弈，不允许合作的称为不结盟博弈.5.1 博弈论的基本概念（2）策略(Strategies)在一局博弈中，每个局中人都有一套可供选择的指导自始至终如何行动的方案，以求争取较好的结果，我们称此行动方案为这个局中人的一个策略，而把这个局中人的策略全体称为这个局中人的策略集.在一局博弈中，各个局中人选定的策略构成的一个策略组，称之为一个局势.如果在一局博弈中，各个局中人只有有限

9、的策略，我们称之为有限博弈；否则称为无限博弈.5.1 博弈论的基本概念（3）支付函数(Payoff Function)在一局博弈结束后，对每个局中人来说，其结果不外乎是赢（得）或输（失）.显然，这种输赢局势是随局中人所选取的策略组的变化而变化的，局中人选定一个策略组，必然对应着一个博弈结果.因此，我们可以用一个函数来表示输赢（或得失）.将这个函数称之为支付函数.对应所有策略组的支付函数的各个取值可以用一个矩阵来表示，称之为支付矩阵.5.1 博弈论的基本概念对于一个博弈问题，如果在每一个局势中，全体局中人的得失相加都是零，则称此博弈为零和博弈，否则称为非零和博弈.5.1 博弈论的基本概念博弈中有

10、关局中人的策略集、支付函数等构成了博弈的信息.按照局中人对信息掌握的情况，可分为完全信息博弈和不完全信息博弈。按照局中人采取行动的次序，当局中人同时采取行动或在互相保密情况下采取行动，称这种情况为静态博弈.如果局中人采取行动有先后，后采取行动的人可以观察到前面人采取的行动，则属于动态博弈。按照局中人是否结盟情况，还可以将博弈分为结盟博弈与不结盟博弈.5.1 博弈论的基本概念完全理性非合作博弈按博弈方式有限理性合作博弈二人零和博弈二人博弈按博弈人数二人非零和博弈多人博弈完全信息静态博弈静态博弈不完全信息静态博弈按博弈状态完全信息动态博弈动态博弈不完全信息动态博弈博弈分类5.1 博弈论的基本概念二

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

12、后输者要付给赢者一千金.就同级的马而言，齐王的马都比田忌的马强.解 在本问题中局中人为齐王和田忌。以马出场的顺序而言，齐王有六种博弈策略.例如先用上等马，再用中等马，最后下等马，以（上、中、下）表示之.同样，田忌也有六种博弈策略，即两位局中人的策略集都含有六个策略.可以用表5.2表示齐王的支付.5.1 博弈论的基本概念5.1 博弈论的基本概念表5.25.1 博弈论的基本概念将表5.2中的数字表成矩阵称为齐王的赢得矩阵.311111131111113111111311111131111113 这个博弈问题是一个二人有限零和博弈问题.形势显然对田忌不利.但是田忌的谋士孙膑建议，每场比赛前要齐王报他

13、要出哪匹马.孙膑让田忌的下等马对齐王的上等马，用中等马对齐王的下等马，用上等马对齐王的中等马.结果反而赢了齐王一千金，这是一个典型的博弈问题.它表明在博弈问题中，局中人必须运用智慧，保守自己的秘密并设法获得对方的情报，采取恰当的策略方能取得较好的结果.5.1 博弈论的基本概念本节知识要点 1.博弈论研究的问题 2.博弈论思想的主要特征 3.博弈论的基本概念 4.博弈论有三个基本假设 5.博弈论的分类 5.1 博弈论的基本概念5.2矩阵博弈的纯策略局中人从 中选一个策略 ，同时局中人从 中选一个策略 ，这样就构成一个局势 对应于策略集 和 ，一共有 个局势.在局势 下局中人的赢得记为 ，则局中人

14、在m个策略 下的赢得构成一个矩阵.5.2矩阵博弈的纯策略用，分别表示两个局中人，设局中人有m个策略；局中人有n个策略；其策略集分别表示为 ，112,mS 212,nS 1Si2Sj(,).ij1S2Snm(,)ijija12,.,m5.2矩阵博弈的纯策略称为局中人的赢得矩阵.111212122212.().nnijm nmmmnaaaaaaAaaaa由于对策是零和的，表示在同一局势 下局中人的赢得，故局中人的赢得矩阵为 记这个博弈为 ija(,)ij 12,;.GSSA.A矩阵博弈的数学模型为：，其中 12,;GS S A112,mS 212,nS 111212122212.().nnijm

15、nmmmnaaaaaaAaaaa5.2矩阵博弈的纯策略5.2矩阵博弈的纯策略在矩阵博弈中要讨论的问题是：各局中人应该如何选择自己的策略，使自己在博弈中获得最好的结果.下面用一个例子说明.5.2矩阵博弈的纯策略【例5.2】设矩阵博弈局中人，应如何选择自己的策略，以保证自己在博弈中取得有利的地位？12,;GS S A112,mS 212,nS 812534121A解:对局中人而言，他的最大的收益是8，他理所当然地会选择策略 ，同时，他希望局中人选择策略 。但是局中人发现，如果局中人采取策略 ，他不会愚蠢地选择 以致失去8。反之，他会选择 ，这样他仅失去1。然而，当局中人选择 时，局中人就会选择 ，

16、这样做比选择 有利，可使收益由1增加到3。这时，局中人、都不愿再改变选择，因为如果局中人改变选择，失去的不是3，而是5或4，如果局中人改变选择，其得到的不是3，而是1或2。显然，这种状态是一种平衡状态。111122215.2矩阵博弈的纯策略对应于策略 ，局中人的赢得由5降到3，然后又由3升到4；对应于策略 ，局中人的支付由1上升到3，然后又由3下降到2.中间这个 数3，从第二行看来它形成一个凹 槽，从第二列看它形成一个凸脊，正像一个马鞍形，点3处于马鞍的 中心.225.2矩阵博弈的纯策略上面解题的数学方法为：对局中人来讲，先对矩阵A的每行元素取最小值：min 8,1,21;min 5,3,43

17、;min1,2,11.再从这些最小值中取最大值：。也就是说，局中人采取悲观主义原则，从最坏的情况中，取得的最好结果是3，这时，他应采取的策略是 ，不论局中人采取什么策略，都可以保证赢得不会少于3.31,3,1max25.2矩阵博弈的纯策略5.2矩阵博弈的纯策略注意到矩阵A中的元素 反号后是局中人的赢得，故局中人采取悲观主义原则时，应先对矩阵A的每一列元素中取出最大值：再从这些最大值中取最小值：。因此，局中人应采取策略 ，则不论局中人采取什么策略，最大损失不会大于3。ijamax 8,5,18;max 1,3,23;max 2,4,14.34,3,8min25.2矩阵博弈的纯策略因此，局中人、只

18、有分别采取 、时才是他们的最优策略。为了与后面的概念相区别，我们称 、分别为局中人、的最优纯策略，而局势 称为博弈的解，或博弈 的纳什均衡。222222(,)12,;GS SA12,;GS SA5.2矩阵博弈的纯策略一般地，对最优纯策略及纯策略意义下的纳什均衡有如下定义：考虑矩阵博弈如果成立等式则 分别称为局中人、的最优纯策略，对应的策略组合即局势 称为矩阵博弈 在纯策略意义下的纳什均衡。数值 称为矩阵博弈 的值。112,mS 212,nS 812534121A*1111maxminminmaxijiji jj nj ni mi maaa 12,;GS SA*,ij*(,)ij12,;GS S

19、 A*Gi jVa12,;GS S A【例例5.3】设矩阵博弈设矩阵博弈 ，其中，其中5.2矩阵博弈的纯策略求解纳什均衡与博弈的值。12,;GS SA11232123,SS 534519206A 解 对局中人，先对矩阵A的每行求最小值，得到 ，再求其最大值得到3，即3,5,21313max min3ijjia 对局中人，先对矩阵A的每行求最大值，得到 ，再求其最大值得到3，即5,3,91313m in m ax3ijjia 从而13131313maxminminmax3ijijjjiiaa 所以，该博弈的纳什均衡为 ，博弈的值 .可以看出：满足不等式12(,)123GVa12a2121,(1,

20、2,3;1,2,3)ijaaaij 将这个结论推广，我们给出如下定理：5.2矩阵博弈的纯策略5.2矩阵博弈的纯策略矩阵博弈 在纯策略意义下有纳什均衡的充分必要条件是：存在策略 ，使得 12,;GS SA*(,)ij*1111max minmin maxijiji jj nj ni mi maaa 或 ，*iji ji jaaa1,2,;1,2,im jn定理5.15.2矩阵博弈的纯策略设矩阵博弈 ，其中 12,;GS SA1123421234,SS 85952343105754282A求解纳什均衡与博弈的值.【例例5.45.4】解 对局中人，先对矩阵A的每行求最小值，得到 ，再求其最大值得到5

21、，即.5,3,5,41414maxmin5ijjia 对局中人，先对矩阵A的每列求最大值，得到 ，再求其最小值得到5，即10,5,9,514 14minmax5ijjia 从而 *14141414maxminminmax5(1,3;2,4)ijiji jjjiiaaaij 所以，局势 都是博弈 的纳什均衡，博弈值 。12143234(,),(,),(,),(,)5GV12,;GS SA5.2矩阵博弈的纯策略本节知识要点本节知识要点 1.矩阵博弈的数学模型 2.博弈 的纳什均衡 3.矩阵博弈 在纯策略意义下有纳什均衡的充分必要条件12,;GS SA12,;GS SA5.3 矩阵博弈的混合策略矩阵

22、博弈的混合策略 5.3 矩阵博弈的混合策略矩阵博弈的混合策略上节讨论了在纯策略意义下有纳什均衡的矩阵博弈问题。但是，并非所有的矩阵博弈在纯策略意义下都有纳什均衡。例如本章的齐王赛马的博弈在纯策略下没有纳什均衡。因为所以在齐王赛马的博弈中，双方都没有最优纯策略，从而在纯策略意义下就没有纳什均衡。1616161616161616maxmin1;minmax3;maxminminmax.ijijjjiiijijjjiiaaaa 5.3 矩阵博弈的混合策略矩阵博弈的混合策略【例例5.55.5】设矩阵博弈 ，其中解解 故此博弈不存在鞍点，从而双方都没有最优纯策略。12,;GS SA11211215,73

23、SSA 33,1maxminmax2121ijjia55,7minmaxmin2121ijija5.3 矩阵博弈的混合策略矩阵博弈的混合策略此时，我们可以设想局中人随机地取纯策略来进行博弈。例如，局中人以概率选取纯策略，以概率选取纯策略；局中人以概率选取纯策略，以概率选取纯策略。于是，对局中人来说，他的赢得可用期望值来描述：x1x1y21y12),(yxE)1)(1(3)1(7)1(5),(yxyxyxxyyxE8243118()()4.24xyxyxy 5.3 矩阵博弈的混合策略矩阵博弈的混合策略由上式可以看出，当时，即局中人以概率选取纯策略时，其期望值至少是4，但不能保证期望值超过4，这是

24、因为局中人取时，即以概率选取纯策略时，可以控制局中人的赢得不会超过4.21x21141y4115.3 矩阵博弈的混合策略矩阵博弈的混合策略从上述分析可以看出，每个局中人决策时，不是决定用哪一个纯策略，而是决定用多大概率选择每一个纯策略。一般地，设矩阵博弈，其中 12,;GS SA112,.,mS nmijaA)(212,nS 5.3 矩阵博弈的混合策略矩阵博弈的混合策略则将纯策略集合对应的概率向量 分别称为局中人与的混合策略，这里是局中人选取的概率，是局中人选取的概率，显然，纯策略可以看成是混合策略的一种特殊情况。又称数学期望为局中人的赢得，为局中人的赢得，而称为混合局势。121(,),0,1

25、,2,;1mmiiiXx xxximx121(,),0,1,2,;1nnjjjYy yyyjnyminjjiijyxaYXE11),(ixijyj),(YXE),(YX5.3 矩阵博弈的混合策略矩阵博弈的混合策略对给定博弈，称为博弈的混合扩充，其中为局中人的所有混合策略集；为局中人的所有混合策略集。12,;GS SA*12,;GSSE*1SX*2SY5.3 矩阵博弈的混合策略矩阵博弈的混合策略在混合扩充博弈中，局中人选取某种混合策略时，必定要想到局中人会针对性选取一种策略，使其期望赢得最小，于是局中人的目标就是寻求一种以概率选取的策略，使局中人不论采取何种策略时，都能使自己的期望赢得中最小的尽

26、可能大，即局中人想找到一个最大的数，使其在以概率 选取策略时，对局中人的每种策略都有(5.1)我们称 为局中人的最优混合策略，简称最优策略。1SV*X1*(,)SE XYV*X5.3 矩阵博弈的混合策略矩阵博弈的混合策略同理，局中人也想以概率寻找最优策略，使局中人不论采取何种策略时，都能使自己的期望损失中最大的尽可能小，即局中人想找到一个最小的数，使其在以概率选取策略时，对局中人的每种策略都有（5.2）我们称 为局中人的最优策略.*Y2SV*Y*Y2*(,)SE X YV5.3 矩阵博弈的混合策略矩阵博弈的混合策略可以证明，在任何一个给定的二人零和博弈中，对局中人和分别存在最优策略和，以及和，

27、使得式（5.1）和（5.2）成立，且，我们称 为博弈 的值，而混合局势称为 在混合策略意义下的一个纳什均衡。*X*Y1SV2SV12SSGVVVGVG*(,)XYG5.3 矩阵博弈的混合策略矩阵博弈的混合策略定理定理5.25.2 设，则为的纳什均衡的充要条件是：存在数，使得是线性不等式组*12,XS YS*(,)XYGV*X11(1,2,),1,0(1,2,).mijiimiiia xVjnxxim*Y11(1,2,),1,0(1,2,).nijjjnjjja yV imyyjn 的解，是线性不等式组5.3 矩阵博弈的混合策略矩阵博弈的混合策略定理5.2表明，局中人的期望赢得至少为，局中人的期

28、望损失至多为，且 ；如果局中人选用其最优策略，但局中人未选用其最优策略，则局中人的期望赢得将高于；同样，如果局中人选用其最优策略而局中人未选用其最优策略，则局中人的期望损失会低于.当局中人都采用其最优策略时，则可以达到某种程度的平衡，即混合策略意义下的纳什均衡.1SV1SV2SV12SSGVVV2SV5.3 矩阵博弈的混合策略矩阵博弈的混合策略定理定理5.35.3 任何一个给定的二人零和博弈一定存在混合策略下的纳什均衡。定理定理5.45.4 设为二人零和博弈在混合策略下的一个纳什均衡，则（1）若，则；（2）若，则；（3）若，则；（4）若，则。G*(,)XYGGVV*0ix*ijjja yV*0

29、jy*ijiia xV*1nijjja yV*0ix*1mijiia xV*0jy 本节知识要点本节知识要点 1.矩阵博弈的混合扩充 2.混合策略意义下的纳什均衡 3.定理5.2-定理5.45.4 矩阵博弈求解方法矩阵博弈求解方法 5.4 矩阵博弈求解方法矩阵博弈求解方法1.1.代数解法代数解法【例5.6】求例5.1中齐王与田忌各自的最优混合策略及博弈的值。解 齐王的赢得矩阵 311111131111113111111311111131111113A5.4 矩阵博弈求解方法矩阵博弈求解方法由于它没有鞍点，不存在纯策略解，由定理5.2可得到两组不等式：（5.3）12345612345612345

30、61234561234561234561234563,3,3,3,3,3,1,0(1,2,6).ixxxxxxVxxxxxxVxxxxxxVxxxxxxVxxxxxxVxxxxxxVxxxxxxxi（5.4）1234561234561234561234561234561234561234563,3,3,3,3,3,1,0(1,2,6).jyyyyyyVyyyyyyVyyyyyyVyyyyyyVyyyyyyVyyyyyyVyyyyyyyj5.4 矩阵博弈求解方法矩阵博弈求解方法这里，每个均大于零，换言之，每个纯策略都可能被局中人选取。由定理5.3与定理5.4知，式（5.4）和（5.3）都应当取等

31、号，将不等式组求解转化成线性方程组求解。将所有式子相加，便得：由 及其 故得。代入其他各式解得jiyx,Vxxxxxx6)(6654321Vyyyyyy6)(66543211ix1jy1(1,2,6)6ixi1(1,2,6)6jyj5.4 矩阵博弈求解方法矩阵博弈求解方法齐王的最优策略是；田忌的最优策略是 。博弈值。即比赛的双方都很聪明，有理智，总的结果是齐王赢一千金。)61,61,61,61,61,61(*X)61,61,61,61,61,61(*Y1V5.4 矩阵博弈求解方法矩阵博弈求解方法2.2.图解法图解法 用平面直角坐标图解的方法来求出双方的最优策略。【例5.7】用图解法求解例5.5

32、的博弈问题。解 支付矩阵先考虑局中人：如果局中人取纯策略，则局中人赢得的期望值为如果局中人取纯策略，则局中人赢得的期望值为 13751A11167)1(7xxxV211123)1(35xxxV5.4 矩阵博弈求解方法矩阵博弈求解方法现以策略和所取概率值和为横坐标，赢得为纵坐标，分别画出局中人取策略和 时，局中人所能获得的赢得的变动直线l1和l2。如图121x2xV12V5.4 矩阵博弈求解方法矩阵博弈求解方法这里注意到显然，只有以直线l1和l2的交点M处相应的概率值分别取策略和，才是局中人所选取的最优混合策略，这时，局中人的赢得总是，而不论局中人选择何种混合策略，由图知 所以局中人的最优混合策

33、略为121xx+=21,xx124V5.0,5.021xx)5.0,5.0(*X显然，只有以直线l1和l2的交点M处相应的概率值分别取策略和，才是局中人所选取的最优混合策略，这时，局中人的赢得总是，而不论局中人选择何种混合策略，由图知 所以局中人的最优混合策略为21,xx124V5.0,5.021xx)5.0,5.0(*X当局中人当局中人取策略时，局取策略时，局中人中人损失的期望值为：损失的期望值为：用同样的方法作图，得局中人用同样的方法作图，得局中人的的最优混合策略最优混合策略 ，博，博弈值。弈值。5.4 矩阵博弈求解方法矩阵博弈求解方法同理，考虑局中人取最优策略的情况，当局中人同理，考虑局

34、中人取最优策略的情况，当局中人取取策略时，局中人策略时，局中人损失的期望值为：损失的期望值为：111145)1(5yyyV211143)1(37yyyV)75.0,25.0(*Y4V5.4 矩阵博弈求解方法矩阵博弈求解方法【例例5.85.8】设给定一个矩阵博弈，其中 求其最优策略及博弈值。解解 我们注意到矩阵 的第2列各数大于第1列对应各数，也就是无论局中人选取什么策略，局中人选取策略的损失都比选取策略的损失要大，故局中人绝不会去选取策略，他可以把 从策略集中删去，并把第2列从 中删去，即局中人只要用到策略，所以只要考虑下列矩阵就可以了。12,;GS SA3326125314327839AA2

35、122A1341A3.优超法优超法5.4 矩阵博弈求解方法矩阵博弈求解方法解解 我们注意到矩阵 的第2列各数大于第1列对应各数，也就是无论局中人选取什么策略，局中人选取策略的损失都比选取策略的损失要大，故局中人绝不会去选取策略，他可以把 从策略集中删去，并把第2列从 中删去，即局中人只要用到策略，所以只要考虑下列矩阵就可以了。A2122A1341A1326153132739A1A232151373A此时此时 再抹去中第3列得5.4 矩阵博弈求解方法矩阵博弈求解方法从局中人看来，中第2行各元素比第3行对应各元素大，也就是无论局中人选取什么策略，局中人选取策略 比选取策略 有利，这样，局中人删去策

36、略，同样可删去策略，得2A233337513A5.4 矩阵博弈求解方法矩阵博弈求解方法利用上例结果可得局中人的最优混合策略；局中人的最优混合策略。以上降低支付矩阵维数的方法称为优超法。超法。)5.0,5.0(*X)75.0,25.0(*Y5.4 矩阵博弈求解方法矩阵博弈求解方法优超法一般描述如下：在支付矩阵 中，如果第i行元素都不小于第k行对应各元素，即，则称局中人的策略优超于策略，记为。这时局中人无论选取哪种策略，局中人选取总比选取好。那么可将第k行元素从支付矩阵中抹去，即将策略从策略集中删去；如果中的第j列各元素都不大于第k列对应的各元素，即，则称局中人的策略优超于策略，记为。这时，局中人

37、无论选取哪一种策略，局中人选取总比选取好。那么，可将第k列从中抹去，即将策略从策略集中删去。nmijaA)(kjijaa),.,2,1(nj ikikjikk1Sikijaa),.,2,1(mi jkkjkijk2S5.4 矩阵博弈求解方法矩阵博弈求解方法定理定理5.55.5 设矩阵博弈，其中，。如果被其余纯策略 中之一所优超，由 可以得到一个新矩阵博弈，其中 ，则有（1）；（2）中局中人的最优策略就是中局中人的最优策略；（3）如果是中局中人的最优策略，则就是中局中人的最优策略。12(1),()(2,3,1,2,)mijmnSAaim jn nmijaA)(12,;GS SA112,mS 21

38、2,nS 212,nS 12,.,m12,;GS SA12,;GSSAGGVVGG*2(,)mxx*2(0,)mxxGG5.4 矩阵博弈求解方法矩阵博弈求解方法4.4.线性规划解法线性规划解法从定理5.2的表示形式可以看出，求解矩阵博弈混合策略意义下的纳什均衡问题可以用线性规划方法求解。因为求相当于解（5.5）及（5.6）*,YX11maxs.t.(1,2,),1,0,(1,2,).mijiimiiiVa xVjnxxim11mins.t.(1,2,),1,0,(1,2,).nijjjnjjjVa yV imyyjn5.4 矩阵博弈求解方法矩阵博弈求解方法不妨设，引入新变量不妨设，引入新变量（

39、5.5）化为线性规划）化为线性规划0V（5.6）化为线性规划）化为线性规划/(1,2,);/(1,2,)iijjxx VimyyVjn11mins.t.1(1,2,),0,(1,2,);miimijjijxa xjnxim （5.7）11maxs.t.1(1,2,),0,(1,2,).njjnijjjjya yimyjn （5.8）这两个线性规划的最优解都这两个线性规划的最优解都存在，而且最优值相等。存在，而且最优值相等。5.4 矩阵博弈求解方法矩阵博弈求解方法【例例5.95.9】设给定一个矩阵博弈，其中求其最优策略及博弈值。解解 此博弈既无鞍点，又不能用优超法简化，可用线性规划求解。求解的线

40、性不等式组为12,;GS SA164316452A5.4 矩阵博弈求解方法矩阵博弈求解方法及123123123123min()s.t.2641,561,431,0(1,2,3).ixxxxxxxxxxxxxi 123123123123max()s.t.2541,631,461,0(1,2,3).jyyyyyyyyyyyyyj 5.4 矩阵博弈求解方法矩阵博弈求解方法故局中人的最优混合策略为所以局中人的最优混合策略为解得 123124/35,21/124,10/124,1/124.Vxxx*21 131(,)35 35 35X 123124/35,13/124,10/124,12/124.Vyy

41、y*13 10 12(,)35 35 35Y 同理，解得 本节知识要点本节知识要点 主要介绍矩阵博弈求解方法：1.代数解法 2.图解法 3.优超法 4.线性规划方法5.4 矩阵博弈求解方法矩阵博弈求解方法5.5 纳什均衡纳什均衡 5.5 纳什均衡纳什均衡在二人零和博弈中，双方局中人寻求的最优解是一种纳什均衡。当达到这种均衡时，无论是纯策略解还是混合策略解，只要其他局中人不改变自己的策略，则任何一方单独改变自己的策略，只能带来收益或效用的减少。纳什均衡是一种策略组合，它是每个局中人的策略对其他局中人策略的最优反应。下面先给出个局中人博弈的标准式，然后给出相应的纳什均衡的定义。5.5 纳什均衡纳什

42、均衡1.博弈的标准式在有n个局中人的博弈中，设第i个局中人的策略集为 .用 表示每个局中人选定某一个策略时形成的局势.这里 是相应于该局势的第i个局中人的支付函数，则称 为博弈的标准式.设有，如果对其他局中人所有可能策略组成的局势均有不等式成立，则称是对 的严格劣战略.(1,2,)iSin12(,)ns ss1212,;,nnGS SS u uu1212,;,nnGS SS u uu,iiiisS sS111111(,)(,)iiiiniiiinu sss ssu sss ssisis5.5 纳什均衡纳什均衡2.纳什均衡纳什均衡定义定义 在有在有n个局中人的标准式博弈个局中人的标准式博弈 中，

43、中，如果局势如果局势 满足：对每一个局中人是至少不劣满足：对每一个局中人是至少不劣于他针对其他于他针对其他n-1个局中人所选策略个局中人所选策略 的最的最优反应策略，则称局势优反应策略，则称局势 是该博弈的一是该博弈的一个纳什均衡。即对任意的个纳什均衡。即对任意的 ，有，有 或或 是最优化问题是最优化问题 的解的解.1212,;,nnGS SS u uu*12(,)ns ss*,ii s*111,iinssss*111,iiinsss ssiisS*111111(,)(,)iiiiniiiinu sss ssu sss ss*is*111max(,)iiiiiinsSu sss ss5.5 纳

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

45、比较为劣策略；比较B的第的第j个和第个和第k个策略，如果有个策略，如果有 ,其中至少其中至少有一个取有一个取“”号，则称第号，则称第k个策略为劣策略个策略为劣策略.(1,2,)aaijljccjn(1,2,)bbijikccim5.5 纳什均衡纳什均衡在本例中，是劣策略，将其删除得到 5.5 纳什均衡纳什均衡由于纳什均衡是每个局中人策略对其他局中人策略的最优反应，对局中人A：当局中人B采用策略时，局中人A的最优反应是采取策略，支付为5，在5下面划横线；当局中人B采用策略时，局中人A的最优反应是采取策略 支付为6，在6下面划横线；当局中人B采用策略时，局中人A的最优反应时采取策略.支付为4，在4

46、下面划横线。1b3a2b1,a3b3a5.5 纳什均衡纳什均衡对局中人B：当局中人A采用策略时，局中人B的最优反应是采取策略，支付为6，在6下面划横线；当局中人A采用策略时，局中人B的最优反应是采取策略，支付为6，在6下面划横线.对支付值都划有横线的组合，即为所求的纳什均衡解.这种解法简称为划线法.由上表可知，本例的纳什均衡解为(4,6)，其对应的策略组合为.该局势是一种平衡局势.1a1b3a3b,abijijc c33(,)a b5.5 纳什均衡纳什均衡【例5.11】以弱敌强博弈在战争史上，不乏以弱胜强的例子。例如在二战中的诺曼底登陆战的谋略策划中，盟军就面临以弱敌强的问题。盟军有两个可以选

47、择的登陆目标地，一是多佛，二是诺曼底。德国守军在人数上超过了盟军，并且就军事进攻而言，在人数相同的情况下，攻方与守方相比会处于不利的情形。下面，将这种情形模型化。假设有一支军队准备进攻一座城市，它有军力两个师；守城军队有三个师。通往城市有甲、乙两条道路或方向。两军相遇时，人数居多的一方取胜，当两方人数相等时，守方获胜。并假定军队只能整师调动。5.5 纳什均衡纳什均衡攻方战略：a.两个师集中沿甲方向进攻；b.兵分两路，一个师沿甲方向进攻，另一个师沿乙方向进攻；c.两个师集中沿乙方向进攻。守方战略：A.三个师集中守甲方向；B.两个师守甲方向，一个师守乙方向；C.一个师守甲方向，两个师守乙方向；D.

48、三个师集中守乙方向。5.5 纳什均衡纳什均衡用“+”、“”，分别表示胜和败，攻、守双方布阵结果见下表 5.5 纳什均衡纳什均衡分析：进攻方无劣战略，但守方有劣战略，A劣于B，D劣于C，故守方不会采用战略A和D，剔除后的博弈变为：5.5 纳什均衡纳什均衡攻方知道守方不会选A和D，他由此知道博弈变成上图所示。此时，攻方就有一个劣战略b，他剔除b后得到新的博弈：此时，两方的形势是相同的，即攻方尽管开始在军力上劣于守方，但实际上它只要运用计谋，其获胜的可能与守方是相同的。5.5 纳什均衡纳什均衡本节知识要点本节知识要点 1.n个局中人博弈的标准式 2.纳什均衡与纳什均衡解 3.求纳什均衡解的划线法 5

49、.6 合作博弈与效益分配合作博弈与效益分配5.6 合作博弈与效益分配合作博弈与效益分配1.1.问题的提出问题的提出 多人合作博弈中的效益分配或费用分摊问题与现实的经济活动多人合作博弈中的效益分配或费用分摊问题与现实的经济活动 有着密切的关系有着密切的关系.最典型的例子有最典型的例子有横向经济联合中的效益分配问题和资金重组过程中的利益分横向经济联合中的效益分配问题和资金重组过程中的利益分配；配；大气污染总量控制优化治理投资的费用分摊；大气污染总量控制优化治理投资的费用分摊；联合兴建污水处理厂建设费用的分摊；联合兴建污水处理厂建设费用的分摊；联合投资企业破产以后所发生的债务如何进行分担等。联合投资

50、企业破产以后所发生的债务如何进行分担等。这类问题由于涉及的资金数目较大，比较敏感，只有处理好才这类问题由于涉及的资金数目较大，比较敏感，只有处理好才能够保证合作项目的成功能够保证合作项目的成功.本节以三人合作经商为问题为例，介绍解决多人合作博弈中的本节以三人合作经商为问题为例，介绍解决多人合作博弈中的效益分配或费用分摊问题的基本概念和方法效益分配或费用分摊问题的基本概念和方法.5.6 合作博弈与效益分配合作博弈与效益分配设有A,B,C三人经商.若各人单干，则每人仅能获利1万元；若A,B合作,可获利7万元，A,C合作可获利5万元，B,C合作可获利4万元，三人合作可获利10万元。问三人合作时应如何