最新十一章节博弈模型幻灯片.ppt

《最新十一章节博弈模型幻灯片.ppt》由会员分享，可在线阅读，更多相关《最新十一章节博弈模型幻灯片.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、对策论(博弈论)简介 例例1：孙膑：孙膑：田忌赛马田忌赛马 战国时期齐王欲与大将田忌赛马，双方约战国时期齐王欲与大将田忌赛马，双方约定每人挑选上、中、下三个等级的马各一定每人挑选上、中、下三个等级的马各一匹进行比赛，每局赌金为一千金。齐王同匹进行比赛，每局赌金为一千金。齐王同等级的马均比田忌的马略胜一筹，似乎必等级的马均比田忌的马略胜一筹，似乎必胜无疑。胜无疑。 田忌的朋友给他出了一个主意，让他用下田忌的朋友给他出了一个主意，让他用下等马比齐王的上等马，上等马对齐王的中等马比齐王的上等马，上等马对齐王的中等马，中等马对齐王的下等马，结果田忌等马，中等马对齐王的下等马，结果田忌二胜一败，反而赢了

2、一千金。二胜一败，反而赢了一千金。模型假设模型假设 博弈参与者为两方（盟军和德军）博弈参与者为两方（盟军和德军） 盟军有盟军有3种使用其预备队的行动：强化缺口，原地种使用其预备队的行动：强化缺口，原地待命，东进；德军有待命，东进；德军有2种行动：向西进攻或向东撤退种行动：向西进攻或向东撤退. 博弈双方博弈双方完全理性完全理性，目的都是使战斗中己方获得，目的都是使战斗中己方获得的净胜场次（胜利场次减去失败场次）尽可能多的净胜场次（胜利场次减去失败场次）尽可能多. 盟军胜盟军胜1场场盟军败盟军败2场场东进东进无战斗无战斗盟军胜盟军胜2场场原地待命原地待命无战斗无战斗盟军胜盟军胜1场场强化缺口强化缺

3、口向东撤退向东撤退向西进攻向西进攻盟军盟军德军德军完全信息完全信息静态博弈静态博弈 共同知识共同知识(以上信息双方共有以上信息双方共有) 双方同时做出决策双方同时做出决策博弈模型博弈模型 博弈参与者集合博弈参与者集合N=1,2(1为盟军，为盟军，2为德军为德军) 用用u1(a1，a2)表示对盟军产生的结果，即净胜场次，表示对盟军产生的结果，即净胜场次，称为盟军的称为盟军的效用函数效用函数. 盟军胜盟军胜1场场盟军败盟军败2场场东进东进无战斗无战斗盟军胜盟军胜2场场原地待命原地待命无战斗无战斗盟军胜盟军胜1场场强化缺口强化缺口向东撤退向东撤退向西进攻向西进攻盟军盟军德军德军12020123ijm

4、M 盟军行动盟军行动a1 A1=1,2,3(强化缺口强化缺口/原地待命原地待命/东进东进)； 德军行动德军行动a2 A2=1,2(进攻进攻/撤退撤退). (行动：即纯战略行动：即纯战略)支付矩阵支付矩阵（Payoff Matrix） 完全竞争完全竞争: 零和博弈零和博弈 (常数和博弈常数和博弈) u2(a1，a2)对应对应 M博弈的解：博弈的解：纳什均衡纳什均衡 (NE: Nash Equilibrium)本案例本案例.2 , 1),(),(,3 , 2 , 1),(),(22*12*2*121*211*2*11aaauaauaaauaau(纯战略纯战略)纳什均衡纳什均衡NE: 单向改变战略不

5、能提高自己效用，单向改变战略不能提高自己效用，即每一方的战略即每一方的战略对于他方的战略而言都是最优的对于他方的战略而言都是最优的. 3 2( 1)(0)( 2)10202(0)(2)( 1)1ijMm(纯纯)NE: a*=(a1*, a2*) =(2, 2) 3,1,2,2,2,122121, 1M非常数和非常数和博弈博弈(双矩双矩阵表示阵表示)例：求例：求纯纯NE的的划线法划线法不存在不存在纯纯NE混合战略（概率策略混合战略（概率策略) 盟军的盟军的混合战略混合战略集集 期望收益期望收益盟军盟军德军德军 S1=p=(p1, p2, p3) | 311, 10iiipp德军的德军的混合战略混

