《运筹学博弈论》PPT课件.ppt

《《运筹学博弈论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《运筹学博弈论》PPT课件.ppt（63页珍藏版）》请在三一办公上搜索。

1、,第10章 博弈论,10.1博弈论概述10.2完全信息静态博弈,第一节 博弈论概述,田忌赛马博弈华容道博弈,一、博弈论的产生和发展,1.博弈在中国,从孙子兵法到三十六计从田忌赛马到孙庞斗智从运筹帷幄到韬光养晦从曹刿论战到论持久战,2.博弈论的开山之作1943年，冯诺依曼和摩根斯顿发表博弈论和经济行为的一书，,标志着博弈论作为一门独立科学的开始，也标志着新古典经济学进入了一个新的发展阶段。,3.1994年三位获诺奖的博弈论学者,John Nash,John Harsany,Leihaden Selten,4.1996年诺贝尔经济学奖得主：詹姆斯莫里 斯：主要贡献：不对称信息条件下的激励理论,5.

2、2001年诺贝尔经济学奖得主：迈克尔斯宾塞：在不对称信息市场分析方面所做出开创性研究。,6.2005年二位获诺奖的博弈论学者,Robert Aumann,Thomas Shelling,10.1.2 博弈及博弈论,博弈就是策略对抗，或策略有关键作用的游戏博弈Game，博弈论Game Theory，Game即游戏、竞技游戏和经济等决策竞争较量的共同特征：规则、结果、策略选择，策略和利益相互依存，策略的关键作用 游戏下棋、猜大小 经济寡头产量决策、市场阻入、投标拍卖 政治、军事美国和伊拉克、以色列和巴勒斯坦,定义：博弈就是参与人（可能是个人，也可能是团体，如国家、企业、国际组织等）在一定得规则下，

3、同时或先或后，一次或多次，从各自允许选择的行动或战略中进行选择并加以实施，而取得相应结果（支付函数）的过程。都有一定的规则 都有一个结果 策略至关重要，游戏者不同的策略选择常会带来不同的游戏结果 策略和利益有相互依存性 博弈论：博弈论就是系统研究具有上述特征的博弈问题，寻求各博弈方合理选择战略情况下博弈的解，并对这些解进行讨论分析的理论。,博弈的分类及对应的均衡概念,10.2 完全信息静态博弈,10.2.1 策略型博弈模型及占优战略博弈10.2.2 重复剔除的占优战略博弈10.2.3 纳什均衡,10.2.1 策略型博弈模型及占优战略博弈,非合作博弈模型从模型自身形式上可分为扩展型和策略型两种，

4、一般用策略型模型描述完全信息静态博弈模型。构成策略型博弈模型的三个要素:局中人、策略、支付函数,参与人或局中人(Players)：独立决策、独立承担博弈结果的个人或组织博弈规则面前博弈方之间平等，不因博弈方之间权利、地位的差异而改变博弈方数量对博弈结果和分析有影响根据博弈方数量分单人博弈、两人博弈、多人博弈等。最常见的是两人博弈，单人博弈是退化的博弈,策略或战略（strategies）：博弈中各博弈方的选择内容。策略有定性定量、简单复杂之分不同博弈方之间不仅可选策略不同，而且可选策略数量也可不同有限博弈：每个博弈方的策略数都是有限的无限博弈：至少有某些博弈方的策略有无限多个,支付函数(Payo

5、ffs function)：各博弈方从博弈中所获得的利益。得益对应博弈的结果，也就是各博弈方策略的组合得益是各博弈方追求的根本目标及行为和判断的主要依据根据得益的博弈分类：零和博弈、常和博弈、变和博弈,例10.1 囚徒困境博弈,囚徒的困境是图克（Tucker）1950年提出的该博弈是博弈论最经典、著名的博弈该博弈本身讲的是一个法律刑侦或犯罪学方面的问题，但可以扩展到许多经济问题，以及各种社会问题，可以揭示市场经济的根本缺陷,基本模型,经典的囚徒困境如下：警方逮捕甲、乙两名嫌疑犯，但没有足够证据指控二人入罪。于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供以下相同的选择：若一人认罪并作证检举

