4 完全信息动态博弈.ppt

1、完全信息动态博弈Complete Information Dynamic Game,2,主要内容,博弈的扩展式表述 子博弈精练Nash均衡 应用举例,3,扩展式表述（博弈树）一般需确定的要素 参与人集合 参与人行动顺序 参与人的行动空间（集合） 参与人的信息集 参与人的支付函数 外生事件的发生概率/概率分布 扩展式表述的三个基本要素 参与人的集合 每个参与人的策略集合 由策略组合决定的每个参与人的支付 动态博弈中参与人的“行动”与“策略”相同？,4,地产开发博弈,不开发,开发商A,开发,不开发,开发,不开发,开发商B,开发商A,开发,不开发,开发,开发商B,需求小的情况,需求大的情况,5,地产

2、开发博弈的扩展式表述,A,开发,不开发,N,N,大,小,1/2,1/2,大,小,1/2,1/2,B,B,B,B,开发,不开发,开发,不开发,开发,不开发,开发,不开发,(4,4),(8,0),(-3,-3),(1,0),(0,8),(0,0),(0,1),(0,0),参与人集合 参与人行动顺序 参与人的行动空间 参与人的信息集 参与人的支付函数 外生事件的概率分布,6,博弈数的基本结构,结: 包括决策结和终点结两类;决策结是参与人行动的始点,终点结是决策人行动的终点. 结满足传递性和非对称性 x之前的所有结的集合，称为x的前列集P（x），x之后的所有结的集合称为x的后续集T（x）。 枝: 枝是

3、从一个决策结到它的直接后续结的连线,每一个枝代表参与人的一个行动选择. 信息集: 每个信息集是决策结集合的一个子集,该子集包括所有满足下列条件的决策结: 每个决策结都是同一个参与人的决策结; 该参与人知道博弈进入该集合的某个决策结,但不知道自己究竟处于哪一个决策结.,7,博弈数表述（1）,A,开发,不开发,N,N,大,小,1/2,1/2,大,小,1/2,1/2,B,B,B,B,开发,不开发,开发,不开发,开发,不开发,开发,不开发,(4,4),(8,0),(-3,-3),(1,0),(0,8),(0,0),(0,1),(0,0),B在决策时不确切地知道自然的选择; B的决策结由4个变为2个,8

4、,博弈数表述（2）,A,开发,不开发,N,N,大,小,1/2,1/2,大,小,1/2,1/2,B,B,B,B,开发,不开发,开发,不开发,开发,不开发,开发,不开发,(4,4),(8,0),(-3,-3),(1,0),(0,8),(0,0),(0,1),(0,0),B知道自然的选择;但不知道A的选择(或A、B同时决策),9,博弈树的几点说明,只包含一个决策结的信息集称为单结信息集，如果博弈树的所有信息都是单结的，该博弈称为完美信息博弈。 自然总是假定是单结的，因为自然在参与人决策之后行动等价于自然在参与人之前行动但参与人不能观测到自然的行动。 不同的博弈树可以代表相同的博弈，但是有一个基本规则

5、：一个参与人在决策之前知道的事情，必须出现在该参与人决策结之前。,10,囚徒困境博弈的扩展式表述,A,B,坦白,抵赖,B,B,A,A,坦白,抵赖,坦白,抵赖,(-8,-8),(0，-10),(-10,0),(-1,-1),坦白,抵赖,坦白,抵赖,坦白,抵赖,(-8,-8),(0，-10),(-10,0),(-1,-1),11,智猪博弈的扩展式表述（练习）,等待,小猪,大猪,按,等待,按,12,主要内容,博弈的扩展式表述 子博弈精练Nash均衡 应用举例,13,思考问题：为什么需要“子博弈精炼纳什均衡”？,对完全信息动态博弈，考虑以下问题： 一个博弈可能有多个（甚至无穷多个）纳什均衡，究竟哪个更

6、合理？ 纳什均衡假定每一个参与人在选择自己的最优战略时假定所有其他参与人的战略是给定的，但是如果参与人的行动有先有后，后行动者的选择空间依赖于前行动者的选择，前行动者在选择时不可能不考虑自己的行动对后行动者的影响。 子博弈精练纳什均衡的一个重要改进是将“合理纳什均衡”与“不合理纳什均衡”分开。,博弈的基本类型：完全信息、不完全信息博弈 静态博弈、动态博弈,14,子博弈精炼纳什均衡,一个纳什均衡称为精练纳什均衡，当只当参与人的战略在每个子博弈中都构成纳什均衡，也就是说，组成精练纳什均衡的战略必须在每一个子博弈中都是最优的。 一个精练纳什均衡首先必须是一个纳什均衡，但纳什均衡不一定是精练纳什均衡。

