运筹学博弈论课堂PPT.ppt

第第1010章章 博弈论博弈论ï10.110.1博弈论概述博弈论概述ï10.210.2完全信息静态博弈完全信息静态博弈1第一节第一节 博弈论概述博弈论概述2¡田忌赛马博弈田忌赛马博弈¡华容道博弈华容道博弈 一、博弈论的产生和发展一、博弈论的产生和发展1. 1. 博弈在中国博弈在中国3从孙子兵法到三十六计从孙子兵法到三十六计从田忌赛马到孙庞斗智从田忌赛马到孙庞斗智从运筹帷幄到韬光养晦从运筹帷幄到韬光养晦从曹刿论战到论持久战从曹刿论战到论持久战42. 博弈论的开山之作博弈论的开山之作1943年年，，冯冯·诺诺依依曼曼和和摩摩根根斯斯顿顿发发表表《《博博弈弈论论和和经经济行为》的一书，济行为》的一书，标标志志着着博博弈弈论论作作为为一一门门独独立立科科学学的的开开始始，，也也标标志志着着新新古古典典经经济济学学进进入入了了一一个个新新的的发发展展阶阶段5 3. 1994年三位获诺奖的博弈论学者年三位获诺奖的博弈论学者John NashJohn HarsanyLeihaden Selten64. 1996年年诺诺贝贝尔尔经经济济学学奖奖得得主主：：詹詹姆姆斯斯·莫莫里里 斯斯：：主主要要贡贡献献：：不不对对称称信信息息条件下的激励理论条件下的激励理论75. 2001年年诺诺贝贝尔尔经经济济学学奖奖得得主主：：迈迈克克尔尔·斯斯宾宾塞塞：：在在不不对对称称信信息息市市场场分分析析方方面面所所做做出出开开创创性研究。

性研究 86. 2005年二位获诺奖的博弈论学者年二位获诺奖的博弈论学者Robert AumannThomas Shelling910.1.2 博弈及博弈论博弈就是策略对抗，或策略有关键作用的游戏博弈就是策略对抗，或策略有关键作用的游戏¡博弈Game，博弈论Game Theory，Game即游戏、竞技¡游戏和经济等决策竞争较量的共同特征：规则、结果、策略选择，策略和利益相互依存，策略的关键作用 游戏——下棋、猜大小 经济——寡头产量决策、市场阻入、投标拍卖 政治、军事——美国和伊拉克、以色列和巴勒斯坦10定义定义：博弈就是参与人（可能是个人，也可能是团体，如国家、企业、国际组织等）在一定得规则下，同时或先或后，一次或多次，从各自允许选择的行动或战略中进行选择并加以实施，而取得相应结果（支付函数）的过程 ™都有一定的规则都有一定的规则 ™都有一个结果都有一个结果 ™策略至关重要，游戏者不同的策略选择常会带来不同的游戏策略至关重要，游戏者不同的策略选择常会带来不同的游戏结果结果 ™策略和利益有相互依存性策略和利益有相互依存性 ¡博弈论：博弈论就是系统研究具有上述特征的博弈问博弈论：博弈论就是系统研究具有上述特征的博弈问题，寻求各博弈方合理选择战略情况下博弈的解，并题，寻求各博弈方合理选择战略情况下博弈的解，并对这些解进行讨论分析的理论。

对这些解进行讨论分析的理论11博弈的分类及对应的均衡概念博弈的分类及对应的均衡概念 1210.2 完全信息静态博弈ï10.2.1 策略型博弈模型及占优战略博弈ï10.2.2 重复剔除的占优战略博弈ï10.2.3 纳什均衡1310.2.1 策略型博弈模型及占优战略博弈¡非合作博弈模型从模型自身形式上可分为扩展型和策略型两种，一般用策略型模型描述完全信息静态博弈模型¡构成策略型博弈模型的三个要素: 局中人、策略、支付函数 14 参与人或局中人参与人或局中人(Players) (Players) ：独立决策、独立承担博弈结果的个人或组织¡博弈规则面前博弈方之间平等，不因博弈方之间权利、地位的差异而改变¡博弈方数量对博弈结果和分析有影响¡根据博弈方数量分单人博弈、两人博弈、多人博弈等最常见的是两人博弈，单人博弈是退化的博弈15 策略或战略（策略或战略（strategiesstrategies）） ：博弈中各博弈方的选择内容¡策略有定性定量、简单复杂之分¡不同博弈方之间不仅可选策略不同，而且可选策略数量也可不同¡有限博弈：每个博弈方的策略数都是有限的¡无限博弈：至少有某些博弈方的策略有无限多个16 支付函数支付函数(Payoffs function)(Payoffs function) ：各博弈方从博弈中所获得的利益。

