运筹学博弈论.pptx

《运筹学博弈论.pptx》由会员分享，可在线阅读，更多相关《运筹学博弈论.pptx（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一节第一节 博弈论概述博弈论概述第1页/共63页田忌赛马博弈田忌赛马博弈华容道博弈华容道博弈 一、博弈论的产生和发展一、博弈论的产生和发展1.1.博弈在中国博弈在中国第2页/共63页从孙子兵法到三十六计从田忌赛马到孙庞斗智从运筹帷幄到韬光养晦从曹刿论战到论持久战第3页/共63页2.博弈论的开山之作1943年，冯诺依曼和摩根斯顿发表博弈论和经济行为的一书，标标志志着着博博弈弈论论作作为为一一门门独独立立科科学学的的开开始始，也也标标志志着着新新古古典典经经济济学学进进入入了了一一个个新新的的发发展展阶阶段。段。第4页/共63页 3.1994年三位获诺奖的博弈论学者John NashJohn H

2、arsanyLeihaden Selten第5页/共63页4.1996年诺贝尔经济学奖得主：詹姆斯莫里 斯：主要贡献：不对称信息条件下的激励理论第6页/共63页5.2001年诺贝尔经济学奖得主：迈克尔斯宾塞：在不对称信息市场分析方面所做出开创性研究。第7页/共63页6.2005年二位获诺奖的博弈论学者Robert AumannThomas Shelling第8页/共63页10.1.2 10.1.2 博弈及博弈论博弈及博弈论博弈就是策略对抗，或策略有关键作用的游戏博弈就是策略对抗，或策略有关键作用的游戏博弈Game，博弈论Game Theory，Game即游戏、竞技游戏和经济等决策竞争较量的共同

3、特征：规则、结果、策略选择，策略和利益相互依存，策略的关键作用 游戏下棋、猜大小 经济寡头产量决策、市场阻入、投标拍卖 政治、军事美国和伊拉克、以色列和巴勒斯坦第9页/共63页定义定义：博弈就是参与人（可能是个人，也可能是团体，如国家、企业、国际组织等）在一定得规则下，同时或先或后，一次或多次，从各自允许选择的行动或战略中进行选择并加以实施，而取得相应结果（支付函数）的过程。都有一定的规则都有一定的规则 都有一个结果都有一个结果 策略至关重要，游戏者不同的策略选择常会带来不同的游策略至关重要，游戏者不同的策略选择常会带来不同的游戏结果戏结果 策略和利益有相互依存性策略和利益有相互依存性 博弈论

4、：博弈论就是系统研究具有上述特征的博弈博弈论：博弈论就是系统研究具有上述特征的博弈问题，寻求各博弈方合理选择战略情况下博弈的解，问题，寻求各博弈方合理选择战略情况下博弈的解，并对这些解进行讨论分析的理论。并对这些解进行讨论分析的理论。第10页/共63页博弈的分类及对应的均衡概念博弈的分类及对应的均衡概念 第11页/共63页10.2 10.2 完全信息静态博弈完全信息静态博弈10.2.1 策略型博弈模型及占优战略博弈10.2.2 重复剔除的占优战略博弈10.2.3 纳什均衡第12页/共63页10.2.1 10.2.1 策略型博弈模型及占优战略博弈策略型博弈模型及占优战略博弈非合作博弈模型从模型自

5、身形式上可分为扩展型和策略型两种，一般用策略型模型描述完全信息静态博弈模型。构成策略型博弈模型的三个要素:局中人、策略、支付函数 第13页/共63页 参与人或局中人参与人或局中人(Players)(Players)：独立决策、独立承担博弈结果的个人或组织博弈规则面前博弈方之间平等，不因博弈方之间权利、地位的差异而改变博弈方数量对博弈结果和分析有影响根据博弈方数量分单人博弈、两人博弈、多人博弈等。最常见的是两人博弈，单人博弈是退化的博弈第14页/共63页 策略或战略（策略或战略（strategiesstrategies）：博弈中各博弈方的选择内容。策略有定性定量、简单复杂之分不同博弈方之间不仅可

6、选策略不同，而且可选策略数量也可不同有限博弈：每个博弈方的策略数都是有限的无限博弈：至少有某些博弈方的策略有无限多个第15页/共63页 支付函数支付函数(Payoffs function)(Payoffs function)：各博弈方从博弈中所获得的利益。得益对应博弈的结果，也就是各博弈方策略的组合得益是各博弈方追求的根本目标及行为和判断的主要依据根据得益的博弈分类：零和博弈、常和博弈、变和博弈第16页/共63页例例10.1 10.1 囚徒困境博弈囚徒困境博弈囚徒的困境是图克（Tucker）1950年提出的该博弈是博弈论最经典、著名的博弈该博弈本身讲的是一个法律刑侦或犯罪学方面的问题，但可以扩

