《管理运筹学》12-管理博弈.ppt

《《管理运筹学》12-管理博弈.ppt》由会员分享，可在线阅读，更多相关《《管理运筹学》12-管理博弈.ppt（97页珍藏版）》请在三一办公上搜索。

1、第 12 章,管理博弈,第一节 现实中的管理博弈问题第二节 管理博弈的基本概念与分类第三节 矩阵博弈的基本理论第四节 矩阵博弈的求解方法第五节 其他类型博弈简介第六节 管理博弈的应用,现实中的管理博弈问题,博弈论也称对策论,是采用数学理论和方法来研究理性决策者之间的冲突与合作现象的科学。它既是现代数学的一个新分支，也是运筹学的一个重要学科。博弈论发展的历史并不长，但是在经济、政治、军事和人们的日常生活等领域具有广泛的应用，学习博弈论对管理工作者具有重要的现实意义。,同一地区有两家港口企业A和B相互竞争，该地区的市场货运量为一常数，因此，如果A港货运量增加，就意味着B港的货运量减少，反之亦然。为

2、了在下一年从对方手中赢取一些货运量，每家港口都在制定新的竞争策略。每个港口可采取的竞争策略有以下三种：策略1：优质服务，通过提供更优质的服务来吸引客户；策略2：营销公关，通过采用各种市场营销手段和提升港口企业形象来赢得客户；策略3：降低价格，整合优化企业资源，降低服务成本，通过提供更优惠的港口服务价格来吸引客户。,现实中的管理博弈问题,例12-1 港口竞争问题,上述每一种策略方案的实施都需要高额的成本投入，因此每个港口只能选取其中一种。估计各种策略组合下港口企业A在下一年的货运量增加的百分比值如下表12-1所示。每家港口企业在获知对方的决策之前，必须做出选择，试分析各个港口应该采取何种策略。,

3、现实中的管理博弈问题,表12-1 各策略组合下港口企业A在下一年的货运量增加的百分比值(单位:%),例12-1 港口竞争问题,某单位采购员在秋季要决定冬季取暖用煤的贮量问题，已知在正常的气温条件下要消耗150吨煤，在较暖与较冷的气温条件下要消耗100吨和200吨。假定冬季的煤价随天气的寒冷程度而变化，在较暖、正常、较冷的气候条件下每吨煤价分别为500元、550元和600元。设秋季时煤价为每吨500元。在没有关于当年冬季气温准确气象预报的条件下，秋季贮存多少吨煤能使单位的支出最少？,现实中的管理博弈问题,例12-2 贮煤问题,局中人(Players)：指的是一个博弈中的决策主体，是有权决定自己行

4、动方案并承担风险的博弈参与者，也称为“博弈方”。通常用I表示局中人的集合，如果有n个局中人，则I=1，2，n。局中人的概念是广义的，可以是个人，也可以是群体，甚至有时可以是“自然”。两个基本假设：第一，局中人都是理性的；第二，局中人都是自利的。例12-1港口竞争问题的局中人分别是港口企业A和B，例12-2贮煤问题中的局中人1是采购员，局中人2是自然状态。,管理博弈的基本概念与分类,一、博弈的基本要素,策略集(Strategy Set)：可供局中人选择的一个完整的行动方案称为该局中人的一个策略，通常用si表示局中人i的一个策略。策略是事先确定的，是局中人在博弈过程中遇到不同情况所做出的反应，每个

5、局中人都至少有两个可选的策略，所有可选的策略构成该局中人的一个策略集，表示为Si。例12-1港口竞争问题中港口企业A和B各有三个可选的策略：优质服务、营销公关和降低价格。例12-2贮煤问题中局中人1（采购员）可选择的策略分别为：秋季购煤100吨、150吨和200吨，而局中人2（自然状态）的三个策略“选择”分别是冬季气候较暖、正常、较冷。,管理博弈的基本概念与分类,一、博弈的基本要素,赢得函数(Payoff Function)：赢得是局中人最终获得的利益，也是博弈各方追求的最终目标。每个局中人在一局博弈结束时的赢得，不仅与该局中人自身所选择的策略有关，而且与所有局中人各自取定的一组策略有关。所以

