对策论基础NEW.ppt

《对策论基础NEW.ppt》由会员分享，可在线阅读，更多相关《对策论基础NEW.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、对策论基础NEW Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第十四章 对策论基础竞争无处不在,体育比赛、军事斗争、商业谈判、市场争夺、职位竞聘。为了在竞争中谋取最大利益，必须采取对抗其他竞争者的策略，这就是对策问题。研究竞争场合下决策者采取对策的理论与方法，称为对策论，又称为博弈论。我国古代就有著名的“齐王赛马”例子。第一节 概论基本概念与名词对策分类对策现象的三个基本要素1.局中人:在竞争中，拥有决策权的参与者,可以是个人,也可以是团体。桥牌，象棋；2.策略

2、:可供局中人选择对付其他局中人行动方案称为一个策略。该方案必须是自始至终通盘筹划的行动方案。例子。“当头炮”不是一个策略，而是某一个策略的组成部分。3.一局对策的得失：一局对策结束后，对每个局中人来说，不外乎胜利和失败，或其它收入，这些统称为“得失”.对策现象的三个基本要素4.策略集：一个局中人所拥有的策略全体。5.局势：各局中人使用一定的对策，从而形成了一种状态称为局势。6.支付函数：局中人不同的策略,会有不同的得失,故”得失”是策略组合的结果;即一局对策结束时，每个局中人的“得失”是全体局中人所取定的一组策略的函数,称为“支付函数”.一、基本概念与名词7.零和对策：如果在任一“局势”中，全

3、体局中人的“得失”相加总是等于0时，这个对策就称为零和对策。上述赛马就是零和对策。否则称为非零和对策8.矩阵对策：参加对策的局中人只有二人,而每个局中人可选策略只有有限个,每局的得失之和为零.二、对策分类二、对策分类对策静态对策动态对策结盟对策不结盟对策微分对策联合对策合作对策有限无限二人多人零和非零和零和非零和二人多人零和非零和零和非零和三、博弈论发展史三、博弈论发展史1944年，von Neumann and Oskar Morgenstern发表专著 The Theory of Games and Economic Behavior创立了博弈论1950，1951年，纳什(Nash)和图克

4、(Tucker)奠定了非合作博弈论的基础1965年，泽尔腾(Selten)将动态分析引入纳什平衡，建立了精炼纳什平衡1967，1968年，海萨尼(Harsanyi)将不完全信息引入博弈论三、博弈论发展史三、博弈论发展史1982年，克瑞普斯(Kreps)和威尔逊(Wilson)发表了动态不完全信息博弈的重要文章，建立了动态不完全信息博弈的理论上世纪八十年代开始，博弈论进入经济学，进而在管理学中得到了很好的应用；九十年代，经济学教科书中加入了博弈论1994年，Nash,Selten&Harsanyi三人获得了诺贝尔经济学奖，博弈论的地位正式确立。恰逢Von Neumann and Morgenst

5、ern建立博弈论50周年。三、博弈论发展史三、博弈论发展史1994-1996年美国国会授权联邦通讯委员会(FCC)公开拍卖部分用于个人通讯服务(PCS)的无线电频段，FCC接受博弈论专家的设计，采用多回合的竞买者同时出价的增价模式，取得了巨大的成功。博弈论开始为企业界所接受并走向实用。1999-2001年美国先后出版了小说美丽的心灵和拍成了电影美丽的心灵，并获奥斯卡奖。纳什和博弈论妇孺皆知。第二节 矩阵对策的基本理论矩阵对策的数学模型矩阵对策的数学模型最优纯策略最优纯策略混合策略与混合扩充混合策略与混合扩充一、矩阵对策的数学模型一、矩阵对策的数学模型以齐王赛马为例说明齐王赛马二人非合作零和对策

6、局中人齐王和田忌策略 上 中下三种等级的马的组合 ，比三次，有六组策略：(上，中，下)、(中，上，下)、(上，下，中)、(中，下，上)、(下，上，中)、(下，中，上)对齐王，这六组策略用 表示，对田忌，则用 表示。四、博弈论的典型例子齐王赛马支付函数31111-11311-111-13111-11131111-1131111-113(上中下上中下)(上下中上下中)(中上下中上下)(中下上中下上)(下中上下中上)(下上中下上中)田 忌(上中下上中下)(上下中上下中)(中上下中上下)(中下上中下上)(下中上下中上)(下上中下上中)齐齐王王策略组合的得失:齐王赛马赢得矩阵A31111-11311-1

