十一章节弈模型

1、第十一章第十一章 博弈模型博弈模型11.1 进攻与撤退的抉择进攻与撤退的抉择（非合作对策）（非合作对策）11.5 效益的合理分配效益的合理分配 （合作对策）（合作对策）对策论(博弈论)简介 例例1：孙膑：孙膑：田忌赛马田忌赛马 战国时期齐王欲与大将田忌赛马，双方约战国时期齐王欲与大将田忌赛马，双方约定每人挑选上、中、下三个等级的马各一定每人挑选上、中、下三个等级的马各一匹进行比赛，每局赌金为一千金。齐王同匹进行比赛，每局赌金为一千金。齐王同等级的马均比田忌的马略胜一筹，似乎必等级的马均比田忌的马略胜一筹，似乎必胜无疑。胜无疑。 田忌的朋友给他出了一个主意，让他用下田忌的朋友给他出了一个主意，让

2、他用下等马比齐王的上等马，上等马对齐王的中等马比齐王的上等马，上等马对齐王的中等马，中等马对齐王的下等马，结果田忌等马，中等马对齐王的下等马，结果田忌二胜一败，反而赢了一千金。二胜一败，反而赢了一千金。对策论(博弈论)简介嫌疑犯嫌疑犯b供认供认不供认不供认嫌疑犯嫌疑犯a 供认供认不供认不供认（2，2）（5，0）（0，5）（0.5，0.5） 例2：囚徒困境囚徒困境 注：囚徒被分离审查，无法串供最终会出现什么结局？最终会出现什么结局？（5,0）表示）表示(a,b)所判刑期所判刑期囚徒困境囚徒困境假设每个囚徒都是聪明的，会发现假设每个囚徒都是聪明的，会发现如果对方拒供，则自己供认便可立即获得释放，而

3、自己拒供则会被判0.5年，因此供认是较好的选择。如果对方供认，则自己供认将被判2年，而自己拒供则会被判5年，因此供认是较好的选择。 由于每个囚徒都发现供认是自己更好的选择，因此，博弈的稳定由于每个囚徒都发现供认是自己更好的选择，因此，博弈的稳定结果是两个囚徒都会选择供认结果是两个囚徒都会选择供认(2,2)(2,2)。这就是博弈的。这就是博弈的纳什均衡纳什均衡。攻守同盟攻守同盟(0.5,0.5)？很难达成：隔离审查，每个人都担心对方背弃盟约。很难达成：隔离审查，每个人都担心对方背弃盟约。占优均衡与纳什均衡 上策（占优）均衡上策（占优）均衡是指不管你选择什么策略，我所选是指不管你选择什么策略，我所

4、选择的是最好的；不管我选择什么策略，你所选择的是最择的是最好的；不管我选择什么策略，你所选择的是最好的。好的。 纳什均衡纳什均衡是指给定你的策略，我所选择的是最好是指给定你的策略，我所选择的是最好的；给定我的策略，你所选择的是最好的。的；给定我的策略，你所选择的是最好的。 所谓均衡是指一种稳定的结局，当这种结局出现的时候，所谓均衡是指一种稳定的结局，当这种结局出现的时候，所有的对局者都不想再改变他们所选择的策略所有的对局者都不想再改变他们所选择的策略。 两个囚徒都会选择供认，不仅是两个囚徒都会选择供认，不仅是纳什均衡，纳什均衡，也是也是占优均衡占优均衡。单一决策主体单一决策主体决策变量决策变量

5、目标函数目标函数约束条件约束条件决策主体的决策决策主体的决策行为发生直接相行为发生直接相互作用互作用 (相互影响相互影响)博弈模型博弈模型非合作博弈非合作博弈合作博弈合作博弈三要素三要素博弈模型博弈模型(game theory)多个决策主体多个决策主体优化模型优化模型(optimization)决策问题（decision problem）静态、动态静态、动态信息完全、不完全信息完全、不完全军事、政治、经济、企业管理和社会科学中应用广泛军事、政治、经济、企业管理和社会科学中应用广泛诺曼底战役诺曼底战役(1944.6.6-8.25)(1944.6.6-8.25)是目前为是目前为止世界上最大的两栖登