7、 泽尔腾引入子博弈精练纳什均衡的概念的目的是将那些不可置信威胁战略的纳什均衡从均衡中剔除，从而给出动态博弈的一个合理的预测结果，简单说，子博弈精练纳什均衡要求均衡战略的行为规则在每一个信息集上是最优的。,15,子博弈（sub-game）,子博弈：是原博弈的一部分，它本身也可以作为一个独立的博弈进行分析： 子博弈必须从一个单结信息点开始：只有决策者在原博弈中确切地知道博弈进入一个特定的决策结时，该决策结才能作为一个子博弈的初始结。如果信息集包含两个以上的决策结，则这两个都不可以作为子博弈的初始结。 子博弈的信息集和支付向量都直接继承自原博弈。 习惯上，任何博弈的本身称为自身的一个子博弈。,16,

8、一个例子,A,开发,不开发,X,X,大,小,1/2,1/2,大,小,1/2,1/2,B,B,B,B,开发,不开发,开发,不开发,开发,不开发,开发,不开发,(4,4),(8,0),(-3,-3),(1,0),(0,8),(0,0),(0,1),(0,0),参与人X的信息集不能开始一个子博弈，否则的话参与人B的信息将被切割。,17,例2,找出房地产开发博弈的子博弈 对“囚徒困境”呢？,18,子博弈精练纳什均衡,定义：扩展式博弈的战略组合是一个子博弈精练纳什均衡，如果: 它是原博弈的纳什均衡； 它在每一个子博弈上都是纳什均衡。 战略是参与人行动规则的完备描述，它要告诉参与人在每一种可预见的情况下（

9、即每一个决策结）上选择什么行动，即使这种情况实际上没有发生（甚至参与人并不预期它会发生）。 只有当一个战略规定的行动规则在所有可能的情况下都是最优的，它才是一个合理的可置信的战略，子博弈精练纳什均衡就是要剔除那些只在特定情况下是合理的而在其他情况下不合理的行动规则。,19,逆向归纳法,U,D,L,（3，1),(0,0),2,2，2,R,给定博弈达到最后一个决策结，该决策结上行动的参与人有一个最优选择，这个最优选择即该决策结开始的子博弈的纳什均衡 倒数第二个决策结，找倒数第二个的最优选择，这个最优选择与我们在第一步找到的最优选择构成一个纳什均衡。,如此重复直到初始结。每一步都得到对应于子博弈的一

10、个纳什均衡，并且根据定义，该纳什均衡一定是该子博弈的子博弈的纳什均衡，这个过程的最后一步得到整个博弈的纳什均衡,20,例子（逆向归纳法）,房地产开发博弈,21,情侣博弈与先动优势,结论：先行动方的支付大于后行动方的支付，即“先动优势”。 启示：在情侣博弈中，具有先动优势，如男方先把足球票卖好等。“先下手为强”等 后动优势：分蛋糕的例子：先行动方分蛋糕，后行动方选择。有限市场的选择：具有信息优势方放弃，而不具有信息优势方单独占有市场等。,男方先行动的均衡结果： 足球，足球而不是芭蕾，芭蕾,女方先行动的均衡结果： 芭蕾，芭蕾而不是足球，足球,22,先动优势的例子,沃尔马是山姆华尔顿于1969年创立

11、的一家很庞大的也是很成功的折扣零售连锁店公司。上世纪7080年代，其它类似的公司纷纷倒闭时，沃尔马却保持快速增长，从1976年的153家分店发展到1986年的1009家，且盈利性更强。到1985年末，山姆华尔顿已是美国最富有的人之一。 沃尔马成功的关键在于其市场进入与市场扩张策略。在60年代，人们通常都认为折扣店只能在10万或以上人口的城市中才能成功经营，但山姆华尔顿不同意这种看法并决定在美国西南部的小镇上开店，到1970年已经有30家沃尔马店开设在阿肯色、密苏里和俄克拉荷马的小镇上。一个10万人口以下的小镇所具有的市场容量并不太大，但却足够容纳下一个大型折扣店，并能让它获得一定的利润。 到7

