数学建模-对策论

1、GAME THEORY对 策 论第11章9/27/2022111 矩阵对策6.1 引言6.2 对策论的基本概念6.3 矩阵对策的概念及模型6.4 矩阵对策的纯策略解（鞍点解）6.5 矩阵对策的混合策略解（mixed strategic solution）6.6 矩阵对策的解法9/27/20222Operations Research6.1.1 何谓对策论（Game Theory）？6.1.2 对策的例子6.1.3 对策论的诞生与发展简况6.1 引 言9/27/20223Operations Research6.1.1 何谓对策论(Game Theory)？ 定义：对策论亦称竞赛论或博弈论，是研

2、究具有斗争或竞争性质现象的数学理论和方法。 囚徒困境局中人2坦白不坦白局中人1坦白(-6,-6)(-1,-8)不坦白(-8,-1)(-2,-2)9/27/20224Operations Research齐王赛马决斗问题：神雕侠侣中武林盟主大会6.1.2 对策的例子朱子柳霍 都郭 靖达尔巴郝大通金轮法王9/27/20225Operations Research6.1.3 对策论的诞生与发展简况早期工作1912年E.Zermelo 关于集合论在象棋对策中的应用 1921年E.Borel 引入最优策略 1928年J.V.Neumann证明了一些猜想9/27/20226Operations Resea

3、rch6.1.3 对策论的诞生与发展简况产生标志 1944年J.V.Neumann和O.Morgenstern”对策论与经济行为” （Theory of Games and Economic Behavior）发展成熟 Nash均衡、经济博奕论、信息不对称对策和广义对策9/27/20227Operations Research6.2 对策论的基本概念6.2.1 局中人（Player）6.2.2 策略（Strategy）6.2.3 支付与支付函数9/27/20228Operations Research6.2.1 局中人（Player）1、局中人：在一场竞争或斗争中的决策者称为该局对策的局中人

4、通常，一局对策具有两个或两个以上-决策者，一般用I表示局中人集合：9/27/20229Operations Research6.2.1 局中人（Player）2、对策分类：依据局中人的数量，可将对策分为有限对策无限对策(n2)对策无限零和对策无限非零和对策有限零和对策有限非零和对策9/27/202210Operations Research6.2.2 策略（Strategy）1、 策略与策略集局中人指导自己自始至终如何行动的一个方案，称为策略(Strategy)由所有策略构成的集合，称为策略集(StrategySet)9/27/202211Operations Research6.2.2 策略

5、（Strategy）2、策略集的元素：对于局中人i,iI，都有自己的策略集Si,通常每一局中人的策略集中至少应包括两个策略对于例4的包、剪、锤游戏。假设有两个局中人I=甲，乙，甲的策略集为S甲=(包)、(剪)、(锤)=a1、a2、a3;乙的策略集为S乙=(包)、(剪)、(锤) =b1、b2、b3;9/27/202212Operations Research6.2.3 支付与支付函数1、局势：各局中人所选定的策略形成的策略组2、策略组 若si是第i个局中人的一个策略，则n个局中人的策略组 s=(s1,s2,sn) 就是一个局势。9/27/202213Operations Research6.2.

6、3 支付与支付函数例如，对于包、剪、锤游戏。假设有两个局中人I=甲，乙，甲的策略集为S甲=(包)、(剪)、(锤)=(a1)、(a2)、(a3);乙的策略集为S乙=(包)、(剪)、(锤) =(b1)、(b2)、(b3); 则甲的一个策略ai，和乙的一个策略bj就构成一个局势sij.9/27/202214Operations Research6.2.3 支付与支付函数3、赢得（支付）：当每个局中人所采取的策略确定后，他们就会得到相应的收益或损失，称为局中人的支付（Payoff）。 若甲的一个策略a3(锤)，乙的一个策略b2(剪)，则构成一个局势s32 。在局势s32下，甲的支付为：乙的支付9/27

