十一章节博弈模型.ppt

第十一章 博弈模型,11.1 进攻与撤退的抉择（非合作对策） 11.5 效益的合理分配 （合作对策）,对策论(博弈论)简介,例1：孙膑：田忌赛马 战国时期齐王欲与大将田忌赛马，双方约定每人挑选上、中、下三个等级的马各一匹进行比赛，每局赌金为一千金。齐王同等级的马均比田忌的马略胜一筹，似乎必胜无疑。 田忌的朋友给他出了一个主意，让他用下等马比齐王的上等马，上等马对齐王的中等马，中等马对齐王的下等马，结果田忌二胜一败，反而赢了一千金。,对策论(博弈论)简介,例2：囚徒困境 注：囚徒被分离审查，无法串供,最终会出现什么结局？,（5,0）表示(A,B)所判刑期,囚徒困境,假设每个囚徒都是聪明的，会发现,如果对方拒供，则自己供认便可立即获得释放，而自己拒供则会被判0.5年，因此供认是较好的选择。,如果对方供认，则自己供认将被判2年，而自己拒供则会被判5年，因此供认是较好的选择。,由于每个囚徒都发现供认是自己更好的选择，因此，博弈的稳定结果是两个囚徒都会选择供认(2,2)。这就是博弈的纳什均衡。,攻守同盟(0.5,0.5)？ 很难达成：隔离审查，每个人都担心对方背弃盟约。,占优均衡与纳什均衡, 上策（占优）均衡是指不管你选择什么策略，我所选择的是最好的；不管我选择什么策略，你所选择的是最好的。, 纳什均衡是指给定你的策略，我所选择的是最好的；给定我的策略，你所选择的是最好的。,所谓均衡是指一种稳定的结局，当这种结局出现的时候，所有的对局者都不想再改变他们所选择的策略。,两个囚徒都会选择供认，不仅是纳什均衡，也是占优均衡。,单一决策主体,决策变量目标函数约束条件,决策主体的决策行为发生直接相互作用 (相互影响),博弈模型,非合作博弈,合作博弈,三要素,多个决策主体,决策问题（Decision Problem）,军事、政治、经济、企业管理和社会科学中应用广泛,诺曼底战役(1944.6.6-8.25)是目前为止世界上最大的两栖登陆作战。美英军队开辟第二战场，重返欧洲大陆，使第二次世界大战的战略态势发生了根本性变化。,1944年6月初，盟军在诺曼底登陆成功. 到8月初的形势：,背景,11.1 进攻与撤退的抉择,双方应该如何决策 ？,模型假设,博弈参与者为两方（盟军和德军）,盟军有3种使用其预备队的行动：强化缺口，原地待命，东进；德军有2种行动：向西进攻或向东撤退.,博弈双方完全理性，目的都是使战斗中己方获得的净胜场次（胜利场次减去失败场次）尽可能多.,完全信息静态博弈,共同知识(以上信息双方共有),双方同时做出决策,博弈模型,博弈参与者集合N=1,2(1为盟军，2为德军),用u1(a1，a2)表示对盟军产生的结果，即净胜场次，称为盟军的效用函数.,盟军行动a1 A1=1,2,3(强化缺口/原地待命/东进)； 德军行动a2 A2=1,2(进攻/撤退). (行动：即纯战略),支付矩阵 （Payoff Matrix）,完全竞争: 零和博弈 (常数和博弈),u2(a1，a2)对应 M,博弈的解：纳什均衡 (NE: Nash Equilibrium),本案例,(纯战略)纳什均衡,NE: 单向改变战略不能提高自己效用，即每一方的战略对于他方的战略而言都是最优的.,(纯)NE: a*=(a1*, a2*) =(2, 2),非常数和博弈(双矩阵表示),例：求纯NE的划线法,不存在纯NE,混合战略（概率策略),盟军的混合战略集,期望收益,盟军,德军,S1=p=(p1, p2, p3) | ,德军的混合战略集,S2= q=(q1, q2) | ,模型求解,理性推理：不管自己怎么做，另一方总是希望使自己得分尽量低. （二人零和博弈，完全竞争）,盟军,德军,设辅助变量x=min pM,转化为线性规划,最优策略：使得自己最小赢得达到最大,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），而德军选择向西（行动1），结果德军大败.,模型评述,多人(或非常数和)博弈问题，一般不能用上面的线性规划方法求解，而通过纳什均衡的定义求解.,纳什均衡存在性：在任何一个有限个博弈方存在的有限博弈中，都至少存在一个(混合策略)纳什均衡 。,冯.诺依曼极小化极大值定理：二人零和游戏博弈双方的任何一方，选择极小化“极大损失” 的(混合)策略（从统计角度来看）是最优策略。,博弈论小史,1928年，冯·诺依曼证明了博弈论的基本原理（极小化极大定理），标志博弈论诞生。 1944年，冯·诺依曼和摩根斯坦共著博弈论与经济行为将二人博弈推广到n人博弈结构并将博弈论系统的应用于经济领域。 19501951年，约翰·福布斯·纳什（John Forbes Nash Jr）在博士论文中利用不动点定理证明了纳什均衡的存在性 ，从而奠定了这一学科的基础和理论体系。,冯·诺依曼的辉煌人生,John Von Neumann (19031957 ) 美籍匈牙利人. 计算机之父，博弈论之父, 量子理论之父. 学习：瑞士苏黎世大学，匈牙利布达佩斯大学 工作：德国柏林大学, 普林斯顿大学 美国国家科学院院士 ，美国数学会主席。,约翰·纳什的跌宕人生,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妄想型精神分裂症 1964回到Princeton， “我在这里得到庇护，因此没有变成无家可归。” 1978获得冯诺依曼奖(Nash equilibria) 1994年获得诺贝尔经济学奖 现为 Princeton “高级研究数学家” (非正式职位) 2002年 ，来北京出席24届世界数学家大会，美丽心灵获得4项奥斯卡金像奖； 2008年，任青岛大学名誉教授。,习题,P411 ex1，ex3,11.5 效益的合理分配(合作对策),例,甲乙丙三人合作经商，若甲乙合作获利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的获利,公理化方法,s子集 s中的元素数目， Si 包含i的所有子集,由s决定的“贡献”的权重, i 对合作s 的“贡献”,Shapley合作对策,权重构成：|s|可能取值1n, 先按此n等分；|s|=k的含有i的子集个数有 个，再按此等分1/n。,合作的获利真的不少于他单干时的获利吗,对每一iI，有,求证:,证明:,|s|=K时，包含i的子集s共有 个,故,从而,又根据性质，有,故有,三人(I=1,2,3)经商中甲的分配x1的计算,1/3 1/6 1/6 1/3,1 1 2 1 3 I,1 7 5 11,0 1 1 4,1 6 4 7,1/3 1 2/3 7/3,x1=13/3,类似可得 x2=23/6, x3=17/6,1 2 2 3,合作对策的应用案例 污水处理费用的合理分担,污水处理，排入河流.,三城镇可单独建处理厂，或联合建厂(用管道将污水由上游城镇送往下游城镇).,Q污水量，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=73,D5,城3建议：d1 按 5:3:5分担, d2,d3由城1,2担负,城2建议：d3由城1,2按 5:3分担, d2由城1担负,城1计算：城3分担 d15/13=174C(1),不同意!,D5如何分担？,特征函数v(s)联合(集s)建厂比单独建厂节约的投资,三城从节约投资v(I)中得到的分配,Shapley合作对策,计算城1从节约投资中得到的分配x1,x1 =19.7,城1 C(1)-x1=210.4, 城2 C(2)-x2=127.8, 城3 C(3)-x3=217.8,x2 =32.1, x3=12.2,x2最大，如何解释？,优点：公正、合理，有公理化基础.,如n个单位治理污染, 通常知道第i方单独治理的投资yi 和n方共同治理的投资Y, 及第i方不参加时其余n-1方的投资zi (i=1,2, ,n). 确定共同治理时各方分担的费用.,其他v(s)均不知道, 无法用Shapley合作对策求解,Shapley合作对策小结,若定义特征函数为合作的获利(节约的投资)，则有,缺点：需要知道所有合作的获利, 即要定义I=1,2,n的所有子集(共2n-1个)的特征函数，实践中难以得到.,求解合作对策的其他方法,例. 甲乙丙三人合作经商，若甲乙合作获利7元， 甲丙合作获利5元，乙丙合作获利4元，三人 合作获利11元. 问三人合作时如何分配获利？,（1）协商解,将剩余获利 平均分配,模型,以n-1方合作的获利为下限,求解, xi 的下限,（2）纳什均衡解,为现状点（谈判时的威慑点）,在此基础上“均匀地”分配全体合作的获利B,模型,只知全体合作的获利B和各自谈判底线,（3）最小距离解,模型,第i 方的边际效益,若令,（4）满意解,di现状点(最低点) ei理想点(最高点),模型,（5）Raiffi 解,与协商解x=(5,4,2)比较,求解合作对策的6种方法（可分为三类）,Shapley合作对策,A类,B类,协商解,Nash解,最小距离解,例：有一资方(甲)和二劳方(乙,丙), 仅当资方与至少一劳方合作时才获利10元，应如何分配该获利？,Raiffi解,C类,B类：计算简单，便于理解，可用于各方实力相差不大的情况；一般来说它偏袒强者.,C类： 考虑了分配的上下限，又吸取了Shapley的思想，在一定程度上保护弱者.,A类：公正合理；需要信息多，计算复杂.,求解合作对策的三类方法小结,一句话小结,共赢是合作的前提。 提出方案之前先要确定原则(公理)。 一些局部看起来合理的方案，事实上可能是违反原则的。,习题,P412ex11 补充题：用协商解和纳什均衡解方法讨论P392“污水处理费用”问题,