对策论1-070516

《高等运筹学》甘小冰高等运筹学主讲：甘小冰时间：2007年5月22日Email:[e-mail]《高等运筹学》甘小冰对策论GameTheory对策论博弈论GameTheory《高等运筹学》甘小冰对策论GameTheory对策论1引论2矩阵对策的基本理论3矩阵对策的解法4其他类型对策简介5冲突分析《高等运筹学》甘小冰对策论GameTheory1、引论1.0对策论(博弈论)简介《高等运筹学》甘小冰对策论GameTheory1、引论1.1对策行为和对策论对策行为:具有竞争和对抗性质的行为.体育比赛政治斗争企业之间的竞争对策论:对策行为中斗争各方是否存在着最合理的行动方案,以及如何找到这个合理方案的数学理论和方法。《高等运筹学》甘小冰对策论GameTheory局中人:有权决定自己行为的参与者.I={1,2,...,n},n=2.假设:局中人都是理智的,等智力的.策略集策略:可供选择的行动方案.策略集:Si--至少有两个策略1.2对策行为的基本要素《高等运筹学》甘小冰对策论GameTheory局中人:有权决定自己行为的参与者.I={1,2,...,n},n=2.假设:局中人都是理智的,等智力的.策略集策略:可供选择的行动方案.策略集:Si--至少有两个策略1.2对策行为的基本要素例齐王赛马：局中人齐王与田忌各有六个策略：1、（上，中，下）2、（上，下，中）3、（中，上，下）4、（中，下，上）5、（下，中，上）6、（下，上，中）《高等运筹学》甘小冰对策论GameTheory赢得函数(支付函数)局势:各局中人所选定的策略形成的策略组.赢得函数:Hi(s)--第i个局中人例),,,(21nssss1.2对策行为的基本要素《高等运筹学》甘小冰对策论GameTheory赢得函数(支付函数)局势:各局中人所选定的策略形成的策略组.赢得函数:Hi(s)--第i个局中人例),,,(21nssss1.2对策行为的基本要素例齐王赛马：局中人集合Ｉ＝｛1，2｝策略集：齐王S1={1,2,…,6}田忌S2={1,2,…,6}齐王的任一策略i与田忌的任一策略i决定了一个局势Sij。若1＝(上，中，下）1＝(上，中，下）赢得函数:H1(s11)＝3H2(s11)＝-3。《高等运筹学》甘小冰对策论GameTheory对策静态对策动态对策结盟对策不结盟对策有限对策无限对策两人对策多人对策零和对策非零和对策1.3对策的分类√《高等运筹学》甘小冰对策论GameTheory2.矩阵对策的基本理论2.1矩阵对策的数学模型《高等运筹学》甘小冰对策论GameTheory2.矩阵对策的基本理论2.1矩阵对策的数学模型矩阵对策：二人有限零和对策，亦称为对抗对策。局中人：两个；策略：有限；赢得之和：为零。《高等运筹学》甘小冰对策论GameTheory2.矩阵对策的基本理论有关概念局中人I:纯策略m个,其策略集合是局中人II:纯策略n个,其策略集合是纯局势:共有mxn个纯局势121),...,,(Sm221),...,,(Sn),(ji2.1矩阵对策的数学模型《高等运筹学》甘小冰对策论GameTheoryaij--局中人I在纯局势下的赢得,则:局中人I的赢得矩阵(局中人II的支付矩阵)矩阵对策记为:G={I,II;S1,S2;A}G=(S1,S2;A}),(jimnmmnnaaaaaaaaaA,...,,.............,...,,,...,,212222111211《高等运筹学》甘小冰对策论GameTheory例:齐王赛马中齐王的赢得表田忌的策略齐王的策略1上中下2上下中3中上下4中下上5下中上6下上中1上中下31111-12上下中1311-113中上下1-131114中下上-1113115下中上11-11316下上中111-113《高等运筹学》甘小冰对策论GameTheory表14-1齐王赛马中齐王的赢得表田忌的策略齐王的策略1上中下2上下中3中上下4中下上5下中上6下上中1上中下31111-12上下中1311-113中上下1-131114中下上-1113115下中上11-11316下上中111-113齐王赢三次，没有输，赢得值为3-0=3《高等运筹学》甘小冰对策论GameTheory表14-1齐王赛马中齐王的赢得表田忌的策略齐王的策略1上中下2上下中3中上下4中下上5下中上6下上中1上中下31111-12上下中1311-113中上下1-131114中下上-1113115下中上11-11316下上中111-113齐王赢2次，输1次，赢得值为2-1=1《高等运筹学》甘小冰对策论GameTheory齐王赛马中齐王的赢得表田忌的策略齐王的策略1上中下2上下中3中上下4中下上5下中上6下上中1上中下31111-12上下中1311-113中上下1-131114中下上-1113115下中上11-11316下上中111-113齐王赢1次，输2次，赢得值为1-2=1《高等运筹学》甘小冰对策论GameTheory齐王赛马中齐王的赢得矩阵为：311111131111113111111311111131111113A《高等运筹学》甘小冰对策论GameTheory思考题甲、乙两名儿童玩游戏，双方可分别出拳头（代表石头），手掌（代表布），两个手指（代表剪刀），规则是：剪刀赢布，布赢石头，石头赢剪刀，赢者得１分。若双方所出相同，为和局，均不得分，试列出儿童甲的赢得矩阵。011101110剪刀布石头剪刀布石头《高等运筹学》甘小冰对策论GameTheory对策目标如何选取对自己最为有利的策略以谋取最大的赢得（或最少损失）。《高等运筹学》甘小冰对策论GameTheory603-10-1-94238-16-A例1设有一矩阵对策G=｛S1,S2;A｝，其中S1={1,2,3,4},S2={1,2,3}，2.矩阵对策的基本理论《高等运筹学》甘小冰对策论GameTheoryS2S11231-61-8232439-1-104-306局中人I与II的对策过程《高等运筹学》甘小冰对策论GameTheoryS2S11231-61-8232439-1-104-306局中人I与II的对策过程213《高等运筹学》甘小冰对策论GameTheory对策原则双方都是理智行为，考虑到对方必然会使自己所得最少，应从各自出现的最不利的情形中选择一种最为有利的情形。《高等运筹学》甘小冰对策论GameTheoryS2S11231-61-8232439-1-104-306局中人I与II的对策过程选择1时的最少赢得选择2时的最少赢得选择3时的最少赢得选择4时的最少赢得《高等运筹学》甘小冰对策论GameTheoryS2S11231-61-8232439-1-104-306局中人I与II的对策过程(I的对策)选择1时的最少赢得选择2时的最少赢得选择3时的最少赢得选择4时的最少赢得《高等运筹学》甘小冰对策论GameTheoryS2S11231-61-8232439-1-104-306局中人I与II的对策过程(I的对策)最少赢得中最好结果为2，局中人I以2为选择对策。《高等运筹学》甘小冰对策论GameTheoryS2S11231-61-8232439-1-104-306局中人I与II的对策过程(II的对策)选择1时的最少赢得选择2时的最少赢得选择3时的最少赢得《高等运筹学》甘小冰对策论GameTheoryS2S11231-61-8232439-1-104-306局中人I与II的对策过程(II的对策)最少赢得中最好结果为2，局中人II以2为选择对策。《高等运筹学》甘小冰对策论GameTheoryS2S11231-61-8232439-1-104-306局中人I与II的对策过程最优纯策略（2，2）《高等运筹学》甘小冰对策论GameTheory最优对策局中人I按最大最小原则，局中人II按最小最大原则选择策略，这样的策略对双方来说是最优策略。《高等运筹学》甘小冰对策论GameTheory最优策略（纯策略下的解）,,I,),(,,,maxminminmax,};,{********21的最优策略局中人的最优策略局中人在纯策略下的解为的值为对策则称记成立若为矩阵对策设IIGGVaVaaaASSGjijiGjiGjiijijijji《高等运筹学》甘小冰对策论GameTheory例:由上例,有503-3-1-164238-17-A.3,2,1;4,3,2,1,22**jiaaajjii《高等运筹学》甘小冰对策论GameTheory定理:矩阵对策G={S1,S2;A}在纯策略意义下有解的充分必要条件是存在纯局势使得i=1,2,…,m,j=1,2,…,njijiijaaa****),(**ji矩阵对策的基本理论《高等运筹学》甘小冰对策论GameTheory定义2:f(x,y)是一个定义在x∈A,y∈B上的实质函数,且存在x*∈A,y*∈B,对一切x∈A,y∈B有:f(x,y*)≤f(x*,y*)≤f(x*,y)则称(x*,y*)为函数f的一个鞍点.矩阵对策的基本理论《高等运筹学》甘小冰对策论GameTheory定理的直观解释及对策意义*j*i一个平衡局势应具有这样的性质，当局中人Ⅰ选取了纯策略后，局中人Ⅱ只能选取纯略，否则就可能失得更多；反之，当局中人Ⅱ选取了纯策略后，局中人Ⅰ只能选取纯略，否则就可能赢得更多。双方的竞争在局势下达到了一个平衡状态。),(**ji*j*i),(**ji《高等运筹学》甘小冰对策论GameTheory无差别性:可交换性22112211,G),(),(jijijijiaa则的两个解是对策和若也是解。和则的两个解是对策和若),(),(,G),(),(12212211jijijiji矩阵对策的性质《高等运筹学》甘小冰对策论GameTheory对G=(S1,S2;A)局中人I至少赢得:局中人II至多损失:ijjiavminmax1ijijavmaxmin2.,,,2121存在纯策略意义下的解时当一般地Gvvvv2.2矩阵对策的混合策略《高等运筹学》甘小冰对策论GameTheory2.2矩阵对策的混合策略一般情形中更多的是v1v2，对策不存在纯策略意义下的解。例赢得矩阵为4563A1,5maxmin2,4minmax*2*1javiavijijijji1245vv《高等运筹学》甘小冰对策论GameTheory2.2矩阵对策的混合策略S2S112min13632544max《高等运筹学》甘小冰对策论GameTheory2.2矩阵对策的混合策略S2S112min13632544max56《高等运筹学》甘小冰对策论GameTheory2.2矩阵对策的混合策略S2S112min13632544max56双方都从最不利和情形中选择最好的双方都从最不利和情形中选择最好的《高等运筹学》甘小冰对策论GameTheory2.2矩阵对策的混合策略S2S112min13632544max56《高等运筹学》甘小冰对策论GameTheory2.2矩阵对策的混合策略S2S112min13632544max56《高等运筹学》甘小冰对策论GameTheory2.2矩阵对策的混合策略S2S112min13632544max56局中人的赢得5