Extensive form games and subgame perfection

so far we have described games using the normal form or matrix form what that means is we show in a matrix the strategies the choices that the players can make maybe top and bottom for player 1 and for player 2 maybe left and right and then for each combination of choices like top left we show the payoffs for those two players so top right maybe you get 0 0 and maybe bottom left gets to 0 and then bottom right would get maybe to 2 and that's the description of the game we have the players we have the actions that they have available and we have the payoffs for every combination of actions in such a game we assume that player 1 and player 2 move simultaneously in other words when player 1 moves he doesn't know what they are two is doing and when player 2 moves she doesn't know what player 1 is doing that works a lot of in a lot of cases but many times we actually have to describe the temporal structure of the game so player 2 may move first or maybe player 1 moves first and then player 2 if player 1 were to move first we'll already know the choice that player 1 is making it that would be a different kind of game to describe a game like that now we need the extensive form in an extensive form game we have an opportunity to incorporate a temporal structure of the moves of the players so in this game for instance the Challenger gets to move first and choose whether to enter a market or stay out and then the incumbent can acquiesce that entry or fight it and then of course if the Challenger stays out the incumbent doesn't even make a choice in this kind of a game so in this game these two players are not moving simultaneously they are moving one after another we still have to describe who the players are we describe the actions and the temporal structure of the game using a game tree in which there are some notes that are terminal or end nodes that's where the game ends and other nodes are decision notes where one or another player must make a choice and then of course we have to say which player makes a choice at each decision node and finally we have to show payoffs or preferences for terminal nodes so in the game that we just looked at the players are the Challenger and the incumbent and the Challenger can choose to enter the market or stay out if the Challenger enters the incumbent gets to choose to acquiesce or to fight that entry the terminal nodes in this case are these where the game ends and we assign payoffs to those for example if the Challenger and enters the market and the incumbent fights that's really bad for both of them and they both get a zero payoff the decision nodes are this one where the Challenger must make a choice and this one where the incumbent must make a choice so in a game like that notice that for every node we can associate a history of the game for example we go to this node by the Challenger choosing in and the incumbent choosing to fight and that's really the only way we can get to this node for every node in an extensive form game we can associate such a unique history so what's a Nash equilibrium in a game like this first of all we must describe a strategy before we can say what a Nash equilibrium is in principle a Nash equilibrium is going to be the same thing as before so it would be a combination of strategies such that neither player can do better by unilaterally deviating assuming that the other player sticks to the same strategy as they are following in the Nash equilibrium so in this case what would be a strategy while the Challenger can choose to enter the market or stay out and the incumbent can choose to acquiesce the entry or fight it in case the Challenger enters the market so how do we find a Nash equilibrium one way to do it is really to start at the end of the game and this is called backward induction we'll talk about it in a little more detail soon but that would mean we would first ask what the incumbent would do if the Challenger chooses to enter and the incumbent would have a choice between acquiescing and getting won or fighting and getting zero and therefore the incumbent will choose one equius now the Challenger has a choice between entering the market knowing that the income will acquiesce and therefore get to or to stay out and therefore get one and the Challenger will choose to enter the market so in and acquiesce is a Nash equilibrium in this game because given what the other player is doing each player is doing as well as they can be doing are there any other Nash equilibria well let's see what happens if the incumbent chooses to fight you may say well why would they come and do that don't worry about that for a moment just suppose that the incumbent says if you enter the market I will fight to the entry the Challenger if he believes it will will then think this way if I enter the market I'll get 0 because the incumbent would fight if I stay out I'll get 1 so I'll stay out them and in fact out and fight is also a Nash equilibrium of this game and given that the incumbent says that she will fight the challengers entry the Challenger is best off by staying out of the market and given that the Challenger stays out of the market the incumbent the can threaten to fight without actually having to fight that sort of threat is referred to as an incredible threat it's not credible it's incredible because we know that if the Challenger did enter the market the incumbent actually would be better off acquiescing and it would not be in her interest to fight the challengers entry but then if the challenger believes that threat then in fact he will stay out and so that's a Nash equilibrium but it's one that impose an incredible threat so the two Nash equilibria in this game are in and acquiesce and out and fight let's take a look at another game which is also a famous game called the ultimatum game in which players 1 and 2 get to split $10 but the way they do it is a player 1 first gives an offer and then player 2 gets to either accept it in which case they follow the split player 1 offered or two gets to reject it in which case nobody gets anything so you see if to chooses reject then the payoffs are zero zero for both of them one can choose to split the ten dollars fairly and in that case if player two accepts both get five or in a greedy way in which case is it clear to accept player one gets nine and player two gets only one so think about the Nash equilibria or equilibrium of this game well first let's think about what player - boo - if player one were to offer a greedy split player 2 could reject it and then get 0 or accept it and get one the one is better than the zero so player two would probably accept that even though it's not a great split it's better than getting nothing at all if player one were to offer a fair split of course player two would accept that - that that makes a lot of sense because five would be better than the zero given that player two is going to accept no matter what what should player one do well of course the fair split will give only 5 - player 1 but the greedy split would give 9 so player 1 is going to choose to split the ten dollars in a greedy way and player two is going to accept because that's really the best that he can do and that's a Nash equilibrium are there any other Nash equilibria in this game can you think of a way of player 2 maybe making a threat similar to the one in the previous game maybe a threat that could be an incredible threat but nevertheless could lead to another Nash equilibrium well think about this suppose player 2 says if you offer me the greedy split I'm going to reject it but if you offer me the first whip I will accept it player 1 knowing that would say but if I believe that for offering the greedy split I get 0 for offering the fair split I get 5 I'm going to choose the fair split so in fact fair and accept reject is also a Nash equilibrium of this game it's one that again involves the so called in credit both Rhett because we know that if it really came to the greedy split player two would be better off taking it accepting it than rejecting it but if player one believes that threat then she reinfect choose fair and the outcome will be 5:5 now notice that the strategy for player one is simply fair but for player two it's accept reject so we do need to say what player two would do even at a node that will not be reached in this equilibrium even at the nodes that will never happen because player 1 chooses fair we need to say what player 2 would do why is that important well player 1 and would really not know what to do unless she has some idea of what their two would do some belief about what player 2 would do if she were to choose greedy so in our equilibrium we need to describe what player 2 would do at every decision note that player 2 has so we have two Nash equilibria so far could there be even more Nash equilibria well think about this green equilibrium in this one player 2 threatens to reject a greedy offer and accept a fair offer and therefore player 1 offers fair a split of 5 5 would it be possible for player 2 to sort do it the other way and threaten to reject a fair offer and accept a greedy offer well you may say why would you ever do that as player 2 we are not really talking about what would make sense in an intuitive way right now we are talking about what would be the Nash equilibria of this game so you're just asking would it be a Nash equilibrium we can then talk about whether it makes sense or not but will it be a Nash equilibrium okay well let's think about it so player 2 chooses reject accept player 1 chooses greedy good player 1 do better by choosing differently given what they or 2 is doing well for choosing fair player 1 would get a 0 for choosing greedy player 1 would get a 9 so no player 1 could not do better she would choose greedy what about player 2 given that player 1 is choosing greedy could he do better by choosing differently well if he chose differently at this know that this decision node it actually wouldn't make any difference at all because player 1 is choosing greedy and this node is never reached in this pair of strategies so player 2 couldn't do better by choosing accept here because player 1 is choosing greedy now what about at this decision node player 2 could choose reject and get 0 instead of 1 that's not better so again player 2 can't do better either given what player 1 is doing which means this purple the pair of strategies is also a Nash equilibrium in this game which therefore has these three Nash equilibria one of them the first one makes a lot more sense than the second or the third the third seems to make no sense at all the second involves an incredible threat the first one seems to be the most sensible one so is there any way to single out that first equilibrium and that's what sub game perfection does the notion of sub game perfect equilibrium does for us and the way we solve for a sub game perfect equilibrium is to ask what the last mover does first so in this case 2 is the last mover so we ask what what would to do at those the almost terminal decision nodes and here 2 would choose to accept as we already discussed earlier and this node again 2 would choose to accept and given that to does that we can go one level higher and asked what would player 1 do given those choices of player 2 and player one we choose greedy and that's how we arrive at the sub game perfect equilibrium greedy accept accept notice again we need to specify what player 2 does at every decision node that he has so we think of a sub game perfect equilibrium as a more sensible equilibrium in many ways and the other Nash equilibria are nevertheless Nash equilibria but they don't seem to make as much sense often as the sub game perfect equilibrium the way we find the sub game perfect equilibrium is called backward induction and it means we start at the end of the game we move one level up and when we find the first decision node we ask what would that player do and then once we know for that level what that player does we go one level up again and ask what the next player would do and now we know here what player two would do already so we can talk about fair ones choice easily so let's look at a somewhat more extended version of this game so that we can understand the notion of sub game perfect equilibrium better in a larger game this is pretty much the same game as the one before we are now splitting not ten dollars but ten apples and we are doing it in two rounds so what that means is player one still gets to offer a fair split or a greedy split and if player two accepts then the first quickly stood a 5/5 split and the greedy split leads to a nine one split but if player 2 rejects we play a second round of the same game however in the second round you know the first round took time in the second round we don't have as many apples because unfortunately by the time we get to the second round a couple of those apples have already gotten rotten and so now we only have eight apples total so in the second round if player one offers a fair split and player two accept we only have four each of course it's the same after this first round in the second round if player one offers a fair split and player two accepts they each get four only and again if they are to reject the game is over and both get zero so in the second round the reject choice for player two leads to a zero then if player one offers a greedy split in the second round then player 1 gets seven and player two gets one so after a greedy split in the second round is going to be seven one first of all think about how many strategies each player has here how many decision notes do they have where player one has this decision node and this one and this one does three decision nodes and there are two choices at each decision node so one strategy for player one would be fair fair fair another strategy would be greedy fair fair how many such strategies are there for player one think about that well to here to here to here that's 2 times 2 times 2 that's 8 strategies for player 1 what about player 2 well player 2 has 1 2 3 4 5 6 decision nodes so how many strategies does player to have think about that for a moment and this shows us how complicated an extensive form game can get and therefore how important it is to be able to think through it and understand the strategic structure of the game without having to check every pair of strategies for player 1 and 2 against each other which would be virtually impossible without the help of the coarser computer so in this game how would these players act well let's find the sub game perfect equilibrium using backward induction which we just learned about first of all these are the terminal nodes these are all terminal nodes and so we start backward induction by going up from the terminal nodes and asking what the first player who must make a choice would do so going up from here player to here would have a choice between accepting and rejecting and getting 4 versus 0 so player 2 would accept here player 2 again would accept a 1 instead of a 0 then again notice we don't move up right away to this level but first we go through all the terminal nodes and move up one level and ask what the last player to make a choice would do player 2 again would accept 4 vs 0 and player 2 here would again accept the one versus is zero now that we know that we can move one level up and ask what player one would do it for example this decision node well for choosing fair player one would get a four because player two would choose except here for choosing greedy player one would get a seven because player two would choose except here so player one would choose greedy and similarly here player one would choose greedy for the same reason so now we know what player one would do at this level we can move one level up and asked what would player to do at this decision node and player two would have a choice of choosing to reject player ones greedy offer so clear two could choose reject but then player one would give a greedy offer again and then player two would accept that and get one so in fact for player two at this node choosing to accept and getting one would really lead to the same outcome as choosing to reject and still getting one so in fact player 2 is indifferent between accepting or rejecting at this decision node will say player to accept but we could also say player 2 rejects player two israelian difference between those two at this decision node and then at this decision node player two could accept the fair offer and get a five for rejected and then player one would give a greedy offer and player two would accept that and get a one so accepting here is certainly better for player two and finally we can move up to the root of the tree and ask what player one will do for offering a fair split player one would get five for offering a greedy split player one would get a nine of course you player two were to reject that player one would get seven either way it makes more sense for player one to choose greedy and get the nine or the seven than to choose fair and get the five so in this game the sub game perfect equilibrium this player 1 chooses greedy greedy greedy those are the three decision nodes of player 1 player 2 chooses except here except here accept accept accept accept that's how we describe the strategy of player 2 because clear 2 has six decision notes so that in fact would be the sub game perfect equilibrium now you might ask are there any other Nash equilibria in this game and in fact there is at least one other Nash equilibrium which is not sub game perfect in which player 2 threatens to reject this fair offer for example and accept this greedy offer in round 2 and accept both the fair and the greedy offer in round 2 on this branch of the tree and then player 1 chooses to offer a fair split here and the greedy split here and player 2 chooses to reject a greedy offering the first round but chooses to accept a fair offer in the first round and player 1 chooses to give a greedy offer in the first round so in this with these pair of strategies player 1 gives a greedy offer clear to reject it player 1 gives another greedy offer player to accept it and this is the payoff that would result from this pair of strategies you should check that this is in fact a Nash equilibrium so you should ask yourself given what player 1 is doing and those three decision nodes a good player to possibly do better and given what player 2 is doing at those six-six decision nodes could player 1 possibly do better and hopefully you would find that neither one could do better given what the other is doing and therefore this pair of strategies is a Nash equilibrium even though it is not sub game perfect

Channel: Adam G

Views: 57,250

Rating: 4.7677422 out of 5

Keywords: subgame perfect equilibrium

Id: GoeX3fNKghQ

Length: 22min 3sec (1323 seconds)

Published: Sun Mar 13 2016