子博弈完美.ppt

子博弈完美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 GameExample: Dynamic Game of Perfect InformationGrocery Shopping on Market St