数学建模-对策论省名师优质课赛课获奖课件市赛课一等奖课件

GAMETHEORY

对策论第11章第1页9/12/2023111矩阵对策6.1引言6.2对策论基本概念6.3矩阵对策概念及模型6.4矩阵对策纯策略解（鞍点解）6.5矩阵对策混合策略解（mixedstrategicsolution）6.6矩阵对策解法第2页9/12/20232OperationsResearch6.1.1何谓对策论（GameTheory）？6.1.2对策例子6.1.3对策论诞生与发展简况6.1引言第3页9/12/20233OperationsResearch6.1.1何谓对策论(GameTheory)？定义：对策论亦称竞赛论或博弈论，是研究含有斗争或竞争性质现象数学理论和方法。囚徒困境局中人2坦白不坦白局中人1坦白(-6,-6)(-1,-8)不坦白(-8,-1)(-2,-2)第4页9/12/20234OperationsResearch齐王赛马决斗问题：神雕侠侣中武林盟主大会6.1.2对策例子朱子柳霍都郭靖达尔巴郝大通金轮法王第5页9/12/20235OperationsResearch6.1.3对策论诞生与发展简况早期工作1912年E.Zermelo‘关于集合论在象棋对策中应用’1921年E.Borel引入最优策略1928年J.V.Neumann证实了一些猜测第6页9/12/20236OperationsResearch6.1.3对策论诞生与发展简况产生标志

1944年J.V.Neumann和O.Morgenstern”对策论与经济行为”（TheoryofGamesandEconomicBehavior）发展成熟

Nash均衡、经济博奕论、信息不对称对策和广义对策第7页9/12/20237OperationsResearch6.2对策论基本概念6.2.1局中人（Player）6.2.2策略（Strategy）6.2.3支付与支付函数第8页9/12/20238OperationsResearch6.2.1局中人（Player）1、局中人：在一场竞争或斗争中决议者称为该局对策局中人通常，一局对策含有两个或两个以上---决议者，普通用I表示局中人集合：第9页9/12/20239OperationsResearch6.2.1局中人（Player）2、对策分类：依据局中人数量，可将对策分为有限对策无限对策(n>2)对策无限零和对策无限非零和对策有限零和对策有限非零和对策第10页9/12/202310OperationsResearch6.2.2策略（Strategy）1、策略与策略集局中人指导自己自始至终怎样行动一个方案，称为策略(Strategy)由全部策略组成集合，称为策略集(StrategySet)第11页9/12/202311OperationsResearch6.2.2策略（Strategy）2、策略集元素：对于局中人i,i∈I，都有自己策略集Si,通常每一局中人策略集中最少应包含两个策略对于例4包、剪、锤游戏。假设有两个局中人I={甲，乙}，甲策略集为S甲={(包)、(剪)、(锤)}={a1、a2、a3};乙策略集为S乙={(包)、(剪)、(锤)}={b1、b2、b3};第12页9/12/202312OperationsResearch6.2.3支付与支付函数1、局势：各局中人所选定策略形成策略组2、策略组若si是第i个局中人一个策略，则n个局中人策略组s=(s1,s2,…,sn)就是一个局势。第13页9/12/202313OperationsResearch6.2.3支付与支付函数比如，对于包、剪、锤游戏。假设有两个局中人I={甲，乙}，甲策略集为S甲={(包)、(剪)、(锤)}={(a1)、(a2)、(a3)};乙策略集为S乙={(包)、(剪)、(锤)}={(b1)、(b2)、(b3)};则甲一个策略ai，和乙一个策略bj就组成一个局势sij.第14页9/12/202314OperationsResearch6.2.3支付与支付函数3、赢得（支付）：当每个局中人所采取策略确定后，他们就会得到对应收益或损失，称为局中人支付（Payoff）。若甲一个策略a3(锤)，乙一个策略b2(剪)，则组成一个局势s32。在局势s32下，甲支付为：乙支付第15页9/12/202315OperationsResearch6.2.3支付与支付函数4、支付（赢得）函数：不一样策略会造成不一样支付，所以，支付是策略(准确说应该是局势)函数，称为支付函数(payofffunction)。对于例4，两人支付函数分别记为：和比如，对于策略a3,b1第16页9/12/202316OperationsResearch6.2.3支付与支付函数5、零和对策和非零和对策