12、0年代中期，当其它连锁店的经营者意识到这一点时，沃尔马已经大量占领了这样的市场。对于小镇来说，开出一家折扣连锁店可以盈利。如果开出两家来，有限的市场容量会使两家都亏损。沃尔马的策略就是先发制人，力图抢先一步，在其他小镇开设分店。到1986年，它每年赚取4.5亿美元利润。到1993年，它已有1800多家分店并赚取15亿美元的年利润。,23,几点说明,逆向归纳法求解子博弈精练纳什均衡的过程，实质上是重复剔除劣战略的过程：从最后一个决策结依次剔除每个子博弈的劣战略，最后生存下来的战略构成精练纳什均衡。 用逆向归纳法求解的子博弈精练纳什均衡也要求“所有的参与人是理性的”是共同知识。 如果博弈由多个阶段

13、组成，则从逆向归纳法得到的均衡可能并不非常令人信服。,24,作业,请将“囚徒困境”、“斗鸡博弈”用博弈树来表示，并找出它们的均衡。,25,主要内容,博弈的扩展式表述 子博弈精练Nash均衡承诺与威胁 应用举例,26,承诺威胁的可信性,承诺与威胁：参与人在博弈前，对另一博弈说“不管你怎么选择，我一定选择X策略”。这种承诺或威胁可能影响对手的选择。如情侣博弈中，如女生在博弈前对男生说：“只要你不陪我去看芭蕾，则我们分手”，如果男生相信女生说的话，而又不愿意分手，则他只好去看芭蕾，尽管他可能很想去看足球。 承诺与威胁的可信性：承诺与威胁可能是不可信的，如女生说“如果你不陪我去看芭蕾，我就去自杀”，男

14、生就可能不相信。不可信的承诺对博弈均衡是没有影响的。 不可信的威胁的例子：小孩不听话，父母说要打死他等。 可信的威胁或承诺：要改变均衡，必须要让威胁或承诺可信。如美国打伊拉克，阿富汗前，先派遣大批军舰前往该地区，因为这种威胁需要成本。如市场博弈，不管对方什么策略，先做广告或建厂房，也是一种可信的承诺。 思考：为什么老师要让部分学生考试不及格；罪犯违法，为什么要刑罚，甚至死刑？,27,承诺行动与子博弈精练纳什均衡,有些战略之所以不是精练纳什均衡,是因为它包含了不可置信的威胁战略,如果参与人能在博弈之前采取某种行动改变自己的行动空间或支付函数，原来不可置信威胁将变得可置信,博弈的精练纳什均衡也会随

15、之改变. 这些改变博弈结果而采取的措施称为承诺行动. 完全承诺:承诺可以使某项行动完全没有可能(破釜沉舟). 不完全承诺:承诺只是增加了某个行动的成本而不是使该活动完全没有可能.,28,完全承诺,完全承诺：使自己选择某一行动的成本无穷大（对方看到后，肯定相信你，因为你付出这么大成本，假如你实施，你的损失也很大）； 赌徒坎下自己的手指，以示以后不赌了，因为即使想赌，没有手指也不方便。 婚姻中的承诺：彩礼、昂贵的婚礼可以理解为一种对婚姻的承诺； 订金、抵押物做为对交易的承诺； “安营扎寨”； 固定资产投资可以作为承诺； 所有权的承诺作用； 假定企业一开始定价80，如果前两个消费者购买了，企业将有积

16、极性在50的价格下向第三个顾客出售。预期到这一点，前两个顾客将不会购买。如果企业向保证，任何降价的差额将返还顾客，前两个顾客将会购买。因为企业事实上不会降价了。,29,成语故事,破釜沉舟 秦朝末年，秦国大将章邯率领数10万人攻打赵国的都城巨鹿。赵国向楚国求援，楚王派项羽率兵救赵。项羽带领人马渡过漳河后，马上命令弄沉渡船，每人只带三天的粮食。将士们知道后退的路没有了，个个奋勇杀敌，终于解了赵国之危。 背水一战 汉将韩信带兵去攻赵军，出了井陉口，布置了一万人背水列阵，与赵军作战。汉军前临大敌，后无退路，都拼死作战，结果大败赵军。,30,承诺可信性的例子,名画的价值取决于数量，画家常为无法承诺而苦恼

