《十一章节博弈模型》由会员分享，可在线阅读，更多相关《十一章节博弈模型（41页珍藏版）》请在金锄头文库上搜索。
1、十一章节博弈模型Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望对策论(博弈论)简介例例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场东进无无战斗斗盟盟军胜2场原地待命原地
7、待命无无战斗斗盟盟军胜1场强强化缺口化缺口向向东撤退撤退向西向西进攻攻盟盟军德德军模型假设模型假设 博弈参与者为两方（盟军和德军）博弈参与者为两方（盟军和德军） 盟军有盟军有3种使用其预备队的行动：强化缺口，原地待种使用其预备队的行动：强化缺口，原地待命，东进；德军有命，东进；德军有2种行动：向西进攻或向东撤退种行动：向西进攻或向东撤退. 博弈双方博弈双方完全理性完全理性，目的都是使战斗中己方获得，目的都是使战斗中己方获得的净胜场次（胜利场次减去失败场次）尽可能多的净胜场次（胜利场次减去失败场次）尽可能多. 盟盟军胜1场盟盟军败2场东进无无战斗斗盟盟军胜2场原地待命原地待命无无战斗斗盟盟军胜1
8、场强强化缺口化缺口向向东撤退撤退向西向西进攻攻盟盟军德德军完全信息完全信息静态博弈静态博弈 共同知识共同知识(以上信息双方共有以上信息双方共有) 双方同时做出决策双方同时做出决策博弈模型博弈模型 博弈参与者集合博弈参与者集合N=1,2(1为盟军，为盟军，2为德军为德军) 用用u1(a1，a2)表示对盟军产生的结果，即净胜场次，表示对盟军产生的结果，即净胜场次，称为盟军的称为盟军的效用函数效用函数. 盟盟军胜1场盟盟军败2场东进无无战斗斗盟盟军胜2场原地待命原地待命无无战斗斗盟盟军胜1场强强化缺口化缺口向向东撤退撤退向西向西进攻攻盟盟军德德军 盟军行动盟军行动a1 A1=1,2,3(强化缺口强化
9、缺口/原地待命原地待命/东进东进)； 德军行动德军行动a2 A2=1,2(进攻进攻/撤退撤退). (行动：即纯战略行动：即纯战略)支付矩阵支付矩阵（Payoff Matrix） 完全竞争完全竞争: 零和博弈零和博弈 (常数和博弈常数和博弈) u2(a1，a2)对应对应 M博弈的解博弈的解：纳什均衡纳什均衡 (NE: Nash Equilibrium)本案例本案例(纯战略纯战略)纳什均衡纳什均衡NE: 单向改变战略不能提高自己效用，单向改变战略不能提高自己效用，即每一方的战略即每一方的战略对于他方的战略而言都是最优的对于他方的战略而言都是最优的. (纯纯)NE: a*=(a1*, a2*) =(
10、2, 2) 非常数和非常数和博弈博弈(双矩双矩阵表示阵表示)例：求例：求纯纯NE的的划线法划线法不存在不存在纯纯NE混合战略（概率策略混合战略（概率策略) 盟军的盟军的混合战略混合战略集集 期望收益期望收益盟军盟军德军德军 S1=p=(p1, p2, p3) | 德军的德军的混合战略混合战略集集 S2= q=(q1, q2) | 模型求解模型求解理性推理：理性推理：不管自己怎么做，另一方总是希望使自不管自己怎么做，另一方总是希望使自己得分尽量低己得分尽量低.（二人零和博弈，完全竞争）（二人零和博弈，完全竞争） 盟军盟军德军德军设辅助变量设辅助变量x=min pM,转化转化为线性规划为线性规划
11、最优策略：使得自己最小赢得达到最大最优策略：使得自己最小赢得达到最大 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, 转化为线性规划转化为线性规划极大极小化模型等价的线性规划模型混合策略似乎不太可行混合策略似乎不太可行! 但但概率概率可作为可作为参考参考. -现实现实：盟军让预备队原地待命（行动：盟军让预备队原地待命（行动2），而德军），而德军选择向西（行动选择向
12、西（行动1），结果德军大败），结果德军大败. 模型评述模型评述多人多人(或非常数和或非常数和)博弈问题，一般不能用上面的线性博弈问题，一般不能用上面的线性规划方法求解，而通过纳什均衡的定义求解规划方法求解，而通过纳什均衡的定义求解. 纳什均衡存在性：纳什均衡存在性：在任何一个有限个博弈方存在的在任何一个有限个博弈方存在的有限博弈中，都至少存在一个有限博弈中，都至少存在一个(混合策略混合策略)纳什均衡纳什均衡 。冯冯.诺依曼极小化极大值定理诺依曼极小化极大值定理：二人零和游戏博弈双方：二人零和游戏博弈双方的任何一方，选择极小化的任何一方，选择极小化“极大损失极大损失” 的的(混合混合)策略策略（
13、从统计角度来看）是最优策略（从统计角度来看）是最优策略。博弈论小史博弈论小史1928年，冯诺依曼证明了博弈论的基本原理（极小化极大定理极小化极大定理），标志博弈论诞生。1944年，冯诺依曼和摩根斯坦共著博弈论与经济行为将二人博弈推广到n人博弈结构并将博弈论系统的应用于经济领域。19501951年，约翰福布斯纳什（John Forbes Nash Jr）在博士论文中利用不动点定理证明了纳什均衡的存在性 ，从而奠定了这一学科的基础和理论体系。 冯诺依曼的辉煌人生John Von Neumann (19031957 )美籍匈牙利人.计算机之父，博弈论之父, 量子理论之父.学习：瑞士苏黎世大学，匈牙利
14、布达佩斯大学工作：德国柏林大学, 普林斯顿大学 美国国家科学院院士 ，美国数学会主席。约翰约翰纳什的跌宕人生纳什的跌宕人生1928生生, 数学天才，性格孤僻，行为古怪数学天才，性格孤僻，行为古怪 本科硕士本科硕士(三年三年) Carnegie Mellon UniversityR.J. Duffin推荐信推荐信: This man is a genius. 1948 Princeton Univ (导师：导师：Albert Tucker )1950 博士论文博士论文Non-cooperative Games(27页页)1955 MIT工作工作1958妄想型精神分裂症妄想型精神分裂症1964回到
15、回到Princeton， “我在这里得到庇护，因我在这里得到庇护，因此没有变成无家可归。此没有变成无家可归。” 1978获得冯诺依曼奖获得冯诺依曼奖(Nash equilibria)1994年获得诺贝尔经济学奖年获得诺贝尔经济学奖现为现为 Princeton “高级研究数学家高级研究数学家” (非正式职非正式职位位)2002年年 ，来北京出席，来北京出席24届世界数学家大会，届世界数学家大会，美丽心灵美丽心灵获得获得4项奥斯卡金像奖；项奥斯卡金像奖；2008年，任青岛大学名誉教授。年，任青岛大学名誉教授。习题P411 ex1，ex311.5 效益的合理分配效益的合理分配( (合作对策合作对策)
16、 )例例甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，元，三人合作获利三人合作获利11元元. 又知每人单干获利又知每人单干获利1元元.问三人合作时如何分配获利？问三人合作时如何分配获利？记甲乙丙三人分配为记甲乙丙三人分配为解不唯一解不唯一(5，3，3)(4，4，3)(5，4，2)怎样分配怎样分配更合理？更合理？ (1) Shapley合作对策合作对策 I,v n人合作对策，人合作对策，v特征函数特征函数n人从人从v(I)得到的分配，满足得到的分配，满足v(s) 子集子集s的获利的获利公理化方法公理化
17、方法 s 子集子集 s中的元素数目，中的元素数目， Si 包含包含i的所有子集的所有子集由由 s 决定的决定的“贡献贡献”的权重的权重 Shapley值值 i 对合作对合作s 的的“贡献贡献”Shapley合作对策合作对策权重构成：|s|可能取值1n, 先按此n等分；|s|=k的含有i的子集个数有 个，再按此等分1/n。合作的获利真的不少于他单干时的获利吗合作的获利真的不少于他单干时的获利吗 对每一对每一iI，有，有 求证求证:证明证明:|s|=K时，包含时，包含i i的子集的子集s共有共有 个个 故故 从而从而 又根据性质，有又根据性质，有 故有故有 三人三人(I=1,2,3)经商中甲的分配
18、经商中甲的分配x1的计算的计算 1/3 1/6 1/6 1/31 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/61 2 2 3合作对策的应用案例合作对策的应用案例 污水处理费用的合理分担污水处理费用的合理分担20km38km河流河流三城镇地理位置示意图三城镇地理位置示意图123 污水处理，排入河流污水处理，排入河流.三城镇可单独建处理厂，三城镇可单独建处理厂，或联合建厂或联合建厂(用管道将污水用管道将污水由上游城镇送往下游城镇由上游城镇送往下游城镇).Q1=5Q3=5Q2=3Q污水量
19、，污水量，L管道长度管道长度建厂费用建厂费用P1=73Q0.712管道费用管道费用P2=0.66Q0.51L污水处理的污水处理的5 种方案种方案1）单独建厂）单独建厂总投资总投资2）1, 2合作合作3）2, 3合作合作4）1, 3合作合作总投资总投资总投资总投资合作不会实现合作不会实现5）三城合）三城合作总投资作总投资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分担分
20、担, 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如何分担？如何分担？特征函数特征函数v(s)联合联合(集集s)建厂比单独建厂节约的投资建厂比单独建厂节约的投资三三城从城从节约投资节约投资v(I)中得到的分配中得到的分配 Shapley合作对策合作对策计算计算城城1从从节约投资中得到的分配节约投资中得到的分配x11 1 2 1 3 I 0 40 0 640 0 0 250 4
21、0 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方不参加时其余方不参加时其余n-1方的方的投资投资zi (i
22、=1,2, ,n). 确定共同治理时各方分担的费用确定共同治理时各方分担的费用.其他其他v(s)均不知道均不知道, 无法用无法用Shapley合作对策合作对策求解求解Shapley合作对策小结合作对策小结若定义特征函数为合作的获利若定义特征函数为合作的获利(节约的投资节约的投资)，则有，则有缺点：缺点：需要知道所有合作的获利需要知道所有合作的获利, 即要定义即要定义I=1,2,n的的所有子集所有子集(共共2n-1个个)的特征函数，实践中的特征函数，实践中难以得到难以得到.设只知道设只知道无无 i 参加时参加时n-1方合作的获利方合作的获利全体合作的获利全体合作的获利求解合作对策的其他方法求解合
23、作对策的其他方法例例. 甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，三人元，三人合作获利合作获利11元元. 问三人合作时如何分配获利？问三人合作时如何分配获利？（1）协商解）协商解11将剩余获利将剩余获利 平均分配平均分配 模型模型以以n-1方合作的获利为下限方合作的获利为下限求解求解 xi 的下限的下限（2）纳什均衡解）纳什均衡解 为现状点（谈判时的威慑点）为现状点（谈判时的威慑点）在此基础上在此基础上“均匀地均匀地”分配全体合作的获利分配全体合作的获利B模型模型平均分配获利平均分配获利B2）N
24、ash解解 1）协商解）协商解只知全体合作的获利只知全体合作的获利B和各自和各自谈判底线谈判底线（3）最小距离解）最小距离解模型模型 第第i 方的边际效益方的边际效益若令若令3）最小距离解）最小距离解 1）协商解）协商解（4）满意解）满意解di现状点现状点(最低点最低点)ei理想点理想点(最高点最高点)模型模型4）基于满意度的解）基于满意度的解 1）协商解）协商解（5）Raiffi 解解与协商解与协商解x=(5,4,2)比较比较求解合作对策的求解合作对策的6种方法（可分为三类）种方法（可分为三类）Shapley合作对策合作对策A类类B类类协商解协商解Nash解解 最小距离解最小距离解满意解满意
25、解di现状现状, ei理想理想B类类4种方法相同种方法相同例：有一资方例：有一资方(甲甲)和二劳方和二劳方(乙乙,丙丙), 仅当资方与至少仅当资方与至少一劳方合作时才获利一劳方合作时才获利10元，应如何分配该获利？元，应如何分配该获利？Raiffi解解C类类B类：类：计算简单，便于理解，可用于各方实计算简单，便于理解，可用于各方实力相差不大的情况；一般来说它偏袒强者力相差不大的情况；一般来说它偏袒强者. C类：类： 考虑了分配的上下限，又吸取了考虑了分配的上下限，又吸取了Shapley的思想，在一定程度上保护弱者的思想，在一定程度上保护弱者.A类：类：公正合理；需要信息多，计算复杂公正合理；需要信息多，计算复杂.求解合作对策的三类方法小结求解合作对策的三类方法小结一句话小结共赢是合作的前提。提出方案之前先要确定原则(公理)。一些局部看起来合理的方案，事实上可能是违反原则的。习题P412ex11补充题：用协商解和纳什均衡解方法讨论补充题：用协商解和纳什均衡解方法讨论P392“污水处理费用污水处理费用”问题问题
