子博弈完美.ppt

  1. 1、本文档共25页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
子博弈完美

子博弈完美Nash均衡 我们知道,一个博弈可以有多于一个的Nash均衡。在某些情况下,我们可以按照“子博弈完美”的要求,把不符合这个要求的均衡去掉。 扩展型博弈G的一部分g叫做一个子博弈,如果g包含某个节点和它所有的后继点,并且一个G的信息集或者和g不相交,或者整个含于g。 一个Nash均衡称为子博弈完美的,如果它在每 一个子博弈都给出Nash均衡。 子博弈完美Nash均衡 简例1 (宠坏的孩子)妈妈要孩子上幼儿园,孩子却想上街和其他小朋友玩。这个博弈由孩子的决策开始:如果孩子听话上幼儿园(a),赢得向量是(0,1);如果孩子坚持要上街玩,妈妈可以选择责骂(A)获前就(B),前者导致赢得向量(-1,-1),后者导致赢得向量(1,0)。[参阅下图] 子博弈完美Nash均衡 这个博弈的策略型如下: 子博弈完美Nash均衡 简例1(续)从策略型看出,这个博弈有两个纯策略Nash均衡(a,A),(b,B)。先来看(a,A),在妈妈决策的单人子博弈中,A的选择并非最优的,因而并不给出这个子博弈的NE;所以(a,A)并非一个SPNE。我们把A叫做空头恐吓。再来看(b,B),容易验证,B的选择给出妈妈单人子博弈的NE,所以(b,B)是子博弈完美的。 子博弈完美Nash均衡 行为混合策略:对于扩展型博弈来说,行为混合策略的概念比上节介绍的混合策略概念更适用。局中人在他的每一个信息集中按照某个概率分布随机地选用各个着,就构成他的一个行为混合策略;也就是说,一个局中人如果有H个信息集,他的一个行为混合策略就包括H个概率分布。行为混合策略集合的维数一般低于混合策略集合的维数。每一个混合策略都存在一个与之等价的行为混合策略;反之,每一个行为混合策略都存在一组混合策略与之等价。 子博弈完美Nash均衡 利用行为混合策略的概念,可以证明子博弈完美Nash均衡的存在性定理。 定理:每一个有完整记忆的有限扩展型博弈至少存在一个子博弈完美Nash均衡。 倒推归纳法:给定一个有限的扩展型博弈,从处于最后决策阶段的某个信息集开始,让局中人选取最优的着(混合着)使他的(期望)赢得最大化;然后用一个终止节点代替从这信息集引申的子博弈树,附上相应的(期望)赢得向量。这种逐步化简博弈树的方法叫做倒推归纳法。 子博弈完美Nash均衡 有完美信息的扩展型博弈:如果一个扩展型博弈中的每一个信息集都只包含一个节点,那么就称它为一个某完美信息的博弈。 每一个有完美信息的有限扩展型博弈,都可以用倒推对纳法算出至少一个纯策略子博弈完美Nash均衡。 关于子博弈完美Nash均衡(SPNE)的存在性和完美信息博伊德SPNE的算法见附录2。 下面用例子说明倒推归纳法的应用。 Game Tree: Examples In last Lectures we analyzed games in normal form ~ All the dynamic aspects have been stripped Sometimes it is valuable to analyze games in extensive form with dynamics intact Example. Consider the following two-person non-zero sum game in extensive form to minimize costs Normal form analysis DM1: 3 strategies, L, M, and R DM2: 23 = 8 strategies Game in normal form: To overcome the difficulties, we shall analyze the extensive form directly. How? Example. With a slight variation: Game in normal form: Q. To analyze the extensive form directly. How? An exercise on backward induction Subgames and Subgame Perfection Subgames for any non-terminal history h is the part of the game that remains after h occurred. Some examples that is not subgames Location Game Example: Dynamic Game of Perfect Information Grocery Shopping on Market St

文档评论(0)

magui + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

版权声明书
用户编号:8140007116000003

1亿VIP精品文档

相关文档