¡得益对应博弈的结果，也就是各博弈方策略的组合¡得益是各博弈方追求的根本目标及行为和判断的主要依据¡根据得益的博弈分类：零和博弈、常和博弈、变和博弈17例10.1 囚徒困境博弈¡囚徒的困境是图克（Tucker）1950年提出的¡该博弈是博弈论最经典、著名的博弈¡该博弈本身讲的是一个法律刑侦或犯罪学方面的问题，但可以扩展到许多经济问题，以及各种社会问题，可以揭示市场经济的根本缺陷18基本模型 经典的囚徒困境如下： 　　 警方逮捕甲、乙两名嫌疑犯，但没有足够证据指控二人入罪于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供以下相同的选择： ¡若一人认罪并作证检举对方（相关术语称“背叛”对方），而对方保持沉默，此人将即时获释，沉默者将判监8年 ¡若二人都保持沉默（相关术语称互相“合作”），则二人同样判监1年 ¡若二人都互相检举（互相“背叛”），则二人同样判监5年19囚徒困境-5，-50，-8-8，0-1，-1囚徒A囚徒 B坦白抵赖坦白抵赖坦白是坦白是A A的的占优战略占优战略坦白是坦白是B B的的占优战略占优战略20占优策略占优策略( (上策上策) )均衡均衡l占优策略占优策略( (上策上策) )通俗来说是：通俗来说是：• “我所做的是不管你做什么我所能做的最好的我所做的是不管你做什么我所能做的最好的”• “你所做的是不管我做什么你所能做的最好的你所做的是不管我做什么你所能做的最好的”l占优策略均衡占优策略均衡指博弈中的所有参与者的占优策指博弈中的所有参与者的占优策略组合所构成的均衡。

略组合所构成的均衡21囚徒困境（囚徒困境（ Prisoners’Dilemma ））l只达到效率很差的个体理性解，没有实现团体只达到效率很差的个体理性解，没有实现团体理性解l前者是稳定的，是自动实施的；尽管团体理性前者是稳定的，是自动实施的；尽管团体理性解对大家都好，但它是不能自动实施的，需要改变解对大家都好，但它是不能自动实施的，需要改变条件提示：提示：该博弈揭示了个体理性与团体理性之间的矛盾——从个体利益出发的行为往往不能实现团体的最大利益，同时也揭示了个体理性本身的内在矛盾——从个体利益出发的行为最终也不一定能真正实现个体的最大利益，甚至得到相当差的结果22 10.2.2 重复剔除的占优战略均衡 首先找出某一博弈参与人的严格劣战略，将它剔除掉，重新构造一个不包括已剔除战略的新的博弈；然后继续剔除这个新的博弈中某一参与人的严格劣战略；重复进行这一过程，直到剩下唯一的参与人战略组合为止这个唯一剩下的参与人战略组合，就是这个博弈的均衡解，称为“重重复复剔剔除除的的占占优优战战略均衡略均衡”(iterated dominance equilibrium).”(iterated dominance equilibrium).23¡智猪博弈：假设猪圈里有两头猪，一头大猪，一头小猪，猪圈的一端有一个猪食槽，另一端安装了一个按钮，控制猪食的供应。

按一下按钮将有10个单位的猪食进入猪食槽，供两头猪食用两头猪面临选择的策略有两个：自己去按按钮或等待另一头猪去按按钮如果某一头猪作出自己去按按钮的选择，它必须付出如下代价：第一，它需要收益相当于2个单位的成本；第二，由于猪食槽远离猪食，它将比另一头猪后到猪食槽，从而减少吃食的数量¡大猪先到：大猪吃到9个单位，小猪吃到1个单位；¡小猪先到：小猪吃到4个单位，大猪吃到6个单位；¡同时到达：大猪吃到7个单位，小猪吃到3个单位 智猪博弈（大小猪博弈）2425大猪不按按不按按小猪(4, 4)(5, 1)(9, -1) (0, 0)¡¡局中人：大猪和小猪¡¡行动：按按钮吃东西25小猪大猪按等待按5，14，4等待9，－10，0小猪的上策2627¡双方力量不对等时的正确策略™力量强：主动出击™力量弱：等待，搭强者的便车 2728智猪博弈的应用¡¡政治博弈™™大国是大猪，小国是小猪大国是大猪，小国是小猪¡¡资本市场™™大股东是大猪，小股东是小猪大股东是大猪，小股东是小猪¡¡企业创新策略™™大企业是大猪，小企业是小猪大企业是大猪，小企业是小猪28重复剔除的占优均衡1，01，20，30，1M列先生行先生UDL0，12，0R行：没有占优策略列：M严格优于R剔除 R行：U优于D列：无占优策略剔除 DM优于L（U，M）是重复剔除的占优均衡29u纳什均衡概念是现代博弈论的核心概念。

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

