广工管理运筹学第十章博弈论.ppt

第10章 博弈论v博弈论概述v完全信息静态博弈v完全信息动态博弈v博弈论在经济管理中的应用引例v本章主要介绍博弈论的基本概念、种类以及各种博弈均衡的含义、求法和应用。v通过本章学习，要求：了解博弈论的基本概念；掌握非合作博弈的种类以及均衡解之间的关系，特别是完全信息静态博弈和完全信息动态博弈。会求博弈的一些基本类型的均衡解并了解它们在经济管理中的部分应用例子。v田忌赛马博弈田忌赛马博弈v华容道博弈华容道博弈 博弈及博弈论博弈及博弈论博弈就是策略对抗，或策略有关键作用的游戏博弈就是策略对抗，或策略有关键作用的游戏v博弈Game，博弈论Game Theory，Game即游戏、竞技v游戏和经济等决策竞争较量的共同特征：规则、结果、策略选择，策略和利益相互依存，策略的关键作用 游戏下棋、猜大小 经济寡头产量决策、市场阻入、投标拍卖 政治、军事美国和伊拉克、以色列和巴勒斯坦定义定义：博弈就是参与人（可能是个人，也可能是团体，如国家、企业、国际组织等）在一定得规则下，同时或先或后，一次或多次，从各自允许选择的行动或战略中进行选择并加以实施，而取得相应结果（支付函数）的过程。都有一定的规则都有一定的规则 都有一个结果都有一个结果 策略至关重要，游戏者不同的策略选择常会带来不同的游戏结果策略至关重要，游戏者不同的策略选择常会带来不同的游戏结果 策略和利益有相互依存性策略和利益有相互依存性 v博弈论：博弈论就是系统研究具有上述特征的博弈问题，寻博弈论：博弈论就是系统研究具有上述特征的博弈问题，寻求各博弈方合理选择战略情况下博弈的解，并对这些解进行求各博弈方合理选择战略情况下博弈的解，并对这些解进行讨论分析的理论。讨论分析的理论。博弈的分类博弈的分类v首先，分为非合作博弈非合作博弈和合作博弈合作博弈两大类。如果有达成一个具有约束力的协议，就是合作博弈；反之，就是非合作博弈。本章主要介绍非合作博弈。静态博弈与非静态博弈静态博弈与非静态博弈v静态博弈指的是博弈中所有参与人同时选择行动，或虽非同时但后行动者并不知道先行动者采取了什么具体行动。v动态博弈指的是参与人的行动有先后顺序，且后行动者能观察到先行动者所选择的行动。完全信息博弈和不完全信息博弈v完全信息指的是每一个参与者对所有其他参与人（对手）的特征、战略空间及支付函数有准确的知识；否则就是不完全信息。博弈的分类及对应的均衡概念博弈的分类及对应的均衡概念 10.2 完全信息静态博弈v策略型博弈模型及占优战略博弈v重复剔除的占优战略博弈v纳什均衡策略型博弈模型及占优战略博弈策略型博弈模型及占优战略博弈v非合作博弈模型从模型自身形式上可分为扩展型和策略型两种，一般用策略型模型描述完全信息静态博弈模型。v构成策略型博弈模型的三个要素 参与人或局中人参与人或局中人(Players)：独立决策、独立承担博弈结果的个人或组织v博弈规则面前博弈方之间平等，不因博弈方之间权利、地位的差异而改变v博弈方数量对博弈结果和分析有影响v根据博弈方数量分单人博弈、两人博弈、多人博弈等。最常见的是两人博弈，单人博弈是退化的博弈要素之一要素之一策略或战略（策略或战略（strategies）：博弈中各博弈方的选择内容v策略有定性定量、简单复杂之分v不同博弈方之间不仅可选策略不同，而且可选策略数量也可不同v有限博弈：每个博弈方的策略数都是有限的v无限博弈：至少有某些博弈方的策略有无限多个要素之二要素之二支付函数支付函数(Payoffs function)：各博弈方从博弈中所获得的利益v得益对应博弈的结果，也就是各博弈方策略的组合v得益是各博弈方追求的根本目标及行为和判断的主要依据v根据得益的博弈分类：零和博弈、常和博弈、变和博弈要素之三要素之三占优策略占优策略v在某个博弈中，如果不管其他局中人选择什么策略，一个局中人的某个策略选择给他带来的支付始终高于其他策略选择，或者至少不低于其他策略选择。这样，只要这个局中人是一个理性人，那么他必定愿意选择这个策略。这样的策略，叫做占优策略占优策略（dominant strategy）.严格占优策略v指无论其他剧中人选择什么策略，这个局中人的某个策略选择给他带来的支付总是高于其他策略选择。v囚徒困境博弈中，“坦白”就是严格优势策略。对于甲来讲，不管乙采取什么策略，他坦白总是比较有利的。v设在一个二人同时决策博弈中，sisj是局中人1的策略，如果对于局中人2的每一个策略，都有vu1(si,s)u1(sj,s)，则称局中人1的策略si严格严格优于优于局中人1的策略sjvu1(si,s)u1(sj,s)，则称局中人1的策略si严格严格劣于劣于局中人1的策略sj占优策略占优策略(上策上策)均衡均衡l占优策略占优策略(上策上策)通俗来说是：通俗来说是：“我所做的是不管你做什么我所能做的最好的我所做的是不管你做什么我所能做的最好的”“你所做的是不管我做什么你所能做的最好的你所做的是不管我做什么你所能做的最好的”l占优策略均衡占优策略均衡指博弈中的所有参与者的占优策指博弈中的所有参与者的占优策略组合所构成的均衡。略组合所构成的均衡。例10.1 囚徒困境博弈v囚徒的困境是塔克（Tucker）1950年提出的v该博弈是博弈论最经典、著名的博弈v该博弈本身讲的是一个法律刑侦或犯罪学方面的问题，但可以扩展到许多经济问题，以及各种社会问题，可以揭示市场经济的根本缺陷基本模型 1950年，由就职于兰德公司的梅里尔弗拉德（Merrill Flood）和梅尔文德雷希尔（Melvin Dresher）拟定出相关困境的理论，后来由顾问阿尔伯特塔克（Albert Tucker）以囚徒方式阐述，并命名为“囚徒困境”。经典的囚徒困境如下：警方逮捕甲、乙两名嫌疑犯，但没有足够证据指控二人入罪。于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供以下相同的选择：v若一人认罪并作证检举对方（相关术语称“背叛”对方），而对方保持沉默，此人将即时获释，沉默者将判监8年。v若二人都保持沉默（相关术语称互相“合作”），则二人同样判监1年。v若二人都互相检举（互相“背叛”），则二人同样判监5年。双矩阵模式由博弈论大师托马斯 谢林（Thomas C.Schelling）提出，用双矩阵形式来表示博弈双方的支付情况，简单直观，学过博弈论的人都用过双矩阵模式。2005年，谢林教授获得诺贝尔经济学奖。大师的谦逊谢林说：“假如有人问我有没有对博弈论作出一点贡献，我会回答有的。若问是什么，我会说我发明了用一个矩阵反映双方得失的做法。我不认为这个发明可以申请专利，所以我免费奉送，不过，除了我的学生，几乎没有人愿意利用这个便利。现在，我也要给各位免费使用我发明的矩阵。”囚徒困境囚徒困境8，8-1，1010，-12，2坦白坦白坦白坦白不坦白不坦白不坦白不坦白囚徒囚徒2囚徒囚徒1囚徒囚徒1的选择的选择:一定先考虑一定先考虑2的选择。若的选择。若2选坦白，则选坦白，则1选坦白；若选坦白；若2选不选不坦白，则坦白，则1还选坦白。还选坦白。囚徒囚徒1有一个占优策略有一个占优策略“坦坦白白”。囚徒囚徒2的选择的选择:同理，囚徒同理，囚徒2也也 有一个占有一个占优策略优策略“坦白坦白”。（坦白，坦白）是囚徒困（坦白，坦白）是囚徒困境模型的必然占优策略均衡。境模型的必然占优策略均衡。但并不是最优的策略选但并不是最优的策略选择。最优应为（不坦白，不坦择。最优应为（不坦白，不坦白）。白）。囚徒困境（囚徒困境（Prisoners Dilemma ）l只达到效率很差的个体理性解，没有实现团体只达到效率很差的个体理性解，没有实现团体理性解。理性解。l前者是稳定的，是自动实施的；尽管团体理性前者是稳定的，是自动实施的；尽管团体理性解对大家都好，但它是不能自动实施的，需要改变解对大家都好，但它是不能自动实施的，需要改变条件。条件。提示：提示：该博弈揭示了个体理性与团体理性之间的矛盾。从个体利益出发的行为往往不能实现团体的最大利益，同时也揭示了个体理性本身的内在矛盾从个体利益出发的行为最终也不一定能真正实现个体的最大利益，甚至得到相当差的结果。重复剔除的占优战略均衡重复剔除的占优战略均衡 首先找出某一博弈参与人的严格劣战略，将它剔除掉，重新构造一个不包括已剔除战略的新的博弈；然后继续剔除这个新的博弈中某一参与人的严格劣战略；重复进行这一过程，直到剩下唯一的参与人战略组合为止。这个唯一剩下的参与人战略组合，就是这个博弈的均衡解，称为“重重复复剔剔除除的的占占优优战战略略均均衡衡”(iterated”(iterated dominance dominance equilibrium).equilibrium).这种方法也叫做严格劣势逐次消去法严格劣势逐次消去法。v假设猪圈里有两头猪，一头大猪，一头小猪，猪圈的一端有一个猪食槽，另一端安装了一个按钮，控制猪食的供应。按一下按钮。将有10个单位的猪食进入猪食槽，供两头猪食用。两头猪面临选择的策略有两个：自己去按按钮或等待另一头猪去按按钮。如果某一头猪作出自己去按按钮的选择，它必须付出如下代价：第一，它需要收益相当于2个单位的成本；第二，由于猪食槽远离猪食，它将比另一头猪后到猪食槽，从而减少吃食的数量。v大猪先到：大猪吃到9个单位，小猪吃到1个单位；v小猪先到：小猪吃到4个单位，大猪吃到6个单位；v同时到达：大猪吃到7个单位，小猪吃到3个单位。智猪博弈（大小猪博弈）27大猪不按按不按按小猪(4,4)(5,1)(9,-1)(0,0)vv局中人：大猪和小猪vv行动：按按钮吃东西小猪大猪按等待按5，14，4等待9，10，0小猪的上策29v双方力量不对等时的正确策略力量强：主动出击力量弱：等待，搭强者的便车。30智猪博弈的应用vv政治博弈大国是大猪，小国是小猪大国是大猪，小国是小猪vv资本市场大股东是大猪，小股东是小猪大股东是大猪，小股东是小猪vv企业创新策略大企业是大猪，小企业是小猪大企业是大猪，小企业是小猪1，01，33，00，20，13，00，22，45，3甲甲乙乙TMBLCR1，01，30，20，10，22，4TMB乙乙LC甲甲C和R比较，乙绝对不会选R。T和M比较，甲绝对不会选M。严格劣势逐次消去法举例严格劣势逐次消去法举例1，01，30，22，4TB乙乙LC甲甲1，32，4TB乙乙C甲甲最后，博弈均衡的结果是（B，C）。L和C比较，乙绝对不会选L。T和B比较，甲绝对不会选T。严格劣势逐次消去法严格劣势逐次消去法的缺点：严格优、严格劣的情况不是很经常出现，适用范围太窄。纳什（Nash）均衡1.纯战略Nash均衡v策略空间：每个博弈方的全部可选策略的集合v博弈方 的第 个策略：v博弈方 的得益：v博弈：定义1：在博弈 中，如果由各个博弈方的各一个策略组成的某个策略组合 中，任一博弈方 的策略 ，都是对其余博弈方策略的组合 的最佳对策，也即 对任意 都成立，则称 为 的一个纳什均衡（Nash Equilibrium）。定义2：一个Nash均衡是强的（Strict或Strong），如果给定其他局中人的战略，每一个局中人的最优选择是唯一的。即是说 是一个强Nash均衡，当且仅当对于所有的 ，有通俗地讲，纳什均衡就是局中人单独改变策略不会得到好处的策略组合。孤独的天才孤独的天才约翰约翰福布斯福布斯纳什纳什 约翰约翰福布斯福布斯纳什纳什（John Forbes Nash Jr.，1928年6月13日），美国数学家，前麻省理工学院助教，主要研究博弈论和微分几何学。1994年，他和其他两位博弈论学家约翰C海萨尼(John Harsanyi)和莱因哈德泽尔腾共同获得了诺贝尔经济学奖。1950年，纳什获得美国普林斯顿高等研究院的博士学位，他在那篇仅仅27页的博士论文中提出了一个重要概念，也就是后来被称为“纳什均衡”的博弈理论。v他不是一个善于为人处世并受大多数人欢迎的人，他们说他“孤僻，傲慢，无情，幽灵一般，古怪，沉醉于自己的隐秘世界，根本不能理解别人操心的世俗事务。”v在他的孩子出生前，被送进了精神病医院。v在上世纪70和80年代，普林斯顿大学的学生和学者们总能在校园里看见一个非常奇特、消瘦而沉默的男人在徘徊，他穿着紫色的拖鞋，偶尔在黑板上演算。v1980年代末纳什渐渐康复，从疯癫中苏醒。推荐电影推荐电影“美丽心灵美丽心灵”。2求解Nash均衡的方法（1）划线法v思路：先找出自己针对其他博弈方每种策略或策略组合（对多人博弈）的最佳对策，即自己的可选策略中与其他博弈方的策略或策略组合配合，给自己带来最大得益的策略（这种相对最佳对策总是存在的，不过不一定惟一），然后再此基础上，通过对其他博弈方策略选择的判断，包括对其他博弈方对自己策略判断的判断等，预测博弈的可能结果和确定自己的最优策略。划线法求解纳什均衡v例10.2 BLMRU3,24,75,1AH6,12,81,1D3,78,910,42，10，0-1，-11，2足球足球芭蕾芭蕾丽娟丽娟大海大海足球足球芭蕾芭蕾不存在严格优势策略和严格劣势策略。不存在严格优势策略和严格劣势策略。性别战或情侣博弈性别战或情侣博弈2，10，0-1，-11，2足球足球芭蕾芭蕾丽娟丽娟大海大海足球足球芭蕾芭蕾如果丽娟选择“足球”，那么大海当然选择“足球”。2，10，0-1，-11，2足球足球芭蕾芭蕾丽娟丽娟大海大海足球足球芭蕾芭蕾如果丽娟选择“芭蕾”，那么大海也应该选择“芭蕾”。2，10，0-1，-11，2足球足球芭蕾芭蕾丽娟丽娟大海大海足球足球芭蕾芭蕾如果大海选择“足球”，那么丽娟也应该选择“足球”。如果大海选择“芭蕾”，那么丽娟当然会选择“芭蕾”。双方的相对优势策略都这样划线以后，如果哪个格子里面两个数字下面都被划线，这个格子所对应的策略组合，就是一个纳什均衡。（2）反应函数法 例例10.310.3 古诺（Cournot）寡头竞争模型 19世纪法国著名数学家奥古斯丁古诺建立，该模型描述了两个销售完全同质商品的企业，在市场竞争中如何决定各自的产量，以实现各自的利润最大化。设有n人博弈GS1,S2,Sn;u1,u2,un的策略集都是实数的开区间，并且支付函数是可微的多元函数，在这种情况下，如果一个策略组合s*=（s1*,sn*）是这个博弈的纳什均衡的话，那么它必须是方程组的解。连续情形纳什均衡的必要条件连续情形纳什均衡的必要条件古诺寡头竞争模型（1838）企业1企业2v参与人：企业参与人：企业1 1、企业、企业2 2v战略：战略：选择产量选择产量v得益：得益：利润，利润是两个企业产量的函数利润，利润是两个企业产量的函数博弈三要素：博弈三要素：寡头产量竞争以两厂商产量竞争为例假设策略组合（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)）是本博弈唯一的纳什均衡。此时每个企业的利润为 产量博弈的古诺模型是一种囚徒困境，无法实现博弈方总体和各个博弈方各自最大利益的结论，对于市场经济组织、管理，对于产业组织和社会经济制度的效率判断，都具有非常重要的意义。说明对市场的管理，政府对市场的调控和监管都是必须的。（3）混合战略Nash均衡 v例例10.410.4 社会福利博弈 23，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作没有一个策略组合构成纳什均衡例例10.5 10.5 猜硬币游戏 1-1，-11，-11，1-1，反面正面反面正面猜谜游戏v两个儿童各拿一枚硬币，v若同时正面朝上或朝下，A给B 1分钱，v若只有一面朝上，B给A 1分钱。零和博弈博弈参与者有输有赢，但结果永远是0。没有一个策略组合构成纳什均衡没有一个策略组合构成纳什均衡v定义定义3 n人战略式表述博弈 中，概率密度 被称为局中人i的一个混合战略，是i选择 的概率，为 中纯战略个数（可为无穷大）。v定定义义4 n人战略式表述博弈 中，混合战略组合 是一个Nash均衡，如果对于所有的 ，有：n社会福利博弈 23，3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：；不救济的概率：1-。流浪汉找工作的概率为，不找工作的概率：1-。例10.7社会福利博弈的混合策略Nash均衡 流浪汉找工作的最优概率*应该使得政府选择救济或者不救济的期望得益相等。3*+(-1)(1-*)=(-1)*+0(1-*)得*=0.2同样道理，2*+1(1-*)=3*+0(1-*)得*=0.5混合策略博弈的纳什均衡为：（救济，不救济；0.5，0.5），（找工作，游荡；0.2，0.8）23，3-1，1-1，00，流浪1-流浪汉政府救济 不救济 1-寻找工作 政府的期望得益U1=3 +(-1)(1-)-(1-)+0(1-)(1-)=(5-1)-政府的反应函数是 23，3-1，1-1，00，流浪1-流浪汉政府救济 不救济 1-寻找工作 流浪汉的期望得益U2=2 +1(1-)+3 (1-)+0(1-)(1-)=(1-2)+3流浪汉的反应函数是红线是政府的反应函数，蓝线是流浪汉的反应函数。