1:36

if Player 2 were to choose like this if Player 2 was to make the decision that in

Â this situation he would decline the offer.

Â In this situation, he would accept it, and then again, in this situation he

Â would decline it. That's one pure-strategy and that's

Â different from this pure-strategy here. And so, the number of such

Â pure-strategies is 8. So now, let's try to make that a bit more

Â general. generally speaking, a pure-strategy for a

Â player in a perfect information game completely specifies how that player

Â would play the game for anything that could happen in the game.

Â specifically, it says what actions to take at every choice node that that

Â player gets to make a decision on it. So intuitively, the way I like to think

Â about pure-strategies in an extensive-form game, is in terms of

Â giving instructions to another person to play the game for you.

Â Imagine that Player 2 wants to send her friend off to play the game.

Â Then she would need to tell everything to her friend that her friend might ever

Â need to know in order to play the game properly.

Â And specifically, she'd have to say for every choice node that her friend might

Â encounter, what her friend would need to do.

Â So, kind of think of a pure-strategy as proxy instructions that, that you give to

Â someone else to play the game for you. then when we're counting the number of

Â pure-strategies, we really are asking how many different sets of proxy instructions

Â is it possible to have. If we say this formally in Math the

Â pure-strategies of a player in a given perfect information extensive-form game

Â are the cross product of the action sets for that player.

Â So, if we look at the sets of actions that are available at every choice node

Â for the player, the set of pure-strategies is then the

Â cross product of those sets across all of the choice nodes at which that player

Â gets to make a decision. Let's do an example that is a little bit

Â more complicated than we saw in the sharing game.

Â so first of all, I want to ask you here to think what are the pure-strategies for

Â Player 2? Here, I'm not asking you to count them, but I'm asking you actually

Â to say what they are. And again you may like to pause the video

Â and think about this for both players before I give you the answer.

Â So, we'll start with Player 2. Well, Player 2 has 2 choice nodes, this one

Â here and this one here. And so, the pure-strategies for Player 2

Â are going to be the cross products of the action sets at each of those different

Â choice nodes. So, here they are written out.

Â So, for example, the pure-strategy CF is saying that if this choice node Player 2

Â will play C c and if this choice node Player 2 will play F.

Â And because they are two sets of size 2, there's a total of four peer strategies.

Â Now, for Player 1, things are little bit more interesting.

Â What are the peer strategies for Player 1? Well, again Player 1 has two choice

Â nodes, this one and this one. And so again, the pure-strategies for

Â Player 1 are the cross products of those 2 two sets.

Â So, again, there are four pure-strategies for Player 1.

Â Why is this interesting? Well, if Player 1 takes this action,

Â then Player 1 knows that he will never reach this choice node.

Â Because his own action has made it impossible to reach that choice node.

Â Nevertheless, our definition of pure-strategies says.

Â That the pure-strategies AG is different from the pure strategy

Â So, there are still four pure-strategies for Player 1, rather than three

Â pure-strategies. So, pure-strategies are a bit different

Â in extensive-form games than they were in normal form games.

Â However, there's something great. Once we've got this new definition of

Â peer strategies, we can actually leverage it in order to use all of our old

Â definitions of all kinds of other concepts.

Â So, in normal form games, we define mixed

Â strategies as probability distributions over peer strategies and in an

Â extensive-form game, we can use exactly the same definition word for word.

Â A mixed strategy in an extensive-form game is a probability distribution over

Â mixed strategies. All the changes is that the underlying

Â peer strategies themselves are different. They're now policies of what to do at

Â every choice node in the game. Likewise, a best response in an

Â extensive-form game is, a mixed strategy that maximizes expected utility, given a

Â mixed strategy profile of the other agents. So again, that's exactly the same

Â definition we had in the normal form. Finally, Nash equilibrium is again a

Â strategy profile in which every agent is best responding to every other agent.

Â So, all three of these concepts are really just the same as they were before.

Â Now, something we might wonder is whether Nash equilibria exist, how we can reason

Â about them just having the definition doesn't, of course, give us that.

Â but there's an even tighter connection to the normal form that gives us more.

Â And that is that we can convert an extensive-form game into the normal form

Â and there are a couple of reasons why this is interesting.

Â The first is, because there exist in normal form game, we can leverage results

Â we have about the normal form, like the existence of equilibrium just by virtue

Â of the fact that there's a corresponding game.

Â also, if we find it easier to reason about the normal form game, we can

Â actually construct it and look at it, rather than looking at the

Â extensive-form. So, I'm going to show you how to do that

Â conversion. Here's the extensive-form game we just

Â thought about. The conversion is actually really straightforward.

Â Here's the corresponding normal form game.

Â And what you'll see is, we've just listed all of the pure-strategies of each agent

Â as the actions in the normal form game. So, you will remember these because we

Â went through them before in this game already.