17、：谁相信他不会再画呢？这可能是为什么死了画家的画最值钱。 政府也有类似的问题。政府经常缺乏承诺：给定投资者进入的情况下，多征税是最优的；但投资者预期到这一点，将不愿意进入。 中国许多地方支付有严重的机会主义行为。 “坦白从宽，抗拒从严”面临的问题也如此。 可信的承诺：法律 有限政府：政府保护老百姓的基本权利，并限制政府的自由裁决权,31,承诺行动与子博弈精练纳什均衡（例）,曹操与袁绍的仓亭之战，曹操召集将领来献破袁之策，程昱献了十面埋伏之计，他让曹操退军河上，诱袁前来追击，到那时“我军无退路，必将死战，可退袁矣”。 曹操采纳此计，令许褚诱袁军军至河上，曹军无退路，操大呼曰：“前无去路，诸军何不

18、死战！”，众军奋力回头反击，袁军大败。 启示：给对方留退路，避免鱼死网破,32,思考：用可置信承诺怎样改变地产开发博弈均衡？,如果在A决策之前,B与某客户签定了一个合同,规定B若不在特定时期内开发若干面积的写字楼,则将支付违约金3.5,这个合同就是承诺行动.,房地产开发博弈,(1,-3.5),（0，1）,33,要胁诉讼,要胁诉讼：如小企业指控大企业操纵市场，某些人自曝与上司（尤其是政治人物）有暧昧关系等。其目的是希望被指控对象与其“私了”，并获得一定赔偿。如用博弈论方法来分析上述现象，其均衡结果是不确定的，但在一定条件下，“私了”的结果是可能的。其关键是双方是否有承诺行动，即在博弈前是否已经有

19、成本付出，如聘请律师，召开记者会等。,34,不可置信承诺的例子,卓文君与司马相如的故事：司马相如年龄大，离过婚，但很有才华；而卓文君年轻漂亮，未婚。卓文君爱上了司马相如，但其父亲不同意，并威胁说，一旦女儿要嫁给司马，就断绝父女关系。如果你是卓文君，父亲的威胁你是否相信？卓文君的策略集嫁，不嫁，父亲的策略集断，不断，构造博弈，并分析均衡。,均衡嫁，不断,很显然，父亲很难通过什么承诺行动来改变博弈均衡，除非他根本就不在乎自己的女儿。,35,蜈蚣博弈与博弈论困境,按博弈论理论分析，其均衡应该是第一阶段，甲选“要”，并结束博弈。 实验结果表明：博弈结果是坚持到最后，乙得到100，并自愿分50给甲。即博

20、弈理论分析与实验结果相悖。 多人理性问题 博弈论基石：理性与有限理性,36,甲开采一价值4万元的矿，但缺1万元资金，而乙正好有1万元要投资。甲希望乙投资，并承诺采到金子后，分一半给乙；但乙肯定怕甲采到金子后，不分给他。1.如你是乙，你是否给甲投资；2.如你是甲，你用什么办法促使乙向你投资？（提示，甲有两个策略分，不分，乙有两策略借，不借）,37,斯坦克尔伯的寡头竞争模型,qi ：第i个企业的产量 C：代表单位不变成本 假定逆需求函数为： 第i个企业的利润函数为：,38,斯坦克尔伯的寡头竞争模型（2）,用逆向归纳法求解，首先考虑给定q1的情况下，企业2的最优选择。企业2的问题是： 最优化一阶条件意味着： 因为企业1预测到企业2将根据S2（q1）来选择q2，企业1在第1阶段的问题是：,39,模型比较,40,思考,一位富翁的狗在散步时跑丢了，于是他急匆匆到电视台发了一则启示：有狗丢失，归还者得酬金1万元，并附有狗的彩照。一个乞丐看到广告后，第二天一大早就报着狗准备去领酬金.,当他经过一家大商店的墙体屏幕时，发现酬金涨到了3万元，乞丐又折回住处，把狗重新栓在那里，在接下来的几天里，乞丐从来没有离开过这只大屏幕，当酬金涨到使全市居民感到惊讶时，乞丐返回他的住处，可是那只狗已经死了.,启示：在这个世界上，