运筹学博弈论-课件

第10章博弈论10.1博弈论概述10.2完全信息静态博弈2020/12/271第10章博弈论10.1博弈论概述2020/12/271第一节博弈论概述2020/12/272第一节博弈论概述2020/12/272田忌赛马博弈华容道博弈

一、博弈论的产生和发展1.博弈在中国2020/12/273田忌赛马博弈一、博弈论的产生和发展1.博弈在中国2020/从孙子兵法到三十六计从田忌赛马到孙庞斗智从运筹帷幄到韬光养晦从曹刿论战到论持久战2020/12/274从孙子兵法到三十六计2020/12/2742.博弈论的开山之作1943年，冯·诺依曼和摩根斯顿发表《博弈论和经济行为》的一书，标志着博弈论作为一门独立科学的开始，也标志着新古典经济学进入了一个新的发展阶段。2020/12/2752.博弈论的开山之作标志着博弈论作为一门独立科学的开始，也3.1994年三位获诺奖的博弈论学者JohnNashJohnHarsanyLeihadenSelten2020/12/2763.1994年三位获诺奖的博弈论学者JohnNashJ4.1996年诺贝尔经济学奖得主：詹姆斯·莫里斯：主要贡献：不对称信息条件下的激励理论2020/12/2774.1996年诺贝尔经济学奖得主：詹姆斯·莫里斯：主要贡5.2001年诺贝尔经济学奖得主：迈克尔·斯宾塞：在不对称信息市场分析方面所做出开创性研究。

2020/12/2785.2001年诺贝尔经济学奖得主：迈克尔·斯宾塞：在不对称6.2005年二位获诺奖的博弈论学者RobertAumannThomasShelling2020/12/2796.2005年二位获诺奖的博弈论学者RobertAuma10.1.2博弈及博弈论博弈就是策略对抗，或策略有关键作用的游戏博弈Game，博弈论GameTheory，Game即游戏、竞技游戏和经济等决策竞争较量的共同特征：规则、结果、策略选择，策略和利益相互依存，策略的关键作用游戏——下棋、猜大小经济——寡头产量决策、市场阻入、投标拍卖政治、军事——美国和伊拉克、以色列和巴勒斯坦2020/12/271010.1.2博弈及博弈论博弈就是策略对抗，或策略有关键作用定义：博弈就是参与人（可能是个人，也可能是团体，如国家、企业、国际组织等）在一定得规则下，同时或先或后，一次或多次，从各自允许选择的行动或战略中进行选择并加以实施，而取得相应结果（支付函数）的过程。

都有一定的规则

都有一个结果

策略至关重要，游戏者不同的策略选择常会带来不同的游戏结果

策略和利益有相互依存性

博弈论：博弈论就是系统研究具有上述特征的博弈问题，寻求各博弈方合理选择战略情况下博弈的解，并对这些解进行讨论分析的理论。2020/12/2711定义：博弈就是参与人（可能是个人，也可能是团体，如国家、企业博弈的分类及对应的均衡概念

2020/12/2712博弈的分类及对应的均衡概念2020/12/271210.2完全信息静态博弈10.2.1策略型博弈模型及占优战略博弈10.2.2重复剔除的占优战略博弈10.2.3纳什均衡2020/12/271310.2完全信息静态博弈10.2.1策略型博弈模型及占优10.2.1策略型博弈模型及占优战略博弈非合作博弈模型从模型自身形式上可分为扩展型和策略型两种，一般用策略型模型描述完全信息静态博弈模型。构成策略型博弈模型的三个要素:局中人、策略、支付函数2020/12/271410.2.1策略型博弈模型及占优战略博弈非合作博弈模型从模参与人或局中人(Players)：独立决策、独立承担博弈结果的个人或组织博弈规则面前博弈方之间平等，不因博弈方之间权利、地位的差异而改变博弈方数量对博弈结果和分析有影响根据博弈方数量分单人博弈、两人博弈、多人博弈等。最常见的是两人博弈，单人博弈是退化的博弈2020/12/2715参与人或局中人(Players)：独立决策、

