第十四章第十四章 对策论对策论对策论概论对策论概论 对策论（对策论（The Game Theory)也称竞赛论也称竞赛论或博弈论，是研究具有竞争、对抗、利益分或博弈论，是研究具有竞争、对抗、利益分配等方面的数量化方法，并提供寻求最优策配等方面的数量化方法，并提供寻求最优策略的途径。略的途径。1944年以来，对策论在投资分析、价格制定、年以来，对策论在投资分析、价格制定、费用分摊、财政转移支付、投标与拍卖、对费用分摊、财政转移支付、投标与拍卖、对抗与追踪、国际冲突、双边贸易谈判、劳资抗与追踪、国际冲突、双边贸易谈判、劳资关系以及动物行为进化等领域得到广泛应用。关系以及动物行为进化等领域得到广泛应用。14-114-1矩阵对策的基本概念矩阵对策的基本概念案例：俾斯麦海的海空对抗案例：俾斯麦海的海空对抗 1943年年2月，第二次世界大战中的月，第二次世界大战中的日本，在太平洋战区已经处于劣势。日本，在太平洋战区已经处于劣势。为扭转局势，日本统帅山本五十六大为扭转局势，日本统帅山本五十六大将统率下的一支舰队策划了一次军事将统率下的一支舰队策划了一次军事行动：由集结地行动：由集结地南太平洋的新不南太平洋的新不列颠群岛的蜡包尔出发，穿过俾斯麦列颠群岛的蜡包尔出发，穿过俾斯麦海，开往新几内亚的莱城，支援困守海，开往新几内亚的莱城，支援困守在那里的日军。在那里的日军。 当盟军获悉此情报后，盟军统帅当盟军获悉此情报后，盟军统帅麦克阿梭命令太平洋战区空军司令肯麦克阿梭命令太平洋战区空军司令肯尼将军组织空中打击。尼将军组织空中打击。 日本统帅山本五十六大将心里很日本统帅山本五十六大将心里很明白：明白： 在日本舰队穿过俾斯麦海的三在日本舰队穿过俾斯麦海的三天航行中，不可能躲开盟军的空中打天航行中，不可能躲开盟军的空中打击，他要策划的是尽可能减少损失。击，他要策划的是尽可能减少损失。 日美双方的指挥官及参谋人员都日美双方的指挥官及参谋人员都进行了冷静的思考与全面的谋划进行了冷静的思考与全面的谋划。 自然条件对于双方自然条件对于双方 都是已知的。都是已知的。基本情况如下：从蜡包尔出发开往莱基本情况如下：从蜡包尔出发开往莱城的海上航线有南北两条。通过时间城的海上航线有南北两条。通过时间均为均为3天。天。 气象预报表明：未来气象预报表明：未来3天中，北天中，北线阴雨，能见度差；而南线天气晴好，线阴雨，能见度差；而南线天气晴好，能见度好。能见度好。 肯尼将军的轰炸机布置在南线的肯尼将军的轰炸机布置在南线的机场，侦察机全天候进行侦察机场，侦察机全天候进行侦察，但有但有一定的搜索半径一定的搜索半径。 经测算，双方均可得到如下估计：经测算，双方均可得到如下估计：局势局势1： 盟军的侦察机重点搜索北线，盟军的侦察机重点搜索北线，日本舰队也恰好走北线。由于气候恶日本舰队也恰好走北线。由于气候恶劣，能见度差，盟军只能实施两天的劣，能见度差，盟军只能实施两天的轰炸。轰炸。局势局势2：盟军的侦察机重点搜索北线，盟军的侦察机重点搜索北线，日本舰队走南线。由于发现晚，尽管日本舰队走南线。由于发现晚，尽管盟军的轰炸机群在南线，但有效轰炸盟军的轰炸机群在南线，但有效轰炸也只有两天。也只有两天。局势局势3：盟军的侦察机重点搜索南线，盟军的侦察机重点搜索南线，而日本舰队走北线。由于发现晚、盟而日本舰队走北线。由于发现晚、盟军的轰炸机群在南线，以及北线气候军的轰炸机群在南线，以及北线气候恶劣，故有效轰炸只有一天。恶劣，故有效轰炸只有一天。局势局势4：盟军的侦察机重点搜索南线，盟军的侦察机重点搜索南线，日本舰队也恰好走南线。此时日本舰日本舰队也恰好走南线。此时日本舰队迅速被发现，盟军的轰炸机群所需队迅速被发现，盟军的轰炸机群所需航程很短，加上天气晴好，有效轰炸航程很短，加上天气晴好，有效轰炸时间三天。时间三天。 这场海空遭遇与对抗一定会发生，这场海空遭遇与对抗一定会发生，双方的统帅如何决策呢？历史的实际双方的统帅如何决策呢？历史的实际情况是：情况是：局势局势1成为现实。肯尼将军命成为现实。肯尼将军命令盟军的侦察机重点搜索北线；而山令盟军的侦察机重点搜索北线；而山本五十六大将命令日本舰队取道北线本五十六大将命令日本舰队取道北线航行。由于气候恶劣，能见度差，盟航行。由于气候恶劣，能见度差，盟军飞机在一天后发现了日本舰队，基军飞机在一天后发现了日本舰队，基地在南线的盟军轰炸机群远程航行，地在南线的盟军轰炸机群远程航行，实施了两天的有效轰炸，重创了日本实施了两天的有效轰炸，重创了日本舰队，但未能全歼。舰队，但未能全歼。对策的三要素：对策的三要素：局中人：局中人：有权决定自己行为方案的对有权决定自己行为方案的对局参加者称为局中人。案例中，美日局参加者称为局中人。案例中，美日双方的决策者为局中人。当对局中局双方的决策者为局中人。当对局中局中人只有两人时，称为二人对策。中人只有两人时，称为二人对策。策略：策略：对局中一个实际可行的方案称对局中一个实际可行的方案称为一个策略。案例中，美日双方各有为一个策略。案例中，美日双方各有二个策略二个策略。赢得矩阵（支付）：赢得矩阵（支付）：当每个局中人当每个局中人在确定了所采取的策略后，他们就在确定了所采取的策略后，他们就会获得相应的收益或损失，此收益会获得相应的收益或损失，此收益或损失的值称为赢得（支付）。赢或损失的值称为赢得（支付）。赢得与策略之间的对应关系称为赢得得与策略之间的对应关系称为赢得（支付）函数。（支付）函数。案例中，肯尼将军与山本五十六大案例中，肯尼将军与山本五十六大将的赢得（支付）函数都可以用矩将的赢得（支付）函数都可以用矩阵阵A、B表示。表示。 （日军）（日军） 北线北线 南线南线（盟军）北线（盟军）北线 2 2 =A 南线南线 1 3 （日军）（日军） 北线北线 南线南线（盟军）北线（盟军）北线 -2 -2 =B 南线南线 -1 -3在本例中的每一个对局，双方的在本例中的每一个对局，双方的赢得的代数之和为零，这样的对赢得的代数之和为零，这样的对策称为策称为“有限零和二人对策有限零和二人对策”设两个局中人为设两个局中人为I，II，局中人局中人I有有m 个策略：个策略： 1、 2 m ；用用S1表表示这些策略的集合：示这些策略的集合：S1= 1、 2 m 同样，局中人同样，局中人II有有n个策略：个策略： 1、 2。 n ；用用S2表示这些策略的集合：表示这些策略的集合：S2= 1、 2 n 局中人局中人I的赢得矩阵是：的赢得矩阵是： a11 a12 a1n a21 a22 a2n A= a m 1 a m 2 a m n局中人局中人II的赢得矩阵是的赢得矩阵是 -A把一个对策记为把一个对策记为G：G= S1，S2；A 北线北线 1 南线南线 2（盟军）北线（盟军）北线 1 2 2 =A 南线南线 2 1 3 在矩阵中，盟军的最大赢得是在矩阵中，盟军的最大赢得是3，而要得到，而要得到3，必须选择策略，必须选择策略 2，而日军的目的是使盟军的赢得尽量而日军的目的是使盟军的赢得尽量的小，必须选择策略的小，必须选择策略 1 ，使盟军的使盟军的赢得只有赢得只有1。 在局中人在局中人I设法使自己的赢得尽设法使自己的赢得尽可能大的同时，局中人可能大的同时，局中人II也设法使也设法使局中人局中人I的赢得尽可能小。的赢得尽可能小。所以局中人所以局中人I应首先考虑用应首先考虑用 所能赢所能赢得的最小，然后在这些最小赢得中得的最小，然后在这些最小赢得中选择最大。局中人选择最大。局中人I可以保证赢得可以保证赢得 max min aij i j同样，局中人同样，局中人II可以保证局中人可以保证局中人I的的赢得不超过赢得不超过 min max aij j i 案例中局中人案例中局中人I（盟军）应当选盟军）应当选择（北线）策略择（北线）策略 1，这样这样能保证赢能保证赢得得2。局中人。局中人II（日军）应当选择日军）应当选择（北线）策略（北线）策略 1使使盟军赢得不超过盟军赢得不超过2。实际上，在（实际上，在（ 1， 1）局势下，有局势下，有 max min aij= min max aij i j j i上式蕴涵的思想是朴素自然的，可上式蕴涵的思想是朴素自然的，可以概括为以概括为：“从最坏处着想，去争从最坏处着想，去争取最好的结果取最好的结果”定义定义14-1：对给定的矩阵对策对给定的矩阵对策 G = S1，S2；A 若等式若等式max min aij= min max aij i j j i成立，则称这个公共值为对策成立，则称这个公共值为对策G的值，的值，记为记为VG，而达到的局势而达到的局势（ i， j ）称为对策称为对策G在纯策略意义下的解，记在纯策略意义下的解，记为为（ I*， j *）而而 I*和和 j *分别称分别称为局中人为局中人I和局中人和局中人II的最优纯策略。的最优纯策略。定理定理14-1：矩阵对策矩阵对策 G = S1，S2；A在纯策略意义下有解的充分必要条在纯策略意义下有解的充分必要条件是：件是：存在一个局势存在一个局势（ *i*， *j *），），使使得对一切得对一切 i=1，2， m， j=1，2n 均有均有 aij*=ai*j*= ai*j定理定理14-1表明矩阵对策表明矩阵对策 G = S1，S2；A有解的充分必要条件是在有解的充分必要条件是在A中存在元中存在元素素 ai*j*是其所在行中最小的同时又是其所在行中最小的同时又是其所在列中最大的。这时是其所在列中最大的。这时ai*j*即即是是对策值，因此对策值，因此ai*j*也称为也称为“鞍点鞍点”，而，而（ *i*， *j *），），为对策的为对策的解。解。X XY Y马鞍面马鞍面z=f(x,y)鞍点鞍点Z ZY YZ Z在在X=0的平面上的平面上鞍点鞍点是是z=f(0,y)的极大值点的极大值点z=f(0,y)X XZ Z在在Y=0的平面上的平面上鞍点鞍点是是z=f(x,0)的极小值点的极小值点z=f(x,0)例例14-3：对给定的矩阵对策对给定的矩阵对策 G = S1,S2;A S1= 1, 2 , 3 S2= 1 , 2 , 3 6 5 6 A= 1 4 2 8 5 7显然显然 ai2 a12 a1j ai2 a32 a3j对对 I=1,2,3 j=1,2,3 都都成立：成立： a12 = a32 =5由定理由定理5-1，对策值，对策值=5，对策的解：（，对策的解：（ 1 , 2 ）和（和（ 3 , 2 ）例例14-4：某单位采购员在秋天时要决定某单位采购员在秋天时要决定冬天取暖用煤的采购量。已知在正常气冬天取暖用煤的采购量。已知在正常气温条件下需要用煤温条件下需要用煤15吨，在较暖和较冷吨，在较暖和较冷气温条件下需要用煤气温条件下需要用煤10吨和吨和20吨。假定吨。假定冬季的煤价随着天气寒冷的程度而变化，冬季的煤价随着天气寒冷的程度而变化，在较暖、正常、较冷气温条件下每吨煤在较暖、正常、较冷气温条件下每吨煤价为价为100元、元、150元、元、200元。又秋季每吨元。又秋季每吨煤价为煤价为100元。在没有关于当年冬季气温元。在没有关于当年冬季气温情况下，秋季应购多少吨煤，能使总支情况下，秋季应购多少吨煤，能使总支出最少？出最少？解：解：局中人局中人I（采购员）有三个策略：采购员）有三个策略：策略策略 1: 10吨吨,策略策略 2: 15吨吨,策略策略 3 :20吨。吨。 局中人局中人II（环境）：环境）：策略策略 1 较暖较暖 ,策略策略 2 正常，策略正常，策略 3较冷较冷 现把该单位冬天取暖用煤全部费现把该单位冬天取暖用煤全部费用（秋季购煤费用与冬天不够时再补购用（秋季购煤费用与冬天不够时再补购煤费用）作为采购员的赢得矩阵。煤费用）作为采购员的赢得矩阵。 1 2 3 1-1000 -1750 -3000 2-1500 -1500 -2500 3-2000 -2000 -2000由由max min aij= min max aij = a33 = -2000 I j j i该最优策略为（该最优策略为（ 3， 3），），即秋季购煤即秋季购煤20吨。吨。定义定义14-2:对给定的矩阵对策对给定的矩阵对策 G = S1,S2;A其中其中 S1= 1, 2 m S2= 1 , 2 n A=(aij)mn把纯策略集合对应的概率向量把纯策略集合对应的概率向量X=(x1, x2 xm) 其中其中 xi 0 xi=1 和和Y=(y1 , y2 yn ) 其中其中 yj 0 yj=1 分别称为局中人分别称为局中人I和局中人和局中人II的混合策略。的混合策略。如果局中人如果局中人I选取的策略为选取的策略为X=(x1, x2 xm)局中人局中人II选取的策略为选取的策略为Y=(y1 , y2 yn )，则期望值则期望值E（X，Y）= xi aij yj=XAYT称为局中人称为局中人I期望赢得，而局势（期望赢得，而局势（X，Y）称为称为“混合局势混合局势”，局中人，局中人I，II的混合的混合策略集合记为策略集合记为S1*， S2*。定义定义14-3:对给定的矩阵对策对给定的矩阵对策 G = S1,S2;A则对策则对策G*= S1*,S2*;E称为对策称为对策G混合扩充。混合扩充。定义定义14-4:设设G*= S1*,S2*;E 是对策是对策G混合扩充，如果有混合扩充，如果有max min E(X,Y)= min max E(X,Y)X X S S1 1* * Y Y S S2 2* * Y Y S S2 2* * X X S S1 1* * 则称这个公共值为则称这个公共值为对策对策G在混合意义在混合意义下的下的值，记为值，记为V*G，而达到而达到V*G 的混的混合局势（合局势（X*，Y*）称为称为对策对策G在混合在混合策略意义下的策略意义下的解，而解，而X*和和Y*分别称分别称为局中人为局中人I，II的最优的最优混合策略。混合策略。定理定理14-2：矩阵对策矩阵对策 G = S1，S2；A在混合策略意义下有解的充分必要条件在混合策略意义下有解的充分必要条件是：是：存在混合局势存在混合局势（ X*，Y*），），使得对一使得对一切切 X S1* Y S2*均有均有 E（X，Y*） E（X*，Y*） E（X*，Y）定理定理14-3：对给定的矩阵对策对给定的矩阵对策 G = S1，S2；A设设X* S1* Y* S2*则混合局势则混合局势（ X*，Y*）是是G的解且的解且V=VG*的充分必要条件的充分必要条件是：是：对一切对一切 i,j均有均有 E（ i， Y*） V E（X*， j ）定理定理14-4：任意一个给定的任意一个给定的矩阵对策在混合策略意义下矩阵对策在混合策略意义下一定有解。一定有解。 矩阵对策的解可能不只矩阵对策的解可能不只一个，但对策值是唯一。一个，但对策值是唯一。例例14-5（订货计划）某厂制造和销售一种（订货计划）某厂制造和销售一种新仪器，需要外购一种配件。现有三个新仪器，需要外购一种配件。现有三个厂生产这种配件，牌号为厂生产这种配件，牌号为A，B，C。 A配件每只配件每只10元，但有次品，装配的仪器元，但有次品，装配的仪器也是次品，每台损失也是次品，每台损失100元；元；B配件每只配件每只55元，也有次品，但装配的仪器出售后元，也有次品，但装配的仪器出售后可在保修期内稍加修理就能使用，修理可在保修期内稍加修理就能使用，修理费费55元；元； C配件每只配件每只118元，没有次品；元，没有次品；问该厂应如何购置各种配件，使总费用问该厂应如何购置各种配件，使总费用（包括损失费和修理费）最少？（包括损失费和修理费）最少？例例14-6（费用分摊问题）假设沿某河流有（费用分摊问题）假设沿某河流有相邻的三个城市：相邻的三个城市：A，B，C。各城市都各城市都想建立自来水厂解决用水问题。各城市想建立自来水厂解决用水问题。各城市可单独建立自来水厂，也可以合作建一可单独建立自来水厂，也可以合作建一个大水厂，再用管道送到各城市。经估个大水厂，再用管道送到各城市。经估计，合作建一个大水厂比单独建三个自计，合作建一个大水厂比单独建三个自来水厂的总费用少。三个城市来水厂的总费用少。三个城市有意合作，但是否实施，看总费用的分摊是否合理。问题是如何合理分摊费用，使合作建立大水厂的方案得以实现。大水厂的方案得以实现。例例14-7（拍卖问题）拍卖形式是先由拍卖（拍卖问题）拍卖形式是先由拍卖商对拍卖品描述一番，然后提出第一个商对拍卖品描述一番，然后提出第一个报价。接下来由买者报价，每一次都比报价。接下来由买者报价，每一次都比前次高，最后谁出的价格高拍卖品即归前次高，最后谁出的价格高拍卖品即归谁所有。假设报价为谁所有。假设报价为p1,p2 pn-1 , pn,设设p1p2 pn-1 pn.买主只要略高于买主只要略高于pn-1就能买到。问题是，各买主之间可能就能买到。问题是，各买主之间可能知道他人的估价，也可能不知道他人的知道他人的估价，也可能不知道他人的估价，每人应如何报价对自己能以较低估价，每人应如何报价对自己能以较低的价格得到拍卖品最为有利？的价格得到拍卖品最为有利？例例14-8（囚犯难题）设有两个嫌疑犯被警（囚犯难题）设有两个嫌疑犯被警察拘留，警察分别对两人进行审讯。根察拘留，警察分别对两人进行审讯。根据法律，如果两人都承认此案是他们干据法律，如果两人都承认此案是他们干的，则每人各判刑的，则每人各判刑7年；如果两人都不承年；如果两人都不承认，则由于证据不足，两人各判刑认，则由于证据不足，两人各判刑1年；年； 如果只有一人承认，则承认者以宽大处如果只有一人承认，则承认者以宽大处理，当场释放，而不承认者判刑理，当场释放，而不承认者判刑9年。因年。因此，对两个囚犯来说，面临着一个此，对两个囚犯来说，面临着一个“承承认认”和和“不承认不承认”之间两个策略的选择之间两个策略的选择的难题。的难题。14-2 14-2 矩阵对策的解法矩阵对策的解法一、一、 m*n m*n 矩阵对策的线性规划法矩阵对策的线性规划法 求解矩阵对策可以等价地转化成求解矩阵对策可以等价地转化成求解互为对偶的线性规划问题求解互为对偶的线性规划问题对给定的赢得矩阵对给定的赢得矩阵 A=(aij)mn转化成两个互为对偶的线性规划问题转化成两个互为对偶的线性规划问题 ( LP) min pi pi aij 1 i pi 0(i=1,2,. m)( DLP) max qj qj aij 1 j qj 0(j=1,2,. n) 且且 pi = qj = 1/ V 例例14-9 对给定的赢得矩阵对给定的赢得矩阵AA，=（ aij +2） 0 1 -1 2 3 1A= -1 0 1 A，= 1 2 3 1 -1 0 3 1 2 （ LP） min （p1 +p2+p3 ） 2p1 +p2+3p3 1 3p1 +2p2+p3 1 p1 +3p2+2p3 1 pi 0 (i=1,2 , 3) ( DLP) max （q1 +q2 +q3 ） 2q1 + 3q2 + q3 1 q1 + 2q2 +3q3 1 3q1 + q2 +2q3 1 qj 0 (j=1,2,3) 且且 pi = qj = 1/ V 利用单纯形法可求出：利用单纯形法可求出：P*=（1/6，1/6，1/6）Q*=（1/6，1/6，1/6）p1 +p2+p3=1/6+1/6+1/6=1/2=1/ V V=2 原问题的解：原问题的解：X*= V P*=（1/3，1/3，1/3） Y*= V Q*=（1/3，1/3，1/3）对策值对策值V G*= V-2=0例例14-10 对给定的赢得矩阵对给定的赢得矩阵A 7 2 9A= 2 9 0 9 0 11（ LP） min （p1 +p2+p3 ） 7p1 +2p2+9p3 1 2p1 +9p2 1 9p1 +11p3 1 pi 0 (i=1,2 , 3)( DLP) max （q1 +q2 +q3 ） 7q1 + 2q2 +9q3 1 2q1 + 9q2 1 9q1 +11q3 1 qj 0 (j=1,2,3) 且且 pi = qj = 1/ V利用单纯形法可求出：利用单纯形法可求出：P*=（1/20，1/10，1/20）Q*=（1/20，1/10，1/20）p1 +p2+p3=1/20+1/10+1/20=1/5=1/ V V=5 原问题的解：原问题的解：X*= V P*=（1/4，1/2，1/4） Y*= V Q*=（1/4，1/2，1/4）对策值对策值V G*= 5二、二、 2*2 2*2 矩阵对策的公式解法矩阵对策的公式解法定理定理14-5：对给定的矩阵对策对给定的矩阵对策 G = S1，S2；AA=(aij)2*2。如果如果A无鞍点，则局中人无鞍点，则局中人I的最优混合策略的最优混合策略X*=（x1*，x2*），），局中人局中人II的最优混合策略的最优混合策略Y*=（y1*，y2*）和对策值和对策值VG*由下列公式给出：由下列公式给出：令令 D= a11 +a22 - a12 - a21 x1* =（a22-a21）/ Dx2* =（a11-a12 ）/ D y1* =（a22-a12 ）/ Dy2* =（a11-a21 ）/ D VG* = （a11 a22-a12a21 ）/ D例例14-11 在在W城的冰箱市场上，以城的冰箱市场上，以往的市场份额由本市生产的往的市场份额由本市生产的A牌冰箱牌冰箱占有绝大部分。本年初，一个全国占有绝大部分。本年初，一个全国知名的知名的B牌冰箱进入牌冰箱进入W城的市场。在城的市场。在这场竞争中假设双方考虑可采用的这场竞争中假设双方考虑可采用的市场策略均为三种：广告、降价、市场策略均为三种：广告、降价、完善售后服务，且双方用于营销的完善售后服务，且双方用于营销的资金相同。根据市场预测，资金相同。根据市场预测，A的市场的市场占有率为：占有率为： B 广告广告 1 降价降价 2 售后服务售后服务 3 广告广告 1 0.60 0.62 0.65 A = 降价降价 2 0.75 0.70 0.72 售后服务售后服务 3 0.73 0.76 0.78试确定双方的最优策略。试确定双方的最优策略。 解：解：由于无鞍点，故在纯策略意义下无由于无鞍点，故在纯策略意义下无解。但是对于解。但是对于A来说，来说， 1行元素小于行元素小于 2行元素，即行元素，即 2优超优超 1，删除删除 1行行 广告广告 1 降价降价 2 售后服务售后服务 3 降价降价 2 0.75 0.70 0.72 售后服务售后服务 3 0.73 0.76 0.78 同样道理。对于同样道理。对于B来说，来说， 2列元素小于列元素小于 3列元素，即列元素，即 2优超优超 3 ，删除删除 3列列 广告广告 1 降价降价 2 降价降价 2 0.75 0.70 售后服务售后服务 3 0.73 0.76利用公式可得：利用公式可得：X*= （0，3/8，5/8）（）（A） Y*= （3/4，1/4，0）（）（B）对策值对策值V G*= 0 . 7425 A的最优策略是将促销资金的的最优策略是将促销资金的3/8用于降低售价，用于降低售价，5/8用于售后服务。用于售后服务。 B的最优策略是将促销资金的的最优策略是将促销资金的3/4用于广告，用于广告，1/4用于降低售价。用于降低售价。 这样做的结果是这样做的结果是A的市场占有率的市场占有率为为 0 . 7425（74 .25%）习题十四习题十四P417P41714.314.314.514.5