运筹学博弈论-课件.ppt

1、第第1010章章 博弈论博弈论10.110.1博弈论概述博弈论概述10.210.2完全信息静态博弈完全信息静态博弈第一节第一节 博弈论概述博弈论概述精品资料 你怎么称呼老师？如果老师最后没有总结一节课的重点的难点，你是否会认为老师的教学方法需要改进？你所经历的课堂，是讲座式还是讨论式？教师的教鞭“不怕太阳晒，也不怕那风雨狂，只怕先生骂我笨，没有学问无颜见爹娘”“太阳当空照，花儿对我笑，小鸟说早早早”田忌赛马博弈田忌赛马博弈华容道博弈华容道博弈 一、博弈论的产生和发展一、博弈论的产生和发展1.1.博弈在中国博弈在中国从孙子兵法到三十六计从孙子兵法到三十六计从田忌赛马到孙庞斗智从田忌赛马到孙庞斗智

2、从运筹帷幄到韬光养晦从运筹帷幄到韬光养晦从曹刿论战到论持久战从曹刿论战到论持久战2.博弈论的开山之作博弈论的开山之作1943年，冯年，冯诺依曼和摩诺依曼和摩根斯顿发表根斯顿发表博弈论和经博弈论和经济行为济行为的一书，的一书，标志着博弈论作为一门独立科学的开始，标志着博弈论作为一门独立科学的开始，也标志着新古典经济学进入了一个新的发也标志着新古典经济学进入了一个新的发展阶段。展阶段。3.1994年三位获诺奖的博弈论学者年三位获诺奖的博弈论学者John NashJohn HarsanyLeihaden Selten4.1996年诺贝尔经年诺贝尔经济学奖得主：詹姆济学奖得主：詹姆斯斯莫里莫里 斯：主

3、要斯：主要贡献：不对称信息贡献：不对称信息条件下的激励理论条件下的激励理论5.2001年诺贝尔经济年诺贝尔经济学奖得主：迈克尔学奖得主：迈克尔斯斯宾塞：在不对称信息市宾塞：在不对称信息市场分析方面所做出开创场分析方面所做出开创性研究。性研究。6.2005年二位获诺奖的博弈论学者年二位获诺奖的博弈论学者Robert AumannThomas Shelling10.1.2 博弈及博弈论博弈就是策略对抗，或策略有关键作用的游戏博弈就是策略对抗，或策略有关键作用的游戏博弈Game，博弈论Game Theory，Game即游戏、竞技游戏和经济等决策竞争较量的共同特征：规则、结果、策略选择，策略和利益相互

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

5、系统研究具有上述特征的博弈问题，寻求各博弈方合理选择战略情况下博弈的解，并题，寻求各博弈方合理选择战略情况下博弈的解，并对这些解进行讨论分析的理论。对这些解进行讨论分析的理论。博弈的分类及对应的均衡概念博弈的分类及对应的均衡概念 10.2 完全信息静态博弈10.2.1 策略型博弈模型及占优战略博弈10.2.2 重复剔除的占优战略博弈10.2.3 纳什均衡10.2.1 策略型博弈模型及占优战略博弈非合作博弈模型从模型自身形式上可分为扩展型和策略型两种，一般用策略型模型描述完全信息静态博弈模型。构成策略型博弈模型的三个要素:局中人、策略、支付函数 参与人或局中人参与人或局中人(Players)(P

6、layers)：独立决策、独立承担博弈结果的个人或组织博弈规则面前博弈方之间平等，不因博弈方之间权利、地位的差异而改变博弈方数量对博弈结果和分析有影响根据博弈方数量分单人博弈、两人博弈、多人博弈等。最常见的是两人博弈，单人博弈是退化的博弈 策略或战略（策略或战略（strategiesstrategies）：博弈中各博弈方的选择内容。策略有定性定量、简单复杂之分不同博弈方之间不仅可选策略不同，而且可选策略数量也可不同有限博弈：每个博弈方的策略数都是有限的无限博弈：至少有某些博弈方的策略有无限多个 支付函数支付函数(Payoffs function)(Payoffs function)：各博弈方从

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