依据各局中人支付代数和是否为0，将对策分为零和对策和非零和对策(non-zero-sumgames)。若在任一局对策中，全体局中人支付总和为0，则该对策称为零和对策，不然称为非零和对策(non-zero-sumgames)。对于前例，显然为零和对策，因为第17页9/12/202317OperationsResearch6.2.3支付与支付函数6、对策分类依据局中人数目和支付函数代数和有限对策n人对策(n>2)对策合作对策非合作对策第18页9/12/202318OperationsResearch6.3矩阵对策概念及模型1、定义：两个人零和对策称为矩阵对策例，“包、剪、锤”游戏中，甲、乙双方各有三种不一样策略，分别为：第19页9/12/202319OperationsResearch6.3矩阵对策概念及模型甲支付情况以下表β1(包)β2(剪)β3(锤)α1(包)0-11α2(剪)10-1α3(锤)-110乙策略甲支付甲策略表6.1第20页9/12/202320OperationsResearch6.3矩阵对策概念及模型齐王赛马β1β2β3β4β5β6α1(上中下)31111-1α2(上下中)1311-11α3(中上下)1-13111α4(中下上)-111311α5(下中上)11-1131α6(下上中)111-113田忌策略齐王赢得齐王策略上中下上下中中上下中下上下中上下上中第21页9/12/202321OperationsResearch6.3矩阵对策概念及模型表6.1中数字用矩阵形式表示A称为甲支付矩阵。显然，乙支付矩阵为-A。所以，该对策可记为：第22页9/12/202322OperationsResearch6.3矩阵对策概念及模型2、矩阵对策模型普通地，若局中人Ⅰ，Ⅱ策略集分别为：为了与后面概念区分开来，我们称αi为Ⅰ纯策略，βj为Ⅱ纯策略，对于纯策略αi,βj组成策略偶(αi,βj)称为纯局势。

第23页9/12/202323OperationsResearch6.3矩阵对策概念及模型若Ⅰ支付矩阵为：αij表示局势(αi,βj)下，局中人Ⅰ支付,则矩阵对策可记为G={S1,S2,A}：即矩阵对策模型。第24页9/12/202324OperationsResearch6.4矩阵对策纯策略解6.4.1矩阵对策纯策略解例解过程6.4.2矩阵对策纯策略解理论基础6.4.3矩阵对策纯策略解性质第25页9/12/202325OperationsResearch例5设二人零和对策G={S1,S2,A}，，其中6.4.1矩阵对策纯策略解例解过程而且局中Ⅰ支付矩阵为：两位局中人都想自己支付最大化。第26页9/12/202326OperationsResearch6.4.1矩阵对策纯策略解例解过程这里我们认为局中人都是理智，从矩阵A进行逻辑推理可知：假如局中人Ⅰ采取α3作策略，虽有可能取得最大支付18，不过,局中人Ⅱ分析到Ⅰ这种心理，就会采取β3策略，使Ⅰ不但得不到最大值18，反而取得很坏结果-8；一样，局中人Ⅱ为了得到最大支付+12(即局中人Ⅰ支付-12)，会采取β2作为策略,但局中人Ⅰ也会猜到Ⅱ这种心理,而采取α2作策略，这么局中人Ⅱ只能得到-3。第27页9/12/202327OperationsResearch6.4.1矩阵对策纯策略解例解过程从以上分析能够看出，局中人Ⅰ选取最优策略时应该考虑到Ⅱ也是十分理智与精明，Ⅱ策略是要以Ⅰ支付最少为目标，所以不能存在任何侥幸心理。局中人Ⅱ也应作一样考虑。

对于局中人来说，应该是从最坏处着想向最好处努力。第28页9/12/202328OperationsResearch6.4.1矩阵对策纯策略解例解过程对局中人Ⅰ来讲，各策略最坏结果分别为： min{-6,2,-7}=-7 min{5,3,6}=3 min{18,0,-8}=-8 min{-2,-12,7}=-12这些最坏情况中，最好结果是： max{-7,3,-8,-12}=3第29页9/12/202329OperationsResearch6.4.1矩阵对策纯策略解例解过程一样，对局中人Ⅱ而言，各策略最坏结果分别为： max{-6,5,18,-2}=18 max{2,3,0,-12}=3 max{-7,6,-18,7}=7在这些最坏情况中，最好结果（损失最小）是 min{18,3,7}=3第30页9/12/202330OperationsResearch6.4.1矩阵对策纯策略解例解过程β1β2β3α1-62-7-7α25363α3180-8-8α4-2-127-121837第31页9/12/202331OperationsResearch6.4.1矩阵对策纯策略解例解过程课堂练习:求解对策 G=﹛S1,S2,A﹜已知：第32页9/12/202332OperationsResearch定义1对于矩阵对策G=﹛S1,S2,A﹜,假如存在纯局势6.4.2矩阵对策纯策略解理论基础则称局势为对策G在纯策略中解。亦称其为G鞍点(saddlepoint):(列中最大，行中最小)使得对任意j=1,…，n,及任意i=1,…m有：第33页9/12/202333OperationsResearch6.4.2矩阵对策纯策略解理论基础