7、展到许多经济问题，以及各种社会问题，可以揭示市场经济的根本缺陷第17页/共63页基本模型基本模型 经典的囚徒困境如下：警方逮捕甲、乙两名嫌疑犯，但没有足够证据指控二人入罪。于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供以下相同的选择：若一人认罪并作证检举对方（相关术语称“背叛”对方），而对方保持沉默，此人将即时获释，沉默者将判监8年。若二人都保持沉默（相关术语称互相“合作”），则二人同样判监1年。若二人都互相检举（互相“背叛”），则二人同样判监5年。第18页/共63页囚徒困境-5，-50，-8-8，0-1，-1囚徒A囚徒 B坦白抵赖坦白抵赖坦白是坦白是A A的的占优战略占优战略坦白是坦白

8、是B B的的占优战略占优战略第19页/共63页占优策略占优策略(上策上策)均衡均衡l占优策略占优策略(上策上策)通俗来说是：通俗来说是：“我所做的是不管你做什么我所能做的最好的我所做的是不管你做什么我所能做的最好的”“你所做的是不管我做什么你所能做的最好的你所做的是不管我做什么你所能做的最好的”l占优策略均衡占优策略均衡指博弈中的所有参与者的占优策指博弈中的所有参与者的占优策略组合所构成的均衡。略组合所构成的均衡。第20页/共63页囚徒困境（囚徒困境（PrisonersDilemma ）l只达到效率很差的个体理性解，没有实现团体只达到效率很差的个体理性解，没有实现团体理性解。理性解。l前者是稳

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

10、参与人的严格劣战略；重复进行这一过程，直到剩下唯一的参与人战略组合为止。这个唯一剩下的参与人战略组合，就是这个博弈的均衡解，称为“重重 复复 剔剔 除除 的的 占占 优优 战战 略略 均均 衡衡”(iterated(iterated dominance equilibrium).dominance equilibrium).第22页/共63页智猪博弈：假设猪圈里有两头猪，一头大猪，一头小猪，猪圈的一端有一个猪食槽，另一端安装了一个按钮，控制猪食的供应。按一下按钮。将有10个单位的猪食进入猪食槽，供两头猪食用。两头猪面临选择的策略有两个：自己去按按钮或等待另一头猪去按按钮。如果某一头猪作出自己去

11、按按钮的选择，它必须付出如下代价：第一，它需要收益相当于2个单位的成本；第二，由于猪食槽远离猪食，它将比另一头猪后到猪食槽，从而减少吃食的数量。大猪先到：大猪吃到9个单位，小猪吃到1个单位；小猪先到：小猪吃到4个单位，大猪吃到6个单位；同时到达：大猪吃到7个单位，小猪吃到3个单位。智猪博弈（大小猪博弈）第23页/共63页24大猪不按按不按按小猪(4,4)(5,1)(9,-1)(0,0)局中人：大猪和小猪局中人：大猪和小猪 行动：按按钮吃东西行动：按按钮吃东西第24页/共63页小猪大猪按等待按5，14，4等待9，10，0小猪的上策第25页/共63页26双方力量不对等时的正确策略力量强：主动出击力

12、量弱：等待，搭强者的便车。第26页/共63页27智猪博弈的应用智猪博弈的应用 政治博弈政治博弈 大国是大猪，小国是小猪大国是大猪，小国是小猪 资本市场资本市场 大股东是大猪，小股东是小猪大股东是大猪，小股东是小猪 企业创新策略企业创新策略 大企业是大猪，小企业是小猪大企业是大猪，小企业是小猪第27页/共63页重复剔除的占优均衡重复剔除的占优均衡1，01，20，30，1M列先生行先生UDL0，12，0R行：没有占优策略列：M严格优于R剔除 R行：U优于D列：无占优策略剔除 DM优于L（U，M）是重复剔除的占优均衡第28页/共63页u纳什均衡概念是现代博弈论的核心概念。它是以美国数学家、经济学家纳