6、陆作战。美英止世界上最大的两栖登陆作战。美英军队开辟第二战场，重返欧洲大陆，军队开辟第二战场，重返欧洲大陆，使第二次世界大战的战略态势发生了使第二次世界大战的战略态势发生了根本性变化。根本性变化。 1944年年6月初，盟军在诺曼底登陆成功月初，盟军在诺曼底登陆成功. 到到8月初的形势：月初的形势： 背背景景11.1 进攻与撤退的抉择进攻与撤退的抉择双方应该如何决策双方应该如何决策 ？强化缺强化缺口口盟军盟军(预备队预备队)撤退撤退进攻进攻德军德军盟军盟军(加加)盟军盟军(英英)盟军盟军(美一美一)盟 军盟 军(美三美三)东进东进原地原地待命待命盟军胜盟军胜1场场盟军败盟军败2场场东进东进无战斗

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

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

9、胜盟军胜1场场强化缺口强化缺口向东撤退向东撤退向西进攻向西进攻盟军盟军德军德军12020123ijmm 盟军行动盟军行动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

10、*211*2*11aaauaauaaauaau(纯战略纯战略)纳什均衡纳什均衡ne: 单向改变战略不能提高自己效用，单向改变战略不能提高自己效用，即每一方的战略即每一方的战略对于他方的战略而言都是最优的对于他方的战略而言都是最优的. 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混合战略（概率策略混合战略（概率策略) 盟军的盟军的混合战略混合战略集集 期望收益期望收益盟军

11、盟军德军德军 s1=p=(p1, p2, p3) | 311, 10iiipp德军的德军的混合战略混合战略集集 s2= q=(q1, q2) | 211, 10iiiqqtsppmq1maxtsqpmq2min),(),(),(1231211qpuqpuqmppmqqpuijjijit模型求解模型求解理性推理：理性推理：不管自己怎么做，另一方总是希望使自不管自己怎么做，另一方总是希望使自己得分尽量低己得分尽量低.（二人零和博弈，完全竞争）（二人零和博弈，完全竞争） 盟军盟军德军德军tsppmq1maxtsqpmq2min设辅助变量设辅助变量x=min pm,转转化为线性规划化为线性规划 最优策

12、略：使得自己最小赢得达到最大最优策略：使得自己最小赢得达到最大 max min pm min max 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混合策略似乎不太可行混合策略似乎不太可行! 但但概率概率可作为可作为参考参考. -现实现实：盟军

13、让预备队原地待命（行动：盟军让预备队原地待命（行动2），而德军），而德军选择向西（行动选择向西（行动1），结果德军大败），结果德军大败. 模型评述模型评述多人多人(或非常数和或非常数和)博弈问题，一般不能用上面的线性博弈问题，一般不能用上面的线性规划方法求解，而通过纳什均衡的定义求解规划方法求解，而通过纳什均衡的定义求解. 纳什均衡存在性：纳什均衡存在性：在任何一个有限个博弈方存在的在任何一个有限个博弈方存在的有限博弈中，都至少存在一个有限博弈中，都至少存在一个(混合策略混合策略)纳什均衡纳什均衡 。冯冯.诺依曼极小化极大值定理诺依曼极小化极大值定理：二人零和游戏博弈双方：二人零和游戏博弈双方

14、的任何一方，选择极小化的任何一方，选择极小化“极大损失极大损失” 的的(混合混合)策略策略（从统计角度来看）是最优策略（从统计角度来看）是最优策略。博弈论小史博弈论小史 1928年，冯诺依曼证明了博弈论的基本原理（极小化极大定理极小化极大定理），标志博弈论诞生。 1944年，冯诺依曼和摩根斯坦共著博弈论与经济行为将二人博弈推广到n人博弈结构并将博弈论系统的应用于经济领域。 19501951年，约翰福布斯纳什（john forbes nash jr）在博士论文中利用不动点定理证明了纳什均衡的存在性 ，从而奠定了这一学科的基础和理论体系。 冯诺依曼的辉煌人生 john von neumann (1

15、9031957 ) 美籍匈牙利人. 计算机之父，博弈论之父, 量子理论之父. 学习：瑞士苏黎世大学，匈牙利布达佩斯大学 工作：德国柏林大学, 普林斯顿大学 美国国家科学院院士 ，美国数学会主席。约翰约翰纳什的跌宕人生纳什的跌宕人生 1928生生, 数学天才，性格孤僻，行为古怪数学天才，性格孤僻，行为古怪 本科硕士本科硕士(三年三年) carnegie mellon university r.j. duffin推荐信推荐信: this man is a genius. 1948 princeton univ (导师：导师：albert tucker ) 1950 博士论文博士论文non-coop

16、erative games(27页页) 1955 mit工作工作 1958妄想型精神分裂症妄想型精神分裂症 1964回到回到princeton， “我在这里得到庇护，因我在这里得到庇护，因此没有变成无家可归。此没有变成无家可归。” 1978获得冯诺依曼奖获得冯诺依曼奖(nash equilibria) 1994年获得诺贝尔经济学奖年获得诺贝尔经济学奖 现为现为 princeton “高级研究数学家高级研究数学家” (非正式职非正式职位位) 2002年年 ，来北京出席，来北京出席24届世界数学家大会，届世界数学家大会，美丽心灵美丽心灵获得获得4项奥斯卡金像奖；项奥斯卡金像奖； 2008年，任青岛

17、大学名誉教授。年，任青岛大学名誉教授。习题 p411 ex1，ex311.5 效益的合理分配效益的合理分配( (合作对策合作对策) )11321xxx457323121xxxxxx例例甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，元，三人合作获利三人合作获利11元元. 又知每人单干获利又知每人单干获利1元元.问三人合作时如何分配获利？问三人合作时如何分配获利？记甲乙丙三人分配为记甲乙丙三人分配为),(321xxxx 解不唯一解不唯一(5，3，3)(4，4，3)(5，4，2)1,321xxx怎样分配怎

18、样分配更合理？更合理？)(1ivxniiniivxi, 2 , 1),(2121210sssvsvssvv),()()()(,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 决定的

19、决定的“贡献贡献”的权重的权重 shapley值值)()(isvsv i 对合作对合作s 的的“贡献贡献”)(sishapley合作对策合作对策权重构成：|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 从而从而

20、 ( )( )( )v sv s iv i 又根据性质，有又根据性质，有 (| |) ( )( )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合作对策的应用案例合作对策

21、的应用案例 污水处理费用的合理分担污水处理费用的合理分担20km38km河流河流三城镇地理位置示意图三城镇地理位置示意图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. 0c3653836

22、6. 0)53(73)3 , 2(51. 0712. 0c46358566. 0)55(73) 3 , 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）三城合）三城合作总投

