PoliSci30 Week 4 Notes: Solving Extensive Form Games
PoliSci30 Week 4 Notes: Solving Extensive Form Games Poli Sci 30
Popular in Politics and Strategy
Poli Sci 30
verified elite notetaker
Popular in Political Science
This 11 page Class Notes was uploaded by Christine Cheung on Saturday October 24, 2015. The Class Notes belongs to Poli Sci 30 at University of California - Los Angeles taught by Chwe in Summer 2015. Since its upload, it has received 21 views. For similar materials see Politics and Strategy in Political Science at University of California - Los Angeles.
Reviews for PoliSci30 Week 4 Notes: Solving Extensive Form Games
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/24/15
PoliSci3O Week 4 Notes Extensive Form games Preview Kczusc 3950 5 Bey Review We know how to write down strategic form game How do we make predictions 0 Iterative elimination of strongly or weakly dominated strategies 0 pure Nash equilibrium 0 Mixed Nash equilibrium That s it There is at least one pure or mixed strategy Nash Equilibrium for any strategic form game 0 Proved by John Nash 1950 However note that in a strategic form game we implicitly assume that each person chooses independently 0 When choosing your actions you can t respond to the actions of others 0 People choose their actions simultaneously 0 But in many situations chess tictactoe you respond to the actions of others I People move in sequence I To model these we use an extensive form game I Also called a Tree Extensive form game Main ideas 0 Subgame perfection I A NE is subgame perfect if in every subgame people s actions correspond to a NE in that subgame No noncredible threats 0 What is a strategy I To specify a person s strategy you have to write down an arrow from all of her nodes A strategy is a complete contingent plan Example Kidnapping o A kidnapper can choose to kidnap or not if kidnap the family can pay or not Family Pay 10 20 Kidnap Kidna er pp 5 1 OO Not 00 This is an extensive form game tree 0 Step 2 assign utilities 0 This is an extensive form game I It has decision nodes labeled with the person who chooses I Branches from each decision node labeled by the possible choices at that node I Terminal nodes with payoffs o How do we make a prediction I Try to make it like a strategic form game If Kidnapped Pay Not Kidnap m 5 100 Not OO 0 Q I Two NE kidnap if kidnapped pay and not if kidnapped not I In graphic terms the chart represents the kidnapper choosing the top then bottom branch rows then the family choosing the top then bottom branch columns 0 We have two NE but one of them is sketchy I The not if kidnapped not is sketchy Family Pay 10 20 Kidnap Kidnapper 5 100 O O I In this NE the family never chooses because the kidnapper doesn t kidnap Paying weakly dominates not paying I It s sketchy because not paying is a noncredible threat If the family does choose it Will choose to pay 0 Another way to think about this is that once the kidnapper kidnaps the family plays a subgame Family Pay 10 20 Kidnap Kidnap per 5 100 00 I We can think of this subgame as a game in itself I The family s action in this subgame is not a NE of the subgame the family can gain from deviating o What about the other NE kidnap if kidnapped pay 0 IF the family gets to choose it WILL choose to pay I This is a credible choice Family Pay 10 20 Kidnapper 5 1 00 0 We have 2 NE kidnap if kidnapped pay and not if not kidnapped not I In the rst the family s action is a NE in the subgame It s credible This NE is called a subgame perfect NE In the second the family s action is not a NE in the subgame This isn t credible This NE is NOT a subgame perfect NE Subgame perfect occurs in an extensive form game IF in every subgame of the original game people s actions correspond to a NE of that subgame o In any extensive form game there might be several NE I Some are subgame perfect some aren t o In a subgame perfect NE there are no noncredible threats I It s a matter of judgment whether subgame perfect NE are more reasonable than nonperfect NE sometimes noncredible threats are reasonable sometimes not Example Penalty Kick with ESP 0 Say the striker can read the keeper s mind East Striker 1 O O 1 Keeper O 1 WeSt Striker East 1 O 0 As a strategic form game East West East 10 01 West 0 l 1 O o This is wrong Because the Striker always Wins E always Same Opposite West always East East West West East West East West East 10 10 91 0 West 0 10 91 10 0 New NE E WE W WE 0 Both NE are subgame perfect East Striker 1 0 O l Keeper 0 1 West 1 0 I To specify a person s strategy you have to write down an arrow from each one of her nodes I A strategy is a complete contingent plan Example Second grade lunch E t 9 1 Kid 3 00 Dad Money I 4 6 Kid Poke mon l 9 0 As a strategic form game Eat Refuse Eat Refuse Hotdog Pokemon Hot Dog Pokemon Kale Salad 9 l 2 l l O i 0 Money 46 19 6 49 NE Kale eats it and would buy hot dog and Kale eats it and would buy Pokemon 0 Remember that a strategy is a complete contingent plan Kale eat and would buy hotdog is not subgame perfect 91 This is because the kid would not buy the hot dog 0 0 over the Pokemon card You consider the would buy hotdog aspect because that plays a role in the dad s original decision 4 6 Dad s decision depends on things that you do not ever observe Dad Money Pokemon l 9 Kale kid eats 1t and would buy Pokemon card 1s subgame perfect 91 00 Dad Money 4 6 Pokemon l 9 Three main ideas in extensive form game Subgame perfection o A NE is subgame perfect if in every subgame people s actions correspond to a NE in that subgame no noncredible threats What is a strategy 0 To specify a person s strategy you have to write down an arrow from all of her nodes 0 A strategy is a complete contingent plan Backward induction 0 To find subgame perfect NE the method of backward induction is faster Example High school prom Serenade 100 20 50 5 Boy Turn into strategic form game Refuse Go Ask serenade 100 20 m Ask not 50 i m 10 Not ask serenade Q Q 0 Q Not ask not Q Q 0 Q 0 You have to consider whether he ll serenade or not because you must consider every node 0 There are 3 NE not ask serenade refuse not ask not refuse ask serenade go Which are subgame perfect 0 NE not ask serenade refuse 100 20 50 5 Boy 0 0 I NOT subgame perfect because if he serenades and she refuses he can get a better option from deviating to not serenade 0 NE not ask not refuse Serenade 400 20 50 5 Boy I IS subgame perfect because he doesn t serenade which is better for him given her refusal SPNE 0 NE ask serenade g0 Serenade 100 20 BO I NOT subgame perfect because people s actions do not correspond with NE Is there an easier way to do this If you want to nd all NE of an extensive form game you must write it as a strategic form game and then nd the NE If you want to nd ONLY the subgame perfect NE then the easy way to nd them is using backward induction 0 To use this start with the end of the game gure out each person s best response at each node and then work your way backwards Example prom Serenade 100 20 BO 00 10 Sm Step 3 00 0 Start with the end I l chooses not because 50 gt 100 0 Work backward I 2 chooses refusal because 5 gt 10 0 Finally I 1 doesn t ask because 0 gt 50 0 Thus NE not ask not refuse is the Subgame Perfect Nash Equilibrium I SPNE I We found it using backward induction 0 Example kidnapping saus 10 20 Family Kidnap Kidnapper 5 100 Not 00 0 The SPNE is kidnap pay If there are no ties then there is only one SPNE o If there is a tie then more than one SPNE is possible Example Penalty Kick with ESP East Striker 1 o 0 l Keeper 0 1 West l 0 o This is one SPNE 5851 l 0 0 l Keeper 0 1 West I 0 o This is another SPNE Three main ideas in extensive form game What is a strategy 0 Complete contingent plan 0 An arrow from all of her nodes Subgame perfection o If in every subgame people s actions correspond to a NE in that game 0 No noncredible threats Backward induction 0 Fastest method to nding subgame perfect NE
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'