Subgame Perfect Equilibrium in Extensive Form Games Explained

[00:00:00]all right in this episode i'm going to talk about sub game perfect nash equilibrium so this is uh formally how we define it uh let's take any extensive form game with set of players histories etc a mixed strategy profile sigma star is a sub game perfect nash equilibrium or simply sub game perfect equilibrium in mixed strategies of our game if sigma star induces a nash equilibrium in every subgame of this game well what does it mean that sigma star induces a nash equilibrium in every sub game well we mean again for more formally sigma star is an sp e sub game perfect nash equilibrium of our game if the continuation strategy uh that follows history h in uh in the set of continuation strategies uh continuation strategy profile i'm sorry is a nash equilibrium of the continuation game or off the sub game and this should be true for any histories and non-terminal histories meaning for every sub game your continuation strategy not your strategy continuation strategy profile must be a nash equilibrium of this sub game all right that's it well what i would like to underline is the following what if i look at behavioral strategies doesn't matter it's just a matter of notation so take any extensive form game a behavioral strategy profile remember we don't denote it by sigma but beta star in this fat b set is a sub game perfect equilibrium in behavioral strategies all right of this game if beta star induces a nash equilibrium in every sub game of uh the original game more formally the beta star which is coming from this uh fat b set is an sp e of the original game if the continuation behavioral strategy profiles which is oh by the way this s was wrong right it should be it should have been sigma h i'm sorry for my typo uh because you know continuation mixed strategy profile is coming from the set of mixed strategy profiles of the continuation game so that is also coming from b the fat b set restricted to h is the nash equilibrium of the subgame and this has to be true for any history okay as simple as this so it really doesn't matter whether you use mixed strategy or pure strategy definition or behavioral strategy the definition is the same all right nothing is changing um and also mixed strategy behavioral strategy definitions are equivalent because if something if if a mixed strategy is a nash equilibrium well we know that there's outcome equivalent behavioral strategy nash equilibrium sub subgame perfect nash equilibrium all right well uh what about the intuition so let me tell you a few things about it so if you remember the intuition i tried to give you earlier a nash equilibrium is a kind of a strategy profile which uh checks uh regret freeness check uh if of for each player um but but what is the idea so idea is the following so the nash equilibrium looks at simultaneous move game so players simultaneously choose a strategy and then they submit it to someone and then that person reveals all the strategies chosen and tells them what payoff they're gonna receive so the thing is once the game is over uh well uh the each player looks at his payoff i mean his strategy he knows it and the other's strategy he says well there are two things i wasn't expecting my opponents to play that uh well you know what too late too bad there's nothing i can do about it that wasn't my expectation so therefore i did a very poor i got a very poor or terrible payoff but there's nothing i can do at this point so i'm not going to regret if my expectation my conjecture about my opponent's strategy play is is is happened to me i mean happens to be different than my conjecture well but what if my opponents play exactly as i was expecting them to play well in that case am i going to regret no why well because i was best responding this conjecture and this conjecture happened to be correct so you know what i did the best i could do in this game so i'm not going to regret okay well what about so that's the idea of nash equilibrium but what about the subgame perfect nash equilibrium well here you don't have to make this uh regret freeness check uh until the end of the game all right you can say well you know what okay some things happened and then given that the original strategy i picked is it still optimal i mean i mean maybe well if unexpected things happened well i can still have time to make it correct all right so therefore maybe sticking to my original strategy is is no good idea because i can remember in in the nash equilibrium concept it is a concept for simultaneous one-shot game and if your opponents behave unexpectedly well there's nothing you can do because the game is over bro but here the game is not over yet it's just you know few things happen but from now on you may be able to change few things and so you can actually check whether you're going to be regretting your strategy that you picked originally or not even before the game is over all right so this is the difference between nash equilibrium and sub game perfect nash equilibrium i hope that intuition was clear in order to sort of make this intuition clearer hopefully let me talk about this very simple probably you all know about it entry deterrence game player 1 decides to enter to the market or not if he if he doesn't enter he's going to get zero payoff his opponent will enjoy the monopoly profit if he enters his opponent has two options it can fight in which case like price competition they both are gonna get negative one payoff or they can just split the profit one and one all right well it is simple to analyze this game at least for nash equilibrium and also sub game perfect nash equilibrium how so well play player one has two strategies stay out or enter right player two also two strategies fight or don't fight and then the strategic form game representation is going to be well if the player 1 chooses out it really doesn't matter what player 2 does but if he enters well then depending on the second player's choices the payoffs will be either -1 1 or plus 1 plus 1.

