Backward Induction & Subgame Perfect Nash Equilibrium Explained

[00:00:00]okay so let's apply the backward induction idea into this game but before this let's talk about how we can solve this game in general well normally the sort of the only method we know is that we can represent this game this extensive form game as a normal form game where we have one two three players and each player has multiple strategies and so we can write down the matrices and then find the nash equilibrium in pure or and mixed strategies well this is a bit challenging process obviously because you know writing down those mattresses is not going to be is very straightforward because you know the players have a lot of complicated strategies for example player one what is the strategies for player one well remember he moves here and here so therefore his strategy should have two components what he's gonna do here and what he's gonna do here so because he has three actions here and two actions here so these are the strategies for player one uh a m a n b m b n and c m c n all right so he has two four six total strategies very good well what about strategy for player two well she moves only once in this game and it's right here okay and so therefore she has well she has two actions so that means she has two strategies x and y and finally the third player she moves once here and then a second time here so she moves twice and each time she has two potential actions to choose that means she has two to the power two four strategies which basically tells us what she's gonna do here and what she's gonna do in the second decision note that she has so the strategies are like t u t v and w u w v okay so then uh we know how to write the normal form game so we're gonna have uh so if player three is the so this is the let's assume player one is the role player so we're gonna have six rows two columns because player two is the column player and player three is the matrix player and so we're gonna have four mattresses and so we can you know write those uh matrices you know put those numbers and then find the pure strategy nash equilibrium finding strategy nash equilibrium is very challenging in this environment but we can definitely find pure strategy nash equilibria all right well alternative to this and to be honest it's much much easier i can find what we call later sub subgame perfect nash equilibrium or sometimes we just call it perfect nash equilibrium but i prefer to call it subgame perfect nash equilibrium or spne so what we're going to do again i'm not defining it yet we're going to sort of name it later but the backward induction process helps us to find subgame perfect nash equilibrium well again i'm going to talk about why we call it subgame perfect nash equilibrium because actually they are nash equilibria anyway so what is the idea of backward induction we start finding the optimal actions or optimal strategies of the players starting from the lost players in the game so here the last players in the games are you know player three and one so which one should i start it really doesn't matter uh but let's start with player three okay so it doesn't matter from which player we start as long as they are really the last meaning there's no more other player after player three moves here and player one moves here so they are for that reason lost players so here the third players if the game ever comes to this point we know we assume that sequential rationality means he's going to choose wisely meaning she's going to choose a strategy that maximizes her payoff well what is that strategy is it you in this case she's going to get zero remember this is the third player so you should be looking at the third number or is it v in which case she's going to get seven payoff well clearly seven is higher so that means if the game ever comes to this point she's not gonna say i'm gonna play you she is in fact riva even if she started at the beginning of thinking of playing u she will actually if the game ever comes here she will actually play v because that makes sense not you well what about the first player again if the game ever comes to this point where player 1 chooses between m and n well now i have to look at the first number because first number uh corresponds to the first player's payoff if he chooses m he will be getting five if he's using a n he will be getting seven so clearly he will go for n all right so now we know what the optimal strategies will be for the last movers well what if the second last i mean it's the second player and the third player so what does it mean that the you know the second to last uh playing uh moving players well it means those players after which only one player makes a move so it's player two here and player three here well what is the optimal strategy for player two if the game ever comes to this point maybe the game will never come to this point but remember the concept of sequential rationality says at every sub game players are going to play optimally meaning they will choose this strategy that maximizes their payoffs even though they believe that this sub game will never be reached in this game alright so here if the game comes to this point the second player if she plays x she knows we should be looking at the second payoffs she's going to be getting four but if she plays y she knows that her opponent the third guy will play v not u and so she's going to get 5. well which one is higher obviously 5 and hence she should be choosing y not x all right so i put arrow here because later you'll see how i use those arrows to construct my strategy equilibrium strategy profile what about the third player if she chooses t look at the third number she will be getting four payoff but if she chooses w we know that the first guy will be moving next and in which case uh he is playing n and so the third guy is gonna get six is it six or four obviously six is better so therefore player three should go for w all right and then finally the first mover right the player one now player one knows what the optimal strategies will be for player two and three and and three and for himself so he sees that well if he plays b it's a sure three if he plays a it's a sure thing that the second guy will choose y and the third guy will choose v in which case uh he's gonna get three payoff huh three three so he's indifferent okay but if he chooses one i'm sorry c uh the third guy is gonna go for w for sure the first guy is gonna go for n for sure because his opponents are rational guys and including himself and so he's gonna end up seven well is it seven or three well obviously seven is better or higher so therefore he should be going for c hmm so what does that mean that means the following in this game uh the there's going to be a unique solution and in this solution in fact the first guy is going to play c the third guy is gonna play w and then the first guy is gonna play n and hence the outcome should be seven zero and six all right well what about the strategy profile however all right so what is the strategy profile the strategy profile that uh obeys this idea of sequential rationality we found it by using the backward induction approach right all i have to do i mean i have those arrows all i have to do i just need to put those arrows together how am i going to do this well look player one uh has six potential strategies so which one i mean according to this backward induction or according to these arrows which strategy is his optimal strategy well he should be following arrows every time he moves in his first move he should be choosing c either this one or this one in his second move he should be choosing n so therefore cn is his optimal strategy cn very good this is for player one what about player two the player two remember she has two strategies but she was and she moves in this game just once and she she should choose optimally and so it's it's why according to backward induction so therefore her optimal strategy is why well what about player three player three has four strategies and she is going to move optimally every time she moves so here she should be moving or playing not t but w alright so it's either this or this and here he should be playing v not u hm so therefore wv is her optimal strategy all right that means the uh according to backward induction the strategy profile the equilibrium strategy profile of this game so outcome is very simple just arrow just follow the arrows the string the creating the strategy profile is sort of the the challenging part so this strategy profile is going to be the outcome or equilibrium strategy profile later again we're going to call it sub game perfect nash equilibrium and and how did we created it well alternatively just put the arrows together right for player one the first arrow is c i mean you don't really have to write the strategies of the players uh like i did here so the first player strategy c and n the second player strategy is y and then the third player strategy is w and v that's it okay so what i would like to argue next is that this strategy profile i mean when i look at this outcome i can't really say if it is a nash outcome so i need to know the strategy profile so here's the strategy profile that leads to 706 right i mean how do i know that i just leave it to you as an exercise but when you put those strategies onto this game tree just follow the arrows it's going to give you the payoff of zero six okay what i will argue next is that this strategy profile is in fact nash equilibrium okay uh how so all right so this is how we verify that this strategy profile is in ash equilibrium first i'm going to show that player 1 is best responding player 2 and 3's strategy what is player 2 and 3 strategy it's y wv so forget about those strategies for player one only leave the player two and player three strategy okay right so player 2 is playing y player 3 is playing w here and v here so now i would like to know what strategy is best response for him is it cn or is it for example a something else so here how we check nash equilibrium is the following we're not going to look at here because again we're not doing backward induction we are checking that this strategy is in nash equilibrium all right so how do we do this well first of all look at what the payoff will be if player 1 plays cn well if player 1 plays cn we already know that his payoff is going to be seven agree right c and leads to seven payoff so let's try to see if he can achieve something better than this by playing something else well there are different ways if you look at the payoffs of player one seven is the highest he can achieve in this game agree so therefore there's no way player one can get a payoff strictly higher than seven and hence cn is the best or one of the best strategies he could play and hence he is best responding as simple as this alternatively i mean uh what you can think of well instead of playing cn what if he wants to play b b what b n b m doesn't matter what he's going to play here because once he plays b the game is going to be over so if he plays something including b like b m or b n well in this case his path will be three less than seven so this deviation is not profitable what if he plays something incorporating a uh a-m-a-n for example uh well you know what it doesn't matter because if he plays a the game is going to go here all the way to the payoff three so you know what again much less than seven so it's not a profitable deviation so i am checking basically all potential deviations of player 1 and observing that none of them are more profitable than playing cn and hence player 1 is best responding player 2 and 3. so i basically show that player 1 has best responding in two ways now let's see if player two is best responding for this purpose what i should do i should put the arrows for player one back cn and only erase the second player's arrow okay because now second player has the option of changing his strategy given that the other two guys meaning player one is playing cn player three is playing wn question is the following so also erase this so what is the optimal strategy for player 2.