8、默，此人将即时获释，沉默者将判监8年。若二人都保持沉默（相关术语称互相“合作”），则二人同样判监1年。若二人都互相检举（互相“背叛”），则二人同样判监5年。囚徒困境-5，-50，-8-8，0-1，-1囚徒A囚徒 B坦白抵赖坦白抵赖坦白是坦白是A A的的占优战略占优战略坦白是坦白是B B的的占优战略占优战略占优策略占优策略(上策上策)均衡均衡l 占优策略占优策略(上策上策)通俗来说是：通俗来说是：“我所做的是不管你做什么我所能做的最好的我所做的是不管你做什么我所能做的最好的”“你所做的是不管我做什么你所能做的最好的你所做的是不管我做什么你所能做的最好的”l 占优策略均衡占优策略均衡指博弈中的所有

9、参与者的占优策指博弈中的所有参与者的占优策略组合所构成的均衡。略组合所构成的均衡。囚徒困境（囚徒困境（PrisonersDilemma ）l 只达到效率很差的个体理性解，没有实现团体只达到效率很差的个体理性解，没有实现团体理性解。理性解。l 前者是稳定的，是自动实施的；尽管团体理性前者是稳定的，是自动实施的；尽管团体理性解对大家都好，但它是不能自动实施的，需要改变解对大家都好，但它是不能自动实施的，需要改变条件。条件。提示：提示：该博弈揭示了个体理性与团体理性之间的矛盾。从个体利益出发的行为往往不能实现团体的最大利益，同时也揭示了个体理性本身的内在矛盾从个体利益出发的行为最终也不一定能真正实现

10、个体的最大利益，甚至得到相当差的结果。10.2.2 重复剔除的占优战略均衡 首先找出某一博弈参与人的严格劣战略，将它剔除掉，重新构造一个不包括已剔除战略的新的博弈；然后继续剔除这个新的博弈中某一参与人的严格劣战略；重复进行这一过程，直到剩下唯一的参与人战略组合为止。这个唯一剩下的参与人战略组合，就是这个博弈的均衡解，称为“重复剔除的占优战重复剔除的占优战略均衡略均衡”(iterated dominance equilibrium).(iterated dominance equilibrium).智猪博弈：假设猪圈里有两头猪，一头大猪，一头小猪，猪圈的一端有一个猪食槽，另一端安装了一个按钮，控

11、制猪食的供应。按一下按钮。将有10个单位的猪食进入猪食槽，供两头猪食用。两头猪面临选择的策略有两个：自己去按按钮或等待另一头猪去按按钮。如果某一头猪作出自己去按按钮的选择，它必须付出如下代价：第一，它需要收益相当于2个单位的成本；第二，由于猪食槽远离猪食，它将比另一头猪后到猪食槽，从而减少吃食的数量。大猪先到：大猪吃到9个单位，小猪吃到1个单位；小猪先到：小猪吃到4个单位，大猪吃到6个单位；同时到达：大猪吃到7个单位，小猪吃到3个单位。27大猪不按按不按按小猪(4,4)(5,1)(9,-1)(0,0)小猪大猪按等待按5，14，4等待9，10，0小猪的上策2930重复剔除的占优均衡1，01，20

12、，30，1M列先生行先生UDL0，12，0R行：没有占优策略列：M严格优于R剔除 R行：U优于D列：无占优策略剔除 DM优于L（U，M）是重复剔除的占优均衡u纳什均衡概念是现代博弈论的核心概念。它是以美国数学家、经济学家纳什（Nash）的名字命名的，纳什在1950年的一篇论文中提出了纳什均衡的概念。10.2.3 10.2.3 纳什（纳什（NashNash）均衡）均衡纳什均衡(Nash Equilibrium)通俗地说，纳什均衡的含义就是：给定你的策略，我的策略是最好的策略；给定我的策略，你的策略也是你的最好的策略。即双方在给定的策略下不愿意调整自己的策略。1.纯战略Nash均衡策略空间：每个博