6、，一局博弈结束时每个局中人的“赢得”是全体局中人所取定的一个策略组合（局势）的函数，通常称为赢得（支付）函数（Payoff Function），记为Hi(S)。把赢得函数用矩阵来表示，就称为赢得矩阵，如表12-1就是港口企业A的赢得矩阵。,管理博弈的基本概念与分类,一、博弈的基本要素,例12-3 囚徒困境,管理博弈的基本概念与分类,一、博弈的基本要素,嫌疑犯A和B因为一桩案件而被捕，两人被关在不同的屋子里接受审讯。警方的政策是“坦白从宽，抗拒从严”，如果两人都坦白，各判刑5年，如果其中一人坦白另外一人不坦白，则坦白者立即释放，不坦白者重判10年，如果两人都不坦白则因证据不足各判一年。试建立该问

7、题的博弈模型。,例12-3 囚徒困境,管理博弈的基本概念与分类,一、博弈的基本要素,解 A和B为两个局中人，每个局中人都有两个策略：坦白或不坦白。按照各局中人的策略组合，共有四个局势：坦白，坦白，坦白，不坦白，不坦白，坦白，不坦白，不坦白。两个局中人的赢得函数可以用表12-2所示的一个双变量矩阵来表示。,表12-2 囚徒困境的赢得表,例12-4 田忌赛马,管理博弈的基本概念与分类,一、博弈的基本要素,战国时期，齐威王常邀武臣田忌赛马赌金，双方约定共赛三局，每方分别出上、中、下三个等级的马一匹各赛一局，每局赌注千金。在同一等级马中，田忌的马都稍逊一筹，不如齐王的马，但田忌的上等马优于齐王的中等马

8、，田忌的中等马优于齐王的下等马。试建立该问题的博弈模型。,例12-4 田忌赛马,管理博弈的基本概念与分类,一、博弈的基本要素,解 建立博弈模型，局中人分别是齐王和田忌，每个局中人的策略是各个等级的马参赛的次序，他们都各有6个策略：（上，中，下），（上，下，中），（中，上，下），（中，下，上），（下，上，中），（下，中，上）。表12-3给出了双方的赢得矩阵（第一个数字是齐王的赢得，第二个数字是田忌的赢得）。,例12-4 田忌赛马,管理博弈的基本概念与分类,一、博弈的基本要素,表12-3 田忌赛马博弈的赢得矩阵,例12-4 田忌赛马,管理博弈的基本概念与分类,一、博弈的基本要素,这个博弈的结果是众

9、所周知的。开始的时候，田忌采用的是对应策略，因此每次赛马总输给齐王三千金。后来田忌的一位谋士孙膑就向田忌献策：每局比赛让齐王先出马，然后以下马对齐王的上马，以上马对齐王的中马，以中马对齐王的下马。田忌依计而行，结果一负两胜，反赢一千金。那么，齐威王能否改进其策略呢？双方的最优决策又是怎样的呢？,例12-5 产量竞争问题,管理博弈的基本概念与分类,一、博弈的基本要素,有A、B两家企业垄断生产某种商品，它们同时决定自己的产量。设企业A选择的产量为q1，设企业B选择的产量为q2。产品的售价与产量有关：p=a-b(q1+q2)，其中a和b均为大于零的常数。若两家企业生产该商品的单位成本为正常数c，则两

10、家企业应该如何选择各自的产量，才能使得自己获得的利润最大。试建立该问题的博弈模型。,例12-5 产量竞争问题,管理博弈的基本概念与分类,一、博弈的基本要素,解 企业A和B分别为两个局中人，它们的策略为各自的产量qi 0,)(i=1，2)，每一方都有无穷多个策略。在局势(q1+q2)下，局中人i的赢得函数为,按局中人的数量：二人博弈和多人博弈；按各局中人赢得函数的代数和是否为零：零和博弈与非零和博弈；按局中人之间是否合作：合作博弈和非合作博弈；按策略集中策略数目的有限和无限：有限博弈和无限博弈；按局中人选择策略的先后顺序：静态博弈和动态博弈；按博弈过程中对信息掌握的情况：完全信息博弈和不完全信息

11、博弈。,管理博弈的基本概念与分类,二、博弈问题的分类,本章：二人有限零和非合作博弈，也称矩阵博弈！,对于矩阵博弈模型，若局中人1有m个策略1，2，m可供选择，局中人2有n个策略1，2，n可供选择，则各个局中人的策略集分别表示为：当局中人1选取第i个策略，局中人2选取第j个策略时，就形成一个局势(i，j)，用aij表示局中人1在局势(i，j)下的赢得，则矩阵博弈的赢得矩阵A如下所示。,矩阵博弈的基本理论,一、矩阵博弈的基本模型,零和博弈：A也是局中人2的损失矩阵！,矩阵博弈的基本理论,一、矩阵博弈的基本模型,局中人1的策略集：S1局中人2的策略集：S2赢得矩阵：A,矩阵博弈模型：G=S1，S2，

