《子博弈完美Nash均衡.ppt》由会员分享，可在线阅读，更多相关《子博弈完美Nash均衡.ppt（25页珍藏版）》请在三一文库上搜索。
1、子博弈完美Nash均衡,我们知道，一个博弈可以有多于一个的Nash均衡。在某些情况下，我们可以按照“子博弈完美”的要求，把不符合这个要求的均衡去掉。 扩展型博弈G的一部分g叫做一个子博弈，如果g包含某个节点和它所有的后继点，并且一个G的信息集或者和g不相交，或者整个含于g。 一个Nash均衡称为子博弈完美的，如果它在每 一个子博弈都给出Nash均衡。,子博弈完美Nash均衡,简例1 （宠坏的孩子）妈妈要孩子上幼儿园，孩子却想上街和其他小朋友玩。这个博弈由孩子的决策开始：如果孩子听话上幼儿园(a)，赢得向量是(0,1)；如果孩子坚持要上街玩，妈妈可以选择责骂(A)获前就(B)，前者导致赢得向量(
2、-1,-1)，后者导致赢得向量(1,0)。参阅下图,孩子,妈妈,a,b,A,B,(0,1),(-1,-1),(1,0),子博弈完美Nash均衡,这个博弈的策略型如下：,0, 1,0, 1,-1, -1,1, 0,孩子,a,b,妈妈,A,B,子博弈完美Nash均衡,简例1（续）从策略型看出，这个博弈有两个纯策略Nash均衡(a,A)，(b,B)。先来看(a,A)，在妈妈决策的单人子博弈中，A的选择并非最优的，因而并不给出这个子博弈的NE；所以(a,A)并非一个SPNE。我们把A叫做空头恐吓。再来看(b,B)，容易验证，B的选择给出妈妈单人子博弈的NE，所以(b,B)是子博弈完美的。,子博弈完美N
3、ash均衡,行为混合策略：对于扩展型博弈来说，行为混合策略的概念比上节介绍的混合策略概念更适用。局中人在他的每一个信息集中按照某个概率分布随机地选用各个着，就构成他的一个行为混合策略；也就是说，一个局中人如果有H个信息集，他的一个行为混合策略就包括H个概率分布。行为混合策略集合的维数一般低于混合策略集合的维数。每一个混合策略都存在一个与之等价的行为混合策略；反之，每一个行为混合策略都存在一组混合策略与之等价。,子博弈完美Nash均衡,利用行为混合策略的概念，可以证明子博弈完美Nash均衡的存在性定理。 定理：每一个有完整记忆的有限扩展型博弈至少存在一个子博弈完美Nash均衡。 倒推归纳法：给定
4、一个有限的扩展型博弈，从处于最后决策阶段的某个信息集开始，让局中人选取最优的着（混合着）使他的（期望）赢得最大化；然后用一个终止节点代替从这信息集引申的子博弈树，附上相应的（期望）赢得向量。这种逐步化简博弈树的方法叫做倒推归纳法。,子博弈完美Nash均衡,有完美信息的扩展型博弈：如果一个扩展型博弈中的每一个信息集都只包含一个节点，那么就称它为一个某完美信息的博弈。 每一个有完美信息的有限扩展型博弈，都可以用倒推对纳法算出至少一个纯策略子博弈完美Nash均衡。 关于子博弈完美Nash均衡（SPNE）的存在性和完美信息博伊德SPNE的算法见附录2。 下面用例子说明倒推归纳法的应用。,Game Tr
5、ee: 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,Q. How to solve
6、it? Two methods: M1 Convert to normal form M2 Deal directly in extensive form,Normal form analysis DM1: 3 strategies, L, M, and R DM2: 23 = 8 strategies Game in normal form:,Q. Major difficulties? Dimensionality can be very large (Recall the DP example) Dynamic aspects are not appropriately consider
7、ed Which of the four Nash solutions will actually happen?,To overcome the difficulties, we shall analyze the extensive form directly. How?,The solution process is backward induction Starting from leaf nodes and work backward until the root node is reached, each time solve a simple problem Then movin
8、g forward from the root to obtain the solution,Q. If DM1 selected L, what should DM2 do? How about if DM1 selected M or R?,The solution is unique (0, -1) is not a solution since DM1 who acts first will not select L,Extensive form is a reasonable approach for this problem,Example. With a slight varia
9、tion:,If DM1 selected M or R, DM2 does not know how DM1 acted,Again there are two methods: M1 Convert to a normal form M2 Deal directly in extensive form Normal form analysis: How? DM1: 3 strategies, L, M, and R DM2: 22 = 4 strategies,Q. How to solve it?,Game in normal form:,Q. Major difficulties? S
10、ame as before Dimensionality can be very large Dynamic aspects are not appropriately considered,Q. To analyze the extensive form directly. How?,Q. At information set 2A, what should DM2 do? How about at 2B? What should DM1 select?,At 2A, DM2 should select L with costs (0, -1),Q. What problem does DM
11、1 face? How should he select?,At 2B, DM2 faces the following normal game:,The solution process is backward induction,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.,Subgames,Subgame perfe
12、ct equilibrium: No subgame can any player do better by choosing a different strategy,Some examples that is not subgames,2A,2B,Location Game Example: Dynamic Game of Perfect Information Grocery Shopping on Market Street,Market Street is a one-way street.,1,100,One-Way Market Street,Two firms locate g
13、rocery stores on Market Street sequentially. That is, first firm 1 locates and then firm 2.,Consumers live along streets 1-100.,N,W,1,2,3,i,99,100,Consumers drive to market street, then drive west on market street (there are no left turns onto market street) until they reach a grocery store.,Payoffs
14、 An example: Firm 1 locates at 15 and 2 locates at 47.,15,47,Firm 1,Firm 2,Consumers: 1 consumer uniformly distributed on each street.,Since firm 1 gets all consumers who live on 15th St, 16th St, 45th St and 46th St.,1(15, 47) = 47-15 = 32. 2 (15, 47) = 101-47 =54,100,1,Now lets use backward induct
15、ion to find all subgame perfect Nash equilibrium.,Recall that subgame perfection is an equilibrium refinement concept. If SGPNE then NE.,1,i,100,1,2,j,100,1,2,2,2,2,2,What are the pay-offs to Player 1? Player 2?,Payoffs: i (i,j) = 101-i if ij (101-i)/2 if i=j j-i if ij,j,i,Firm j,Firm i,100,1,101-i,
16、i-j,i=j,Firm j,Firm i,100,1,(101-i)/2,Payoffs: j (i,j) = i-j if ij (101-i)/2 if i=j 101-j if ij,Backward Induction,Fix a player 2 node i0 (player 1 has located at i0). What maximizes player 2s payoff? First note that player 2 will always want to be at 1, i0, or i0 + 1. For example suppose player 1 h
17、as located at 4 (i.e. player 2 is at node 4). Where will 2 want to locate? Suppose player 1 has located at 75. Where will player 2 want to locate?,Solving the game via backward induction,At node i , firm 2 plays j= i+1 if 1 i 50 j= 1 if 51 i 100 Back at firm is node: 1(i, j ) = i+1-i if 1 i 50 =101-
18、i if 51 i 100 Therefore unique subgame perfect equilibrium is: firm 1 plays 51 = i* firm 2 plays j=i+1 if 1 i 50 and j=1 if 51 i 100 = j* Note the way in which the strategies are stated.,The end of market street,Equilibrium path: firm 1 plays 51, firm 2 plays 1. Payoffs 1(i*, j* ) = 50 and 2 (i*, j*) = 50 Also note that there is no first mover advantage.,