13、什（Nash）的名字命名的，纳什在1950年的一篇论文中提出了纳什均衡的概念。10.2.3 10.2.3 纳什（纳什（NashNash）均衡）均衡第29页/共63页纳什均衡纳什均衡(Nash Equilibrium)通俗地说，纳什均衡的含义就是：给定你的策略，我的策略是最好的策略；给定我的策略，你的策略也是你的最好的策略。即双方在给定的策略下不愿意调整自己的策略。第30页/共63页1.纯战略Nash均衡策略空间：每个博弈方的全部可选策略的集合博弈方 的第 个策略：博弈方 的得益：博弈：第31页/共63页定义1在博弈 中，如果由各个博弈方的各一个策略组成的某个策略组合中，任一博弈方 的策略 ，都

14、是对其余博弈方策略的组合 的最佳对策，也即 对任意 都成立，则称 为 的一个纳什均衡（Nash Equilibrium）。第32页/共63页 定义2：一个Nash均衡是强的（Strict或Strong），如果给定其他局中人的战略，每一个局中人的最优选择是唯一的。即是说 是一个强Nash均衡，当且仅当对于所有的 ，有第33页/共63页2求解Nash均衡的方法（1）划线法思路：先找出自己针对其他博弈方每种策略或策略组合（对多人博弈）的最佳对策，即自己的可选策略中与其他博弈方的策略或策略组合配合，给自己带来最大得益的策略（这种相对最佳对策总是存在的，不过不一定惟一），然后再此基础上，通过对其他博弈方

15、策略选择的判断，包括对其他博弈方对自己策略判断的判断等，预测博弈的可能结果和确定自己的最优策略。第34页/共63页划线法求解纳什均衡划线法求解纳什均衡例10.2 BLMRU3,24,75,1AH6,12,81,1D3,78,910,4第35页/共63页（2）反应函数法 例例 古诺（Cournot）寡头竞争模型 第36页/共63页古诺寡头竞争模型（古诺寡头竞争模型（18381838）企业企业1企业企业2v参与人：企业参与人：企业1 1、企业、企业2 2v战略：战略：选择产量选择产量v得益：得益：利润，利润是两个企业产量的函数利润，利润是两个企业产量的函数第37页/共63页寡头产量竞争以两厂商产量

16、竞争为例第38页/共63页假设策略组合（q1*，q2*）是本博弈的纳什均衡，那么 max（）q1 max（）q2q1*，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)）是本博弈唯一的纳什均衡。此时每个企业的利润为第39页/共63页 产量博弈的古诺模型是一种囚徒困境，无法实现博弈方总体和各个博弈方各自最大利益的结论，对于市场经济组织、管理，对于产业组织和社会经济制度的效率判断，都具有非常重要的意义。说明对市场的管理，政府对市场的调控

17、和监管都是必须的。第40页/共63页（3）混合战略Nash均衡 例例 社会福利博弈 23，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作没有一个策略组合构成纳什均衡第41页/共63页 1-1，-11，-11，1-1，反面正面反面正面猜谜游戏v两个儿童各拿一枚硬币，v若同时正面朝上或朝下，A给B 1分钱，v若只有一面朝上，B给A 1分钱。零和博弈博弈参与者有输有赢，但结果永远是0。没有一个战略组合构成纳什均衡第42页/共63页警察与小偷银行酒馆警察小偷2万元1万元东边西边警察与小偷的最优策略各是什么？第43页/共63页上述博弈的特征是：在这类博弈中，都不存在纯纳什均衡。参与人的支付取决于

18、其他参与人的战略；以某种概率分布随机地选择不同的行动每个参与人都想猜透对方的战略，而每个参与人又不愿意让对方猜透自己的战略。这种博弈的类型是什么？如何找到均衡？第44页/共63页请举一些这样的例子：石头、剪子、布游戏老虎、杠子、鸡、虫子游戏扑克游戏橄榄球赛战争中第45页/共63页u策略：参与人在给定信息集的情况下选择行动的规则，它规定参与人在什么情况下选择什么行动，是参与人的“相机行动方案”。纯策略：如果一个策略规定参与人在每一个给定的信息情况下只选择一种特定的行动，该战略为纯策略。混合策略：如果一个策略规定参与人在给定信息情况下以某种概率分布随机地选择不同的行动，则该策略为混合策略。纯策略可

19、以理解为混合策略的特例，即在诸多策略中，选该纯策略si的概率为1，选其他纯策略的概率为0。第46页/共63页第47页/共63页 1-1，-11，-22，2-2，西边东边西边东边警察抽签决定去银行还是酒馆，警察抽签决定去银行还是酒馆，2/32/3的机会去银行，的机会去银行，1/31/3的机会去酒馆；的机会去酒馆；同样，小偷也抽签决定去银行还是酒馆，同样，小偷也抽签决定去银行还是酒馆，2/32/3的机会去酒馆，的机会去酒馆，1/31/3的机会的机会去银行。去银行。第48页/共63页n社会福利博弈 23，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：设：政府救济的概率：1