12、A,矩阵博弈的基本理论,二、矩阵博弈的纯策略,对于给定的博弈模型，各局中人面临的问题是：如何选取对自己最为有利的策略以谋取最大的赢得（或最小的损失）。例12-6 一个矩阵博弈的赢得矩阵A如表12-4所示，试确定各局中人的最优策略。,表12-4 具有鞍点的矩阵博弈的赢得矩阵,矩阵博弈的基本理论,二、矩阵博弈的纯策略,解 局中人1策略选择分析：,取最大！,矩阵博弈的基本理论,二、矩阵博弈的纯策略,局中人2策略选择分析：,取最小！,矩阵博弈的基本理论,二、矩阵博弈的纯策略,从以上分析可以看出，各局中人的最优策略是局中人1选取策略3而局中人2选取策略2，从而使得局中人1赢得5个单位而局中人2损失5个单

13、位。局中人1是按照最小最大原则选取的策略，其赢得值是赢得矩阵中每一行的最小值中取最大；局中人2是按照最大最小原则选取的策略，其损失值是赢得矩阵中每一列的最大值中取最小。,矩阵博弈的基本理论,二、矩阵博弈的纯策略,定义12-1 对于矩阵博弈模型G=S1，S2，A，其中S1=1，2，m，S2=1，2，n，A=aijmn，若满足等式 则称ai*j*为该博弈的一个鞍点，VG=ai*j*为博弈G的值，i和j分别为局中人1和2的最优纯策略，纯局势(i*，j*)为G在纯策略下的解。,矩阵博弈的基本理论,二、矩阵博弈的纯策略,从例12-1可以看出，其实赢得矩阵的鞍点就是它所在行的最小元素，同时又是所在列的最大

14、元素。将这一事实推广，可以得到如下定理。定理12-1 矩阵博弈模型G=S1，S2，A有解的充要条件是：存在纯局势(i*，j*)使得对于任何的i和j，都有aij*ai*j*ai*j，即存在一个鞍点元素。,矩阵博弈的基本理论,二、矩阵博弈的纯策略,在矩阵博弈中，如果赢得矩阵有鞍点存在，则该博弈称为有鞍点的矩阵博弈，否则称为无鞍点的矩阵博弈。对于有鞍点的矩阵博弈，局中人应选择自己的最优纯策略，任何一方单独改变策略都不会使自己获益。因此，最优局势(i*，j*)具有稳定性，是该博弈的稳定解，将这种局势也称为均衡局势。,矩阵博弈的基本理论,二、矩阵博弈的纯策略,例12-7 试判断例12-2贮煤问题是否有纯

15、策略解。解 首先需要建立贮煤问题的赢得矩阵。以冬季取暖用煤的实际费用作为局中人1的赢得，包括秋季购煤的费用和冬季用煤不够时再补购的费用之和，得到赢得矩阵如表12-5所示。,表12-5 贮煤问题的赢得矩阵（单位：万元）,矩阵博弈的基本理论,二、矩阵博弈的纯策略,例12-8 对于矩阵博弈G=S1，S2，A，其中赢得矩阵如下所示，试求该博弈的解。,矩阵博弈的基本理论,二、矩阵博弈的纯策略,从表12-6中可以发现，其中i*=1，3，j*=2，4，因此(1，2)，(1，4)，(3，2)，(3，4)四个局势都是博弈的解，且博弈的值为VG=4。,表12-6 例12-8的赢得矩阵,一般矩阵博弈的解可以不唯一，

16、但矩阵博弈的值唯一。,矩阵博弈的基本理论,三、矩阵博弈的混合策略,由前面的讨论知，对于矩阵博弈G=S1，S2，A，局中人1按照最小最大原则选择策略，可以保证自己的赢得至少为，局中人2按照最大最小原则选取策略，可以保证自己的最大损失。因为局中人1的赢得值不会多于局中人2的损失值，因此总有v1v2。当v1=v2时，矩阵博弈存在稳定的纯策略解。但是对于大多数的矩阵博弈，通常是v1v2，即不存在纯策略解，来看下面的例子。,矩阵博弈的基本理论,三、矩阵博弈的混合策略,例12-9 对于矩阵博弈G=S1，S2，A，其中赢得矩阵如下所示，试分析该问题是否有纯策略解。,不存在纯策略解！,矩阵博弈的基本理论,三、

