(2) Review of Lecture 8 Dynamic games often have multiple Nash equilibria, and some of them do not seem plausible since they rely on non-credible threats. By solving games from the back to the forward, we can erase those implausible equilibria. ⇒ Backward Induction . . As we will see, this idea leads us to the refinement of NE, the subgame perfect Nash equilibrium. . 2. Refinement: Reduction of the set of solutions (NE in our case) based on some reasonable criteria. Lecture 8 2013 Winter.

(3) Extensive-Form Games The extensive-form representation of specifies the following 5 elements: 3 + timing & information 1. 2. 3. 4. 5. . 3. The players in the game. When each player has the move. ⇒ timing What each player can do at each of her opportunities to move. What each player knows at ---. ⇒ information The payoff received by each player for every possible combination of moves. Lecture 8 2013 Winter.

(4) Game Tree Illustration. 2 A 1 B. 4. 2. U. (3,1). D. (1,2). U’. (2,1). D’. (0,0) Lecture 8 2013 Winter.

(5) Game Tree: Definition An extensive-form game is depicted by a tree that consists of nodes connected by branches. Each. branch is an arrow, pointing from one node (a predecessor) to another (a successor). . For nodes x, y, and z, if x is a predecessor of y and y is a predecessor of z, then it must be that x is a predecessor of z.. A. tree starts with the initial node and ends at terminal nodes where payoffs are specified.. 5. Lecture 8 2013 Winter.

(6) Tree Rules 1. 2. . 3. 4. . 6. Every node is a successor of the initial node. Each node except the initial node has exactly one immediate predecessor. The initial node has no predecessor. Multiple branches extending from the same node have different action labels. Each information set contains decision nodes for only one of the players.. Lecture 8 2013 Winter.

(7) Review: Extensive-Form ⇒ Normal-Form . . Every dynamic game generates a unique normal-form representation. 1╲2. (U,U’). (U,D’). (D,U’). (D,D’). A. 3,1. 3,1. 1,2. 1,2. B. 2,1. 0,0. 2,1. 0,0. A strategy for a player is a complete plan of actions specifying a feasible action for the player in every contingency.. 7. Lecture 8 2013 Winter.

(8) New: Normal-Form ⇒ Extensive-Form Normal-form can also be translated into extensive-form.. . . . Consider the following static game:. 1╲2. L. R. U. 3,1. 1,2. D. 2,1. 0,0. To express simultaneous move by game tree, we can use information sets. . 8. Depending on how to draw the ordering of players, extensiveform has a multiple normal-formal representation. Lecture 8 2013 Winter.

(9) Game Tree (1): Player 1 “Moves” First Information Set. U 1. (3,1). R. (1, 2). L. (2,1). R. (0,0). 2 D. 9. L. Lecture 8 2013 Winter.

(10) Game Tree (2): Player 2 “Moves” First Information Set. L 2. (3,1). D. (2,1). U. (1,2). D. (0,0). 1 R. 10. U. Lecture 8 2013 Winter.

(11) Information Set . An information set for a player is a collection of decision nodes satisfying that the player has the move at every node in the information set, and when a node contained in the information set is reached, the player with the move does not know which node in the information set has been reached.. 1. 2. . ⇒ At. every decision node in an information set, each player must have the same set of feasible actions, and choose the same action.. 1. 2. . 11. Backward induction CANNOT be applied! Lecture 8 2013 Winter.

(12) Subgame To solve dynamic game backward, divide it into small segment, called sugbame. A subgame in an extensive-form game 1. 2. 3. . begins at some single decision node n which does not share other nodes in an information set, includes all the decision and terminal nodes following n, and does not cut any information sets.. We. can analyze a subgame on its own, separating it from the other part of the game.. 12. Lecture 8 2013 Winter.

(13) Subgame Perfect Nash Equilibrium A. subgame perfect Nash equilibrium (SPNE) is a combination of strategies which induces a Nash equilibrium in every subgame.. ⇒ Since. the entire game itself is a subgame, it is obvious that a SPNE is a NE, i.e., SPNE is stronger solution concept than NE.. 13. Lecture 8 2013 Winter.