7、11-13111-11131111-1131111-113 (上中下)(上下中)齐 (中上下)王 (中下上)(下中上)(下上中)田 忌31111-11311-111-13111-11131111-1131111-113 (上中下)(上下中)齐 (中上下)王 (中下上)(下中上)(下上中)田 忌当齐王从S1中选定一个策略ai,田忌从S2挑选一个策略bj应对,那么双方就形成了一个局势(ai,bj),称为纯局势.ai,bj称为纯策略.对策的数学表示齐王,田忌赛马的模型可表示为:其中I、II表示两个局中人，S1、S2分别表示局中人I、II的策略集，A则表示赢得矩阵：2.最优纯策略现有一矩阵对策其中从最

8、坏处着想,去争取最好的结果-即最优纯策略。对局中人甲局中人甲来说，所有最坏的结果是（取A中每一行的最小）：得-8，2，-10，-3，在这些最坏的情况中最好的结果是2，因此，无论局中人乙采取什么策略，局中甲只要选a2参加对策，就能保证收入不会小于2。对局中人乙局中人乙来说，所有最坏的结果是（取A中每一列的最大元素，损失最大）：9，2，6，在这些最坏的情况中最好的结果是2，因此，无论局中人甲采取什么策略，局中乙只要选B2参加对策，就能保证损失（支出）不会大于2。那么，此时，局中人甲和乙的最坏情况下的最好结果的绝对值相等（都是2），那么我们就称a2为局中人甲的最优策略，B2就称为局中人乙的最优策略。

9、（a2,B2)就称为对策模型G=S1，S2，A的最优局势，而局中人甲的赢得值2称为对策G的值；例:甲乙乒乓球队进行团体对抗赛,每队由三名球员组成,双方都可排成三种不同的阵容,每一种阵容可以看成一种策略,双方各选一种策略参赛.比赛共三局,规定每局胜者得1分,输者得-1分.甲队的策略集为S1=a1,a2,a3;乙队的策略集S2=B1,B2,B3。根据以往比赛得分资料,可得甲队的赢得矩阵为A:1111-1-33-131 2 3 1 2 3A=试问这次比赛各队应采用哪种阵容上场最为稳妥?上述描述可表示为：G=甲,乙;S1,S2;A;G=S1,S2;A题中所谓的稳妥,是指不求得分最多,期望失分最少;由于

10、A是甲队的赢得矩阵(得分矩阵),因此,甲队失分最少,意味着有最基本的得分底线(最少应得分).甲队采用策略1,可得分min=1,max=12,可得分min=-3,max=13,可得分min=-1,max=3很显然,甲队有保底得分:max1,-3,-1=1只要采用策略1即可实现.1111-1-33-131 2 3 1 2 3A=从乙队角度看,采用以下策略的最少赢得(即A中最大):1,失分3,1,2,失分1,-1,3,失分3,-3,为稳妥起见,乙队应从失分中挑选最小最小的.即采用策略2,无论甲队怎样布阵,乙队最多失1分.总结上述可知,在上述对策中,甲队采用策略1,乙队采用策略2,可获取自己所需要的最

11、底最底线.称(1,2)为局中人甲队,乙队的最优策略。1111-1-33-131 2 3 1 2 3A=在一个对策G中,局中双方要获得最优纯策略，必须满足一定的条件，1111-1-33-131 2 3 1 2 3A=得分方:正方失分方:反方例子11111-1-33-13B1 2 312 33 1 3 1-3-1Min3,1,3=1Max:1理智行为各列最大(Max):A=各行最小(Min)例子2采购博弈二人非合作零和博弈局中人采购员和气候策略 气候：偏暖、正常、偏冷；采购员购煤:10、15、20吨支付函数秋天购买价格为10元/吨，冬天再购买价格是10元/吨(偏暖)、15元/吨(正常)、20元/吨

12、(偏冷)吨。假设不知天气预报,问:秋天应贮存多少吨煤能使单位的支出最少?-100-175-300-300-150-150-250-250-200-200-200-200-100-150-200A3,B3气候 偏暖 正常 偏冷 10采购员 15 20MAX:MINMin:-200MAX:-200例子2-100-175-300-300-150-150-250-250-200-200-200-200*-100-150-200*气候 偏暖 正常 偏冷采 10购 15员 20MAX:MINMin:-200MAX:-200秋季采购最优纯策略的表述设对于矩阵对策G：G=S1，S2，A等式成立，记其值为VG，