13、弈方的全部可选策略的集合博弈方 的第 个策略：博弈方 的得益：博弈：,;,11nnuuSSGnSS,1ijiSsiuiij定义1在博弈 中，如果由各个博弈方的各一个策略组成的某个策略组合中，任一博弈方 的策略 ，都是对其余博弈方策略的组合 的最佳对策，也即 对任意 都成立，则称 为 的一个纳什均衡（Nash Equilibrium）。,;,11nnuuSSGi),.,(*1*1*niiissss),.,(),.,(*1*1*1*1*niijiiiniiiiisssssusssssuijiSs),(*nissG),(*niss*is 定义2：一个Nash均衡是强的（Strict或Strong），

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

15、12,81,1D3,78,910,4（2）反应函数法 例例10.310.3 古诺（Cournot）寡头竞争模型 古诺寡头竞争模型（1838）企业企业1企业企业2v参与人：企业参与人：企业1 1、企业、企业2 2v战略：战略：选择产量选择产量v得益：得益：利润，利润是两个企业产量的函数利润，利润是两个企业产量的函数寡头产量竞争以两厂商产量竞争为例QaQPPqqQ)(2112111111)()(cqqqaqqcQPqu22122222)()(cqqqaqqcQPqu假设策略组合（q1*，q2*）是本博弈的纳什均衡，那么 max（）q1 max（）q2q1*，q2*只要能使两式各自对q1，q2的导数

16、为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)）是本博弈唯一的纳什均衡。此时每个企业的利润为1211)(cqqqaq2212)(cqqqaq2913131312cacaccacaai 产量博弈的古诺模型是一种囚徒困境，无法实现博弈方总体和各个博弈方各自最大利益的结论，对于市场经济组织、管理，对于产业组织和社会经济制度的效率判断，都具有非常重要的意义。说明对市场的管理，政府对市场的调控和监管都是必须的。（3）混合战略Nash均衡 例例10.410.4 社会福利博弈 23，

17、3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作没有一个策略组合构成纳什均衡 1-1，-11，-11，1-1，反面正面反面正面猜谜游戏v两个儿童各拿一枚硬币，v若同时正面朝上或朝下，A给B 1分钱，v若只有一面朝上，B给A 1分钱。零和博弈博弈参与者有输有赢，但结果永远是0。没有一个战略组合构成纳什均衡警察与小偷银行酒馆警察小偷2万元1万元东边西边警察与小偷的最优策略各是什么？上述博弈的特征是：在这类博弈中，都不存在纯纳什均衡。参与人的支付取决于其他参与人的战略；以某种概率分布随机地选择不同的行动每个参与人都想猜透对方的战略，而每个参与人又不愿意让对方猜透自己的战略。这种博弈的类型是什么

18、？如何找到均衡？请举一些这样的例子：石头、剪子、布游戏老虎、杠子、鸡、虫子游戏扑克游戏橄榄球赛战争中u策略：参与人在给定信息集的情况下选择行动的规则，它规定参与人在什么情况下选择什么行动，是参与人的“相机行动方案”。纯策略：如果一个策略规定参与人在每一个给定的信息情况下只选择一种特定的行动，该战略为纯策略。混合策略：如果一个策略规定参与人在给定信息情况下以某种概率分布随机地选择不同的行动，则该策略为混合策略。纯策略可以理解为混合策略的特例，即在诸多策略中，选该纯策略si的概率为1，选其他纯策略的概率为0。1-1，-11，-22，2-2，西边东边西边东边警察抽签决定去银行还是酒馆，警察抽签决定去

19、银行还是酒馆，2/32/3的机会去银行，的机会去银行，1/31/3的机会去酒馆；的机会去酒馆；同样，小偷也抽签决定去银行还是酒馆，同样，小偷也抽签决定去银行还是酒馆，2/32/3的机会去酒馆，的机会去酒馆，1/31/3的机会的机会去银行。去银行。n社会福利博弈 23，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：设：政府救济的概率：1/2 1/2；不救济的概率：；不救济的概率：1/21/2。流浪汉：流浪汉：寻找工作的期望效用：寻找工作的期望效用：1/21/22+1/2 2+1/2 1=1.51=1.5 流浪的期望效用：流浪的期望效用：1/21/23+1/2 3+1/

20、2 0=1.50=1.5因此，流浪汉的任何一种战略都是都是对政府混合战略的最优反应因此，流浪汉的任何一种战略都是都是对政府混合战略的最优反应n社会福利博弈 23，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：设：政府救济的概率：1/2 1/2；不救济的概率：；不救济的概率：1/21/2。流浪汉：寻找工作的概率：流浪汉：寻找工作的概率：0.20.2；流浪的概率：；流浪的概率：0.80.8每个参与人的战略都是给定对方混合战略时的最优战略每个参与人的战略都是给定对方混合战略时的最优战略 1-1，-11，-11，1-1，反面正面反面正面猜谜游戏v两个小孩的最优策略是采取每个

21、策略的可能性均为1/2；v每个小孩各取策略的1/2是纳什均衡。零和博弈猜硬币博弈-1，11，-11，-1-1，1正 面反 面猜硬币方猜硬币方盖盖硬硬币币方方正 面反 面猜硬币博弈一个非常突出的特点猜硬币博弈一个非常突出的特点每个局中人都试图能先猜中对方的策略每个局中人都试图能先猜中对方的策略 猜硬币博弈猜硬币博弈严格竞争博弈和混合策略的引进严格竞争博弈和混合策略的引进-1，11，-11，-1-1，1正 面反 面猜硬币方猜硬币方盖盖硬硬币币方方正 面反 面（1 1）不存在前面定义的纳什均衡策略组合）不存在前面定义的纳什均衡策略组合（2 2）关键是不能让对方猜到自己策略）关键是不能让对方猜到自己策

22、略这类博弈很多，引出混合策略纳什均衡概念这类博弈很多，引出混合策略纳什均衡概念如何寻找混合策略纳什均衡？如何寻找混合策略纳什均衡？支付最大化法支付最大化法支付等值法支付等值法由于混合战略伴随的是支付的不确定性，因此参与人由于混合战略伴随的是支付的不确定性，因此参与人关心的是其关心的是其期望效用期望效用。最优混合策略最优混合策略：是指使：是指使期望效用函数最大期望效用函数最大的混合战略的混合战略（给定对方的混合战略）（给定对方的混合战略）在两人博弈里，在两人博弈里，混合策略纳什均衡是两个参与人的最混合策略纳什均衡是两个参与人的最优混合策略的组合优混合策略的组合。23，3-1，1-1，00，流浪流

23、浪流浪汉政府救济救济不救济不救济寻找工作寻找工作2.00151510111311*故化的一阶条件：求微分，得到政府最优）（）（）（）（），（：政府的期望效用函数为）。，（流浪汉的混合战略是）；，（假定政府的混合战略是GLGLGvv即：即：流浪汉以流浪汉以0.20.2的概率选择寻的概率选择寻找工作，找工作，0.80.8的概率选择游荡的概率选择游荡同样，可以根据流浪汉同样，可以根据流浪汉的期望效用函数找到政的期望效用函数找到政府的最优混合战略。？府的最优混合战略。？支付最大化法支付最大化法n社会福利博弈 23，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：设：政府救济的

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

25、定意味着政府在救济与不救济之间是无差异的。之间是无差异的。)1,(23，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作支付等值法14)1)(1(3)1(010.2 14n社会福利博弈 23，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：1/2；不救济的概率：1/2。流浪汉：寻找工作的概率：0.2；流浪的概率：0.8每个参与人的战略都是给定对方混合战略时的最优战略对 的解释：如果流浪汉找工作的概率小于0.2,则政府选择不救济,如果大于0.2,政府选择救济,只有当概率等于0.2时,政府才会选择混合战略或任何纯战略.对*=0.5的解释:如果政府救济的概率大于0.5

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