1Recap:{ Last classes (January 26, 2010)zMonopolyzMonopolyz Stackelberg (sequential versus simultaneous)z Multi-stage game{ Today (January 28, 2010)zBackwards Induction1zBackwards Inductionz Extensive form gamesz Subgamesz Subgame perfect equilibriumExample (cont.)1L’R’L’R’223333LR2L”R”3L”R”3L”R”3L”R”2Information set{ An information set for a player is a pycollection of decision nodes satisfying:z The player has the move at every node in the information setz When the play of the game reaches a dhf hl3node in the information set, the player with the move does not know which node in the information set has (or has not) been reachedExample (cont.)1L’R’L’R’22333LR4L”R”3L”R”3L”R”L”R”Player 2 has two information sets, both singletons.Player 3 has two information sets, one of them is singleton.3Subgame{ A subgame in an extensive form gamez begins at a decision node n that is a singleton information set z includes all the decision and terminal nodes following n in the game tree (but no nodes that do not follow n), andz does not cut any information sets (i.e., if a decision node n’ follows nin the game tree 5decision node n follows nin the game tree, then all other nodes in the information set containing n’ must also follow n, and so must be included in the subgame).Example 12UDLRLR22(2,1)(0,0)(-1,1)(3,2)LRUDUD11(2,1)(-1.1)(0,0)(3,2)6(,)(,)(1,1)(,)Two subgames, one beginning at each of player 2’s decisionnodes (+ whole game)(2,1)(.)(0,0)(3,2)No subgames other than whole game4Example (cont.)1L’R’L’R’22333LR7L”R”3L”R”3L”R”L”R”Subgame Perfection{ Definition (Selten 1965): A Nash ()equilibrium is subgame-perfect if the players’ strategies constitute a Nash equilibrium in every subgame.z (A Result: Any finite dynamic game of complete information has a subgame-perfect Nash equilibrium, perhaps in mixed strategies) fff8z (Q: How is subgame perfection different than backwards induction?){ Q: What is the difference between the outcome and an equilibrium?5Nash/subgame example1UDLRLR22(3,1)(1,2)(2 1)(0,0)9(3,1)(1,2)(2,1)(0,0)Nash/subgame example1UDLRLR22(3,1)(1,2)(2 1)(0,0)10(3,1)(1,2)(2,1)(0,0)Find the backwards induction solution.6Nash/Subgame example: Suppose we examine normal-formPlayer 2(L,L) (L,R) (R,L) (R,R)U 3,1 3,1 1,2 1,2D 2,1 0,0 2,1 0,0Player 111{ Find the pure strategy Nash Equilibrium(s) in Normal Form:Nash/subgame example{ One Nash Equilibrium from the qnormal-form is the subgame-perfect Nash equilibrum{ The other one represents a threat or promise that is not crediblez In which subgame is it not a Nash 12gEquilibrium?7Dr. Strangelove13Critiques{ Backward Induction and Subgame Perfection may be less reasonable if Perfection may be less reasonable if there are multiple players or if each player moves several times{ Example: I players with decision A or DAAAA14(1,1,…1) (1/2,1/2,…1/2) (1/I,1/I,…1/I)(2,2,…2)12I-1IADD D
View Full Document
Unlocking...