[00:15:41]if you look at those strategies c and w the v well that means player 1 is going to play c all right and then player 3 is going to play w not t and then player one is gonna play n and so the game will over without asking player two what he would like to or she would like to play this is what i mean so according to those strategies player two will never have the opportunity to make a move what does that mean that means whether she chooses y or x is not going to change her payoff meaning her payoff if she plays uh x given that the other two guys are playing this her payoff is gonna be equal to her payoff if she plays y again given that the other two guys are playing the same strategies which is equal to by the way zero so therefore both x and y are best response to first and the third player's strategies and that means y is also a best response right meaning the first guy and also second guy are best responding their opponents now there's only one more player i need to check to say or conclude that this strategy profile is in fact nash equilibrium which is the third player now let's erase the third player strategy and keep everybody else the same i changed the color sorry the third player so it's not w anymore it's not v anymore because he can actually play something else if he wants to okay so remember if he does not deviate his payoff is going to be six in this game he can make seven right which is better than six but is it possible let's check so here player one is playing c all right he's not playing a or b so he's playing c that means the game will never come to this part of this game all right so i can basically ignore this part of this game which means i can actually ignore seven so seven it will never be achieved and so therefore six is the best payoff he can get meaning playing w and here playing v or or u doesn't matter is is one of the best he can do okay but let's let's make sure so here the player one is playing c if player three is playing something incorporating t right t u or t v well he's gonna get well he's the third player he's gonna get four much less than six so t u and t v are not best response to these strategies what about wuwv so if he plays w here well whether he plays wu or wv doesn't matter the game is going to end up here and he's gonna make six payoff so that means if player one and two are playing those strategies the best response for the third player is to play wu and play wv alright but remember i was checking if playing wv is the best response and it is a best response so what does that mean that means all three players are best responding each other and hence this strategy profile is a nash equilibrium strategy profile okay