[00:07:31]well in pure strategies forget about mixed strategies but in pure strategies what are the nash equilibria well both of those strategies are best response to o only this one is d is the best response to e and then here the best responses are here and here so these are two pure strategy nash equilibrium outcomes and in terms of strategies the first one is of and the other one is e d these are nash equilibrium strategies remember well what about the sub game well in the subgame we use the backward induction at least backward induction is so useful but it is so powerless when the game is a very complicated or infinite horizon so in a very simple game like this i can use backward induction how well if e happens player 2 is gonna look forward he can choose fight and get minus one or don't get one obviously he's gonna go for d well given that right player one can reason and say you know why am i staying out because i'm gonna get zero i know my opponent is not an idiot so he's going to choose d so you know what i should also choose e so the backward induction says in fact one of those nash equilibrium is not optimal ed is the only optimal solution or one one is the optimal solution well why is it sub game perfect nash equilibrium because this game has two sub games one sub game is the game itself and and there's another sub game which is a proper sub game after history a e i'm sorry so this is where player two makes a move is a sub game well you're gonna say it is not a game because it's just one person well it's the simplest possible game you can think of player two is gonna make it so what is the nash equilibrium here well because player two doesn't have any opponent player two maximizing his exp payoff is the nash equilibrium strategy so it's d all right well therefore remember the restriction of you know sigma star b star whatever should form nash equilibrium in every subgame so the restriction of this strategy profile in this sub game which means ignore all f is the restricted strategy is it is it nash equilibrium of this game no it is not so therefore but but here d is a nash equilibrium of this game so you know what this is the sp the only sp and pure strategies but once again that regret freeness idea it says look o f so the nash asks the following suppose the game is over all right period one period two and over now i ask you the following question um your opponent was expected to play oh and you were playing i'm sorry you you were hoping that your opponent is going to play f well the thing is uh well obviously once you play o your opponent did no chance opportunity to play in this game so basically this will not be realized and so you will never be able to learn your opponent's strategy and hence you're not going to regret anything because you don't know what he would do you just you know leave with your conjecture however however if you choose e all right well what is going to happen well your opponent player 2 is going to look well you know what initially i was chosen this strategy f fight but the thing is unexpected thing happened and the game is not yet over right my opponent was expected to play i was expecting him to play o but he played e so all right uh should i still continue with fight well i'm gonna get minus one clearly it's not optimal so i make i'm sorry not i the second player is going to make this regret freeness check after something unexpected happens and he will definitely change his mind so once he see that you played e i mean player 1 played e he will certainly not commit play f he will change it so therefore knowing this player one should know that his opponent's strategy f is actually not regret free he will regret from choosing this strategy at the beginning of the game very much if i show him something unexpected and play e so therefore i shouldn't play o all right so this strategy is all the nonsense of the non-credible threat but this one makes a lot of sense because here the unexpected thing is well i mean let's say player 1 played o so that's the unexpected unexpected thing well but the thing is player 2 will still not regret from this why is that well i mean the game is over there's nothing he could do all right so uh what about player one well player one if he does something unexpected of course he will regret for that reason he's not gonna do something unexpected from him he's gonna choose e but once he chooses e is player two is going to regret from his choice d well no because uh he's getting one otherwise if he plays f he's gonna get minus one all right so this is why we need this nash equilibrium in every sub-game so in every sub-game players are re-optimizing their strategies given the history all right so initially maybe they thought some histories are not possible they're impossible they weren't expecting it but the thing is it they may happen so if they do happen all right if they do happen well are they going to stick to their strategies or not well so a sub game perfect nash equilibrium strategy profile is a strategy profile or strategy for each player so that at any point of the game whenever a player makes a regret freeness check he's gonna say well you know what expected or unexpected things happen who cares i am happy with what i'm doing all right so it is much stronger than nash equilibrium but nevertheless every game has at least one sub-game perfect nash equilibrium strategy maybe in pure strategies maybe in mix or behavioral doesn't matter but every finite game i'm sorry i should take it back every finite game has at least one sub game perfect nash equilibrium