6、对方（相关术语称“背叛”对方），而对方保持沉默，此人将即时获释，沉默者将判监8年。若二人都保持沉默（相关术语称互相“合作”），则二人同样判监1年。若二人都互相检举（互相“背叛”），则二人同样判监5年。,囚徒困境,囚徒A,囚徒 B,坦白,抵赖,坦白,抵赖,坦白是A的占优战略,坦白是B的占优战略,占优策略(上策)均衡,占优策略(上策)通俗来说是：“我所做的是不管你做什么我所能做的最好的”“你所做的是不管我做什么你所能做的最好的”占优策略均衡指博弈中的所有参与者的占优策略组合所构成的均衡。,囚徒困境（PrisonersDilemma）,只达到效率很差的个体理性解，没有实现团体理性解。前者是稳定的，是

7、自动实施的；尽管团体理性解对大家都好，但它是不能自动实施的，需要改变条件。,提示：该博弈揭示了个体理性与团体理性之间的矛盾。从个体利益出发的行为往往不能实现团体的最大利益，同时也揭示了个体理性本身的内在矛盾从个体利益出发的行为最终也不一定能真正实现个体的最大利益，甚至得到相当差的结果。,10.2.2 重复剔除的占优战略均衡,首先找出某一博弈参与人的严格劣战略，将它剔除掉，重新构造一个不包括已剔除战略的新的博弈；然后继续剔除这个新的博弈中某一参与人的严格劣战略；重复进行这一过程，直到剩下唯一的参与人战略组合为止。这个唯一剩下的参与人战略组合，就是这个博弈的均衡解，称为“重复剔除的占优战略均衡”(

8、iterated dominance equilibrium).,智猪博弈：假设猪圈里有两头猪，一头大猪，一头小猪，猪圈的一端有一个猪食槽，另一端安装了一个按钮，控制猪食的供应。按一下按钮。将有10个单位的猪食进入猪食槽，供两头猪食用。两头猪面临选择的策略有两个：自己去按按钮或等待另一头猪去按按钮。如果某一头猪作出自己去按按钮的选择，它必须付出如下代价：第一，它需要收益相当于2个单位的成本；第二，由于猪食槽远离猪食，它将比另一头猪后到猪食槽，从而减少吃食的数量。大猪先到：大猪吃到9个单位，小猪吃到1个单位；小猪先到：小猪吃到4个单位，大猪吃到6个单位；同时到达：大猪吃到7个单位，小猪吃到3个单

9、位。,智猪博弈（大小猪博弈）,25,大猪,不按,按,不按,按,小猪,(4,4),(5,1),(9,-1),(0,0),局中人：大猪和小猪行动：按按钮吃东西,小猪的上策,27,双方力量不对等时的正确策略力量强：主动出击力量弱：等待，搭强者的便车。,28,智猪博弈的应用,政治博弈大国是大猪，小国是小猪资本市场大股东是大猪，小股东是小猪企业创新策略大企业是大猪，小企业是小猪,重复剔除的占优均衡,M,列先生,行先生,U,D,L,R,行：没有占优策略列：M严格优于R剔除 R,行：U优于D列：无占优策略剔除 D,M优于L,（U，M）是重复剔除的占优均衡,纳什均衡概念是现代博弈论的核心概念。它是以美国数学家