6、合战略集集 S2= q=(q1, q2) | 211, 10iiiqqTSppMq1maxTSqpMq2min),(),(),(1231211qpUqpUqmppMqqpUijjijiT模型求解模型求解理性推理：理性推理：不管自己怎么做，另一方总是希望使自不管自己怎么做，另一方总是希望使自己得分尽量低己得分尽量低.（二人零和博弈，完全竞争）（二人零和博弈，完全竞争） 盟军盟军德军德军TSppMq1maxTSqpMq2min设辅助变量设辅助变量x=min pM,转转化为线性规划化为线性规划 最优策略：使得自己最小赢得达到最大最优策略：使得自己最小赢得达到最大 max min pM min max

7、 MqT (p*, q*): 混合混合(策略策略)纳什均衡纳什均衡(Mixed NE) p2*=3/5，p3*=2/5同理同理 q1*=1/5，q2*=4/5最优值为最优值为2/5最优值也为最优值也为2/5达到均衡达到均衡设设x=min pM, 转化为线性规划转化为线性规划极大极小化模型等价的线性规划模型1233max min(22,)pppp1233123max .22,1.xstxpppxpppp混合策略似乎不太可行混合策略似乎不太可行! 但但概率概率可作为可作为参考参考. -现实现实：盟军让预备队原地待命（行动：盟军让预备队原地待命（行动2），而德军），而德军选择向西（行动选择向西（行动

8、1），结果德军大败），结果德军大败. 模型评述模型评述多人多人(或非常数和或非常数和)博弈问题，一般不能用上面的线性博弈问题，一般不能用上面的线性规划方法求解，而通过纳什均衡的定义求解规划方法求解，而通过纳什均衡的定义求解. 纳什均衡存在性：纳什均衡存在性：在任何一个有限个博弈方存在的在任何一个有限个博弈方存在的有限博弈中，都至少存在一个有限博弈中，都至少存在一个(混合策略混合策略)纳什均衡纳什均衡 。冯冯.诺依曼极小化极大值定理诺依曼极小化极大值定理：二人零和游戏博弈双方：二人零和游戏博弈双方的任何一方，选择极小化的任何一方，选择极小化“极大损失极大损失” 的的(混合混合)策略策略（从统计角

9、度来看）是最优策略（从统计角度来看）是最优策略。博弈论小史博弈论小史 1928年，冯诺依曼证明了博弈论的基本原理（极小化极大定理极小化极大定理），标志博弈论诞生。 1944年，冯诺依曼和摩根斯坦共著博弈论与经济行为将二人博弈推广到n人博弈结构并将博弈论系统的应用于经济领域。 19501951年，约翰福布斯纳什（John Forbes Nash Jr）在博士论文中利用不动点定理证明了纳什均衡的存在性 ，从而奠定了这一学科的基础和理论体系。 冯诺依曼的辉煌人生 John Von Neumann (19031957 ) 美籍匈牙利人. 计算机之父，博弈论之父, 量子理论之父. 学习：瑞士苏黎世大学，

10、匈牙利布达佩斯大学 工作：德国柏林大学, 普林斯顿大学 美国国家科学院院士 ，美国数学会主席。约翰约翰纳什的跌宕人生纳什的跌宕人生 1928生生, 数学天才，性格孤僻，行为古怪数学天才，性格孤僻，行为古怪 本科硕士本科硕士(三年三年) Carnegie Mellon University R.J. Duffin推荐信推荐信: This man is a genius. 1948 Princeton Univ (导师：导师：Albert Tucker ) 1950 博士论文博士论文Non-cooperative Games(27页页) 1955 MIT工作工作 1958妄想型精神分裂症妄想型精神

11、分裂症 1964回到回到Princeton， “我在这里得到庇护，因我在这里得到庇护，因此没有变成无家可归。此没有变成无家可归。” 1978获得冯诺依曼奖获得冯诺依曼奖(Nash equilibria) 1994年获得诺贝尔经济学奖年获得诺贝尔经济学奖 现为现为 Princeton “高级研究数学家高级研究数学家” (非正式职非正式职位位) 2002年年 ，来北京出席，来北京出席24届世界数学家大会，届世界数学家大会，美丽心灵美丽心灵获得获得4项奥斯卡金像奖；项奥斯卡金像奖； 2008年，任青岛大学名誉教授。年，任青岛大学名誉教授。习题 P411 ex1，ex311.5 效益的合理分配效益的合

12、理分配( (合作对策合作对策) )11321xxx457323121xxxxxx例例甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，元，三人合作获利三人合作获利11元元. 又知每人单干获利又知每人单干获利1元元.问三人合作时如何分配获利？问三人合作时如何分配获利？记甲乙丙三人分配为记甲乙丙三人分配为),(321xxxx 解不唯一解不唯一(5，3，3)(4，4，3)(5，4，2)1,321xxx怎样分配怎样分配更合理？更合理？)(1Ivxniiniivxi, 2 , 1),(2121210sssvsvs

13、svv),()()()(,2, 1nI集合 (1) Shapley合作对策合作对策满足实函数，子集)(svIs I,v n人合作对策，人合作对策，v特征函数特征函数),(21nxxxxn人从人从v(I)得到的分配，满足得到的分配，满足v(s) 子集子集s的获利的获利| | 11()!(1)!1()!snnssw snnCniisvsvswxiSsi,),()()(21公理化方法公理化方法 s 子集子集 s中的元素数目，中的元素数目， Si 包含包含i的所有子集的所有子集)( sw由由 s 决定的决定的“贡献贡献”的权重的权重 Shapley值值)()(isvsv i 对合作对合作s 的的“贡献

14、贡献”)(si Shapley合作对策合作对策权重构成：|s|可能取值1n, 先按此n等分；|s|=k的含有i的子集个数有 个，再按此等分1/n。11knC合作的获利真的不少于他单干时的获利吗合作的获利真的不少于他单干时的获利吗 对每一对每一iI，有，有 ( )ixv i求证求证:证明证明:|s|=K时，包含时，包含i i的子集的子集s共有共有 个个 11KnC111| |111(| |)iKnKs Kns Sw sCnCn 故故1| |(|)(|)1iins SKsKs Sw sw s 从而从而 ( )( )( )v sv s iv i 又根据性质，有又根据性质，有 (| |) ( )( )

15、iis Sxw sv sv s i( )(|)( )isSv iwsvi 故有故有 三人三人(I=1,2,3)经商中甲的分配经商中甲的分配x1的计算的计算 1/3 1/6 1/6 1/3)1()()(svsvsw)( sws)1()(svsv)1(sv)(sv1S1 1 2 1 3 I1 7 5 11 0 1 1 4 1 6 4 7 1/3 1 2/3 7/3x1=13/3类似可得类似可得 x2=23/6, x3=17/6)1()()(11svsvswxSs1 2 2 3合作对策的应用案例合作对策的应用案例 污水处理费用的合理分担污水处理费用的合理分担20km38km河流河流三城镇地理位置示意

16、图三城镇地理位置示意图123 污水处理，排入河流污水处理，排入河流.三城镇可单独建处理厂，三城镇可单独建处理厂，或联合建厂或联合建厂(用管道将污水用管道将污水由上游城镇送往下游城镇由上游城镇送往下游城镇).Q1=5Q3=5Q2=3Q污水量，污水量，L管道长度管道长度建厂费用建厂费用P1=73Q0.712管道费用管道费用P2=0.66Q0.51L230)3(,160)2(,230573) 1 (712. 0CCC35020566. 0)35(73)2 , 1 (51. 0712. 0C36538366. 0)53(73)3 , 2(51. 0712. 0C46358566. 0)55(73) 3