17、矩阵博弈的混合策略,对两个局中人来说，不存在一个双方都能接受的均衡局势。在这种情况下，双方应该如何选择策略呢？一个切合实际合乎逻辑的想法是：各个局中人按照某种概率分布来选择策略。,矩阵博弈的基本理论,三、矩阵博弈的混合策略,定义12-2 对于矩阵博弈模型G=S1，S2，A，S1=1，2，m，S2=1，2，n，A=aijmn，令xi表示局中人1选取策略i(i=1，2，m)的概率,yj表示局中人2选取策略j(j=1，2，n)的概率,则,矩阵博弈的基本理论,三、矩阵博弈的混合策略,分别称为局中人1和局中人2的混合策略集，X S1*，Y S2*分别称为局中人1和局中人2的混合策略，(X，Y)称为一个混

18、合局势，局中人在此局势下的期望赢得记为：混合策略X=(x1，x2，xm)可设想成当两个局中人多次重复进行博弈时，局中人1分别采取纯策略1，2，m的频率。若只进行一次博弈，则表示局中人1对各个纯策略的偏爱程度，即以概率xi选择纯策略i参加博弈。,矩阵博弈的基本理论,三、矩阵博弈的混合策略,定义12-3 设X和Y分别为局中人1和2的任一混合策略，若存在局中人1的某个混合策略X*和局中人2的某个混合策略Y*，使下式成立称VG为该博弈的值，X*和Y*分别称作局中人1和局中人2的最优混合策略，局势(X*，Y*)称为最优（混合）局势，也称为博弈G在混合策略意义下的解。,矩阵博弈的基本理论,三、矩阵博弈的混

19、合策略,定理12-2 矩阵博弈模型G=S1，S2，A在混合策略意义下有解的充要条件是：存在X*S1*，Y*S2*，使得对于任意的X S1*和 Y S2*，有,矩阵博弈的基本理论,三、矩阵博弈的混合策略,定理12-2说明，如果局中人2采取自己的最优策略Y*，如果局中人1不采用最优策略，则他的期望赢得会减少（小于双方都采用最优策略时的所得）；若局中人1采用自己的最优策略X*，局中人2不采用最优策略，则他的期望损失会更大（大于双方都采用最优策略时的损失），因此X*和Y*对两个局中人来说互为最佳反应策略。,矩阵博弈的基本理论,四、矩阵博弈的基本性质,令E(i，Y)表示局中人1选取纯策略i 而局中人2选

20、取混合策略 Y时的期望赢得，令E(X，j)表示局中人1选取混合策略X而局中人2选取纯策略j时的期望赢得，则应有：从而，混合策略(X，Y)的期望赢得可以表示为：,矩阵博弈的基本理论,四、矩阵博弈的基本性质,定理12-3 设X*S1*，Y*S2*，则(X*，Y*)为矩阵博弈G的解的充要条件是：对于任意的i=1，2，m和j=1，2，n，有,矩阵博弈的基本理论,四、矩阵博弈的基本性质,定理12-4 设X*S1*，Y*S2*，则(X*，Y*)为矩阵博弈G的解的充要条件是：存在数v，使得X*和Y*分别是下面两个不等式的解，且对策的值VG=v。,矩阵博弈的基本理论,四、矩阵博弈的基本性质,定理12-5 对任

21、一矩阵博弈G=S1，S2，A，一定存在混合策略意义下的解。定理12-6 若(X*，Y*)为矩阵博弈G的解，VG是博弈的值，则对于每一个i和j有：,矩阵博弈的基本理论,四、矩阵博弈的基本性质,定理12-7 设有两个矩阵博弈G1=S1，S2，A1和G2=S1，S2，A2，其中A1=(aij)，A2=(aij+k)，k为任意常数，则有：定理12-8 设有两个矩阵博弈G1=S1，S2，A和G2=S1，S2，A，其中0为任一常数，则有：,矩阵博弈的求解方法,一、22矩阵博弈的公式法,所谓22矩阵博弈是指两个局中人分别只有两个纯策略，赢得矩阵为22阶矩阵，即如果赢得矩阵中不存在鞍点，则两个局中人的最优混合

22、策略分别可以由下式给出：,矩阵博弈的求解方法,一、22矩阵博弈的公式法,当赢得矩阵中不存在鞍点时,可以证明上面等式组(1)和(2)一定有严格非负解X*=(x1*，x2*)和Y*=(y1*，y2*)，其中,矩阵博弈的求解方法,二、矩阵博弈的劣汰原则,根据博弈中对局中人的理性假设，每个局中人在选择策略时总是选择对自己有利的策略。因此，若存在某纯策略，局中人选择该策略的赢得值肯定比选择其他纯策略时的赢得值更小（或损失值比其他纯策略的损失值更大），则局中人从自身利益出发，绝不会选择这种策略（选择该策略的概率为零），从而在求解时可以将这些策略删去，使赢得矩阵得到简化。,矩阵博弈的求解方法,二、矩阵博弈的

