This video is about strategies, best response, and Nash equilibrium in the

Perfect Information Extensive-Form. Let's look again at the sharing game

which you see here. And now, instead of just thinking about

what this game models, I want to think about it in terms of strategies.

So in a normal form game, it was easy to talk about pure-strategies,

pure-strategies were just actions. but you can see in an extensive-form game

there, there are sort of multiple places where players get to choose different

actions. And so, strategies are going to need to

be something a little bit more complicated.

So, I want to ask you to think about how many pure-strategies each player has in

this game. You may like to pause the video at the

point and work this out for yourself before I tell you the answer.

We'll start by thinking about Player 1. Player 1 is kind of easy because there's

only one choice nodes for Player 1 here. And so, Player 1 has the three

pure-strategies that you would expect taking this action, this action, and this

action. Things are a little bit more complicated

for Player 2 because Player 2 has three choice nodes.

So, the number of pure-strategies for Player 1 is actually eight rather than

six. Player 1 has six different actions.

But the reason that there are eight pure-strategies is that a pure-strategy

really is every combination of choices that Player 2 could make kind of in the

aggregate. So, if Player 2, oops,

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.

4-3 Perfect Information Extensive Form: Strategies, BR, NE

博弈论

与讲师见面