(14) =·. !")&0 &0 %0 #)$0 0 %)0 "$&0 #)$0 !$0 &0 !!+. 0 %0 !0 %!0 -0 +$&0 &0 !$!$0 &$%0 !$0 0 0 0 &%0 %)%0 0 %0#)$0 $0 !&0 %)0 "$&0. Practice of Dynamic Game (1). # # # # # SL·. . °·. ±·. ´·. '14. ?·. ·. ]·. Lecture 9 2013 Winter.

(15) =·. !")&0 &0 %0 #)$0 0 %)0 "$&0 #)$0 !$0 &0 !!+. 0 %0 !0 %!0 -0 +$&0 &0 !$!$0 &$%0 !$0 0 0 0 &%0 %)%0 0 %0#)$0 $0 !&0 %)0 "$&0. There Are 2 Subgames. # # # # # SL·. . °·. ±·. ´·. '15. ?·. ·. ]·. Lecture 9 2013 Winter.

(16) How to Solve each subgame . In the lower subgame: . . Player 2 simply chooses C (same idea as backward induction). In the upper subgame: . Essentially equivalent to the following static game. Note that there are 2 Nash equilibria in this game.. 2. A. B. X. 3, 0. 4, 6. Y. 8, 5. 2, 1. 1. 16. Lecture 8 2013 Winter.

(17) =·. ·. ·

(18). QLL·. #. SPNE in which (X, B) is played . *0 &0 %0-0 )%0 +$0 )'!0. P1 chooses Z and X; P2 chooses B and C. !")&0 &0 %0 #)$0 0 %)0 "$&0 #)$0 !$0 &0 !!+.. . 0 %0 !0 %!0 -0 +$&0 &0 !$!$0 &$%0 !$0 0 0 0 &%0 %)%0 0 %0#)$0 $0 !&0 %)0 "$&0. . You can write this SPNE, for example, (ZX, BC).. # # # # # SL·. . °·. ±·. ´·. '-. 17. ?·. ·. ]·. Lecture 8 2013 Winter.

(19) =·. ·. ·

(20). QLL·. #. SPNE in which (Y, A) is played . *0 &0 %0-0 )%0 +$0 )'!0. P1 chooses W and Y; P2 chooses A and C. !")&0 &0 %0 #)$0 0 %)0 "$&0 #)$0 !$0 &0 !!+.. . 0 %0 !0 %!0 -0 +$&0 &0 !$!$0 &$%0 !$0 0 0 0 &%0 %)%0 0 %0#)$0 $0 !&0 %)0 "$&0. . You can write this SPNE, for example, (WY, AC).. # # # # # SL·. . °·. ±·. ´·. '-. 18. ?·. ·. ]·. Lecture 8 2013 Winter.

(21) B·. J(B$-C(CL. Practice of Dynamic Game (2). ©·. ]·. (19. !%$0 &0!!+0 0. W·. ·. ]·. # LJ·. '. # &# # . Lecture 9 2013 Winter. . L.

(22) B·. J(B$-C(CL. Does Backward Induction Work?. ©·. ]·. #. W·. LJ·. '. ·. ? (20. !%$0 &0!!+0 0. ]·. # &# # . Lecture 9 2013 Winter. . L.

(23) B·. SPNE in which P2 chooses C . P1 chooses D and E ; P2 chooses B and C . You can express this SPNE as (DE, BC).. ©·. ]·. (21 !%$0 &0 !!+0 0. W·. ·. ]·. J(B$-C(CL. # LJ·. '. # &# # . Lecture 8 2013 Winter. . L.

(24) B·. SPNE in which P2 chooses D . P1 chooses D and E ; P2 chooses B and D . You can express this SPNE as (UE, BD).. ©·. ]·. (22 !%$0 &0 !!+0 0. W·. ·. ]·. J(B$-C(CL. # LJ·. '. # &# # . Lecture 8 2013 Winter. . L.

(25) Further Exercises . Suppose that players engage prisoner’s dilemma twice: after playing one game and before the new game, both of them can observe which action the other has taken. . . Draw the game tree. Derive the subgame perfect Nash equilibrium.. Verify that the Stackelberg equilibrium lies on the follower’s best response curve but not on the leader’s.. 23. Lecture 8 2013 Winter.

(26)