子博弈完美Nash均衡 我们知道，一个博弈可以有多于一个的Nash均衡。在某些情况下，我们可以按照“子博弈完美”的要求，把不符合这个要求的均衡去掉。 扩展型博弈G的一部分g叫做一个子博弈，如果g包含某个节点和它所有的后继点，并且一个G的信息集或者和g不相交，或者整个含于g。 一个Nash均衡称为子博弈完美的，如果它在每 一个子博弈都给出Nash均衡。

子博弈完美Nash均衡 简例1 （宠坏的孩子）妈妈要孩子上幼儿园，孩子却想上街和其他小朋友玩。这个博弈由孩子的决策开始：如果孩子听话上幼儿园(a)，赢得向量是(0,1)；如果孩子坚持要上街玩，妈妈可以选择责骂(A)获前就(B)，前者导致赢得向量(-1,-1)，后者导致赢得向量(1,0)。[参阅下图]

孩子 a b 妈妈 (0,1) A B (-1,-1) (1,0)

子博弈完美Nash均衡 这个博弈的策略型如下： 妈妈 A B a 0, 1 0, 1 孩子 b -1, -1 1, 0

子博弈完美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均衡（SPNE）的存在性和完美信息博伊德SPNE的算法见附录2。 下面用例子说明倒推归纳法的应用。

Game Tree: Examples Q. How to solve it? Two methods: 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 it? Two methods: M1 ~ Convert to normal form M2 ~ Deal directly in extensive form

Q. Major difficulties? Normal form analysis Game in normal form: DM1\2 DM1: 3 strategies, L, M, and R DM2: 23 = 8 strategies Game in normal form: DM1\2 LLL LLR LRL LRR RLL RLR RRL RRR L (0, -1) (-2, 1) M (3, 2) (0, 3) R (2, 1) (-1, 0) Q. Major difficulties? Dimensionality can be very large (Recall the DP example) Dynamic aspects are not appropriately considered Which of the four Nash solutions will actually happen?

The solution process is backward induction To overcome the difficulties, we shall analyze the extensive form directly. How? The solution is unique (0, -1) is not a solution since DM1 who acts first will not select L 2A 2B Extensive form is a reasonable approach for this problem Q. If DM1 selected L, what should DM2 do? How about if DM1 selected M or R? 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 moving forward from the root to obtain the solution

Example. With a slight variation: If DM1 selected M or R, DM2 does not know how DM1 acted 2A 2B Q. How to solve it? 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

Game in normal form: Q. Major difficulties? Same as before DM1\DM2 LL LR RL RR L (0, -1) (-2, 1) M (3, 2) (0, 3) R (2, 1) (-1, 0) Q. Major difficulties? Same as before Dimensionality can be very large Dynamic aspects are not appropriately considered

Q. At information set 2A, what should DM2 do? How about at 2B? 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? 2A 2B At 2A, DM2 should select L with costs (0, -1) At 2B, DM2 faces the following normal game: DM1\DM2 L R M (3, 2) (0, 3) (2, 1) (-1, 0) Q. What problem does DM1 face? How should he select? The solution process is backward induction

An exercise on backward induction

Subgames and Subgame Perfection for any non-terminal history h is the part of the game that remains after h occurred. Subgames Subgame perfect equilibrium: No subgame can any player do better by choosing a different strategy

Some examples that is not subgames

Location Game Example: Dynamic Game of Perfect Information Grocery Shopping on Market Street Market Street is a one-way street. One-Way Market Street 1 100 Two firms locate grocery stores on Market Street sequentially. That is, first firm 1 locates and then firm 2.

Consumers live along streets 1-100. W i 1 2 3 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 An example: Firm 1 locates at 15 and 2 locates at 47. Consumers: 1 consumer uniformly distributed on each street. Firm 1 Firm 2 1 15 47 100 Payoffs An example: Firm 1 locates at 15 and 2 locates at 47. 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

Now let’s use backward induction to find all subgame perfect Nash equilibrium. Recall that subgame perfection is an equilibrium refinement concept. If SGPNE then NE. 1 1 2 i 100 2 2 2 2 100 1 j 2 What are the pay-offs to Player 1? Player 2?

Payoffs: j (i,j) = i-j if i>j (101-i)/2 if i=j 101-j if i<j Payoffs: i (i,j) = 101-i if i>j (101-i)/2 if i=j j-i if i<j i-j 101-i (101-i)/2 Firm j Firm i Firm j Firm i j i 1 i=j 1 100 100 Payoffs: j (i,j) = i-j if i>j (101-i)/2 if i=j 101-j if i<j

Backward Induction Fix a player 2 node i0 (player 1 has located at i0). What maximizes player 2’s payoff? First note that player 2 will always want to be at 1, i0, or i0 + 1. For example suppose player 1 has 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 i’s node: 1(i, j ) = i+1-i if 1 i  50 =101-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.