13、则称VG 为对策G的值。如果纯局势 使 则称 为对策G的鞍点，也称为对策G的在纯策略中的解（矩阵对策的最优解），分别是局中人I、II的最优纯策略。练习：1.设对策G=S1,S2,A,其中-71-832416-1-3-305A=S1=a1,a2,a3,a4,S2=B1,B2,B3求对策G的鞍点和对策值,及局中人的最优策略VG=2,(a2,B2),MAXMIN=5练习：2.设对策=S1,S2,A,其中10-43A=S1=a1,a2,S2=B1,B2求局中人的最优策略和对策值MAXMIN=0MINMAX=1,不相等,无解练习：3.设对策=S1,S2,A,其中6565142-185750262A=S1

14、=a1,a2,a3,a4,S2=B1,B2,B3,B4求局中人的最优策略和对策值VG=5,(a1,B2),(a3,B4)(a1,B4),(a3,B2)MAXMIN=5定理1：矩阵对策G=S1,S2,A有纯策略解的充要条件是存在一个纯局势 使得或赢得矩阵满足条件：证明略.3、混合策略与混合扩充基本概念：当时不存在最优纯策略，此时需要应用混合策略的方法确定参加对策的纯策略。例如分析上述例子因为因为所以所以从从 看看,最优策略是甲选最优策略是甲选a2,乙选乙选B2,但从但从 看看,甲应选甲应选a1,乙选乙选B2两个局人没有稳妥的策略两个局人没有稳妥的策略,此时此时,这时就得估计选取各这时就得估计选取

15、各个策略可能性的大小来进行对策个策略可能性的大小来进行对策.即就是用多大概率即就是用多大概率选取各个纯策略选取各个纯策略.这样局中人不能单独地使用某一个策略这样局中人不能单独地使用某一个策略,只好结合不只好结合不同概率分布以使甲同概率分布以使甲(乙乙)平均赢得平均赢得(损失损失)最多最多(最少最少),为标准来选取策略为标准来选取策略,这种策略称之为混合策略这种策略称之为混合策略.分析上述例子因为因为所以所以此时假设局中人此时假设局中人I以概率以概率x选取策略选取策略a1，以概率，以概率(1-x)选取策略选取策略a2；局中人；局中人II以概率以概率y选取策略选取策略B1，以概率以概率(1-y)选

16、取策略选取策略B2。则对于局中人。则对于局中人I来说，来说，赢得的期望值为赢得的期望值为E(x,y)，它等于，它等于B1B2 a1X,yX,1-y a21-x,y 1-x,1-y1342例子引出混合策略赢得期望值当X=1/2在x=1/2，y=1/4时，赢得函数取得最优值5/2。这实际上是对策双方都满意的结果。我们把纯策略对应的概率向量叫做混合策略，最优解则是最优混合策略。本例中，最优混合策略是(1/2,1/2)和(1/4,3/4)。X,yX,1-y1-x,y1-x,1-y混合策略的定义令纯策略集对应的概率向量是它们满足定义:为局中人甲的赢得,-E(X,Y)为局中人乙的赢得.混合策略的定义局中人

17、甲,乙的混合策略的集合为:将 叫做G=S1,S2,A的混合扩充。最优混合策略的定义若令并有则称(X*,Y*)为最优混合局势，或叫做G在混合策略下的解，V叫做对策G的值。X*、Y*分别是局中人I、II的最优混合策略。混合对策问题的解法如果G的值是V，则局中人I和II的最优策略是下列两组不等式的解：关于混合对策问题的解，我们有如下定理：混合对策最优解定理如果(X*,Y*)是对策G的最优混合局势，则对于某个i或j来说，有：混合对策问题的求解方法：线性规划法，例2:混合对策问题的求解方法：线性规划法，解：设甲使用a1的概率为x1,使用a2的概率为x2,并设在最坏的情况下，甲的赢得的平均值等于V。(1)

18、x1+x2=1 x1=0,x2=0(2)当乙使用b1策略时，甲的平均赢得为5x1+8x2 5x1+8x2=V混合对策问题的求解方法：线性规划法，(2)当乙使用b1策略时，甲的平均赢得为5x1+8x2 5x1+8x2=V 当乙使用b2策略时，甲的平均赢得为 9x1+6x2；此时，9x1+6x2=V由于矩阵A中所有值都大于0，则V0（3）作变量代换：xi=xi/V(i=1,2)对甲来说,它希望V越大越好,即1/V越小越好.那么，甲的最优混合策略的线性规划模型如下：混合对策问题的求解方法：线性规划法，解：(1)目标函数：min x1+x2 (2)约束条件：5x1+8x2=1 9x1+6x2=1 x1