7、/202215Operations Research6.2.3 支付与支付函数4、支付（赢得）函数：不同的策略会导致不同的支付，因此，支付是策略(准确的说应该是局势)的函数，称为支付函数(payoff function)。对于例4，两人的支付函数分别记为： 和例如，对于策略a3, b19/27/202216Operations Research6.2.3 支付与支付函数5、零和对策和非零和对策 根据各局中人支付的代数和是否为0，将对策分为零和对策和非零和对策(non-zero-sum games)。 若在任一局对策中，全体局中人支付的总和为0，则该对策称为零和对策，否则称为非零和对策(non-

8、zero-sum games)。 对于前例，显然为零和对策，因为9/27/202217Operations Research6.2.3 支付与支付函数6、对策分类 根据局中人的数目和支付函数代数和有限对策n人对策(n2)对策合作对策非合作对策9/27/202218Operations Research6.3 矩阵对策的概念及模型1、定义：两个人零和对策称为矩阵对策 例，“包、剪、锤”游戏中，甲、乙双方各有三种不同的策略，分别为：9/27/202219Operations Research6.3 矩阵对策的概念及模型甲的支付情况如下表 1 (包)2(剪)3(锤)1 (包)0-112 (剪)10-

9、13(锤)-110乙的策略甲的支付甲的策略表6.19/27/202220Operations Research6.3 矩阵对策的概念及模型齐王赛马 1234561 (上中下)31111-12 (上下中)1311-113(中上下)1-131114(中下上)-1113115(下中上)11-11316(下上中)111-113田忌策略齐王赢得齐王策略上中下上下中中上下中下上下中上下上中9/27/202221Operations Research6.3 矩阵对策的概念及模型表6.1中的数字用矩阵的形式表示A称为甲的支付矩阵。显然，乙的支付矩阵为-A。因此，该对策可记为： 9/27/202222Opera

10、tions Research6.3 矩阵对策的概念及模型2、矩阵对策的模型一般地，若局中人 ，的策略集分别为：为了与后面的概念区分开来，我们称i为的纯策略， j为的纯策略，对于纯策略i, j构成的策略偶(i, j)称为纯局势。 9/27/202223Operations Research6.3 矩阵对策的概念及模型若的支付矩阵为： ij表示局势(i,j)下，局中人的支付,则矩阵对策可记为G=S1,S2,A：即矩阵对策模型。 9/27/202224Operations Research6.4 矩阵对策的纯策略解6.4.1 矩阵对策的纯策略解例解过程6.4.2 矩阵对策的纯策略解理论基础6.4.3

11、 矩阵对策的纯策略解性质9/27/202225Operations Research例5 设二人零和对策 G=S1, S2, A，其中 6.4.1 矩阵对策的纯策略解例解过程而且局中的支付矩阵为： 两位局中人都想自己的支付最大化。9/27/202226Operations Research6.4.1 矩阵对策的纯策略解例解过程 这里我们认为局中人都是理智的，从矩阵A进行逻辑推理可知： 如果局中人采取3作策略，虽有可能获得最大支付18，但是,局中人分析到的这种心理，就会采取3策略，使不仅得不到最大值18，反而取得很坏的结果-8； 同样，局中人为了得到最大支付+12(即局中人的支付-12)，会采取

12、 2作为策略,但局中人也会猜到的这种心理,而采取 2作策略，这样局中人只能得到-3。9/27/202227Operations Research6.4.1 矩阵对策的纯策略解例解过程从以上的分析可以看出，局中人选取最优策略时应该考虑到也是十分理智与精明的，的策略是要以支付最少为目的，所以不能存在任何侥幸心理。局中人也应作同样的考虑。 对于局中人来说，应该是从最坏处着想向最好处努力。9/27/202228Operations Research6.4.1 矩阵对策的纯策略解例解过程对局中人来讲，各策略的最坏结果分别为：min-6,2,-7=-7 min5,3,6=3min18,0,-8=-8min

13、-2,-12,7=-12这些最坏的情况中，最好的结果是：max-7,3,-8,-12=39/27/202229Operations Research6.4.1 矩阵对策的纯策略解例解过程同样，对局中人而言，各策略的最坏的结果分别为：max-6,5,18,-2=18max2,3,0,-12=3max-7,6,-18,7=7在这些最坏的情况中，最好的结果（损失最小）是min18,3,7=39/27/202230Operations Research6.4.1 矩阵对策的纯策略解例解过程1231-62-7-7253633180-8-84-2-127-1218379/27/202231Operatio

14、ns Research6.4.1 矩阵对策的纯策略解例解过程课堂练习:求解对策 G=S1,S2,A已知：9/27/202232Operations Research定义1 对于矩阵对策G=S1,S2,A,如果存在纯局势 6.4.2 矩阵对策的纯策略解理论基础则称局势 为对策G在纯策略中的解。亦称其为G的鞍点(saddle point): (列中最大，行中最小)使得对任意j=1, ，n,及任意i=1, m有： 9/27/202233Operations Research6.4.2 矩阵对策的纯策略解理论基础 分别称为局中人，的最优纯策略。 称 为对策G的值(value)，记为9/27/20223