23、资作总投资d5最小最小, 应联合建厂应联合建厂 建厂费：建厂费：d1=73 (5+3+5)0.712=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(16

24、0) 2(230) 1 (ccc0)3()2()1(,0)(vvvv3 ,2, 1i集合特征函数特征函数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从从节约投资中得到的分配节约投资

25、中得到的分配x1)1()()(svsvsw)(sws) 1()(svsv) 1(sv)(svs1 1 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个单位治理污染个单位治理污染, 通常知道第通常知

26、道第i方单独治理的投资方单独治理的投资yi 和和n方共同治理的投资方共同治理的投资y, 及第及第i方不参加时其余方不参加时其余n-1方的方的投资投资zi (i=1,2, ,n). 确定共同治理时各方分担的费用确定共同治理时各方分担的费用.iijjzyiiv)(其他其他v(s)均不知道均不知道, 无法用无法用shapley合作对策合作对策求解求解shapley合作对策小结合作对策小结若定义特征函数为合作的获利若定义特征函数为合作的获利(节约的投资节约的投资)，则有，则有,)(),()(yyivniivnii1210缺点：缺点：需要知道所有合作的获利需要知道所有合作的获利, 即要定义即要定义i=1

27、,2,n的的所有子集所有子集(共共2n-1个个)的特征函数，实践中难以得到的特征函数，实践中难以得到.),(nbbb1记设只知道设只知道)(iivbi无无 i 参加时参加时n-1方合作的获利方合作的获利)(ivb及全体合作的获利全体合作的获利021inxxxxxb),(的分配求各方对获利),(),7 , 5 , 4(11321xxxxbb求，即已知求解合作对策的其他方法求解合作对策的其他方法例例. 甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，三人元，三人合作获利合作获利11元元. 问三人合作时如何

28、分配获利？问三人合作时如何分配获利？（1）协商解）协商解tt0,0axba11nniiibxxbxxbx11将剩余获利将剩余获利 平均分配平均分配 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 在此基础上在此基

29、础上“均匀地均匀地”分配全体合作的获利分配全体合作的获利b模型模型0id)(1iiidbndx平均分配获利平均分配获利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现状点现状点(最低点最低点)ei理想点理想点(最高点最高点)模型模型iiiixexd,4）基于满意度的解）基于满意度的解 1）协商解）协商解iiixed , 0)(*iiiiiiideudxdedbu的比例分配中在按iiiiixxbxxx（5）raiffi 解解jjxbbnjj获利为方合作时的原来无参与当,1)(jininxxxxxjiijj, 1,) 1(2,2方再等分方平分，和先由11nnjxj得到再平均取,nj21ijjiiixnxnxnnx) 1(21211) 4 , 6 , 7