策略或战略（strategies）：博弈中各博弈方的选择内容。策略有定性定量、简单复杂之分不同博弈方之间不仅可选策略不同，而且可选策略数量也可不同有限博弈：每个博弈方的策略数都是有限的无限博弈：至少有某些博弈方的策略有无限多个2020/12/2716策略或战略（strategies）：

支付函数(Payoffsfunction)：各博弈方从博弈中所获得的利益。得益对应博弈的结果，也就是各博弈方策略的组合得益是各博弈方追求的根本目标及行为和判断的主要依据根据得益的博弈分类：零和博弈、常和博弈、变和博弈2020/12/2717支付函数(Payoffsfunction)：例10.1囚徒困境博弈囚徒的困境是图克（Tucker）1950年提出的该博弈是博弈论最经典、著名的博弈该博弈本身讲的是一个法律刑侦或犯罪学方面的问题，但可以扩展到许多经济问题，以及各种社会问题，可以揭示市场经济的根本缺陷2020/12/2718例10.1囚徒困境博弈囚徒的困境是图克（Tucker）1基本模型

经典的囚徒困境如下：警方逮捕甲、乙两名嫌疑犯，但没有足够证据指控二人入罪。于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供以下相同的选择：若一人认罪并作证检举对方（相关术语称“背叛”对方），而对方保持沉默，此人将即时获释，沉默者将判监8年。若二人都保持沉默（相关术语称互相“合作”），则二人同样判监1年。若二人都互相检举（互相“背叛”），则二人同样判监5年。2020/12/2719基本模型经典的囚徒困境如下：2020/12/囚徒困境-5，-50，-8-8，0-1，-1囚徒A囚徒B坦白抵赖坦白抵赖坦白是A的占优战略坦白是B的占优战略2020/12/2720囚徒困境-5，-50，-8-8，0-1，-1囚徒A囚徒B坦占优策略(上策)均衡占优策略(上策)通俗来说是：

“我所做的是不管你做什么我所能做的最好的”

“你所做的是不管我做什么你所能做的最好的”占优策略均衡指博弈中的所有参与者的占优策略组合所构成的均衡。2020/12/2721占优策略(上策)均衡占优策略(上策)通俗来说是：2020/1囚徒困境（Prisoners’Dilemma）只达到效率很差的个体理性解，没有实现团体理性解。前者是稳定的，是自动实施的；尽管团体理性解对大家都好，但它是不能自动实施的，需要改变条件。提示：该博弈揭示了个体理性与团体理性之间的矛盾。——从个体利益出发的行为往往不能实现团体的最大利益，同时也揭示了个体理性本身的内在矛盾——从个体利益出发的行为最终也不一定能真正实现个体的最大利益，甚至得到相当差的结果。2020/12/2722囚徒困境（Prisoners’Dilemma）只达到效率

10.2.2重复剔除的占优战略均衡