分别称为局中人Ⅰ，Ⅱ最优纯策略。称为对策G值(value)，记为第34页9/12/202334OperationsResearch6.4.2矩阵对策纯策略解理论基础定理1矩阵对策G={S1,S2,A}存在最优纯策略充分必要条件为：第35页9/12/202335OperationsResearch6.4.2矩阵对策纯策略解理论基础求对G解和值。例6已知G={S1,S2,A}，其中,第36页9/12/202336OperationsResearch6.4.2矩阵对策纯策略解理论基础β1β2β3β4α186866α2134-3-3α396766α4-31103-3961066解：依据A可得第37页9/12/202337OperationsResearch6.4.2矩阵对策纯策略解理论基础因为：四个局势均为G鞍点，且故知：第38页9/12/202338OperationsResearch6.4.3矩阵对策纯策略解性质从上例可知，对策解能够是不唯一，但对策值是唯一。对策解不唯一时，应满足下面两条性质：1.无差异性：若与

是矩阵对策G两个解，则即对策值相等，它们在矩阵中元素相同。第39页9/12/202339OperationsResearch6.4.3矩阵对策纯策略解性质2.可交换性：若与是矩阵对策G两个解,则与也是对策解。第40页9/12/202340OperationsResearch6.4.3矩阵对策纯策略解性质是不是每一个矩阵对策都有纯策略解（鞍点）？β1β2β3α10-11-1α210-1-1α3-110-1111答案是否定。第41页9/12/202341OperationsResearch6.5矩阵对策混合策略解6.5.1混合策略与混合扩充（mixedstrategicsolution）6.5.2解基本定理第42页9/12/202342OperationsResearch6.5.1混合策略与混合扩充β1β2α1363α2544561、问题提出第43页9/12/202343OperationsResearch6.5.1混合策略与混合扩充该对策问题表明不存在使对立双方到达平衡局势，所以，局中人采取任何一个纯策略，都有一定风险。所以，在这种情况下，局中人必须隐瞒自己选取策略意图。第44页9/12/202344OperationsResearch6.5.1混合策略与混合扩充2、问题处理方案设计这时我们能够构想局中人随机地选取纯策略来进行对策。即在一局对策中，局中人Ⅰ以概率

来选取纯策略,其中满足

于是得到一个m维概率向量第45页9/12/202345OperationsResearch6.5.1混合策略与混合扩充一样对于局中人Ⅱ,有对应一个n维概率向量满足yj表示局中人Ⅱ选取纯策略βj概率。第46页9/12/202346OperationsResearch6.5.1混合策略与混合扩充3、混合策略概念引入定义:若给定一个矩阵对策G={S1,S2,A},其中则我们把纯策略集对应概率向量：与分别称作局中人Ⅰ、Ⅱ混合策略，(X,Y)称为一个混合局势。第47页9/12/202347OperationsResearch6.5.1混合策略与混合扩充假如局中人Ⅰ选取策略为

局中人Ⅱ选取

因为两局中人分别选取策略

事件能够看成使相互独立4、混合策略局中人支付

假如局中人Ⅰ选取策略为第48页9/12/202348OperationsResearch6.5.1混合策略与混合扩充就是局中人Ⅰ支付值。所以局势(αi，βj)出现概率是xiyj。从而知局中人Ⅰ支付αij概率是xiyj。于是，数学期望值：第49页9/12/202349OperationsResearch6.5.1混合策略与混合扩充令：则称为G混合扩充。5、混合扩充第50页9/12/202350OperationsResearch6.5.1混合策略与混合扩充定义2假如存在,满足:对任意及都有：则称为G（在混合策略下）解.

分别称为局中人Ⅰ、Ⅱ最优(混合)策略.称为对策G（在混合意义下）值，记为第51页9/12/202351OperationsResearch6.5.1混合策略与混合扩充例7设

,其中求它解及值。解：显然该问题无鞍点解。设局中人Ⅰ、Ⅱ混合策略分别为：X=(x1,x2),Y=(y1,y2).则第52页9/12/202352OperationsResearch6.5.1混合策略与混合扩充则局中人Ⅰ支付数学期望为：第53页9/12/202353OperationsResearch6.5.1混合策略与混合扩充可见:当第54页9/12/202354OperationsResearch6.5.1混合策略与混合扩充显然第55页9/12/202355OperationsResearch6.5.1混合策略与混合扩充由定义1知：分别是局中人Ⅰ、Ⅱ最优策略，且第56页9/12/202356OperationsResearch6.5.2解基本定理定理2(基本定理)任意一个矩阵对策其中一定有解(在混合策略意义下),且假如G值是V,则以下两组不等式解是局中人Ⅰ,Ⅱ最优策略:第57页9/12/202357OperationsResearch6.5.2解基本定理（11-1）（11-2）第58页9/12/202358OperationsResearch6.5.2解基本定理（1）若则（G值）（2）若则（4）若,则（3）若,则可用例7验证定理3