17、 , 1 (51. 0712. 0C460)3() 1 (CC污水处理的污水处理的5 种方案种方案1）单独建厂）单独建厂620)3()2() 1 (1CCCD总投资总投资2）1, 2合作合作3）2, 3合作合作4）1, 3合作合作580)3()2 , 1 (2CCD总投资总投资595) 3 , 2() 1 (3CCD总投资总投资合作不会实现合作不会实现55638) 35(66. 020566. 0)535(73) 3 , 2 , 1 (51. 051. 0712. 05CD5）三城合）三城合作总投资作总投资D5最小最小, 应联合建厂应联合建厂 建厂费：建厂费：d1=73 (5+3+5)0.71

18、2=453 12 管道费：管道费：d2=0.66 50.51 20=30 23 管道费：管道费：d3=0.66 (5+3)0.51 38=73D5城城3建议：建议：d1 按按 5:3:5分担分担, d2,d3由城由城1,2担负担负城城2建议：建议：d3由城由城1,2按按 5:3分担分担, d2由城由城1担负担负城城1计算：计算：城城3分担分担 d1 5/13=174C(3), 城城2分担分担 d1 3/13+d3 3/8 =132C(1)不同意不同意! !D5如何分担？如何分担？230) 3(160) 2(230) 1 (CCC0)3()2()1 (,0)(vvvv3 ,2, 1I集合特征函数

19、特征函数v(s)联合联合(集集s)建厂比单独建厂节约的投资建厂比单独建厂节约的投资),(321xxxx 三三城从城从节约投资节约投资v(I)中得到的分配中得到的分配40350160230)2 , 1 ()2() 1 ()21 (CCCv 64556230160230) 3 , 2 , 1 () 3() 2() 1 ()(0) 31 (25365230160) 3 , 2() 3() 2() 32(CCCCIvvCCCv Shapley合作对策合作对策计算计算城城1从从节约投资中得到的分配节约投资中得到的分配x1)1()()(svsvsw)(sws) 1()(svsv) 1(sv)(svs1 1

20、 2 1 3 I 0 40 0 640 0 0 250 40 0 39 1 2 2 31/3 1/6 1/6 1/3 0 6.7 0 13 x1 =19.7,城城1 C(1)-x1=210.4, 城城2 C(2)-x2=127.8, 城城3 C(3)-x3=217.8三城在总投资三城在总投资556中的分担中的分担x2 =32.1, x3=12.2x2最大，如何解释？最大，如何解释？优点：优点：公正、合理，有公理化基础公正、合理，有公理化基础.如如n个单位治理污染个单位治理污染, 通常知道第通常知道第i方单独治理的投资方单独治理的投资yi 和和n方共同治理的投资方共同治理的投资Y, 及第及第i方

21、不参加时其余方不参加时其余n-1方的方的投资投资zi (i=1,2, ,n). 确定共同治理时各方分担的费用确定共同治理时各方分担的费用.iijjzyiIv)(其他其他v(s)均不知道均不知道, 无法用无法用Shapley合作对策合作对策求解求解Shapley合作对策小结合作对策小结若定义特征函数为合作的获利若定义特征函数为合作的获利(节约的投资节约的投资)，则有，则有,)(),()(YyIvniivnii1210缺点：缺点：需要知道所有合作的获利需要知道所有合作的获利, 即要定义即要定义I=1,2,n的的所有子集所有子集(共共2n-1个个)的特征函数，实践中难以得到的特征函数，实践中难以得到

22、.),(nbbb1记设只知道设只知道)(iIvbi无无 i 参加时参加时n-1方合作的获利方合作的获利)(IvB及全体合作的获利全体合作的获利021inxxxxxB),(的分配求各方对获利),(),7 , 5 , 4(11321xxxxbB求，即已知求解合作对策的其他方法求解合作对策的其他方法例例. 甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，三人元，三人合作获利合作获利11元元. 问三人合作时如何分配获利？问三人合作时如何分配获利？（1）协商解）协商解TT0,0AxbA11nniiibxxbxx

23、Bx11将剩余获利将剩余获利 平均分配平均分配 ixBnBbbnxBnxxiiiii1)(111),7 , 5 , 4(.Bb例模型模型以以n-1方合作的获利为下限方合作的获利为下限TTAxb求解求解iiibbnx11 xi 的下限的下限, 3),1 , 3 , 4(ixBx) 2 , 4 , 5() 1 , 1 , 1 ( xx（2）纳什均衡解）纳什均衡解 ),(1nddd记为现状点（谈判时的威慑点）为现状点（谈判时的威慑点）iiiiiidxBxdxs.t.)(xmaiixd 在此基础上在此基础上“均匀地均匀地”分配全体合作的获利分配全体合作的获利B模型模型0id)(1iiidBndx平均分

24、配获利平均分配获利B2）Nash解解 1）协商解）协商解只知全体合作的获利只知全体合作的获利B和各自和各自谈判底线谈判底线（3）最小距离解）最小距离解iiiiiixxBxxxs.t.)(nmi2模型模型 第第i 方的边际效益方的边际效益iibBx若令若令nBbbnxiii111),7 , 5 , 4(.Bb例)(1Bxnxxiii3）最小距离解）最小距离解 1）协商解）协商解, 6),4 , 6 , 7(Bxxi) 2 , 4 , 5 () 2 , 2 , 2 (xx1( ,)nxxxx记为 的上限(理想点)（4）满意解）满意解iiiiidedxu满意度Bxuiiis.t.)nmi(xmadi

25、现状点现状点(最低点最低点)ei理想点理想点(最高点最高点)模型模型iiiixexd,4）基于满意度的解）基于满意度的解 1）协商解）协商解iiixed , 0)(*iiiiiiideudxdedBu的比例分配中在按iiiiixxBxxx（5）Raiffi 解解jjxbBnjj获利为方合作时的原来无参与当,1)(jininxxxxxjiijj, 1,) 1(2,2方再等分方平分，和先由11nnjxj得到再平均取,nj21ijjiiixnxnxnnx) 1(21211) 4 , 6 , 7 (),1 , 3 , 4(xx与协商解与协商解x=(5,4,2)比较比较11),7 , 5 , 4(.Bb

26、例)1252,12113,324（x11iiixbbBn在基础上进行 的分配求解合作对策的求解合作对策的6种方法（可分为三类）种方法（可分为三类）Shapley合作对策合作对策A类类B类类!)!1()!()(nssnswniisvsvswxiSsi, 2 , 1),()()()(),(IvBiIvbi只需Issv),(需要所有协商解协商解)(1iiixBnxx下限ixNash解解 )(1iiidBndx现状id最小距离解最小距离解)(1Bxnxxiii上限ix满意解满意解)(iiiiiiiiideudxdedBudi现状现状, ei理想理想iiiixexd,iibBx,1bAxB类类4种方法相

27、同种方法相同例：有一资方例：有一资方(甲甲)和二劳方和二劳方(乙乙,丙丙), 仅当资方与至少仅当资方与至少一劳方合作时才获利一劳方合作时才获利10元，应如何分配该获利？元，应如何分配该获利？Raiffi解解C类类)(),(IvBiIvbi只需方再等分方平分，和先由上限对每个11,nnjxjj10)(),10,10, 0(),(.IvBbiIvbBi)67. 1 ,67. 1 ,67. 6().Shapley(xA)0 , 0 ,10(,xbBxii)0 , 0 ,10(1TTbAx)83. 0 ,83. 0 ,34. 8(xijjiiixnxnxnnxC) 1(21211).Raiffi()0

28、 ,0 ,10(xB类：类：计算简单，便于理解，可用于各方实计算简单，便于理解，可用于各方实力相差不大的情况；一般来说它偏袒强者力相差不大的情况；一般来说它偏袒强者. C类：类： 考虑了分配的上下限，又吸取了考虑了分配的上下限，又吸取了Shapley的思想，在一定程度上保护弱者的思想，在一定程度上保护弱者.A类：类：公正合理；需要信息多，计算复杂公正合理；需要信息多，计算复杂.求解合作对策的三类方法小结求解合作对策的三类方法小结一句话小结 共赢是合作的前提。 提出方案之前先要确定原则(公理)。 一些局部看起来合理的方案，事实上可能是违反原则的。习题 P412ex11 补充题：用协商解和纳什均衡解方法讨论补充题：用协商解和纳什均衡解方法讨论P392“污水处理费用污水处理费用”问题问题