23、劣汰原则,定义12-4 对于矩阵博弈G=S1，S2，A，其中S1=1，2，m，S2=1，2，n，A=(aij)mn，若赢得矩阵A中存在i行和k行，其元素之间有关系aijakj(j=1，2，n)，则称局中人1的纯策略i优超于纯策略k，或称纯策略k为局中人1的劣策略；若赢得矩阵A中存在j列和l列，其元素之间有关系aijail(i=1，2，m)，则称局中人2的纯策略j优超于纯策略l，或称纯策略l为局中人2的劣策略。,矩阵博弈的求解方法,二、矩阵博弈的劣汰原则,定理12-9 对于矩阵博弈G=S1，S2，A，其中S1=1，2，m，S2=1，2，n，A=(aij)mn，如果纯策略1被其余纯策略2，m中之一

24、所优超，由G可得到一个新的矩阵博弈G=S1，S2，A，其中S1=2，m，A=(aij)(m-1)n，aij=aij(i=2，m，j=1，2，n)，则G和G之间有下述关系：(1)VG=VG；(2)G中局中人2的最优策略与G中局中人2的最优策略相同；(3)若X*=(x2*，xm*)是G中局中人1的最优策略，则X*=(0，x2*，xm*)就是G中局中人1的最优策略。,矩阵博弈的求解方法,二、矩阵博弈的劣汰原则,定理12-9表明：若1为局中人1的劣策略，则必被淘汰（即有x1*=0)，这时可将第1行删去，使矩阵降阶简化。对于任意一个较大的博弈矩阵，通常应先检查是否存在优超关系。当局中人的纯策略之间存在上

25、述优超关系时，划去赢得矩阵中劣策略对应的行或者列，使得赢得矩阵得到简化，而博弈的最优策略和博弈的值保持不变，这就是所谓的汰劣原则。,矩阵博弈的求解方法,二、矩阵博弈的劣汰原则,例12-10 求解矩阵博弈G=S1，S2，A，其中解 根据定义12-4，可以发现，矩阵A中第4行优于第1行，第3行优于第2行，故删去第1行和第2行，从而得到,矩阵博弈的求解方法,二、矩阵博弈的劣汰原则,第1列优于第3列，第2列优于第4列，删去第3列和第4列,第1行优于第3行，删去第3行,第1列优于第3列，删去第3列,22矩阵博弈，公式法进行求解,X*=(0，0，1/3，2/3，0)，Y*=(1/2，1/2，0，0，0)，

26、博弈的值VG=5。,矩阵博弈的求解方法,二、矩阵博弈的劣汰原则,例12-11 求解矩阵博弈G=S1，S2，A，其中解 为方便起见，记矩阵的第k行为ak，第l列为bl。从矩阵A中可发现，故删去第2列，得到,矩阵博弈的求解方法,二、矩阵博弈的劣汰原则,删去第1行和第2行,第3列优于第1列，删去第1列,22矩阵博弈，公式法求解,X*=(0，0，1/3，2/3)，Y*=(0，0，2/3，1/3)，VG=14/3。,矩阵博弈的求解方法,三、图解法,（一）赢得矩阵为2n的图解法例12-12 采用图解法求解例12-9的矩阵博弈。,表12-7 例12-9的赢得矩阵,矩阵博弈的求解方法,三、图解法,（一）赢得矩

27、阵为2n的图解法解 第一步，首先检查赢得矩阵是否存在优超现象。从表12-7的赢得矩阵可以发现，无论对手选择哪个策略，局中人1的策略3总是劣于策略2。从赢得矩阵中删去策略3后，局中人1只有两个纯策略了，如表12-8所示。,表12-8 缩减后的赢得矩阵,矩阵博弈的求解方法,三、图解法,（一）赢得矩阵为2n的图解法第二步，确定局中人1的最优混合策略。设局中人1的混合策略为(x，1-x)，x0，1，则当局中人2分别取纯策略1，2，3时局中人1的期望赢得可以表示为以下三条直线：,矩阵博弈的求解方法,三、图解法,（一）赢得矩阵为2n的图解法联立b2、b3方程组局中人1的最优混合策略为X*=(7/11，4/

28、11)。,矩阵博弈的求解方法,三、图解法,（一）赢得矩阵为2n的图解法第三步，确定局中人2的最优混合策略。设Y*=(y1*，y2*，y3*)为局中人2的最优混合策略，从图中可以看出，局中人2的最优混合策略只由2和3组成。实际上，当局中人1选取最优策略X*=(7/11，4/11)时，局中人2的期望收益为：,矩阵博弈的求解方法,三、图解法,（一）赢得矩阵为2n的图解法由于y1*+y2*+y3*=1，故可知y1*=0。从而，根据定理12-6，局中人2的最优策略可以由以下方程联立得到：故局中人2的最优混合策略为Y*=(0，5/11，6/11)。,矩阵博弈的求解方法,三、图解法,（二）赢得矩阵为m2的图