即是说 是一个强Nash均衡，当且仅当对于所有的 ， ，有342．求解Nash均衡的方法（1）划线法¡思路：先找出自己针对其他博弈方每种策略或策略组合（对多人博弈）的最佳对策，即自己的可选策略中与其他博弈方的策略或策略组合配合，给自己带来最大得益的策略（这种相对最佳对策总是存在的，不过不一定惟一），然后再此基础上，通过对其他博弈方策略选择的判断，包括对其他博弈方对自己策略判断的判断等，预测博弈的可能结果和确定自己的最优策略35划线法求解纳什均衡¡例10.2 BLMRU3,24,75,1AH6,12,81,1D3,78,910,436（2） 反应函数法 ¡例例10.310.3 古诺（Cournot）寡头竞争模型 37古诺寡头竞争模型（1838）企业企业1企业企业2v参与人：企业参与人：企业1 1、企业、企业2 2v战略：战略： 选择产量选择产量v得益：得益： 利润，利润是两个企业产量的函数利润，利润是两个企业产量的函数38寡头产量竞争——以两厂商产量竞争为例39假设策略组合（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) ）是本博弈唯一的纳什均衡此时每个企业的利润为40 产量博弈的古诺模型是一种囚徒困境，无法实现博弈方总体和各个博弈方各自最大利益的结论，对于市场经济组织、管理，对于产业组织和社会经济制度的效率判断，都具有非常重要的意义说明对市场的管理，政府对市场的调控和监管都是必须的41（3）混合战略Nash均衡 ¡例例10.410.4 社会福利博弈 23， 3-1， 1-1， 00，流浪流浪汉政府救济不救济寻找工作没有一个策略组合构成纳什均衡42 1-1， -11， -11， 1-1，反面正面反面正面猜谜游戏v两个儿童各拿一枚硬币，v若同时正面朝上或朝下，A给B 1分钱，v若只有一面朝上，B给A 1分钱零和博弈博弈参与者有输有赢，但结果永远是0没有一个战略组合构成纳什均衡43¡警察与小偷银行酒馆警察小偷2万元1万元东边西边警察与小偷的最优策略各是什么？44¡上述博弈的特征是：ü在这类博弈中，都不存在纯纳什均衡ü参与人的支付取决于其他参与人的战略；以某种概率分布随机地选择不同的行动ü每个参与人都想猜透对方的战略，而每个参与人又不愿意让对方猜透自己的战略。

这种博弈的类型是什么？如何找到均衡？45¡请举一些这样的例子：ü石头、剪子、布游戏ü老虎、杠子、鸡、虫子游戏ü扑克游戏ü橄榄球赛ü战争中46u策略：参与人在给定信息集的情况下选择行动的规则，它规定参与人在什么情况下选择什么行动，是参与人的“相机行动方案”Ø纯策略：如果一个策略规定参与人在每一个给定的信息情况下只选择一种特定的行动，该战略为纯策略Ø混合策略：如果一个策略规定参与人在给定信息情况下以某种概率分布随机地选择不同的行动，则该策略为混合策略¡纯策略可以理解为混合策略的特例，即在诸多策略中，选该纯策略si的概率为1，选其他纯策略的概率为04748 1-1， -11， -22， 2-2，西边东边西边东边警察抽签决定去银行还是酒馆，警察抽签决定去银行还是酒馆，2/32/3的机会去银行，的机会去银行，1/31/3的机会去酒馆；的机会去酒馆；同样，小偷也抽签决定去银行还是酒馆，同样，小偷也抽签决定去银行还是酒馆， 2/32/3的机会去酒馆，的机会去酒馆， 1/31/3的机会的机会去银行49n社会福利博弈 23， 3-1， 1-1， 00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：设：政府救济的概率：1/2 1/2 ；不救济的概率：；不救济的概率：1/21/2。

流浪汉：流浪汉：寻找工作的期望效用：寻找工作的期望效用：1/2×2+1/2 ×1=1.51/2×2+1/2 ×1=1.5 流浪的期望效用：流浪的期望效用： 1/2×3+1/2 ×0=1.5 1/2×3+1/2 ×0=1.5因此，流浪汉的任何一种战略都是都是对政府混合战略的最优反应因此，流浪汉的任何一种战略都是都是对政府混合战略的最优反应50n社会福利博弈 23， 3-1， 1-1， 00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：设：政府救济的概率：1/2 1/2 ；不救济的概率：；不救济的概率：1/21/2流浪汉：寻找工作的概率：流浪汉：寻找工作的概率：0. 20. 2；流浪的概率：；流浪的概率：0.80.8每个参与人的战略都是给定对方混合战略时的最优战略每个参与人的战略都是给定对方混合战略时的最优战略51 1-1， -11， -11， 1-1，反面正面反面正面猜谜游戏v两个小孩的最优策略是采取每个策略的可能性均为1/2；v每个小孩各取策略的1/2是纳什均衡。