15、4Operations Research6.4.2 矩阵对策的纯策略解理论基础定理1 矩阵对策G=S1,S2,A存在最优纯策略的充分必要条件为：9/27/202235Operations Research6.4.2 矩阵对策的纯策略解理论基础求对G的解和值。例6 已知 G=S1,S2,A，其中, 9/27/202236Operations Research6.4.2 矩阵对策的纯策略解理论基础12341868662134-3-33967664-31103-3961066解：根据A可得9/27/202237Operations Research6.4.2 矩阵对策的纯策略解理论基础由于： 四个局

16、势均为G的鞍点，且 故知： 9/27/202238Operations Research6.4.3 矩阵对策的纯策略解性质从上例可知，对策的解可以是不唯一的，但对策的值是唯一的。对策解不唯一时，应满足下面两条性质：1. 无差别性：若 与 是矩阵对策G的两个解，则即对策值相等，它们在矩阵中的元素相同。9/27/202239Operations Research6.4.3 矩阵对策的纯策略解性质2. 可交换性：若 与 是矩阵对策G的两个解,则与 也是对策的解。 9/27/202240Operations Research6.4.3 矩阵对策的纯策略解性质是不是每一个矩阵对策都有纯策略解（鞍点）？1

17、2310-11-1210-1-13-110-1111答案是否定的。9/27/202241Operations Research6.5 矩阵对策的混合策略解6.5.1 混合策略与混合扩充（mixed strategic solution）6.5.2 解的基本定理9/27/202242Operations Research6.5.1 混合策略与混合扩充1213632544561、问题提出 9/27/202243Operations Research6.5.1 混合策略与混合扩充该对策问题表明不存在使对立双方达到平衡的局势，因此，局中人采取任何一种纯策略，都有一定的风险。所以，在这种情况下，局中人必

18、须隐瞒自己选取策略的意图。 9/27/202244Operations Research6.5.1 混合策略与混合扩充2、问题处理方案设计这时我们可以设想局中人随机地选取纯策略来进行对策。即在一局对策中，局中人以概率 来选取纯策略 ,其中的 满足 于是得到一个m维的概率向量 9/27/202245Operations Research6.5.1 混合策略与混合扩充同样对于局中人,有相应的一个n维的概率向量 满足 yj表示局中人选取纯策略j的概率。9/27/202246Operations Research6.5.1 混合策略与混合扩充3、混合策略概念引入定义:若给定一个矩阵对策G=S1,S2,

19、A ,其中则我们把纯策略集对应的概率向量： 与 分别称作局中人、的混合策略，(X,Y)称为一个混合局势。 9/27/202247Operations Research6.5.1 混合策略与混合扩充如果局中人选取的策略为 局中人选取 由于两局中人分别选取策略 的事件可以看成使相互独立4、混合策略的局中人支付 如果局中人选取的策略为 9/27/202248Operations Research6.5.1 混合策略与混合扩充就是局中人的支付值。 所以局势(i，j)出现的概率是xiyj。从而知局中人支付ij的概率是xiyj。于是，数学期望值： 9/27/202249Operations Researc

20、h6.5.1 混合策略与混合扩充令： 则称 为G的混合扩充。 5、混合扩充9/27/202250Operations Research6.5.1 混合策略与混合扩充定义2 如果存在 ,满足:对任意 及 均有： 则称 为G（在混合策略下的）解. 分别称为局中人、的最优(混合)策略. 称为对策G（在混合意义下的）值，记为 9/27/202251Operations Research6.5.1 混合策略与混合扩充例7 设 ,其中 求它的解及值。解：显然该问题无鞍点解。设局中人、 的混合策略分别为： X=(x1,x2),Y=(y1,y2).则9/27/202252Operations Research

21、6.5.1 混合策略与混合扩充则局中人支付的数学期望为：9/27/202253Operations Research6.5.1 混合策略与混合扩充可见:当 9/27/202254Operations Research6.5.1 混合策略与混合扩充显然 9/27/202255Operations Research6.5.1 混合策略与混合扩充由定义1知： 分别是局中人、的的最优策略，且 9/27/202256Operations Research6.5.2 解的基本定理定理2 (基本定理) 任意一个矩阵对策 其中 一定有解(在混合策略意义下),且如果G的值是V,则以下两组不等式的解是局中人,的最