Â Here are the four pure-strategies for Player 1.

Â And here are the four pure-strategies for Player 2.

Â Now, to fill in the payoff values, what we do is we just kind of simulate

Â play of the game. So if, for example, I wanted to figure

Â out how to put the numbers in this cell of the game,

Â I would look at the pure- strategy BG by Player 1 and the pure-strategy CF by

Â Player 2. So, BG means playings like this and CF

Â means playing like that. And then, I look at what node I would

Â actually reach in the game and I would get down here and follow the treat like

Â that and so I write in the number 2,10. And so, this whole table has been filled

Â in that way. And this is what we call the Induced

Â Normal Form of this extensive-form game. Now, one thing to notice about this

Â Induced Normal Form, is that it has more numbers in it, then there are leaf nodes

Â in the extensive-form. You'll notice there are repititions. So,

Â for example, 3,8 get's repeated four times here even though it only

Â corresponds to one payoff value. Similarly, 8,3 gets repeated four times

Â even though it only corresponds to one payoff value and that's not an accident.

Â That's because there are four pure-strategy profiles that leads to that

Â same leaf node in the tree. So this can be a problem because this

Â blowup is actually exponential. It doesn't look so bad here because the

Â game we're looking at is very small. But as the size of the game tree grows,

Â this blowout can really be profound. It can mean that in practice, it might be

Â very difficult for us to write down this Induced Normal Form.

Â Another thing that's important to notice is that we can't always do a

Â transformation in reverse. So, you might be curious and wonder,

Â if you give me a, a normal form game, can I make a perfect information

Â extensive-form game out of it? And the answer is, in general, no.

Â this kind of special structure that you see to the game where payoffs are

Â repeated is kind of important. And general extensive-form games so in

Â general, normal form games can't be turned into extensive-form games.

Â an example of that is matching pennies. Intuitively, in matching pennies, it's

Â really important that the two players play simultaneously.

Â And we don't really have a way of talking about two players playing simultaneously

Â in a perfect information game because one of the players would have to move first,

Â the second player would then get to see that move, and there's just no way of

Â representing a simultaneous move game like matching pennies that way.

Â So intuitively, we shouldn't expect a transformation from matching pennies into

Â a perfect information game. Seems like something would have to be

Â lost. Indeed, there's a theorem that says, that

Â every perfect information extensive-form game always has at least one

Â pure-strategy Nash equilibrium. That's not something that's true in

Â general of normal form games. Matching pennies, which we just talked

Â about, doesn't have a pure-strategy equilibrium.

Â it's easy to see why this theorem is true.

Â intuitively randomization often serves the role of confusing the other player

Â and there's really no reason that it, that could ever worked in a perfect

Â information game. If Player 1 randomized about this choice

Â Player 2 would nevertheless get to see what Player 1 had done.

Â And so it, it can't gain us anything to have randomization in the game that, that

Â can't create the opportunity for an equilibrium that wasn't there before.

Â So lastly, I want to look at this game and reason about what its three

Â pure-strategy equilibria are. Now, we can do this by actually looking

Â at the game tree and trying to think about what would make sense as an

Â equilibrium in that game. But that can be a little bit hard to do,

Â in part, because we can't quite so easily read the pure-strategies off the game

Â tree. instead, what can be more convenient for

Â a small game like this, is to construct its pure-strategy its Induced Normal Form

Â here, which list the pure-strategies directly.

Â And then to just reason about the pure-strategies directly on this game, so

Â let's do that. So I'll let you again, pause the video

Â here if you like, and try to find those equilibria for yourself and and then,

Â then I'll tell you what they are. So, the three pure-strategy equilibria,

Â are AGCF, AHCF, and BHCE. So, let's talk about how we're able to

Â see that those are equilibria. Recall always the way that we test for a

Â pure-strategy equilibrium in a normal form game is to, for each player,

Â check and see whether there's any deviation that would give that player

Â greater utility. So, let's, for example, look at BHCE.

Â If player 1 was to deviate here, you can see there's no other action he

Â could take that would give him more than 5.

Â And similarly, if Player 2 was to deviate here,

Â you can see, there's no other action she could take that would give her more than

Â 5. in both cases, there's something that

Â would tie but that's okay. Because a best response just says that

Â there, there isn't anything better. So that confirms that it is in

Â equilibrium. In contrast, if I looked at something

Â like this, which I have claimed isn't in equilibrium, you can see that it isn't in

Â equilibrium by checking for each player. So, Player 2 indeed, can't do anything

Â better than ten. So, this is a best response, CF is a best

Â response to BG for Player 2. But on the other hand, Player 1 could deviate from

Â BG to AG and get a payoff of three instead of a payoff of two.

Â So BG is not a best response to CF for Player 1,

Â and so this is not a Nash equilibrium. And that's it for this video.

Â Thanks.

Â