零和博弈52猜硬币博弈-1， 11， -11， -1-1， 1正 面反 面猜硬币方猜硬币方盖盖硬硬币币方方正 面反 面猜硬币博弈一个非常突出的特点猜硬币博弈一个非常突出的特点每个局中人都试图能先猜中对方的策略每个局中人都试图能先猜中对方的策略 53猜硬币博弈猜硬币博弈——严格竞争博弈和混合策略的引进严格竞争博弈和混合策略的引进-1， 11， -11， -1-1， 1正 面反 面猜硬币方猜硬币方盖盖硬硬币币方方正 面反 面（（1 1）不存在前面定义的纳什均衡策略组合）不存在前面定义的纳什均衡策略组合（（2 2）关键是不能让对方猜到自己策略）关键是不能让对方猜到自己策略这类博弈很多，引出混合策略纳什均衡概念这类博弈很多，引出混合策略纳什均衡概念54如何寻找混合策略纳什均衡？如何寻找混合策略纳什均衡？§支付最大化法支付最大化法§支付等值法支付等值法Ø由于混合战略伴随的是支付的不确定性，因此参与人由于混合战略伴随的是支付的不确定性，因此参与人关心的是其关心的是其期望效用期望效用Ø最优混合策略最优混合策略：是指使：是指使期望效用函数最大期望效用函数最大的混合战略的混合战略（给定对方的混合战略）（给定对方的混合战略）Ø在两人博弈里，在两人博弈里，混合策略纳什均衡是两个参与人的最混合策略纳什均衡是两个参与人的最优混合策略的组合优混合策略的组合。

55 23， 3-1， 1-1， 00，流浪流浪流浪汉政府救济救济不救济不救济寻找工作寻找工作即：即：流浪汉以流浪汉以0.20.2的概率选择寻的概率选择寻找工作，找工作，0.80.8的概率选择游荡的概率选择游荡同样，可以根据流浪汉同样，可以根据流浪汉的期望效用函数找到政的期望效用函数找到政府的最优混合战略府的最优混合战略支付最大化法支付最大化法56n社会福利博弈 23， 3-1， 1-1， 00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：设：政府救济的概率：1/2 1/2 ；不救济的概率：；不救济的概率：1/21/2流浪汉：寻找工作的概率：流浪汉：寻找工作的概率：0. 20. 2；流浪的概率：；流浪的概率：0.80.8每个参与人的战略都是给定对方混合战略时的最优战略每个参与人的战略都是给定对方混合战略时的最优战略57¡假定最优混合战略存在，给定假定最优混合战略存在，给定流浪汉选择混合战略，流浪汉选择混合战略，¡政府选择纯战略救济的期望效政府选择纯战略救济的期望效用为：用为：¡选择纯战略不救济的效用为：选择纯战略不救济的效用为：¡如果一个混合战略（而不是纯如果一个混合战略（而不是纯战略）是政府的最优选择，一战略）是政府的最优选择，一定意味着政府在救济与不救济定意味着政府在救济与不救济之间是无差异的。

之间是无差异的 23， 3-1， 1-1， 00，流浪流浪汉政府救济不救济寻找工作支付等值法58n社会福利博弈 23， 3-1， 1-1， 00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：1/2 ；不救济的概率：1/2流浪汉：寻找工作的概率：0. 2；流浪的概率：0.8每个参与人的战略都是给定对方混合战略时的最优战略59¡对 的解释：如果流浪汉找工作的概率小于0.2, 则政府选择不救济,如果大于0.2,政府选择救济 ,只有当概率等于0.2时,政府才会选择混合战略或任何纯战略.¡对*=0.5的解释:如果政府救济的概率大于0.5,流浪汉的最优选择是流浪,如果政府救济的概率小于0.5,流浪汉的最优选择是寻找工作.60¡混合战略纳什均衡的含义：¡纳什均衡要求每个参与人的混合战略是给定对方的混合战略下的最优选择因此在社会福利博弈中， *=0.5是唯一的混合战略纳什均衡¡从反面来说，如果政府认为流浪汉选择寻找工作的概率严格小于0.2，那么政府的唯一最优选择是纯战略：不救济；¡如果政府以1的概率选择不救济，流浪汉的最优选择是寻找工作，这又将导致政府选择救济的战略，流浪汉则选择游荡。

如此等等61流浪汉寻找工作的概率小于0.2政府概率为1：不救济流浪汉寻找工作政府救济62经 济 如 局人 生 如 棋博 弈 之 道生 活 之 常运 用 之 妙存 乎 一 心63若有不当之处，请指正，谢谢！64。