22、优策略: 9/27/202257Operations Research6.5.2 解的基本定理（11-1）（11-2）9/27/202258Operations Research6.5.2 解的基本定理（1）若 则 （G的值） （2）若 则 （4）若 ,则 （3）若 ,则 可用例7验证定理3 若 是对策G(同前)的最优混合局势,则对某一个i或j来说：9/27/202259Operations Research6.5.2 解的基本定理y1y2yn12nx11a11a12a1nV1x22a21a22a2nV2 xmmam1am2amnVm V1V2VnVV9/27/202260Operations

23、 Research6.6 矩阵对策的解法6.6.1 图解法6.6.2 优势法6.6.3 简化计算法6.6.4 线性规划解法9/27/202261Operations Research6.6.1 图解法例8 已知： 其中 求矩阵对策的解和值。 9/27/202262Operations Research解: 设局中人 的混合策略为 (x,1-x)T,x0,1。对局中人而言，他的最少可能收入为局中人选取1，2所确定的两条直线(定理3知): 6.6.1 图解法V1=5x+20(1-x)=20-15xV2=35x+10(1-x)=25x+10 因为x1和x2一定大于0在x处的纵坐标中的最小者. 局中人

24、用“最大最小”原则选取自己的策略,即:9/27/202263Operations ResearchD点为极值点,D点坐标为： 即 的最优混合策略为： ED(1/4,16 )VV1=5x+20(1-x)=20-15xV2=35x+10(1-x)=25x+10 xF从上图可以看出： 就是折线EDF. 9/27/202264Operations Research6.6.1 图解法同理，对局中人而言有 V=5y+35(1-y)=35-30y V=20y+10(1-y)=10+10y最小最大点为: 即 的最优解为 ：对策值为： 9/27/202265Operations Research6.6.1 图解

25、法FG(5/8,16 )HYV=5y+35(1-y)=35-30yV=20y+10(1-y)=10+10y9/27/202266Operations Research6.6.1 图解法课堂练习p145-10.4-3：求解下列矩阵对策，已知赢得矩阵为：9/27/202267Operations Research6.6.1 图解法例9 已知： 其中 求对策的解和值。 解：显然无鞍点，作混合扩充： 9/27/202268Operations Research6.6.1 图解法对局中人而言，若选取 时，的最小可能收入为以下四条直线在x处纵坐标中的最小者 v=2x+4(1-x)=4-2x (1)v=3x

26、+(1-x)=2x+1 (2)v=x+6(1-x)=-5x+6 (3)v=5x (4)9/27/202269Operations Research6.6.1 图解法从图上可以看出 B点坐标即为所求的极值点. AB(2)(3)(1)(4)B点坐标为:即 的最优解为 9/27/202270Operations Research6.6.1 图解法同理可得： v=2y1+3y2+y3+5y4 (5) v=4y1+y2+6y3 (6)由上节的定理3求出的最优解 将 分别代入方程(1)(4)得：9/27/202271Operations Research6.6.1 图解法定理3的(4)定理3的(2)定理3

27、的(2)定理3的(4)9/27/202272Operations Research6.6.1 图解法代入(5)、(6)得： 解之得：故的最优策略为9/27/202273Operations Research6.6.2 优势法对于一般的矩阵对策 其中 定义3 若对固定的i、k有若对固定的j和l，有 则称优超，记为则称优超，记为9/27/202274Operations Research6.6.2 优势法(1) 定理4 设G中的某个 被其余的 之一优超, 由G可得 ，其中 于是有 (2) 中局中人的最优策略就是G中的最优策略；9/27/202275Operations Research6.6.2

28、优势法若 是在 中的最优解，则 为在G中的最优解. (3) 9/27/202276Operations Research6.6.2 优势法例10 已知某矩阵对策G的支付矩阵为： 求解这个矩阵对策。 9/27/202277Operations Research6.6.2 优势法解：显然无鞍点，由于A的阶数为 图解法失效。由定义可知 由定理1可将该问题简化为:9/27/202278Operations Research6.6.2 优势法可用图解法求得最优解和值分别为： 由又可看出：从又可看出：，因此得： 9/27/202279Operations Research6.6.2 优势法即可得到对策G的解为： 值为V=5。9/27/202280Operations Research6.6.3 简化计算法定理5 若矩阵对策 其中d为常数，则G1与G2有相同的解，且对策的值相差一个常数d，即： 9/27/202281Operations Research6.6.3 简化计算法推论1 若矩阵对策 其中k0为常数，则G1与G2有相同的解,且9/27/202282Operations Research6.6.3 简化计算法例11 已知某矩阵对策G的支付矩阵如下： 解：由推论1可取 得同解矩阵：