教案对策论基础

教案对策论基础第六章对策论基础概论矩阵对策的基本理论第一节概论对策与决策决策是由单方做出的对策是由利害冲突的多方做出的1944年，VonNeumann&D.Morgenstern合作出版《对策论与经济行为》，标志着对策论的诞生博弈现象下棋与打牌体育比赛战争市场进入谈判生产管理决策竞拍几个典型的博弈案例锤子、剪刀、布的儿童游戏囚徒困境智猪博弈强盗分金币一、基本概念与名词局中人策略与策略集局势赢得函数零和对策矩阵对策：二人有限零和对策在一个对策行为（或一局对策）中，有权决定自己行动方案的对策参加者，称为局中人（Player）通常用I表示局中人的集合，如果有n个局中人，则I＝｛1,2,3,…,n｝在一个对策中，至少要有两个局中人局中人，不一定是单个人，也可以是利益完全一致的一个集体只有两个局中人的对策，称为两人对策局中人策略和策略集一局对策中，可供局中人选择的一个实际可行的完整的行动方案，称为一个策略，它的集合称为策略集S。在儿童游戏中，锤子、剪刀、布就分别是一个策略，｛锤子、剪刀、布｝就是一个策略集。如果每个局中人只有有限个策略，则相应的对策称为有限对策，否则称为无限对策局势在一局对策中，每个局中人采用的策略所形成的策略组称为一个局势，用s表示。赢得函数（支付、支付函数，Payoff）当局势出现后，对策的结果也就确定。即：对任一局势，局中人i可以得到一个赢得，显然，是局势s的函数，称之为第i个局中人的赢得函数零和对策如果各局中人的赢得函数之和为零，则称之为零和对策，反之为非零和对策矩阵对策有限二人零和对策三个特征：局中人只有2个；每个局中人只有有限个可选择的策略；在任一局势中，两个局中人的得失之和为零二、对策分类（一）按对策双方是否存在有约束力的协议来分：合作对策非合作对策（二）按局中人数分类：二人对策多人对策（三）按策略数分类：

有限策略对策无限策略对策

二人有限零和对策是讨论的重点。第二节矩阵对策的基本理论矩阵对策的数学模型最优纯策略混合策略与混合扩充一、矩阵对策的数学模型以齐王赛马为例说明：齐王赛马—二人有限零和对策局中人—齐王和田忌策略—上中下三种等级的马的组合，比三次，有六组策略：(上，中，下)、(中，上，下)、(上，下，中)、(中，下，上)、(下，上，中)、(下，中，上)，对齐王，这六组策略用表示，对田忌，则用表示。支付函数—赢了得一千金，输了付一千金。齐王赛马赢得函数31111-11311-111-13111-11131111-1131111-113

(上中下)

(上下中)齐

(中上下)王(中下上)(下中上)(下上中)田忌对策的数学表示二人矩阵对策用下列式子表示其中I、II表示两个局中人，S1、S2分别表示局中人I、II的策略集，A则表示赢得矩阵：齐王的赢得矩阵(支付矩阵)A

A=田忌的赢得矩阵是什么？31111-11311-111-13111-11131111-1131111-113锤头、剪刀、布游戏设游戏双方为甲、乙，则甲的赢得乙甲的赢得甲包剪锤包0-11剪10-1锤-110二、最优纯策略现有一矩阵对策其中纯策略与纯局势如果局中人I，II的策略集分别为称的纯策略，的纯策略，对于纯策略构成的策略偶()称为纯局势矩阵对策的纯策略解（鞍点解）对于局中人I来说，各策略中最坏的结果分别为｛-8,2,-10,-3｝在这些最坏的情况中，最好的结果是