29、解法例12-13 采用图解法求解矩阵博弈G=S1，S2，A，其中赢得矩阵解 第一步，检查赢得矩阵是否存在优超现象。经检查，该赢得矩阵没有优超现象。,矩阵博弈的求解方法,三、图解法,（二）赢得矩阵为m2的图解法第二步，确定局中人2的最优混合策略。设局中人2的混合策略为(y，1-y)，y0，1，则当局中人1分别取纯策略1，2，3时局中人2的期望损失可以表示为以下三条直线：,矩阵博弈的求解方法,三、图解法,（二）赢得矩阵为m2的图解法联立求解过C点的两条线段，可以得到y和V的值：y=2/3，V=8/3。因此，局中人2的最优混合策略为Y*=(2/3，1/3)。第三步，确定局中人1的最优混合策略。设X*

30、=(x1*，x2*，x3*)为局中人1的最优混合策略，从前页图可以看出，局中人1的最优混合策略只由1和2组成。根据定理12-6，可以由以下方程联立得到：,矩阵博弈的求解方法,四、方程组解法,由定理12-4知，求矩阵博弈的解等价于求解其中的两个不等式组，又由定理12-6知，如果最优混合策略中的每一个分量均不为零，则可将不等式组转换为如下的两个方程组：,矩阵博弈的求解方法,四、方程组解法,如果这两个方程组存在非负解X*和Y*，则求得了该博弈的一个解；如果不存在非负解，则需要视情况将其中的某些等式改为不等式进行试算，直到求得满意的解。这种方法的应用前提是事先假定了X*和Y*的所有分量都大于零，因而当

31、最优策略的某些分量实际为零时，该方法失效。,矩阵博弈的求解方法,四、方程组解法,例12-14 求解例12-4的矩阵博弈“田忌赛马”。解 齐王的赢得矩阵为,不存在鞍点，无最优纯策略解！,矩阵博弈的求解方法,四、方程组解法,设齐王和田忌的最优混合策略分别为X*和Y*。从该博弈的特点来看，每种策略的赢得和损失差别不大，因此每个局中人选用每一个策略的可能性都是存在的，故可事先假定X*和Y*的所有分量都大于零。于是，求解方程组,矩阵博弈的求解方法,四、方程组解法,解得X*=(1/6，1/6，1/6，1/6，1/6，1/6)，Y*=(1/6，1/6，1/6，1/6，1/6，1/6)，VG=v=1。,矩阵博

32、弈的求解方法,四、方程组解法,计算结果表明，双方都以均等的机会选用各自的6个纯策略，总的结局是，齐王的期望赢得为一千金(VG=1)，这与各自的马力情况是相吻合的。田忌之所以反赢一千金，是因为他接受了孙膑的建议，每次都让齐王先出马，然后再有针对性的选择有利于自己的纯策略。因此，当矩阵博弈不存在最优纯策略时，策略保密是十分重要的，谁不保密谁吃亏。,矩阵博弈的求解方法,五、线性规划法,线性规划可以用来求解任何类型的矩阵博弈模型。下面用一个经典的“石头-剪刀-布”博弈游戏来说明其建模过程。例12-15 甲乙两名儿童玩游戏，双方可分别出拳头（代表石头），手掌（代表布），两个手指（代表剪刀），规则是：剪刀

33、赢布，布赢石头，石头赢剪刀，赢者得一分，如果双方出的相同，则算和局不得分。试建立该博弈的模型并求出其混合策略。,矩阵博弈的求解方法,五、线性规划法,解 建立局中人1的赢得矩阵如表12-9所示。可以看出，该矩阵博弈无鞍点，也不存在优超现象。,表12-9“石头-剪刀-布”博弈游戏的赢得矩阵,矩阵博弈的求解方法,五、线性规划法,为了求解该博弈模型，设甲的最优混合策略为X*=(x1*，x2*，x3*)，乙的最优混合策略为Y*=(y1*，y2*，y3*)。对于乙的每一个策略，甲采用最优混合策略(x1*，x2*，x3*)的期望赢得如表12-10所示。,表12-10 甲采用最优混合策略时的期望赢得,矩阵博弈

