Lec8 最近の更新履歴 yyasuda's website
23
0
0
全文
(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)
関連したドキュメント
A variational problem for axisymmetric shapes is stated where the shapes with extreme average mean curvature and extreme average cur- vature deviator at relevant constraints are
Corollary 24 In a P Q-tree which represents a given hypergraph, a cluster that has an ancestor which is an ancestor-P -node and spans all its vertices, has at most C vertices for
Solutions of integral equa- tions are expressed by the inverse operators of auxiliary exterior and interior boundary value problems, i.e., theorems on the solvability of
We denote by Rec(Σ, S) (and budRec(Σ, S)) the class of tree series over Σ and S which are recognized by weighted tree automata (respectively, by bottom- up deterministic weighted
The paper is organized as follows: in Section 2 is presented the necessary back- ground on fragmentation processes and real trees, culminating with Proposition 2.7, which gives a
The operators considered in this work will satisfy the hypotheses of The- orem 2.2, and henceforth the domain of L will be extended so that L is self adjoint. Results similar to
We will show that either the set of nodes with L (w) = 0 or those nodes together with the root form a minimum distance-k dominating set. Dominators are pushed beginning at the leaves
A nonempty binary tree can also be regarded as a rooted directed tree graph (arborescence) where the outgoing arcs of each node are labeled by distinct labels from the set { L, R