19、=0,x2=0Max V s.t.5x1+8x2=V 9x1+6x2=V x1+x2=1 x1,x2=0混合对策问题的求解方法：线性规划法，解：Lindo 软件程序：min x1+x2 s.t.5x1+8x2=1 9x1+6x2=1 x1=0 x2=0 end混合对策问题的求解方法：线性规划法，LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)0.1428571 VARIABLE VALUE REDUCED COST X1 0.047619 0.000000 X2 0.095238 0.000000 ROW SLACK OR SURPL

20、US DUAL PRICES 2)0.000000 -0.071429 3)0.000000 -0.071429 NO.ITERATIONS=2混合对策问题的求解方法：线性规划法，RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 1.000000 0.500000 0.375000 X2 1.000000 0.600000 0.333333 RIGHTHAND SIDE RANGES ROW CU

21、RRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 1.000000 0.333333 0.444444 3 1.000000 0.800000 0.250000 求得结果：X1=0.047619,X2=0.095238那么V=1/（x1+x2)=0.047619+0.095238)=7.0X1=0.047619*7.0=0.3333;x2=0.095238*7.0=0.6666;故甲的最优策略是以0.3333概率出a1,以0.6666的概率出策略a2;简记X*=(0.3333,0.6666)T,V=7.0同样可求出乙的最优混合策略:设乙的使用策

22、略的概率为:y1,y2 y1+y2=1 5y1+9y2=V 8y1+6y2=0 作变换后,得模型为:解：(1)目标函数：min y1+y2 (2)约束条件：5y1+9y2=1 8y1+6y2=0,y2=0 解：Lindo 软件程序 min y1+y2 s.t.5y1+9y2=1 8y1+6y2=0 y2=0 end LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)0.1428571 VARIABLE VALUE REDUCED COST Y1 0.071429 0.000000 Y2 0.071429 0.000000 ROW SLA

23、CK OR SURPLUS DUAL PRICES 2)0.000000 0.047619 3)0.000000 0.095238 4)0.071429 0.000000 5)0.071429 0.000000V=1/(y1+y2)=1/(0.071429*2)=7.0 y1=7.0*0.071429=0.5 y2=7.0*0.071429=0.5故乙的最优策略是以0.5概率出B1,以0.5的概率出策略B2;简记Y*=(0.5,0.5),V=7.0上述题目的求解是基于矩阵A0的条件,往往实际不能满足A0;此时,需要对A中每个元素加以足够大数,以保证A0;定理:G=S1,S2,A,G=S1,S2

24、,A若A=A+K,满足A0,当VG为G的最优策略时,则VG=VG-K为G的最优策略。“齐王赛马”31111-11311-111-13111-11131111-1131111-113A=“齐王赛马”533313353331315333133533331353331335A+2=“齐王赛马”533313353331315333133533331353331335A+2=X1X2X3X4X5X6“齐王赛马”甲方最优策略的线性规划模型:目标函数:max V约束条件:5x1+3x2+3x3+1x4+3x5+3x6=V3x1+5x2+1x3+3x4+3x5+3x6=V3x1+3x2+5x3+3x4+3x5

25、+1x6=V3x1+3x2+3x3+5x4+1x5+3x6=V1x1+3x2+3x3+3x4+5x5+3x6=V3x1+1x2+3x3+3x4+3x5+5x6=v x1+x2+x3+x4+x5+x6=1Xi=0“齐王赛马”代换:xi=xi/V目标函数:min x1+x2+.+x6约束条件:5x1+3x2+3x3+1x4+3x5+3x6=13x1+5x2+1x3+3x4+3x5+3x6=13x1+3x2+5x3+3x4+3x5+1x6=13x1+3x2+3x3+5x4+1x5+3x6=11x1+3x2+3x3+3x4+5x5+3x6=13x1+1x2+3x3+3x4+3x5+5x6=1Xi=0“