34、的求解方法,五、线性规划法,根据最大最小原则，乙会选取策略以使得甲的期望赢得等于min(x2-x3，-x1+x3，x1-x2)，而甲会选择(x1，x2，x3)从而使得min(x2-x3，-x1+x3，x1-x2)(记为v)尽可能的大。因此，甲的最优策略可以通过求解下面的线性规划模型LP1得到：,矩阵博弈的求解方法,五、线性规划法,对于甲的每一个策略，如果乙采用最优混合策略(y1，y2，y3)，那么甲的期望赢得如表12-11所示。,表12-11 乙采用最优混合策略时甲的期望赢得,矩阵博弈的求解方法,五、线性规划法,甲会选取策略使得自己的期望赢得达到max(-y2+y3，y1-y3，-y1+y2)

35、，因此乙会选取y1，y2，y3的值使得从而使得max(-y2+y3，y1-y3，-y1+y2)的值(记为w)尽可能的小。因此，乙的最优策略可以通过求解下面的线性规划模型LP2得到：,矩阵博弈的求解方法,五、线性规划法,对线性规划模型LP1和LP2进行求解，可以得到甲的最优混合策略为X*=(1/3，1/3，1/3)，乙的最优混合策略为Y*=(1/3，1/3，1/3)。该矩阵博弈的值为v=w=0，说明该游戏对双方是公平的。,矩阵博弈的求解方法,五、线性规划法,改写,矩阵博弈的求解方法,五、线性规划法,令线性规划模型LP1的对偶变量分别为y1，y2，y3和w，从而可以得到LP1的对偶规划如下所示：,

36、与LP2完全相同！,矩阵博弈的求解方法,对于一般的矩阵博弈模型G=S1，S2，A，各局中人的线性规划模型如下所示。局中人1的线性规划模型LP1表示为：,或,矩阵博弈的求解方法,局中人2的线性规划模型LP2表示为：,或,矩阵博弈的求解方法,为了便于采用单纯形法或对偶单纯形法求解，可以先对模型进行变形。变换方法如下：首先由定理12-7，对赢得矩阵的每一个元素加上一个正常数k（赢得矩阵中最小负数的绝对值），使得矩阵中的所有元素都大于等于零，从而保证v0，w0，然后做变换xi=xi/v，yi=yi/w，则有从而相应的线性规划模型可以变换为：,矩阵博弈的求解方法,显然，LP1和LP2依然是互为对偶的线性

37、规划，对上述线性规划模型进行求解，然后根据所施行的变换即可得到原博弈问题的解和值。,矩阵博弈的求解方法,对于一般的矩阵博弈模型G=S1，S2，A，其求解步骤如下所示。第一步：首先检查该模型的赢得矩阵A中是否存在鞍点，如果存在，则得到该博弈的纯策略解，若没有，则转下一步。第二步：检查赢得矩阵A中是否存在优超现象，若存在，使用汰劣原则对矩阵进行缩减。第三步：如果缩减后的赢得矩阵为2n或者m2矩阵，采用图解法进行求解；否则，采用线性规划法进行求解。,其他类型博弈简介,一、二人有限非零和博弈,一般的，二人有限非零和博弈的数学模型可以用G=S1，S2，A，B表示，其中局中人1的纯策略集S1=1，2，m，

38、赢得矩阵为A=(aij)mn，局中人2的纯策略集S2=1，2，n，赢得矩阵为B=(bij)mn，(A，B)=(aij，bij)mn，一般A+B0，这类博弈也称为双矩阵博弈。可见，矩阵博弈(A+B=0)是双矩阵博弈的一个特例。,其他类型博弈简介,一、二人有限非零和博弈,定义12-5 设G=S1，S2，A，B为双矩阵博弈，X*S1*，Y*S2*。对于任意给定的XS1*和Y S2*，有则称(X*，Y*)为双矩阵博弈G的均衡局势，也称为双矩阵博弈G的均衡解。,其他类型博弈简介,一、二人有限非零和博弈,例12-16 试分析例12-3囚徒困境的均衡解。解 假定嫌疑犯A选择坦白的话，B最好是选择坦白，因为B