首先找出某一博弈参与人的严格劣战略，将它剔除掉，重新构造一个不包括已剔除战略的新的博弈；然后继续剔除这个新的博弈中某一参与人的严格劣战略；重复进行这一过程，直到剩下唯一的参与人战略组合为止。这个唯一剩下的参与人战略组合，就是这个博弈的均衡解，称为“重复剔除的占优战略均衡”(iterateddominanceequilibrium).2020/12/272310.2.2重复剔除的占优战略均衡首先找出某一智猪博弈：假设猪圈里有两头猪，一头大猪，一头小猪，猪圈的一端有一个猪食槽，另一端安装了一个按钮，控制猪食的供应。按一下按钮。将有10个单位的猪食进入猪食槽，供两头猪食用。两头猪面临选择的策略有两个：自己去按按钮或等待另一头猪去按按钮。如果某一头猪作出自己去按按钮的选择，它必须付出如下代价：第一，它需要收益相当于2个单位的成本；第二，由于猪食槽远离猪食，它将比另一头猪后到猪食槽，从而减少吃食的数量。大猪先到：大猪吃到9个单位，小猪吃到1个单位；小猪先到：小猪吃到4个单位，大猪吃到6个单位；同时到达：大猪吃到7个单位，小猪吃到3个单位。智猪博弈（大小猪博弈）2020/12/2724智猪博弈：假设猪圈里有两头猪，一头大猪，一头小猪，猪圈的一端25大猪不按按不按按小猪(4,4)(5,1)(9,-1)(0,0)局中人：大猪和小猪行动：按按钮吃东西2020/12/272525大猪不按按不按按小猪(4,4)(5,1)(9,-1小猪大猪按等待按5，14，4等待9，－10，0小猪的上策2020/12/2726小猪大猪按等待按5，14，4等待9，－10，0小猪的上策2027双方力量不对等时的正确策略力量强：主动出击力量弱：等待，搭强者的便车。2020/12/272727双方力量不对等时的正确策略2020/12/272728智猪博弈的应用政治博弈大国是大猪，小国是小猪资本市场大股东是大猪，小股东是小猪企业创新策略大企业是大猪，小企业是小猪2020/12/272828智猪博弈的应用政治博弈2020/12/2728重复剔除的占优均衡1，01，20，30，1M列先生行先生UDL0，12，0R行：没有占优策略列：M严格优于R剔除R行：U优于D列：无占优策略剔除DM优于L（U，M）是重复剔除的占优均衡2020/12/2729重复剔除的占优均衡1，01，20，30，1M列先生行先生UD纳什均衡概念是现代博弈论的核心概念。它是以美国数学家、经济学家纳什（Nash）的名字命名的，纳什在1950年的一篇论文中提出了纳什均衡的概念。10.2.3纳什（Nash）均衡2020/12/2730纳什均衡概念是现代博弈论的核心概念。它是以美国数学家、经济学纳什均衡(NashEquilibrium)通俗地说，纳什均衡的含义就是：给定你的策略，我的策略是最好的策略；给定我的策略，你的策略也是你的最好的策略。即双方在给定的策略下不愿意调整自己的策略。2020/12/2731纳什均衡(NashEquilibrium)通俗地说，纳什均1.纯战略Nash均衡策略空间：每个博弈方的全部可选策略的集合博弈方的第个策略：博弈方的得益：博弈：2020/12/27321.纯战略Nash均衡2020/12/2732定义1在博弈中，如果由各个博弈方的各一个策略组成的某个策略组合中，任一博弈方的策略，都是对其余博弈方策略的组合的最佳对策，也即

对任意都成立，则称为的一个纳什均衡（NashEquilibrium）。2020/12/2733定义1在博弈定义2：一个Nash均衡是强的（Strict或Strong），如果给定其他局中人的战略，每一个局中人的最优选择是唯一的。即是说是一个强Nash均衡，当且仅当对于所有的，，有2020/12/2734定义2：一个Nash均衡是强的（Strict或S2．求解Nash均衡的方法（1）划线法思路：先找出自己针对其他博弈方每种策略或策略组合（对多人博弈）的最佳对策，即自己的可选策略中与其他博弈方的策略或策略组合配合，给自己带来最大得益的策略（这种相对最佳对策总是存在的，不过不一定惟一），然后再此基础上，通过对其他博弈方策略选择的判断，包括对其他博弈方对自己策略判断的判断等，预测博弈的可能结果和确定自己的最优策略。2020/12/27352．求解Nash均衡的方法2020/12/2735划线法求解纳什均衡例10.2BLMRU3,24,75,1AH6,12,81,1D3,78,910,42020/12/2736划线法求解纳什均衡例10.2BLMRU3,24,75,1A（2）反应函数法例10.3古诺（Cournot）寡头竞争模型

2020/12/2737（2）反应函数法2020/12/2737古诺寡头竞争模型（1838）企业1企业2参与人：企业1、企业2战略：选择产量得益：利润，利润是两个企业产量的函数2020/12/2738古诺寡头竞争模型（1838）企业1企业2参与人：企业1、企业寡头产量竞争——以两厂商产量竞争为例2020/12/2739寡头产量竞争——以两厂商产量竞争为例2020/12/2739假设策略组合（q1*，q2*）是本博弈的纳什均衡，那么max（）

q1

max（

）

q2q1*，q2*只要能使两式各自对q1，q2的导数为0，就能实现两式的最大值，令：a－c－q2*－2q1*＝0

a－c－q1*－2q2*＝0解之，q1*＝q2*＝1/3(a-c)。因此，策略组合（1/3(a-c)，1/3(a-c)）是本博弈唯一的纳什均衡。此时每个企业的利润为2020/12/2740假设策略组合（q1*，q2*）是本博弈的纳什均衡，那么q1

产量博弈的古诺模型是一种囚徒困境，无法实现博弈方总体和各个博弈方各自最大利益的结论，对于市场经济组织、管理，对于产业组织和社会经济制度的效率判断，都具有非常重要的意义。说明对市场的管理，政府对市场的调控和监管都是必须的。2020/12/2741产量博弈的古诺模型是一种囚徒困境，无法实现博弈方（3）混合战略Nash均衡例10.4社会福利博弈

23，

3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作没有一个策略组合构成纳什均衡2020/12/2742（3）混合战略Nash均衡23

1-1，

-11，-11，1-1，反面正面反面正面猜谜游戏两个儿童各拿一枚硬币，若同时正面朝上或朝下，A给B1分钱，若只有一面朝上，B给A1分钱。零和博弈博弈参与者有输有赢，但结果永远是0。没有一个战略组合构成纳什均衡2020/12/27431-1-1警察与小偷银行酒馆警察小偷2万元1万元东边西边警察与小偷的最优策略各是什么？2020/12/2744警察与小偷银行酒馆警察小偷2万元1万元东边西边警察与小偷的最上述博弈的特征是：在这类博弈中，都不存在纯纳什均衡。参与人的支付取决于其他参与人的战略；以某种概率分布随机地选择不同的行动每个参与人都想猜透对方的战略，而每个参与人又不愿意让对方猜透自己的战略。这种博弈的类型是什么？如何找到均衡？2020/12/2745上述博弈的特征是：2020/12/2745请举一些这样的例子：石头、剪子、布游戏老虎、杠子、鸡、虫子游戏扑克游戏橄榄球赛战争中2020/12/2746请举一些这样的例子：石头、剪子、布游戏2020/12/274策略：参与人在给定信息集的情况下选择行动的规则，它规定参与人在什么情况下选择什么行动，是参与人的“相机行动方案”。纯策略：如果一个策略规定参与人在每一个给定的信息情况下只选择一种特定的行动，该战略为纯策略。混合策略：如果一个策略规定参与人在给定信息情况下以某种概率分布随机地选择不同的行动，则该策略为混合策略。纯策略可以理解为混合策略的特例，即在诸多策略中，选该纯策略si的概率为1，选其他纯策略的概率为0。2020/12/2747策略：参与人在给定信息集的情况下选择行动的规则，它规定参与人2020/12/27482020/12/2748

1-1，

-11，-22，2-2，西边东边西边东边警察抽签决定去银行还是酒馆，2/3的机会去银行，1/3的机会去酒馆；同样，小偷也抽签决定去银行还是酒馆，2/3的机会去酒馆，1/3的机会去银行。2020/12/27491-1-2社会福利博弈

23，

3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：1/2；不救济的概率：1/2。流浪汉：寻找工作的期望效用：1/2×2+1/2×1=1.5流浪的期望效用：1/2×3+1/2×0=1.5因此，流浪汉的任何一种战略都是都是对政府混合战略的最优反应2020/12/2750社会福利博弈23社会福利博弈

23，

3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：1/2；不救济的概率：1/2。流浪汉：寻找工作的概率：0.2；流浪的概率：0.8每个参与人的战略都是给定对方混合战略时的最优战略2020/12/2751社会福利博弈23

1-1，

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

23，

3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作即：流浪汉以0.2的概率选择寻找工作，0.8的概率选择游荡同样，可以根据流浪汉的期望效用函数找到政府的最优混合战略。？？支付最大化法2020/12/2756231社会福利博弈

23，

3-1，1-1，00，流浪流浪汉政府救济不救济寻找工作设：政府救济的概率：1/2；不救济的概率：1/2。流浪汉：寻找工作的概率：0.2；流浪的概率：0.8每个参与人的战略都是给定对方混合战略时的最优战略2020/12/2757社会福利博弈23假定最优混合战略存在，给定流浪汉选