10、、经济学家纳什（Nash）的名字命名的，纳什在1950年的一篇论文中提出了纳什均衡的概念。,10.2.3 纳什（Nash）均衡,纳什均衡(Nash Equilibrium),通俗地说，纳什均衡的含义就是：给定你的策略，我的策略是最好的策略；给定我的策略，你的策略也是你的最好的策略。即双方在给定的策略下不愿意调整自己的策略。,1.纯战略Nash均衡策略空间：每个博弈方的全部可选策略的集合博弈方 的第 个策略：博弈方 的得益：博弈：,定义1在博弈 中，如果由各个博弈方的各一个策略组成的某个策略组合中，任一博弈方 的策略，都是对其余博弈方策略的组合 的最佳对策，也即 对任意 都成立，则称 为 的一个

11、纳什均衡（Nash Equilibrium）。,定义2：一个Nash均衡是强的（Strict或Strong），如果给定其他局中人的战略，每一个局中人的最优选择是唯一的。即是说 是一个强Nash均衡，当且仅当对于所有的，有,2求解Nash均衡的方法（1）划线法思路：先找出自己针对其他博弈方每种策略或策略组合（对多人博弈）的最佳对策，即自己的可选策略中与其他博弈方的策略或策略组合配合，给自己带来最大得益的策略（这种相对最佳对策总是存在的，不过不一定惟一），然后再此基础上，通过对其他博弈方策略选择的判断，包括对其他博弈方对自己策略判断的判断等，预测博弈的可能结果和确定自己的最优策略。,划线法求解纳什

12、均衡,例10.2,（2）反应函数法 例10.3 古诺（Cournot）寡头竞争模型,古诺寡头竞争模型（1838）,企业1,企业2,参与人：企业1、企业2战略：选择产量得益：利润，利润是两个企业产量的函数,寡头产量竞争以两厂商产量竞争为例,假设策略组合（q1*，q2*）是本博弈的纳什均衡，那么 max（）q1 max（）q2,q1*，q2*只要能使两式各自对q1，q2的导数为0，就能实现两式的最大值，令：a c q2*2 q1*0 a c q1*2 q2*0,解之，q1*q2*1/3(a-c)。因此，策略组合（1/3(a-c)，1/3(a-c)）是本博弈唯一的纳什均衡。此时每个企业的利润为,产量

13、博弈的古诺模型是一种囚徒困境，无法实现博弈方总体和各个博弈方各自最大利益的结论，对于市场经济组织、管理，对于产业组织和社会经济制度的效率判断，都具有非常重要的意义。说明对市场的管理，政府对市场的调控和监管都是必须的。,（3）混合战略Nash均衡 例10.4 社会福利博弈,流浪,流浪汉,政府,救济,不救济,寻找工作,没有一个策略组合构成纳什均衡,反面,正面,反面,正面,猜谜游戏两个儿童各拿一枚硬币，若同时正面朝上或朝下，A给B 1分钱，若只有一面朝上，B给A 1分钱。,零和博弈博弈参与者有输有赢，但结果永远是0。,没有一个战略组合构成纳什均衡,警察与小偷,银行,酒馆,警察,小偷,2万元,1万元,

14、东边,西边,警察与小偷的最优策略各是什么？,上述博弈的特征是：在这类博弈中，都不存在纯纳什均衡。参与人的支付取决于其他参与人的战略；以某种概率分布随机地选择不同的行动每个参与人都想猜透对方的战略，而每个参与人又不愿意让对方猜透自己的战略。这种博弈的类型是什么？如何找到均衡？,请举一些这样的例子：,石头、剪子、布游戏老虎、杠子、鸡、虫子游戏扑克游戏橄榄球赛战争中,策略：参与人在给定信息集的情况下选择行动的规则，它规定参与人在什么情况下选择什么行动，是参与人的“相机行动方案”。纯策略：如果一个策略规定参与人在每一个给定的信息情况下只选择一种特定的行动，该战略为纯策略。混合策略：如果一个策略规定参与

