完全信息静态博弈.ppt

Reference books: 张维迎，博弈论与信息经济学， Drew Fudenberg and Jean Tirole, Game Theory, the MIT Press,1991. Eric Rasmusen, Games & Informationan Introduction to Game Theory, Third Edition, Blackwell Publishers Inc., 2001. Roger B. Myerson, Game TheoryAnalysis of Conflict, Harvard University Press, 1991.,第二章 完全信息静态博弈,Static Games of Complete Information 2009 Zheng Daowen, All Rights Reserved,什么是完全信息静态博弈？ “完全信息”是指每个参与人对其它参与人的特征（包括战略空间、支付函数等）有完全的了解或者说了如指掌。 “静态”是指所有参与人同时选择行动，且只选择一次。即使不是同时选择行动，只要每个参与人在选择行动时不知道其它参与人的选择，在知道后不改变自己的选择，参与人的行动也可以被看作是同时行动。,“完全信息静态博弈”是每个参与人都知道其它参与人特征的情况下，“同时”选择策略或采取行动的博弈。,博弈分析的目的预测博弈的均衡结果 给定每个参与人都是理性的(Rational)，每个参与人都知道所有参与人都是理性的情况下，什么是参与人的最优策略？什么是参与人的最优策略组合？,第一节 纳什均衡 第二节 无限策略博弈的解和反应函数 第三节 混合策略 第四节 纳什均衡的存在性,第一节 纳什均衡 Nash Equilibrium,一、求解博弈的方法 1、划线法就是在每一个参与人针对竞争对手每一策略的最大可能收益（或效用）下划线以求得博弈解的方法。 2、箭头法就是通过反映参与人选择倾向的箭头寻找稳定性策略组合的方法。,上 下 甲 方,1，0,乙 方 左 中 右,乙 方 左 中 右,上 下 甲 方,二、纳什均衡,（一）博弈的标记法 常用G表示一个博弈；n博弈参与人的数量； S1，Sn参与人的策略空间，所谓策略空间是指每个参与人的全部可选策略的集合； sijSi参与人i的第j个策略，其中j可取有限个值（有限策略博弈），也可以取无限个值（无限策略博弈）。 ui参与人i的得益或效用，它是各参与人策略的多元函数。 n人博弈可以写成G=S1,，Sn；u1，un,（二）纳什均衡定义： 在博弈G=S1,，Sn；u1，un中，如果策略组合 中任一参与人i的策略 是对其他参与人策略组合 的最优策略，即 则称 为博弈G的一个“纳什均衡”。,纳什均衡是所有参与人最优策略的组合。 在给定别人策略的情况下，没有任何单个参与人有积极性选择其它策略，从而没有任何人有积极性打破这种均衡。,李四,张三,最后归宿的博弈,纳什均衡有强弱之分( Harsanyi,1973) 当且仅当对于所有的参与人i， 不等式 成立时，策略组合s*才是一个强纳什均衡(Strict or strong Nash equilibrium)。,（三）占优战略均衡,1、 “占优战略”(Dominant strategy)是指参与人在一些特殊的博弈中不受其它参与人的策略选择影响的最优策略。也就是说，不论其它参与人选择什么策略，他的最优策略都是唯一的、不变的。,2、占优战略均衡定义：在博弈的战略式表述中，如果对于任意参与人i， 是占优策略，那么策略组合 被称为占优战略均衡(Dominant-strategy equilibrium)。,（四）重复剔除的战略均衡,“重复剔除严格劣战略”(Iterated elimination of strictly dominated strategies) 思路就是排除法。,1、劣策略 严格劣策略 设 如果对于任意其他参与人的策略组合s-i，参与人从选择得到的收益严格小于选择 得到的收益，即 则，策略 严格劣于 (siis strictly dominated by si“）。,弱劣策略 如果对于所有的 ，且对于某些 ，严格不等式成立，则我们称 弱劣于策略 ， 称为相对于 的弱占优策略。,2、重复剔除的占优均衡,如果策略组合 是重复剔除劣策略后剩下的唯一的策略组合，那么，策略组合 被称为重复剔除的占优战略均衡。,3、注意： 如果每次剔除的是严格劣策略，均衡结果与剔除的顺序无关。 如果剔除的是弱劣策略，则均衡结果可能与剔除顺序有关。 重复剔除的占优战略均衡不仅要求每个参与人是理性的，而且要求“理性”是参与人的共同知识。即所有参与人都知道所有参与人是理性的，所有参与人都知道所有参与人。 当支付取某些极端值时，重复剔除的占优均衡不一定是一个合理的预测结果。,小猪 按 等待,按 等待 大猪,智猪博弈,参与人A,参与人B L M R,U D,R1 R2 R3,参与人A,参与人B C1 C2 C3,R3C3C2R2 (R1, C1),C2R2C1R3 (R1, C3),参与人A,参与人B L R,U D,（五）重复剔除劣策略的 占优战略均衡的应用,第二高价拍卖 (Second Price Auction) An auction in which the bidder who submitted the highest bid is awarded the object being sold and pays a price equal to the second highest amount bid. Alternately, in a procurement auction, the winner is the bidder who submits the lowest bid, and is paid an amount equal to the next lowest submitted bid.,Second-price auctions are either sealed-bid, in which bidders submit bids simultaneously, or English auctions, in which bidders continue to raise each others bids until only one bidder remains. William Vickrey pointed out that bidding ones true value in the second price auctions is a dominant strategy. First price auctions also award the object to the highest bidder, but the payment is equal to the amount bid.,A seller has one indivisible unit of an object for sale. There are I potential buyers, or bidders, with valuations 01I for the object, and these valuations are common knowledge. The bidders simultaneously submit bids si 0,+).,The highest bidder wins the object and pays the second bid, that is Bidder i has utility The other bidders pay nothing, and therefore have utility 0. For player i the strategy of bidding his valuation (si=i) weekly dominates all other strategies,Let Suppose that si i If risi i, bidder i obtains utility 0, which he would get by bidding i If rii 0, which he would get by bidding i If i ri si, then bidder i obtains utility i ri0. If he were to bidi, his utility would be 0.,Suppose that si0, by underbidding. If risi, bidder i obtains utility i ri0, which he would get by biddingi or si,第二节 无限策略博弈的解 和反应函数,一、古诺模型(Cournot Model) 1838 年Augustin Cournot 在Researches into the Mathematical Principles of the Theory of Wealth 一书中提出来的。,（一）反应函数 假定： qi第i个厂商的产量，i（1，2） Ci(qi)第i厂商的成本函数; P=P(Q)=P(q1+q2)市场价格,利润函数为：,一阶导数：,纳什均衡解：,例如： P=P(Q)=8-Q=8-q1-q2 C1=C2=2 (Marginal cost) 解： 两厂商不合作： 其的总产量为2+2=4； 市场价格为P=8-4=4； 两厂商的利润总额为8。,两厂商合作，垄断利润为： 最优产量为：Q*=3， 最大利润为m=9， 各厂商的产量为：q1=q2=Q/2=1.5 各厂商的利润为：1=2 =m /2=4.5,（二）重复剔除严格劣策略的方法,二、寡头价格竞争模型,（一）伯川德模型（Bertrand Model） 1883年伯川德(Bertrand)提出了一个以价格作为决策变量的寡头垄断模型。 结果证明：如果产品是同质的(homogenous)，即使只有两个厂商，在均衡状态下价格也等于边际成本，企业的利润为零，与完全竞争市场均衡一样。这就是所谓的伯川德悖论(Bertrand Paradox),假设： （1）两企业生产同质产品，同时独立确定价格。 （2）两企业有相同的成本函数，单位成本为C1=C2=c。 （3）市场需求函数为Q=D(p)，且D(p)0。 市场对企业i的需求量为,企业i的利润函数为 求解纳什均衡组合 两企业共有四种组合： R1=(p1, p2)p1=p2c R2=(p1, p2)p1p2c (p1, p2)p2p1c R3=(p1, p2)p1p2=c (p1, p2)p2p1=c R4=(p1, p2)p1=p2=c,第1组合R1不是纳什均衡。 对于任意一个足够小的数0， 只要pi-c1/2(pi-c), 且D(pi-)D(pi),第2组合R2也不是纳什均衡。 因为,第3组合R3也不是纳什均衡 设pipj=c, 有,第4组合R4是纳什均衡。 固定pj=c, 对于 有,故(p1,p2)=(c,c)是伯川德模型的纳什均衡,异质产品的价格竞争模型 假设: （1）两厂商的产品价格分别为P1和P2； （2）两厂商的需求函数分别为： （3）两厂商无固定成本，边际成本分别为c1和c2； （4）两厂商同时决策。,则两厂商的策略空间为：,分别是两厂商可以卖出产品的最高价格。,利润函数为：,反应函数： 解,假设a1=a2=28, b1=b2=1, d1=d2=0.5, c1=c2=2. 则结果为,（二）侯特林模型 （Hotellings Location Model）,在侯(霍)特林(Hotelling, 1929)模型中，两厂商的产品在物质性能上是相同的，但在空间位置上存在差异。这样，不同位置上的消费者要支付不同的运输成本，他们不仅关心价格，而且关心运输成本。,1、两商店位于两端： 假设： （1）在一个长条形的城市里，消费者均匀地分布在0，1区间里，分布密度为1。 （2）两个商店分别位于城市的两端，商店1在x=0，商店2在x=1处，出售完全相同的产品。 （3）两个商店提供产品的单位成本为c。 （4）消费者购买商品的路费与到商店的距离成正比，单位距离的成本为t。 （5）消费者具有单位需求，其消费量或者为1单位，或者为0单位。 （6）消费者剩余为cs。,商店1： D1= x； 商店2： D2=1-x 均衡点x满足条件： P1+t x = P2+t (1-x) 两厂商的需求函数：,利润函数： 一阶条件： 均衡解：,2、两商店处于同一位置 则得到伯川德均衡解： P1=P2=c, 1=2=0,3、两商店处于任何位置 假设： （1）商店1位于a0， 商店2位于1-b (其中b0)。 （2）旅行成本与距离的平方成正比，即td2， 其中d为消费者到商店的距离。,两个商店的需求函数分别为：,纳什均衡解：,当a=b=0，两商店位于两端， 均衡解为 当a=1-b时，两商店位于同一位置，则,三、公共地的悲剧,公共地的悲剧(Tragedy of the commons)是新制度经济学家研究的典型案例。它表明：如果一种资源没有排他性所有权，就会导致对这种资源的过渡使用，像公海捕鱼、公共草地上放牧、无线电波、河流和空气的污染等。 American ecologist Garrett Hardin (1968), “The Tragedy of the Commons“, Science, Vol. 162,(Dec.).,假设： 在一个村庄有n个农民，共同拥有一片草地，每个农民都有在草地上放牧的自由； 每年春天，每个农民决定自己养多少只羊。 gi第i个农民饲养的羊的数量， 每只羊的价值与羊的总数有关，是羊总量的减函数。v表示每只羊的平均价值， 。若羊的最大存活数量为Gm。当G0；当GGm时，v=0。 每购买一只羊羔的价格（即成本）为c。,随着羊的数量增加，每只羊的价值下跌。这一变化规律用公式来表述为：,第i农民的利润函数为,最优化的一阶条件为,最优化的二阶条件为,第i个农民的最优饲养量随其它农民饲养量的增加而递减。 根据上述一阶条件可以得到n个反应函数：,纳什均衡 在纳什均衡状态下，总的饲养量为,集体决策,村庄的福利函数为：,村庄最优化的一阶条件：,社会最优饲养量G0满足下列等式,从上图可以看出，个人最优饲养量的总和大于社会最优饲养量，即G* G0。,C,对公共资源的认识和研究可以追溯到休谟（Hume, 1739）时代，学者们早就认识到： 在人们完全从私人动机出发自由利用公共资源时，公共资源倾向于被过度利用(overproduction)、低效率使用和浪费，并且过度利用会达到任何利用它的人都无法得到多少实际好处的程度。,四、公共物品的私人自愿供给,公共物品的私人供给将导致供给不足。 假设：n个居民的村庄准备建一个防洪堤。让每个居民提供沙袋，沙袋的总供给越大，防洪堤越坚固，所有居民都受益。,1、私人最优化 假设：gi第i个居民贡献的沙袋数量 为沙袋的总供给 ui(xi, G)为第i个居民的效用函数， 且 私人物品和公共物品之间的边际替代率是递减的。,px私人物品的价格； pG沙袋的价格； Mi第i个人收入。 个人的最优化问题：,拉格朗日函数：,最优化的一阶条件：,消费者的均衡条件：,N 个均衡条件决定了公共物品自愿供给的数量，即纳什均衡：,2、集体最优化 假设：社会福利函数是个人效用函数的加权和，即,约束条件：,最优化的一阶条件：,拉格朗日函数,集体最优化的条件：,上述等式说明：所有居民的边际替代率之和等于价格的比率。这一条件就是存在公共物品的条件下，实现帕累托最优的萨缪尔逊条件(Samuelson, 1954)。,将此集体最优化条件同私人最优化条件比较,这说明：私人单独决策的公共产品供给小于集体决策的公共产品供给。,设个人效用函数为柯布道格拉斯形式：,个人最优化条件为,战略性贸易政策 Barbara J. Spencer and James A. Brander,政府补贴25单位,第三节 混合策略,一、问题的提出 小偷与门卫 (1996年3月R泽尔腾 ),门卫 睡 不睡,偷 不偷,小偷,V仓库货物的价值； -P坐牢的负效用； S仓库未被偷，门卫睡觉的正效用； -D门卫睡觉，小偷得逞，仓库被盗后门卫被解雇的负效用。 小偷不来，门卫不睡觉，守夜有负效用；同时得到一份收入，以补偿他的劳动付出，其收入的正效用与劳动的负效用正好相抵，效用为0。 双方的最优策略以对方的策略先定为前提，一环套一环，双方的利益始终不一致。,例2、猜硬币,乙方 正面 反面,正面 反面 甲方,例3、石头、剪子和布,二、混合战略(Mixed Strategy),（一）混合战略的定义 在博弈G=S1, , Sn; u1, , un中，如果参与人i有K个纯策略: Si=si1, sik, siK，则参与人i以概率分布i=(i1, ik , ,iK)随机选择他的K个可选纯策略的行动规则称为一个“混合战略”，其中ik=(sik)是i选择sik的概率，对于所有的k =1, K , 0ik1。,i代表i的混合战略空间， 。 代表n个参与人的一个混合战略组合（a mixed strategy profile）。 =ii代表混合战略组合空间， 。,（二）混合战略的期望效用,参与人i的期望效用函数,所有其它参与人的混合战略组合。 s=(s1，sj，sn)是n个参与人的一个纯策略组合； ui=ui(s1, sj, sn) 是参与人i对应于纯策略组合s的效用函数或支付函数。,其中，,表示除i之外,，即,假设两人博弈： 参与人1有K个纯策略：S1=(s11, , s1K)； 参与人2有J个纯策略：S2=(s21, , s2J)。 如果参与人2的混合战略为（即参与人2选择J个可选纯策略的概率分布）： 则参与人1选择纯策略s1k的期望效用为：,参与人1选择混合战略 的期望效用 其中： 是参与人1选择第k个纯策略s1k的概率; 是参与人2选择第j个纯策略s2j的概率; 表示参与人1选择纯策略s1k且参与人2选择纯策略s2j的概率，即纯策略组合（s1k，s2j）出现的概率。,若参与人1选择混合战略 参与人2选择混合战略， 则参与人2的期望效用为：,（三）混合战略纳什均衡 (Mixed-Strategy Equilibrium) 混合战略纳什均衡是所有参与人的最优混合战略组合。 最优混合战略是使参与人的期望效用最大化的混合战略。,定义：在n人博弈G=S1, , Sn; u1, , un中，如果对于所有的参与人（i =1, 2, n），存在一个混合战略组合 使得下式成立： 则混合战略组合 是一个纳什均衡。,三、混合策略的应用,例1、猜币游戏 设盖币方出正面的概率为p，则出反面的概率为1-p。 盖币方的最优战略：以相同的概率随机地出正面或反面 猜币方的最优策略：以相同的概率随机地选择猜正面和反面 。,盖币方和猜币方的最优混合策略： 此即为该博弈的唯一纳什均衡战略。 双方的预期收益：,例2、变和博弈,参与人2,参与人1,参与人1的最优混合战略为 参与人2的最优混合战略为 参与人1的期望效用 v1=2.6 参与人2的期望效用 v2=7/3,例3、男女之争（两纳什均衡）,双方的最优策略： 女方的最优策略是以（0.75，0.25）的概率随机地选择芭蕾和足球； 男方的最优策略是以（1/3，2/3）的概率随机地选择芭蕾和足球。 期望效用： 女方的期望效用=0.751/32+0.752/30+0.251/30+0.252/31=0.67 男方的期望效用=0.751/31+0.752/30+0.251/30+0.252/33=0.75,例4、制式问题 彩电制式：PAL（欧洲A）, NTSC（美国B）,厂商2,厂商1,纳什均衡： 厂商1的混合战略是以（0.4，0.6）的概率分布随机地选择A和B； 厂商2的混合战略是以（0.67，0.33）的概率分布随机选择A和B。 均衡结果： 双方的期望效用分别为0.664和1.296。,例5、市场机会 假设两个厂商同时发现了一个市场机会，但市场容量不大。如果一个厂商单独进入，就能赚利润100；如果两个厂商同时进入，则双方同时亏损50元；如果两个厂商都不进入，则都没有收入。,厂商1,厂 商 2,纳什均衡： 两个纯策略纳什均衡： （不进，进）；（进，不进）。 一个混合战略纳什均衡： 双方都以（2/3，1/3）的概率选择进与不进。 均衡结果： 两厂商的期望得益=0,例6、田忌赛马,例7，小偷与门卫,(1996年3月R泽尔腾 ),门卫 睡 不睡,偷 不偷,小偷,1,S,门卫睡觉的期望效用,小偷偷的期望效用,t*,t,-D,-D,t,-P,-P,1,g,g*,g,左图,右图,0,0,V,t-小偷偷的概率; g-门卫睡的概率,例8、社会福利博弈,政 府,流 浪 汉,给定政府救济，流浪汉的最优策略是游荡； 给定流浪汉游荡，政府的最优策略是不救济； 给定政府不救济，流浪汉的最优策略是寻找工作； 给定流浪汉寻找工作，政府的最优策略是救济； 如此循环，就没有一个纳什均衡的策略组合。,假设： 政府以的概率选择救济，以1-的概率选择不救济。 流浪汉以 的概率选择寻找工作，以 的概率选择游荡 。 则 政府的混合战略为 流浪汉的混合战略为,纳什均衡： 流浪汉最优混合战略是以0.2的概率选择寻找工作，0.8的概率选择游荡。 政府的最优混合战略是各以50%的概率选择救济或不救济。,该博弈的非均衡特征 ： 政府不救济的预期效用高于救济的预期效用，政府的最优选择是不救济； 政府的最优选择是救济。 流浪汉寻找工作的预期效用高于游荡的预期效用，流浪汉的最优选择是寻找工作； 流浪汉的最优选择是游荡。,六、混合策略与反应对应 (Reaction Correspondence),反应函数与反应对应的区别和联系,反应对应（Reaction correspondence）是一个参与人对应于其它参与人混合战略的最优选择。 它允许一个参与人有多个（甚至无穷多个）战略是其它参与人给定战略的最优选择。 反应对应不要求参与人的最优策略与其它参与人的策略存在一一对应关系。,（一）社会福利博弈,政府,=,流浪汉,（二）猜币游戏, =, =,盖币方,猜币方,（三）男女之争 假设女方的混合战略为以（，1-）的概率随即地选择芭蕾和足球，男方的混合战略为以（，1-）的概率随机地选择足球和芭蕾。,女方：,=,男方：,=,0,1,1,E (3/4, 2/3),男方反应曲线=（）,女方反应曲线=（）,威尔逊(Wilson, 1971)的奇数定理（Oddness theorem）：在所有有限策略博弈都有有限纳什均衡，且纳什均衡的个数为奇数。,七、各种纳什均衡的关系,占优战略均衡； 重复剔除的占优均衡； 纯战略纳什均衡； 混合战略纳什均衡。 四个不同的均衡概念有如下关系：后一均衡概念依次是前一均衡概念的拓展，或者说，前一均衡概念是后