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 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)
関連したドキュメント
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
Similarly, the null space algorithm which we implemented, can be subdivided into three phases: a first symbolic phase where the shortest path tree and the quotient tree are computed,
A permutation is bicrucial with respect to squares if it is square-free but any extension of it to the right or to the left by any element gives a permutation that is not
UVP detection starts when PGOOD delay (T d_PGOOD ) is expired right after a soft start, and ends in shutdown and idle time of hiccup mode. Over Current