26、齐王赛马”模型:min x1+x2+x3+x4+x5+x6 s.t.5x1+3x2+3x3+1x4+3x5+3x6=13x1+5x2+1x3+3x4+3x5+3x6=13x1+3x2+5x3+3x4+3x5+1x6=13x1+3x2+3x3+5x4+1x5+3x6=11x1+3x2+3x3+3x4+5x5+3x6=13x1+1x2+3x3+3x4+3x5+5x6=1 xi=0“齐王赛马”Lindo 软件源程序:min x1+x2+x3+x4+x5+x6 s.t.5x1+3x2+3x3+1x4+3x5+3x6=13x1+5x2+1x3+3x4+3x5+3x6=13x1+3x2+5x3+3x4+3

27、x5+1x6=13x1+3x2+3x3+5x4+1x5+3x6=11x1+3x2+3x3+3x4+5x5+3x6=13x1+1x2+3x3+3x4+3x5+5x6=1end“齐王赛马”LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1)0.3333333 VARIABLE VALUE REDUCED COST X1 0.111111 0.000000 X2 0.000000 0.000000 X3 0.000000 0.000000 X4 0.111111 0.000000 X5 0.111111 0.000000 X6 0.000000

28、 0.000000“齐王赛马”ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 -0.111111 3)0.000000 0.000000 4)0.000000 0.000000 5)0.000000 -0.111111 6)0.000000 -0.111111 7)0.000000 0.000000 NO.ITERATIONS=3“齐王赛马”X1+x2+x6=0.33333,V=1/(x1+x2+.+x6)=1/(0.111111*3)=3Xi=V*xi=3*0.111111=0.3333=1/3 X1 0.333333 0.000000 X2 0.00

29、0000 0.000000 X3 0.000000 0.000000 X4 0.333333 0.000000 X5 0.333333 0.000000 X6 0.000000 0.000000X*=(0,1/3,1/3,0,0,1/3)T VG=3“齐王赛马”同理可求乙方的最优策略:目标:max y1+y2+y3+y4+y5+y6 s.t.5y1+3y2+3y3+1y4+3y5+3y6=13y1+5y2+1y3+3y4+3y5+3y6=13y1+3y2+5y3+3y4+3y5+1y6=13y1+3y2+3y3+5y4+1y5+3y6=11y1+3y2+3y3+3y4+5y5+3y6=13y1

30、+1y2+3y3+3y4+3y5+5y6=0“齐王赛马”同理可求乙方的最优策略:Lindo 源程序:max y1+y2+y3+y4+y5+y6 s.t.5y1+3y2+3y3+1y4+3y5+3y6=13y1+5y2+1y3+3y4+3y5+3y6=13y1+3y2+5y3+3y4+3y5+1y6=13y1+3y2+3y3+5y4+1y5+3y6=11y1+3y2+3y3+3y4+5y5+3y6=13y1+1y2+3y3+3y4+3y5+5y6=1 end同理可求乙方的最优策略:LP OPTIMUM FOUND AT STEP 4 OBJECTIVE FUNCTION VALUE 1)0.33

31、33333 VARIABLE VALUE REDUCED COST Y1 0.111111 0.000000 Y2 0.000000 0.000000 Y3 0.000000 0.000000 Y4 0.111111 0.000000 Y5 0.111111 0.000000 Y6 0.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.111111 3)0.000000 0.000000 4)0.000000 0.000000 5)0.000000 0.111111 6)0.000000 0.111111 7)0.000

32、000 0.000000 NO.ITERATIONS=4优优 超超 因而策略L出现的概率为0，可以在支付矩阵中删除该策略对应的行优优 超超优超原则:当局中人甲的某策略ai,被其它策略之一所优超时,可在A中划去第i行,同样,对局中人乙来说,可从A中划去被其它策略之一所优超的列.所得结果A后,所对应的对策G与G等价.优超原则:算例1例1:对于G=S1,S2,A下例说明混合对策问题的特殊解法对于G=S1,S2,A第一步 简化赢得矩阵划去普遍较小的行，例如第1、2行，得划去普遍较大的列，例如第3、4、5三列，结果如上。进一步化简上述结果的第一行比第三行普遍更优，因此再划去第三行，得若混合策略均不为零，由上述定理知混合对策问题数学模型的不等式应为等式。因此有第二步 用方程组求解最优混合策略满足如下方程组解得矩阵混合对策问题的解算算 例例2简简 化化简简 化化对策模型转化为线性规划求的基对策模型转化为线性规划求的基对策模型转化为线性规划求的基对策模型转化为线性规划求的基 本本本本 思思思思 想想想想算算 例例结结 果果习题P.343-344，习题1、2、5。