max{-8,2,-10,-3}=2即：只要局中人I采用，无论II采用何种策略，I都可以保证赢得不少于2在这种情况下，II应采用策略,否则输得更多最优纯策略的表述若满足则上述条件规定的局势叫做最优纯局势，也是矩阵对策的最优解，是局中人I、II的最优纯策略,即鞍点定理：矩阵对策G={S1,S2,A}有纯策略解的充要条件是存在一个纯局势使得例子的最优纯策略在上述定理中因此符合条件的即为最优纯策略。上述例子的最优纯策略为：最优局势且G=2为局中人I的赢得值。再看一例已知求解此矩阵对策对策的解可能不是唯一的,但是对策的值是唯一的,对策的解不唯一时,满足以下两条性质:无差别性:若是矩阵对策G的两个解,则可交换性:若是矩阵对策的两个解,则也是对策的解一个应用题某单位要决定冬季取暖用煤的贮量.已知在正常的冬季气温条件下要消耗15吨煤,在较暖和较冷的气温条件下要消耗10吨和20吨.由于煤价会随着气温情况有所波动,在较暖正常较冷的气温情况下,每吨煤价分别为10元,15元和20元.已知目前在秋季,煤价为每吨10元,在缺乏准确天气预报的情况下,问贮煤多少才能使支出最少.思路单位决策者为局中人I,大自然为局中人II局中人I的策略有三个:秋天买10吨,15吨,20吨局中人II的策略也有三个:较暖,正常,较冷写出局中人I的赢得矩阵A又一例:无最优纯策略(无鞍点解)已知求解此矩阵对策三、混合策略与混合扩充基本概念：当时不存在最优纯策略，此时需要应用混合策略的方法确定参加对策的纯策略。例如分析上述例子因为所以此时假设局中人I以概率x选取策略1，以概率(1-x)选取策略2；局中人II以概率y选取策略1，以概率(1-y)选取策略2。则对于局中人I来说，赢得的期望值为E(x,y)，它等于例子引出混合策略赢得期望值在x=1/2，y=1/4时，赢得函数取得最优值5/2。这实际上是对策双方都满意的结果。我们把纯策略对应的概率向量叫做混合策略，最优解则是最优混合策略。本例中，最优混合策略是(1/2,1/2)和(1/4,3/4)。混合策略的定义令纯策略集对应的概率向量是它们满足混合策略的集合将叫做G的混合扩充。最优混合策略的定义若令并有则称(X*,Y*)为最优混合局势，或叫做G在混合策略下的解，V叫做对策G的值。X*、Y*分别是局中人I、II的最优混合策略。混合对策问题的解法任意一个矩阵对策一定有解（在混合策略意义下）.且如果G的值是V，则局中人I和II的最优策略是下列两组不等式的解：关于混合对策问题的解，我们有如下定理：混合对策最优解定理如果(X*,Y*)是对策G的最优混合局势，则对于某个i或j来说，有：矩阵对策的解法(I):图解法例1已知求此矩阵对策的解和值解：作混合扩充对局中人I而言，若局中人II选取则I的赢得的期望值分别为作图如下011020535DEFxV局中人I用“最大最小”原则选取自己的策略，即从图中可知,D点满足上述要求，求得D的坐标为：D(1/4,67/4)，即x=1/4,V=67/4所以，局中人I的最优混合策略为同理可求出局中人II的最优混合策略图解法例2已知求此矩阵对策的解和值解：作混合扩充对局中人I而言，若局中人II选取则I的赢得的期望值分别为作图如下(示意)01局中人I用“最大最小”原则选取自己的策略，即从图中可知,V2,V3联立即可求出B点坐标为(5/7,17/7)，此即为局中人I的最优解同理可得，对于局中人II显然，已经无法作出图象该怎么办？由混合策略最优解定理将x=5/7，分别代入方程V1-V4混合对策问题的解法(II)优势法定义：对于一矩阵对策,若对一切j均有即矩阵A的第i*行元素均不小于第k*行的对应元素，则称局中人I的纯策略同理，若对于一切i均有则称局中人II的纯策略优势法:例对于G={S1,S2,A}第一步简化赢得矩阵划去普遍较小的行，例如第1、2行，得划去普遍较大的列，例如第3、4、5三列，结果如上。进一步化简上述结果的第一行比第三行普遍更优，因此再划去第三行，得若混合策略均不为零，由上述定理知混合对策问题数学模型的不等式应为等式。因此有第二步用方程组求解最优混合策略满足如下方程组解得矩阵混合对策问题的解混合对策解法(III)简化计算法定理：若矩阵对策其中d为常数，则G1与G2具有相同的解，且对策的值相差一个常数d，即推论：若矩阵对策其中k>0为常数，则G1与G2具有相同的解，且对策的值有以下关系：简化计算的例：已知求此矩阵对策的解和值解：由于数字较大，不便于用图解法由简化计算法的推论知，取可得同解矩阵对策为再由相关定理，取d=-2，进一步简化为解(续)易求解A2所对应的矩阵对策的解为因此原矩阵对策G的解和值分别为练习：已知矩阵对策双方的最优策略为对策值V＝59/14，求以下矩阵对策解和值混合对策解法(IV)线性规划解法以上三种方法只能解决一些特殊的矩阵对策，对于一般的矩阵对策问题，则需要用线性规划的方法求解混合对策解法(IV)线性规划解法对于任一值大于零矩阵对策，总可以转化为求解一对互为对偶的线性规划问题(I)(II)。例：矩阵对策G中，局中人I的赢得矩阵为求此矩阵对策G的解和值解：显然无鞍点解。进行混合扩充，局中人I和II的混合策略分别为对策的值为V，则建立相应的线性规划为由线性规划法，可求得因为所以练习1：用线性规划方法求解矩阵对策练习2：用线性规划方法求解矩阵对策补充一个定理定理：若矩阵对策无鞍点解，并且其中则矩阵对策G的值必大于