20、/2 1/2；不救济的概率：；不救济的概率：1/21/2。流浪汉：流浪汉：寻找工作的期望效用：寻找工作的期望效用：1/22+1/2 1=1.51/22+1/2 1=1.5 流浪的期望效用：流浪的期望效用：因此，流浪汉的任何一种战略都是都是对政府混合战略的最优反应因此，流浪汉的任何一种战略都是都是对政府混合战略的最优反应第49页/共63页n社会福利博弈 23，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：设：政府救济的概率：1/2 1/2；不救济的概率：；不救济的概率：1/21/2。流浪汉：寻找工作的概率：流浪汉：寻找工作的概率：0.20.2；流浪的概率：；流浪的概率

21、：每个参与人的战略都是给定对方混合战略时的最优战略每个参与人的战略都是给定对方混合战略时的最优战略第50页/共63页 1-1，-11，-11，1-1，反面正面反面正面猜谜游戏v两个小孩的最优策略是采取每个策略的可能性均为1/2；v每个小孩各取策略的1/2是纳什均衡。零和博弈第51页/共63页猜硬币博弈-1，11，-11，-1-1，1正 面反 面猜硬币方猜硬币方盖盖硬硬币币方方正 面反 面猜硬币博弈一个非常突出的特点猜硬币博弈一个非常突出的特点每个局中人都试图能先猜中对方的策略每个局中人都试图能先猜中对方的策略 第52页/共63页猜硬币博弈猜硬币博弈严格竞争博弈和混合策略的引进严格竞争博弈和混合

22、策略的引进-1，11，-11，-1-1，1正 面反 面猜硬币方猜硬币方盖盖硬硬币币方方正 面反 面（1 1）不存在前面定义的纳什均衡策略组合）不存在前面定义的纳什均衡策略组合（2 2）关键是不能让对方猜到自己策略）关键是不能让对方猜到自己策略这类博弈很多，引出混合策略纳什均衡概念这类博弈很多，引出混合策略纳什均衡概念第53页/共63页如何寻找混合策略纳什均衡？如何寻找混合策略纳什均衡？支付最大化法支付最大化法支付等值法支付等值法由于混合战略伴随的是支付的不确定性，因此参与由于混合战略伴随的是支付的不确定性，因此参与人关心的是其人关心的是其期望效用期望效用。最优混合策略最优混合策略：是指使：是指

23、使期望效用函数最大期望效用函数最大的混合战的混合战略（给定对方的混合战略）略（给定对方的混合战略）在两人博弈里，在两人博弈里，混合策略纳什均衡是两个参与人的混合策略纳什均衡是两个参与人的最优混合策略的组合最优混合策略的组合。第54页/共63页 23，3-1，1-1，00，流浪流浪流浪汉政府救济救济不救济不救济寻找工作寻找工作即：即：流浪汉以的概率选择寻找流浪汉以的概率选择寻找工作，的概率选择游荡工作，的概率选择游荡同样，可以根据流浪汉同样，可以根据流浪汉的期望效用函数找到政的期望效用函数找到政府的最优混合战略。？府的最优混合战略。？支付最大化法支付最大化法第55页/共63页n社会福利博弈 23

24、，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：设：政府救济的概率：1/2 1/2；不救济的概率：；不救济的概率：1/21/2。流浪汉：寻找工作的概率：流浪汉：寻找工作的概率：0.20.2；流浪的概率：；流浪的概率：每个参与人的战略都是给定对方混合战略时的最优战略每个参与人的战略都是给定对方混合战略时的最优战略第56页/共63页假定最优混合战略存在，给假定最优混合战略存在，给定流浪汉选择混合战略，定流浪汉选择混合战略，政府选择纯战略救济的期望政府选择纯战略救济的期望效用为：效用为：选择纯战略不救济的效用为：选择纯战略不救济的效用为：如果一个混合战略（而不是如果一个混

25、合战略（而不是纯战略）是政府的最优选择，纯战略）是政府的最优选择，一定意味着政府在救济与不一定意味着政府在救济与不救济之间是无差异的。救济之间是无差异的。23，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作支付等值法第57页/共63页n社会福利博弈 23，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：1/2；不救济的概率：1/2。流浪汉：寻找工作的概率：0.2；流浪的概率：每个参与人的战略都是给定对方混合战略时的最优战略第58页/共63页对 的解释：如果流浪汉找工作的概率小于0.2,则政府选择不救济,如果大于0.2,政府选择救济,只有当概率等于0.2时,政府

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