若是对策G(同前)最优混合局势,则对某一个i或j来说：第59页9/12/202359OperationsResearch6.5.2解基本定理y1y2…ynβ1β2…βnx1α1a11a12…a1nV1’x2α2a21a22…a2nV2’…………………xmαmam1am2…amnVm’V1V2…Vn≤V≥V第60页9/12/202360OperationsResearch6.6矩阵对策解法6.6.1图解法6.6.2优势法6.6.3简化计算法6.6.4线性规划解法第61页9/12/202361OperationsResearch6.6.1图解法例8已知：其中求矩阵对策解和值。第62页9/12/202362OperationsResearch解:设局中人Ⅰ混合策略为(x,1-x)T,x∈[0,1]。对局中人Ⅰ而言，他最少可能收入为局中人Ⅱ选取β1，β2所确定两条直线(定理3知):6.6.1图解法V1=5x+20(1-x)=20-15xV2=35x+10(1-x)=25x+10因为x1和x2一定大于0在x处纵坐标中最小者.局中人Ⅰ用“最大最小”标准选取自己策略,即:第63页9/12/202363OperationsResearchD点为极值点,D点坐标为：

即Ⅰ最优混合策略为：

ED(1/4,16¼)VV1=5x+20(1-x)=20-15xV2=35x+10(1-x)=25x+10

xF从上图能够看出：就是折线EDF.第64页9/12/202364OperationsResearch6.6.1图解法同理，对局中人Ⅱ而言有V=5y+35(1-y)=35-30yV=20y+10(1-y)=10+10y最小最大点为:即Ⅱ最优解为：对策值为：第65页9/12/202365OperationsResearch6.6.1图解法FG(5/8,16¼)HYV=5y+35(1-y)=35-30yV=20y+10(1-y)=10+10y第66页9/12/202366OperationsResearch6.6.1图解法课堂练习p145-10.4-3：求解以下矩阵对策，已知赢得矩阵为：第67页9/12/202367OperationsResearch6.6.1图解法例9已知：其中求对策解和值。解：显然无鞍点，作混合扩充：第68页9/12/202368OperationsResearch6.6.1图解法对局中人Ⅰ而言，若Ⅱ选取时，Ⅰ最小可能收入为以下四条直线在x处纵坐标中最小者v=2x+4(1-x)=4-2x (1)v=3x+(1-x)=2x+1 (2)v=x+6(1-x)=-5x+6 (3)v=5x (4)第69页9/12/202369OperationsResearch6.6.1图解法从图上能够看出B点坐标即为所求极值点.AB(2)(3)(1)(4)B点坐标为:即Ⅰ最优解为第70页9/12/202370OperationsResearch6.6.1图解法同理可得： v=2y1+3y2+y3+5y4 (5) v=4y1+y2+6y3 (6) 由上节定理3求出Ⅱ最优解将分别代入方程(1)～(4)得：第71页9/12/202371OperationsResearch6.6.1图解法定理3(4)定理3(2)定理3(2)定理3(4)第72页9/12/202372OperationsResearch6.6.1图解法代入(5)、(6)得：解之得：故Ⅱ最优策略为第73页9/12/202373OperationsResearch6.6.2优势法对于普通矩阵对策其中定义3若对固定i、k有若对固定j和l，有则称优超，记为则称优超，记为第74页9/12/202374OperationsResearch6.6.2优势法(1)定理4

设G中某个被其余之一优超,由G可得，其中于是有(2)中局中人Ⅱ最优策略就是G中Ⅱ最优策略；第75页9/12/202375OperationsResearch6.6.2优势法若是Ⅰ在中最优解，则为Ⅰ在G中最优解.(3)第76页9/12/202376OperationsResearch6.6.2优势法例10已知某矩阵对策G支付矩阵为：求解这个矩阵对策。第77页9/12/202377OperationsResearch6.6.2优势法解：显然无鞍点，因为A阶数为图解法失效。由定义可知由定理1可将该问题简化为:第78页9/12/202378OperationsResearch6.6.2优势法可用图解法求得最优解和值分别为：由又可看出：从又可看出：，所以得：第79页9/12/202379OperationsResearch6.6.2优势法即可得到对策G解为：值为V=5。第80页9/12/202380OperationsResearch6.6.3简化计算法定理5若矩阵对策其中d为常数，则G1与G2有相同解，且对策值相差一个常数d，即：第81页9/12/202381OperationsResearch6.6.3简化计算法推论1若矩阵对策其中k>0为常数，则G1与G2有相同解,且第82页9/12/202382OperationsResearch6.6.3简化计算法例11已知某矩阵对策G支付矩阵以下：解：由推论1可取得同解矩阵：第83页9/12/202383Opera