39、坦白判5年而不坦白却要判10年；假定嫌疑犯A选择不坦白的话，B最好也是选择坦白，因为B坦白不被判刑而不坦白却要判1年。也就是说，不论A选择是坦白还是不坦白，B的最佳选择都是坦白。同样的，不管B是选择坦白还是不坦白，A的最佳选择也是坦白。,其他类型博弈简介,一、二人有限非零和博弈,因此，两个人的最佳选择都是坦白。在（坦白，坦白）这个组合中，A和B都不能通过单方面改变行动以增加自己的收益，于是谁也没有动力游离这个组合，因此这个组合便是该博弈的均衡解，也称为纳什均衡。,其他类型博弈简介,一、二人有限非零和博弈,任何博弈都至少存在一个纳什均衡。这一点是由博弈论大师纳什于1950年提出的“纳什定理”揭示

40、的。定理12-9（纳什定理）在一个有n个博弈方的非合作博弈中，如果n是有限的，且每个博弈人的策略集合也是有限的，则该博弈至少存在一个纳什均衡，但可能包含混合策略。,其他类型博弈简介,一、二人有限非零和博弈,例12-17 供应商的囚徒困境现假定有一家公司的采购人员，正在决定向两家供应商采购100万个零配件，每个零配件的单件生产成本是6元，市场价是每件10元。如果向两家分别订货50万件，则两家各得利润50(10-6)=200万元，采购员需要花费的订货费用是1000万元。如果采购人员向供应商宣布，如果谁肯把单价降到8.5元，谁就可以得到100万件配件的全部订货。当然，如果两家都愿意以8.5元供货的话

41、，则依然是各订50万件。试分析该博弈的均衡解。,其他类型博弈简介,一、二人有限非零和博弈,解 首先建立博弈模型，局中人为两家供应商，可选的策略则产品供货价格为8.5元和10元。按照8.5元的价格，订货100万件时供应商的利润为100(8.5-6)=250万元，订货50万件时的利润为50(8.5-6)=125万元。于是得到博弈矩阵如下所示。,表12-12 供应商的赢得表,该博弈的均衡解是(8.5元，8.5元)。订货费用是850万元，节省了150万元的采购费用。,其他类型博弈简介,二、二人无限非零和博弈,当两个局中人的策略集S1和S2中至少有一个为无限集时，该博弈就称为二人无限博弈。当局中人的赢得

42、之和为零时，称为二人无限零和博弈。若局中人的赢得之和不为零时，该博弈称为二人无限非零和博弈。用Hi(i，j)表示第i个局中人的赢得函数。,其他类型博弈简介,二、二人无限非零和博弈,定义12-6 对于二人无限非零和博弈，若存在i*S1，j*S2，使得对于任意的iS1，j S2，有则称(i*，j*)为博弈在纯策略意义下的解，i*和j*分别称为局中人的最优纯策略。,其他类型博弈简介,二、二人无限非零和博弈,例12-18 在例12-5的产量竞争问题中，若a=8，b=1，c=2，试分析每一家企业应如何选择自己的产量，以实现自己的赢得最大？解 由于市场上只有两家厂商，各自的产量为q1和q2，两家厂商的赢得

43、函数分别为,其他类型博弈简介,二、二人无限非零和博弈,对于每一家企业来说，选择产量qi使自己赢得最大，即 令,此时，产品的价格为8-4=4，两个厂商的赢得即利润均为22=4，市场上总的商品量Q=q1+q2=4，两厂商的 利润总和为4+4=8。,管理博弈应用,针对第一节给出的港口竞争问题进行求解。首先，检查赢得矩阵A中不存在鞍点，因此该博弈不存在纯策略解。第二步，检查赢得矩阵A中也不存在优超现象，由于当前赢得矩阵为33矩阵，因此采用线性规划法进行求解。第三步，建立线性规划模型并求解。,管理博弈应用,为了便于求解，首先给赢得矩阵中的所有元素都加上最小负数的绝对值k=3，将赢得矩阵转化为做变换xi=xi/v，yi=yi/w，建立线性规划模型如下所示：,管理博弈应用,采用Excel对模型进行求解得到：则原博弈的解为：原博弈的值为：,管理博弈应用,从求解结果可以看出，港口A应采取的最优混合策略为(3/5，1/5，1/5)，可以保证最小赢得不低于1/5，港口B应采取的最优混合策略为(1/20，8/20，11/20)，可以保证最大损失不超过1/5。正的博弈值表明，总体情况对港口企业A是有利的，但是若港口A公开自己的策略，则港口B可以灵活选择相应的策略，反而会赢得A的一些货物量。因此，竞争的双方均应对自己的策略保密，否则，公开的一方是要吃亏的。,