Lec8 最近の更新履歴 yyasuda's website

全文

(1)ECO290E: Game Theory Lecture 8: Games in Extensive-Form. 1. Lecture 8. 14-15 Winter.

(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 14-15 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 14-15 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 14-15 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 14-15 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 14-15 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 14-15 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 14-15 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 14-15 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 14-15 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 14-15 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 14-15 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 14-15 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 8 14-15 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 8 14-15 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 14-15 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 14-15 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 14-15 Winter.

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

(22) B·. J(B$-C(CL. Does Backward Induction Work?. ©·. ]·.  #. W·. LJ·. '. Œ·. ? (20. !%$0 &0!!+0 0. ]·. # &# # . Lecture 8 14-15 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 14-15 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 14-15 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 14-15 Winter.

(26)

Updating...

参照

Updating...

Scan and read on 1LIB APP