11博弈论

11.博弈论§1.概述1．博弈模型研究两个或两个以上的参加者在某种对抗性或竞争性的场合下各自作出决策，使自己的一方得到尽可能最有利的结果。带有竞争性质的现象，称为博弈现象。日常生活中：在政治方面：正经济领域内：齐王赛马11.博弈论§1.概述1．博弈模型2．博弈现象的三个基本要素•局中人:决策者,利益得失者,不是公证人、马、谋士等，可以是团体、国家等；聪明的，有理智的；把那些利益完全一致的参加者们看作一个局中人；两人,多人,结盟,不结盟11.博弈论§1.概述1．博弈模型2．博弈现象的三个基本要素•局中人:•策略:自始至终的行动方案；把局中人的策略全体，称做这个局中人的策略集合；例如，在齐王与田忌赛马的例子中，如果—开始就要把各人的三匹马排好次序，然后依次出赛。各局中人都有六个策略：(1)(上、中、下)，(2)(上、下、中)(3)(中、上、下)(4)(中、下、上)，(5)(下、中、上)，(6)(下、上、中)。这个策略全体就是局中人的策略集合。有限,无限11.博弈论§1.概述1．博弈模型2．博弈现象的三个基本要素•局中人:•策略:•得失:一局博弈结束时，每个局中人的“得失”是全体局中人所取定的一组策略的函数。通常称为“支付函数”。从每个局中人的策略集中各取—个策略，组成的策略组，称作“局势”。“得失”是“局势”的函数。如果全体局中人的“得失”相加总是等于零时，这个博弈就称为零和博弈。否则称为“非零和博弈”。11.博弈论§1.概述1．博弈模型2．博弈现象的三个基本要素3．博弈模型的分类博弈静态博弈动态博弈联合博弈合作博弈有限博弈无限博弈二人博弈多人博弈二人博弈多人博弈零和博弈非零和博弈零和博弈非零和博弈零和博弈非零和博弈零和博弈非零和博弈结盟博弈微分博弈不结盟博弈11.博弈论11.博弈论§2.矩阵博弈（MatrixGames）1．定义：有限二人零和博弈，即参加博弈的局中人只有两个，而每个局中人都有有限个可供选择的策略。而且在任一局势中，两个局中人的得失之和总等于零（一个局中人的所得即为另一个局中人的所失）。局中人的利益是冲突的，也称为对抗博弈。§2.矩阵博弈（MatrixGames）例1：配钱币游戏：两个局中人1和2各出示一枚钱币，在不让对方看见的情况下，将钱币放在卓上，若两个钱币都呈正面或都呈反面，则局中人1得1分，局中人2得-1分。若两个钱币一正一反，则局中人2得1分。可用一个支付矩阵表示.局中人2局中人11（正）2（反）1（正）1-12（反）-11§2.矩阵博弈（MatrixGames）例2：“石头、剪刀、布”游戏局中人2局中人11（石头）2（剪刀）3（布）1（石头）01-12（剪刀）-1013（布）1-10§2.矩阵博弈（MatrixGames）例3：局中人1从p=0,1,2,3四个数中选出一个数，局中人2在不知道局中人1出什么数的情况下从q=0,1,2三个数中选出一个数。局中人1得到的支付由下支付函数确定：P=p(q-p)+q(q+p)或P=q2-p2+2pq局中人2q局中人1p01200141-1272-4183-9-27§2.矩阵博弈（MatrixGames）2．数学模型设局中人1有m个纯策略α1,α2,…,αm;记集合为S1={α1,α2,…,αm}。同样，局中人2有n个纯策略，集合为S2={β1,β2,…,βn}支付矩阵（或赢得矩阵）:局中人Ｉ赢得矩阵为：博弈模型记为：Ｇ＝｛S1,S2,A｝§2.矩阵博弈（MatrixGames）2．数学模型如齐王赛马：S1={(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、中、上),(下、上、中)}S２={(上、中、下),(上、下、中),(中、上、下),(中、下、上),(下、中、上),(下、上、中)}田忌的支付（赢得）矩阵为-A3．最优纯策略例4对于一个矩阵博弈Ｇ＝｛I,Ⅱ,S1,S2,A｝，其中S1={α1,α2,α3,α4}，S2={β1,β2,β3}求双方的最优策略。解由A可以看出，局中人I的最大赢得是16，就是说局中人I十分希望自己取得16，就会出α3加入博弈。然而，局中人Ⅱ也在考虑，因为局中人I有出α3的心理状态，于是局中人Ⅱ就想出β3进行博弈，这样不仅不能使I得到16，反而要输9(即赢得-9)。同样，I也会这样想，Ⅱ有出β3的心理状态，于是I就会出α2，结果Ⅱ不但得不到9，反而要输5。同样，如果I出α2，则Ⅱ会出β2，使I的赢得达到最小2。而对于I来说，如果Ⅱ出β2，I的最优策略仍然是α2，可获得最大赢得值2。α2和β2分别是双方的最优策略，a22=2称为矩阵博弈G的值。它是第2行中最小值，也正好是第2列中的最大值。3．最优纯策略对于给定的Ｇ＝｛S1,S2,A｝,局中人1希望支付值越大越好，局中人2希望支付值越小越好。局中人1可选择i，使他得到的支付不少于：局中人2可以选择j，保证他失去的支付不大于:容易证明:局中人2局中人11（正）2（反）1（正）1-12（反）-11例1：配钱币游戏：-113．最优纯策略-11例2：“石头、剪刀、布”游戏局中人2局中人11（石头）2（剪刀）3（布）1（石头）01-12（剪刀）-1013（布）1-103．最优纯策略0=0例3：局中人2q局中人1p01200141-1272-4183-9-273．最优纯策略齐王赛马：-133．最优纯策略定义：一个矩阵博弈，如果它的支付矩阵A的元素满足：则称这个值v为博弈的值。如果纯局势(i*,j*)使：则称(i*,j*)为博弈G的鞍点(Saddlepoint)，也称它是博弈G在纯策略中的解，i*与j*分别为局中人1和局中人2的最优解。3．最优纯策略即矩阵博弈有两个性质：一是鞍点的可交换性，二是各鞍点的值都相等。定理：为博弈G的鞍点的充要条件是对于任意的i,j,有：如:定理：若和都是矩阵博弈A的鞍点，则和也都是它的鞍点，且在鞍点处的值都相等。即：即该列的最大元素及该行的最小元素.3．最优纯策略例5：某单位在秋天要决定冬季取暖用煤贮量问题，在正常的冬季气温下要消耗15吨，但在较暖与较冷的冬季需要10吨和20吨，假定煤的价格随着冬季寒冷程度而有所变动，设在较暖的、正常的、较冷的冬季气温下分别为每吨1000元，1500元，2000元，又设在秋季煤价是每吨1000元，在没有关于当年冬季准确的气象预报条件下，秋季贮煤多少吨才较合理?解:把采购员当作局中人I，他有三个策略：在秋天时买10吨、15吨与20吨，分别记为a1，a2，a3。把大自然看作局中人Ⅱ，(可以当作理智的局中人来处理)，大自然(冬季气温)有三种策略：出现较暖的、正常的与较冷的冬季，分别记为b1，b2，b3。现在把该单位冬季取暖用煤实际费用(即秋季购煤时的用费、与冬季不够时再补购的费用总和)作为局中人I的赢得，得矩阵如下；3．最优纯策略例5：某单位在秋天要决定冬季取暖用煤贮量问题，在正常的冬季气温下要消耗15吨，但在较暖与较冷的冬季需要10吨和20吨，假定煤的价格随着冬季寒冷程度而有所变动，设在较暖的、正常的、较冷的冬季气温下分别为每吨1000元，1500元，2000元，又设在秋季煤价是每吨1000元，在没有关于当年冬季准确的气象预报条件下，秋季贮煤多少吨才较合理?故博弈的解为(3，3)，即秋季贮煤20吨合理。(决策论中的悲观准则)3．最优纯策略例6：甲、乙双方谈判签订一项合同，甲方的“要价”是25万元，而乙方的“出价”是20万元，谈判陷于僵局。为打破僵局，双方约定，再各报一个价。以下述价格成交：谁让步多，取谁出的价；如果双方让步相同，则取双方报价的中间值。问甲、乙双方应如何报价?最后的成交价是多少?解显然，甲、乙双方的报价都在20万元到25万元之间。不妨取整数值，甲、乙各有6个策略：报价20,21,…,25(单位：万元)。由约定知，甲的支付矩阵可用表所示。(23，22)是鞍点。甲方的最优纯策略是要价23万元，乙方的最优纯策略是出价22万元，双方的让步相同(甲方降低2万元，乙方提高2万元)，最后的成交价是22.5万元。§2.矩阵博弈（MatrixGames）4．混合策略一般情况下,二人零和博弈有:用多大概率选取各个纯策略?ijminjijnjmiaa1111maxminminmax定义1：对于支付矩阵A=(aij)mxn,局中人1的一个混合策略就是一组数xi≥0,i=1,2,…,m,满足：局中人2的一个混合策略就是一组数yj≥0,j=1,2,…,n,满足：miix11nijy11设X=(x1,x2,…,xm)和Y=(y1,y2,…,yn)分别为局中人1和局中人2的混合策略，则局中人1选择策略i,局中人2选择策略j，并且支付为aij的概率为xiyj,局中人1的期望支付为：minjjiijyxa11§2.矩阵博弈（MatrixGames）4．混合策略定义2：称数学期望E(X,Y)=为局中人1的赢得，-E(X,Y)为局中人2的赢得，而(X,Y)称为混合局势。定义3：设S1*是满足xi≥0的一切X=(x1,x2,…,xm)的混合策略集，S2*是满足yi≥0的一切Y=(y1,y2,…,yn)的混合策略集，即S1*={X}，S2*={Y}，对于给定的一个博弈G={S1,S2,A},称G*={S1*,S2*,E}为G的混合扩充。§2.矩阵博弈（MatrixGames）4．混合策略对于局中人2，若采取混合策略Y，则可能支出：因此他应选取Y，使支出最小：对于局中人1，若采取混合策略X，则只能希望赢得：因此他应选取X，使赢得最大：§2.矩阵博弈（MatrixGames）4．混合策略定理1：对于给定的博弈G,有：定理2：（最小最大值定理、博弈论基本定理）对于一切矩阵博弈，都有：定义4：设G*={S1*,S2*,E}为博弈G={S1,S2,A}的混合扩充，如果有混合局势(X*,Y*),使：则称V为博弈G的值，而混合局势称为G在混合策略下的解。而X*与Y*分别称为局中人1和局中人2的最优解。§2.矩阵博弈（MatrixGames）4．混合策略定理3：若矩阵博弈G的值为V，则以下两组不等式的解就是局中人1和局中人2的最优策略：定理4：设混合局势(X*,Y*)是矩阵博弈G的最优解，记博弈值V=E(X*,Y*),则：(1)若(2)若(3)若(4)若§3.矩阵博弈的求解1.特殊情况下的解1).如果有鞍点，则鞍点就是最优解。2).如果没有鞍点，但事先知道均不为零，则可将两组不等式化成线性方程组来求解。例1.齐王赛马：没有鞍点，且各个策略出现的可能性均不为零。解:令则有线性方程组：ATX=V,AY=V,§3.矩阵博弈的求解各方程相加，得：因为:)61,61,61,61,61,61(),61,61,61,61,61,61(XYvxxxxxx6)(6654321miix11所以v=1,代入方程组2得：000001101000010100001001000110010010111111~000001202000020200002002000220020020111111~111111311111131111113111111311111131111111~111111311111131111113111111311111131111113),(BA§3.矩阵博弈的求解例2：设解:无鞍点，且混合策略的各分量不为零，求最优混合策略.§3.矩阵博弈的求解3).可降低矩阵阶数求解例3：给定一个矩阵博弈G={S1,S2,A},求博弈G的值与解。其中：若所给矩阵中i行的各个元素比j行各元素小，则对局中人1来说策略i明显不如策略j,称纯策略j优超纯策略j，同理，若i列的元素比j列的对应元素大，则对局中人2来说策略j优超策略i。而明显不利策略出现的概率为零。§3.