0:00

Let us now revisit the solution concept for extensive-form games.

Â And let's start by doing it let's start by looking at the following example.

Â In this game there are a number of Nash equilibrium and here's one of them.

Â (B,H), (C,E). What is (B,H)? Player 1 goes down here

Â and down here, whereas player 2 goes down here and down here.

Â Under this strategy profile, of course the outcome of the game is this one.

Â And the path to both players is five. Let's first convince ourselves that this

Â indeed a natural eqilibrium, so let's hold player one's stratagy fixed and see

Â if player two can profitably deviat from their current response Well, what can

Â they do? They can say, here, I will, instead of going c, I would go d.

Â They could say that. But that wouldn't impact, the outcome at

Â all, given that player 2 is going down b. And so, that's not a profitable

Â deviation. It wouldn't change, their.

Â payoff. The payoff to player 2.

Â And the other thing they could do is say, I'm going to go down this, this way.

Â But that would, in fact, worsen their payoff.

Â Because they would end up here, with a payoff of zero rather than the 5 they're

Â getting. So player 2 cannot profitably, deviate

Â from their current strategy. What, what about player player 1? Can

Â they profitably deviate? Well, what could they do? They could say, okay.

Â Rather than go b, I'll go a. [SOUND] But then, they will get a payoff

Â of 3 rather than the 5 they're getting. That's not profitable.

Â And they could also say I'm going to go down, g over here, but given that player

Â two is going down e. That would matter, though in any case end

Â up in this this outcome of the path of five and so that's not profitable

Â deviation either. So neither player has a profitalbe

Â deviation then by definition it's a natural equilibrium.

Â But there's something a little disturbing about this equilibrium.

Â Let's clear the slide so it's a little less messy and let's again write down the

Â strategy for player 1,going B H and let's focus on, in, on this node right there.

Â Why would player 1 actually do H? Because a G dominates it.

Â The G, they get a payoff of 2 rather than 1.

Â And so even though It did lead to an actual equilibrium.

Â There is something a little troubling about it.

Â And the way to understand it is by claiming that they would go down H here,

Â player 1 is threatening player 2 by telling him, listen do not consider going

Â down here because I'm going to go down here.

Â Therefore and you would get a 0, so you'd better go here and get a 5 is what player

Â 1 is saying to player 2 but this strategy is not credible because after all player

Â 2 says, player 1 says that but in fact, it would not be in their interest.

Â I believe that player 1 actually would go down here.

Â And so how do we capture this in a formal definition? That brings us to a, to the

Â notion of subgame perfect equilibria or subgame perfection.

Â So, let's first define the subgame. It's a very obvious notion

Â a looking at some node in the game, node h, the subgame of G rooted at h is a

Â restricted, a restriction of h to the descendants from, from that, from that

Â node. And similarly what are the set of all

Â subgames of G? Well look at all the nodes in G and the set of all subgrames.

Â is simply all the subgame routed at sum node in g.

Â And so, a Nash equilibrium is a subgame perfect, if its restriction to every

Â subgame is also a Nash equilbrium for that, that subgame.

Â Say for example we go to the previous slide and we consider again clearing the

Â slide for a second. And if we look at the puh, the Nash

Â equilibrium B H, c, e. And we just sort the Nash equilibrium.

Â But among the subgames of this game. the subtrees of this of this tree, is

Â this subtree. So here's a subgame.

Â It's a game of a single player, player one.

Â And the restriction of this [UNKNOWN] is simply the action of going H, but this is

Â not an equalibrium in this very simple tree because theres a proffer of

Â deviation of G to the player and so while there's a [UNKNOWN] of the whole tree is

Â just friction to the sub-tree here. Is not a natural equilibrium and therefor

Â this natural equilibrium is not a sub game perfect.

Â And so, so we see that in fact that captures the intuition of non credible

Â threat and notice also that one special case of the sub tree is the entire tree

Â So subgame perfect equilibirium has got to also be Nash equilibrium.

Â So let's test your understanding of this concept a little bit.

Â Let's look at this tree and ask ourselves what are some of the subgame perfect

Â equilibirium there. For example how about (A,G), (C,F)? Well,

Â the claim is, this in fact is slightly imperfect.Now, why is that.What is a, g,

Â c and f. So that gives you this outcome over here.

Â And you can check that there is no possible deviation, but you can also ask

Â in all the sub-games is there a possible deviation? Well look, let's look at some

Â of the possible sub-games. Well, for example, here there is this

Â this deviation over here. That would not be proper to compare to

Â because they would go down from. eight to three.

Â How about over here? Is there [INAUDIBLE] deviation, for example, to player 2? Not

Â really, because, iIf they deviated over here, they would end up with a five

Â rather than the ten they're getting. How about over here? Is there possible

Â deviation at this node to the agent one? Well, no, because if they deviate they

Â would get one rather than two. So, in all subgames, the restriction of

Â the statuary profile, to that sub-game, is still a Nash equilibrium.

Â And, a,g, c, f, is, in fact, a sub-game perfect Nash equilibrium.

Â How about b, h, c, e? Well, the claim is, that it's not.

Â Well let's first write down the strategy B, H, B, H and C, E and this is not

Â something perfect for the reasons we saw before.

Â We saw that in this subgame right here. There is a profitable deviation for

Â player 1. Namely, to deviate over here, and get 2

Â rather than 1. And so it's not subgame perfect.

Â And, in fact, for the same reason, a, h, c, f.

Â Will not be subgame perfect. Let's write down what (A,H), (C,F) is.

Â (A,H), (C,F). You can check that it's a Nash

Â equilibrium but it is not subgame perfect.

Â Again, this subgame here is allows for a proper deviation on the part of the,

Â player 1. So even though it's what's called off

Â path. Even though player 1 makes sure that he,

Â that he never gets to. Visit this node by going down here.

Â Even so, it's not subgame perfect. Because had he gotten here, he would, not

Â have done what he claims he would have done.

Â And that gives us a good sense for what a subgame perfect Nash equilibrium is.

Â