完全信息静态非合作博弈.ppt

2019/7/19,博弈论 重庆大学 刘辛,1,第二章 完全信息静态博弈,本章介绍完全信息静态博弈。 完全信息静态博弈即各博弈方同时决策，且所有博弈方对各方收益都了解的博弈。 囚徒的困境、齐威王田忌赛马、猜硬币、石头剪子布、古诺产量决策都属于这种博弈。 完全信息静态博弈属于非合作博弈最基本的类型。 本章介绍完全信息静态博弈的一般分析方法、纳什均衡概念、各种经典模型及其应用等。,2019/7/19,博弈论 重庆大学 刘辛,2,本章分六部分,2.1基本分析思路和方法 2.2纳什均衡 2.3无限策略博弈分析和反应函数 2.4混合策略和混合策略纳什均衡 2.5纳什均衡的存在性 2.6纳什均衡的选择和分析方法扩展,2019/7/19,博弈论 重庆大学 刘辛,3,2.1 基本分析思路和方法,2.1.1 占优均衡 2.1.2 严格下策反复消去法 2.1.3 划线法 2.1.4 箭头法,2019/7/19,博弈论 重庆大学 刘辛,4,2.1.1 占优均衡,占优策略：不管其它博弈方选择什么策略，一博弈方的某个策略给他带来的收益始终高于其它的策略，至少不低于其他策略的策略 举例：囚徒的困境中的“坦白”；双寡头削价中“低价”。 占优均衡：一个博弈的某个策略组合中的所有策略都是各个博弈方各自的占优，必然是该博弈比较稳定的结果 占优均衡不是普遍存在的,2019/7/19,博弈论 重庆大学 刘辛,5,2.1.2 严格下策反复消去法,严格下策：不管其它博弈方的策略如何变化，给一个博弈方带来的收益总是比另一种策略给他带来的收益小的策略 严格下策反复消去：,2019/7/19,博弈论 重庆大学 刘辛,6,2.1.3 划线法,2019/7/19,博弈论 重庆大学 刘辛,7,2019/7/19,博弈论 重庆大学 刘辛,8,2.1.4 箭头法,2019/7/19,博弈论 重庆大学 刘辛,9,2.2 纳什均衡,2.2.1 纳什均衡的定义 2.2.2 纳什均衡的一致预测性质 2.2.3 纳什均衡与严格下策反复消去法,2019/7/19,博弈论 重庆大学 刘辛,10,2.2.1 纳什均衡的定义,策略空间： 博弈方 的第 个策略： 博弈方 的收益： 博弈： 纳什均衡：在博弈 中，如果由各个博弈方的各一个策略组成的某个策略组合 中，任一博弈方 的策略，都是对其余博弈方策略的组合 的最佳对策，也即 对任意 都成立，则称 为 的一个纳什均衡,2019/7/19,博弈论 重庆大学 刘辛,11,2.2.2 纳什均衡的一致预测性质,一致预测：如果所有博弈方都预测一个特定博弈结果会出现，所有博弈方都不会利用该预测或者这种预测能力选择与预测结果不一致的策略，即没有哪个博弈方有偏离这个预测结果的愿望，因此预测结果会成为博弈的最终结果 只有纳什均衡才具有一致预测的性质 一致预测性是纳什均衡的本质属性 一致预测并不意味着一定能准确预测，因为有多重均衡，预测不一致的可能,2019/7/19,博弈论 重庆大学 刘辛,12,2.2.3 纳什均衡与严格下策反复消去法,占优均衡肯定是纳什均衡，但纳什均衡不一定是占优均衡 命题2.1：在n个博弈方的博弈 中，如果严格下策反复消去法排除了除 之外的所有策略组合，那么 一定是该博弈的唯一的纳什均衡 命题2.2：在n个博弈方的博弈中 中，如果 是 的一个纳什均衡，那么严格下策反复消去法一定不会将它消去 上述两个命题保证在进行纳什均衡分析之前先通过严格下策反复消去法简化博弈是可行的,2019/7/19,博弈论 重庆大学 刘辛,13,2.3 无限策略分析和反应函数,2.3.1 古诺的寡头模型 2.3.2 最佳反应函数 2.3.3 伯特兰德寡头模型 2.3.4 公共资源问题 2.3.5 反应函数的问题和局限性,2019/7/19,博弈论 重庆大学 刘辛,14,2.3.1 古诺的寡头模型,寡头产量竞争以两厂商产量竞争为例,2019/7/19,博弈论 重庆大学 刘辛,15,以自身最大利益为目标：各生产 2单位产量，各自收益为4 以两厂商总体利益最大：各生产 1.5单位产量，各自收益为4.5,两寡头间的囚徒困境博弈,2019/7/19,博弈论 重庆大学 刘辛,16,2.3.2 最佳反应函数,古诺模型的最佳反应函数,理性局限和古诺调整,2019/7/19,博弈论 重庆大学 刘辛,17,2.3.3 伯特兰德寡头模型,价格竞争寡头的博弈模型 产品无差别，消费者对价格不十分敏感,2019/7/19,博弈论 重庆大学 刘辛,18,2.3.4 公共资源问题,公共草地养羊问题,以三农户为例 n=3，c=4,2019/7/19,博弈论 重庆大学 刘辛,19,合作：总体利益最大化,竞争：个体利益最大化,2019/7/19,博弈论 重庆大学 刘辛,20,2.3.5 反应函数的问题和局限性,在许多博弈中，博弈方的策略是有限且非连续时，其收益函数不是连续可导函数，无法求得最佳反应函数，从而不能通过解方程组的方法求得纳什均衡。 即使收益函数可以求导，也可能各博弈方的收益函数比较复杂，因此各自的反应函数也比较复杂，并不总能保证各博弈方的最佳反应函数有交点，特别不能保证有唯一的交点。,2019/7/19,博弈论 重庆大学 刘辛,21,2.4 混合策略和混合策略纳什均衡,2.4.1 严格竞争博弈和混合策略的引进 2.4.2 多重均衡博弈和混合策略 2.4.3 混合策略和严格下策反复消去法 2.4.4 混合策略反应函数,2019/7/19,博弈论 重庆大学 刘辛,22,2.4.1 严格竞争博弈和混合策略的引进,一、猜硬币博弈,（1）不存在前面定义的纳什均衡策略组合 （2）关键是不能让对方猜到自己策略 这类博弈很多，引出混合策略纳什均衡概念,2019/7/19,博弈论 重庆大学 刘辛,23,二、混合策略、混合策略博弈 和混合策略纳什均衡,混合策略：在博弈 中，博弈方 的策略空间为 ，则博弈方 以概率分布 随机在其 个可选策略中选择的“策略”，称为一个“混合策略”，其中 对 都成立，且 混合策略扩展博弈：博弈方在混合策略的策略空间（概率分布空间）的选择看作一个博弈，就是原博弈的“混合策略扩展博弈）。 混合策略纳什均衡：包含混合策略的策略组合，构成纳什均衡。,2019/7/19,博弈论 重庆大学 刘辛,24,三、一个例子,该博弈无纯策略纳什均衡，可用混合策略纳什均衡分析,策略 收益 博弈方1 （0.8，0.2） 2.6 博弈方2 （0.8，0.2） 2.6,2019/7/19,博弈论 重庆大学 刘辛,25,五、小偷和守卫的博弈,加重对保安的处罚：短期中的效果是使保安真正尽职 在长期中并不能使保安更尽职，但会降低盗窃发生的概略,Pt 小偷 偷的概率,2019/7/19,博弈论 重庆大学 刘辛,26,加重对小偷的处罚：短期内能抑制盗窃发生率 长期并不能降低盗窃发生率，但会是的守卫更多的偷懒,2019/7/19,博弈论 重庆大学 刘辛,27,2.4.2 多重均衡博弈和混合策略,一、夫妻之争的混合策略纳什均衡,夫妻之争博弈的混合策略纳什均衡 策略 收益 博弈方1 （0.75，0.25） 0.67 博弈方2 （1/3，2/3） 0.75,2019/7/19,博弈论 重庆大学 刘辛,28,二、制式问题,制式问题混合策略纳什均衡 A B 收益 厂商1： 0.4 0.6 0.664 厂商2： 0.67 0.33 1.296,2019/7/19,博弈论 重庆大学 刘辛,29,三、市场机会博弈,进 不进 收益 厂商1： 2/3 1/3 0 厂商2： 2/3 1/3 0,2019/7/19,博弈论 重庆大学 刘辛,30,2.4.3 混合策略和严格下策反复消去法,2019/7/19,博弈论 重庆大学 刘辛,31,2.4.4 混合策略反应函数,猜硬币博弈,2019/7/19,博弈论 重庆大学 刘辛,32,夫妻之争博弈,2019/7/19,博弈论 重庆大学 刘辛,33,2.5 纳什均衡的存在性,纳什定理：在一个由n个博弈方的博弈 中，如果n是有限的，且 都是 有限集(对 )，则该博弈至少存在一个纳什均衡，但可能包含混合策略。 参见教材证明。主要根据是布鲁威尔和角谷的不动点定理。 纳什均衡的普遍存在性正是纳什均衡成为非合作博弈分析核心概念的根本原因之一。,2019/7/19,博弈论 重庆大学 刘辛,34,2.6 纳什均衡的选择和分析方法扩展,2.6.1 多重纳什均衡博弈的分析 2.6.2 共谋和防共谋均衡,2019/7/19,博弈论 重庆大学 刘辛,35,2.6.1 多重纳什均衡博弈的分析,帕累托占优均衡 风险占优均衡 聚点均衡 相关均衡,2019/7/19,博弈论 重庆大学 刘辛,36,一、帕累托占优均衡,（鹰鸽博弈） 这个博弈中有两个纯策略 纳什均衡，（战争，战争） 和（和平，和平），显然 后者帕累托优于前者，所 以，（和平，和平）是本 博弈的一个帕累托占优均衡。,2019/7/19,博弈论 重庆大学 刘辛,37,市场进入阻挠,斗争,在位者,进入者,进入,不进入,默许,纳什均衡：进入，默许；不进入，斗争,2019/7/19,博弈论 重庆大学 刘辛,38,二、风险占优均衡,考虑、顾忌博弈方、其他博弈方可能发生错误等时，帕累托占优均衡并不一定是最优选择，需要考虑：风险占优均衡。下面就是两个例子。,2019/7/19,博弈论 重庆大学 刘辛,39,三、聚点均衡,利用博弈设定以外的信息和依据选择的均衡 文化、习惯或者其他各种特征都可能是聚点均衡的依据 城市博弈（城市分组相同）、时间博弈（报出相同的时间）是聚点均衡的典型例子,2019/7/19,博弈论 重庆大学 刘辛,40,四、相关均衡,三个纳什均衡： （U，L）、（D，R）、（D,L） 和混合策略均衡（1/2，1/2），（1/2，1/2） 结果都不理想，不如（D，L）。,可利用聚点均衡（天气，抛硬币），但仍不理想。,相关装置： 1、各1/3概率A、B、C 2、博弈方1看到是否A，博弈方2看到是否C 3、博弈方1见A采用U，否则D；博弈方2见C采用R，否则L。,相关均衡要点： 1、构成纳什均衡 2、有人忽略不造成问题,2019/7/19,博弈论 重庆大学 刘辛,41,一、多人博弈中的共谋问题 本博弈的纯策略纳什均衡：（U，L，A）、（D，R，B） 前者帕累托优于后者。博弈的结果会是什么呢？ （U，L，A）有共谋 (Coalition)问题：博弈方1和2同时偏离。,2.6.2 共谋和防共谋均衡,2019/7/19,博弈论 重庆大学 刘辛,42,二、防共谋均衡,如果一个博弈的某个策略组合满足下列要求： （1）没有任何单个博弈方的“串通”会改变博弈的结果，即单独改变策略无利可图； （2）给定选择偏离的博弈方有再次偏离的自由时，没有任何两个博弈方的串通会改变博弈的结果； （3）依此类推，直到所有博弈方都参加的串通也不会改变博弈的结果。 称为“防共谋均衡”。 前面例子中：（D，R，B） 是防共谋均衡 （U，L，A）不是防共谋均衡,2019/7/19,博弈论 重庆大学 刘辛,43,六 纳什均衡存在性及相关讨论,大流士阴谋推翻波斯王国的故事： 当时，一群波斯贵族聚在一起决定推翻国王，其间有人提议休会，大流士此时站出来大声疾呼，说如果休会的话，就一定会有人去国王那里告密，因为如果别人不那么做的话，他自己就会去做，大流士说唯一的办法就是冲进皇宫，杀死国王。 这个谋反的故事还提供了关于协调博弈的出路。在杀死国王之后，贵族们想从自己人中推选出一个人当国王，他们决定不自相残杀，而是在佛晓十分到山上去，谁的马先叫谁就当国王。大流士的马夫在这场随机的安排中做了手脚，从而成为国王。,2019/7/19,博弈论 重庆大学 刘辛,44,纳什均衡应用举例,案例1 库诺特（Cournot）寡头竞争模型 案例2 公共地的悲剧 案例3 普林斯顿大学的一道习题,2019/7/19,博弈论 重庆大学 刘辛,45,案例1 库诺特（Cournot）寡头竞争模型,企业1,企业2,参与人：企业1、企业2 战略： 选择产量 支付： 利润，利润是两个企业产量的函数,2019/7/19,博弈论 重庆大学 刘辛,46,案例1 库诺特（Cournot）寡头竞争模型,qi ：第i个企业的产量 Ci（qi）代表成本函数 P=P（q1+q2）：价格是两个企业产量的函数 第i个企业的利润函数为：,2019/7/19,博弈论 重庆大学 刘辛,47,案例1 库诺特（Cournot）寡头竞争模型,（q1*，q2*）是纳什均衡意味着：,找出纳什均衡的方法是对每个企业的利润函数求一阶导数，使其为0。,2019/7/19,博弈论 重庆大学 刘辛,48,案例1 库诺特（Cournot）寡头竞争模型,q2,q1,每个企业的最优产量是另一个企业的产量的函数。 交叉点即纳什均衡点,2019/7/19,博弈论 重庆大学 刘辛,49,案例1 库诺特（Cournot）寡头竞争模型,假定每个企业有不变的单位成本：,假定需求函数为：,最优化的一阶条件是：,解反应函数得纳什均衡为：,垄断利润为：,2019/7/19,博弈论 重庆大学 刘辛,50,案例1 库诺特（Cournot）寡头竞争模型,为什么说库诺特（Cournot）寡头竞争模型是典型的囚徒困境问题？ 垄断企业的问题：,垄断企业的最优产量：,垄断利润为：,寡头竞争的总产量大于垄断产量的原因是： 每个企业在选择自己的最优产量时，只考虑对本企业利润的影响，而忽视了对另外一个企业的外部负效应。,2019/7/19,博弈论 重庆大学 刘辛,51,案例1 库诺特（Cournot）寡头竞争模型,练习： 假定有n个库诺特寡头企业，每个企业具有相同的不变单位成本c，市场逆需求函数p=a-Q，其中p是市场价格， 是总供给量，a是大于0的常数，企业的战略是选择产量qi最大化利润 ，给定其他企业的产量q-i，求库诺特-纳什均衡，均衡产量和价格如何随n的变化而变化？为什么？,2019/7/19,博弈论 重庆大学 刘辛,52,纳什均衡应用举例,案例1 库诺特（Cournot）寡头竞争模型 案例2 公共地的悲剧 案例3 普林斯顿大学的一道习题,2019/7/19,博弈论 重庆大学 刘辛,53,案例2 公共地的悲剧,公共地的悲剧证明：如果一种资源没有排他性的所有权，就会导致资源的过度使用。 公海捕鱼 小煤窑的过度发展 ,2019/7/19,博弈论 重庆大学 刘辛,54,案例2 公共地的悲剧,有n个农民的村庄共同拥有一片草地，每个农民都有在草地上放牧的自由。每年春天，农民要决定自己养多少只养。 gi：第i个农民饲养的数量，i=1,2,n.,n个农民饲养的总量,V: 代表每只羊的平均价值,v是G的函数,v=v(G),因为每只羊至少要一定数量的草才不至于饿死,有一个最大的可存活量Gmax,： 当G0; 当G=G(x)时,v(G)=0。,2019/7/19,博弈论 重庆大学 刘辛,55,案例2 公共地的悲剧,当草地上羊很少时，增加一只羊也许不会对其他羊的价值有太大影响，但随着羊的不断增加，每只羊的价值将急剧下降。,参与人：农民 战略： 养羊的数量 支付： 利润,2019/7/19,博弈论 重庆大学 刘辛,56,案例2 公共地的悲剧,假设一只羊的价格为c，对于农民i来讲，其利润函数为：,最优化的一阶条件为：,上述一阶条件可以解释为：增加一只羊有正负两方面的效应，正的效应是这只羊本身的价值v，负的效应是这只羊使所有之前的羊的价值降低。,2019/7/19,博弈论 重庆大学 刘辛,57,案例2 公共地的悲剧,其最优解满足边际收益等于边际成本： 上述n个一阶条件定义了n个反应函数：,因为：,所以：,2019/7/19,博弈论 重庆大学 刘辛,58,案例2 公共地的悲剧,第i个农民的最优饲养量随其他农民的饲养量增加而递减。n个反应函数的交叉点就是纳