15、人在给定信息情况下以某种概率分布随机地选择不同的行动，则该策略为混合策略。纯策略可以理解为混合策略的特例，即在诸多策略中，选该纯策略si的概率为1，选其他纯策略的概率为0。,西边,东边,西边,东边,警察抽签决定去银行还是酒馆，2/3的机会去银行，1/3的机会去酒馆；同样，小偷也抽签决定去银行还是酒馆，2/3的机会去酒馆，1/3的机会去银行。,社会福利博弈,流浪,流浪汉,政府,救济,不救济,寻找工作,设：政府救济的概率：1/2；不救济的概率：1/2。流浪汉：寻找工作的期望效用：1/22+1/2 1=1.5 流浪的期望效用：1/23+1/2 0=1.5因此，流浪汉的任何一种战略都是都是对政府混合战

16、略的最优反应,社会福利博弈,流浪,流浪汉,政府,救济,不救济,寻找工作,设：政府救济的概率：1/2；不救济的概率：1/2。流浪汉：寻找工作的概率：0.2；流浪的概率：0.8每个参与人的战略都是给定对方混合战略时的最优战略,反面,正面,反面,正面,猜谜游戏两个小孩的最优策略是采取每个策略的可能性均为1/2；每个小孩各取策略的1/2是纳什均衡。,零和博弈,猜硬币博弈,猜硬币博弈一个非常突出的特点每个局中人都试图能先猜中对方的策略,猜硬币博弈严格竞争博弈和混合策略的引进,（1）不存在前面定义的纳什均衡策略组合（2）关键是不能让对方猜到自己策略这类博弈很多，引出混合策略纳什均衡概念,如何寻找混合策略纳

17、什均衡？支付最大化法支付等值法由于混合战略伴随的是支付的不确定性，因此参与人关心的是其期望效用。最优混合策略：是指使期望效用函数最大的混合战略（给定对方的混合战略）在两人博弈里，混合策略纳什均衡是两个参与人的最优混合策略的组合。,流浪,流浪汉,政府,救济,不救济,寻找工作,即：流浪汉以0.2的概率选择寻找工作，0.8的概率选择游荡,同样，可以根据流浪汉的期望效用函数找到政府的最优混合战略。？,支付最大化法,社会福利博弈,流浪,流浪汉,政府,救济,不救济,寻找工作,设：政府救济的概率：1/2；不救济的概率：1/2。流浪汉：寻找工作的概率：0.2；流浪的概率：0.8每个参与人的战略都是给定对方混合

18、战略时的最优战略,假定最优混合战略存在，给定流浪汉选择混合战略，政府选择纯战略救济的期望效用为：选择纯战略不救济的效用为：如果一个混合战略（而不是纯战略）是政府的最优选择，一定意味着政府在救济与不救济之间是无差异的。,流浪,流浪汉,政府,救济,不救济,寻找工作,支付等值法,社会福利博弈,流浪,流浪汉,政府,救济,不救济,寻找工作,设：政府救济的概率：1/2；不救济的概率：1/2。流浪汉：寻找工作的概率：0.2；流浪的概率：0.8每个参与人的战略都是给定对方混合战略时的最优战略,对 的解释：如果流浪汉找工作的概率小于0.2,则政府选择不救济,如果大于0.2,政府选择救济,只有当概率等于0.2时,

19、政府才会选择混合战略或任何纯战略.对*=0.5的解释:如果政府救济的概率大于0.5,流浪汉的最优选择是流浪,如果政府救济的概率小于0.5,流浪汉的最优选择是寻找工作.,混合战略纳什均衡的含义：纳什均衡要求每个参与人的混合战略是给定对方的混合战略下的最优选择。因此在社会福利博弈中，*=0.5是唯一的混合战略纳什均衡。从反面来说，如果政府认为流浪汉选择寻找工作的概率严格小于0.2，那么政府的唯一最优选择是纯战略：不救济；如果政府以1的概率选择不救济，流浪汉的最优选择是寻找工作，这又将导致政府选择救济的战略，流浪汉则选择游荡。如此等等。,经 济 如 局人 生 如 棋博 弈 之 道生 活 之 常运 用 之 妙存 乎 一 心,