0:00

In this video, I'm going to tell you about how to define formally, the

Imperfect Information Extensive Form and how to reason about stretegies in these

case. So, in the Perfect Information Extensive

Form, we have a player action at every single choice node in the game.

And a consequence of that definition is that we're seeing that players knows what

node they're in all the time. And that means, they know the whole

history of all of the moves that have happened before in the game.

This is reasonable for some games, like chess, where you really do get to see

what your opponent does in every different move.

It's not reasonable for games like Battleship, where your play, the, your

opponent can do something, and you don't get to see what it is.

And it matters to, to what happens to you later in the game.

It can matter to your payoff. It can matter to whether the game stops

or continues. So, in order to model this richer

situation where players aren't able to observe everything that their opponents

do, we're going to add something new to the game to the game representation.

So we, we're going to call it the imperfect information extensive-form.

And the way this is going to work is we're going to take the old definition

that we had before, but we're going to say that players consider some choice

nodes to be equivalent to each other. So there's some choice nodes that a

player isn't able to tell apart. And that's going to mean they're not able

to completely figure out the history of where they are in the tree because

they're not going to know which of several choice nodes they're at when they

have to take a choice. And we're going to do this by taking the

set of choice nodes for a given player, and putting them into equivalence

classes. So, what that means is, kind of

schematically, if these are some different choice node in the game, that

all belong to the same player. We might say these are one equivalence

class, these are another equivalence class and these are a third equivalence

class. And what that would is, the player

Wouldn't know which of these two choice nodes I, he was at when he was asked to

make a choice. but he would know that he was at one of

these two and not one of these two because they're in different equivalence

classes. So, let's say that a little bit more

formally. So, to formally define an imperfect

information extensive form game. We start with a perfect-information

extensive-form game which we've already learned how to define before.

And then we're going to add this ingredient of equivalence classes.

So we're going to add this element I which is a set of equivalent, a set of

sets of equivalent classes, one for every player.

So, for player 1 we have this set of equivalence classes or let's say for

player I, we have a set of equivalence classes numbered from 1 to K sub I.

So, these are all different equivalence classes.

And each one of these classes is some number of different choice nodes,

one or more choice nodes. And these are going to be different

choice nodes that that player isn't able to tell apart.

So, if every one of these equivalence classes contains only one choice node.

We are back with the perfect information case and if any of these equivalence

classes contains more than one thing, then we have something new.

We have a game where the player doesn't quite know what's going on all the time.

Now, in order to make this definition work, we need to add a couple of

restrictions so that it makes sense. So we want to say that if if two

different choice nodes are part of the same equivalence class.

Then first of all, they have to belong to the same player.

They have to be labelled with the same player because if they're not, you'd be

able to tell them apart because they a, different player would be acting.

So the player, kind of when he show up, he would know which, player he was, he

wou, he would really not be confused about all of the nodes in the equivalence

class. And the second restriction we have, is

that the two choice nodes have to have the same set of available actions,

because is the player can't tell them apart, he has to know what to do.

And, and that's the only restrictions. So let's look at an example game here,

and see what the equivalence classes are. So in this game, player 1 has 2 different

equivalence classes. This is 1 equivalence class, and this is

another equivalence class. So, in other words we're going to use a

dotted line here to connect together choice nodes that belong to the same

equivalence class. And what we want to say in this game is

that player 1 moves and if he goes right, then the game is just going to end and

they're just going to get each a payoff of 1.

If he goes left then they're going to get to make, player 2 is going to get to make

a choice. and player 2's going to go either a or b.

And then, player 1 is going to get to move a second time.

But player 1 isn't going to get to observe the move that player 2 took.

And so, he's going to have to take the same action.

regardless of whether he's at this choice node, or this choice node.

And indeed, you can see, we've labeled it the same way.

So if he says he wants to go left, he would have to go left from both of these

notes. And just to complete the answer to my

question, where the equivalence classes for player two, well player two only has

one choice node actually as the table here.

There shouldn't be a two player two has only one choice node, and so he has only

one equivalence class. So how should we define the pure

strategies for each player in this game? What's going to make sense as the

definition of pure strategies? Well, intuitively remember before what we said

was that we had the cross product of all of the different action sets for each

player. We don't want that here because we don't

want for it to be possible for player 1 to do something different in this choice

mode and then in this choice mode. So instead what we're going to use as a

definition is that the pure strategies is for player i are the cross product of the

action sets in every different equivalence class that he has.

And so, player 1's pure strategies here Are going to be a choice here, and

independently a choice here. So player 1 could take the action L, l or

he could take the action R, l or he could take the action L, r or R, r.

So player 1 here has 4 different pure strategies, rather than 8 as he would

have if we didn't have this equivalence class here.

So, in the imperfect information normal form, we have a more powerful

representation than we did in the perfect information case.

And, one way we can see that is we can represent any normal form game in this

representation, which you may recall we couldn't do with perfect information

games. So, here I'm showing you how to represent

the TCP backoff game or in other words the prisoner's dilemma game in, in

perfect-information extensive-form. So how does this work? Well first of all,

player 1 gets to decide whether to cooperate or to defect.

And after that, player 2 gets to decide whether to cooperate or defect.

Now, of course, in the prisoner's dilemma, you don't get to see what the

other person, chose to do when you take your own action.

So it might sound like a problem that player 2 gets to move second.

But, player 2 isn't able to tell which action player 1 took.

And so, although our game representation says that he goes second.

It doesn't really make a difference that he goes second.

because because you are not informed of what player 1 did.

And then once both of them take their actions, we end up with some payoffs.

So if they go C, D then they end up with this payoff here.

And these are the same payoffs that we have in the game matrix.

Notice that we could, have things work the same way if we put player 2.

At the root node and player 1 down here below because time isn't really playing a

role in this game. So I, what I told you on the previous

slide was how to start with a normal form game and make an extensive game out of

it. I can also still do the thing that we

talked about with the perfect-information extensive-form which is to start with an

extensive form game and make a normal form game out of it.

And, the way this works is exactly the way it did before.

So, I take all of the pure strategies for player one and I make them into rows.

I take all of the pure strategies for player two and I make them into columns

and then, this gives me my matrix. And for every cell of the matrix, I say

well, if player 1 took this pure strategy.

And player 2 took this pure strategy, what payoff would result? And I put that

into the cell of the matrix. And I fill in the whole matrix that way.

And once I have, the matrix like that. Then, then I'm kind of done.

My, my definition of mixed strategies is exactly what it was before.

It's just the mixed strategies in the induced normal form.

the definition of best response in Nash equilibrium for imperfect information

extensive form games again just kind of leverage the induced normal form.

And, and so all of those concepts that you already understand from from normal

form games carry over directly to imperfect information games.

And so for example we know from Nash's theorem that a Nash equilibrium always

exists for every imperfect information extensive form game because I can make a

finite normal form game out of it. Now, it's going to be the case that, this

transformation can make the game exponentially bigger as it could before,

even with the perfect information case. But, for example, for existence of

equilibrium that doesn't matter. Now lastly, you might wonder what

happens, if I take both of these transformations that I've shown you and I

apply them together. So for example, I could start with an

imperfect-information extensive-form game, make it into a normal- form game,

and then make that back into an imperfect-information extensive-form game

again. So, you might wonder, do I end up with

the same game? And the answer is, no, I won't.

Because I might have a game tree which is pretty deep.

it could have all kinds of different equivalence classes.

It, it could have all kinds of different sequential moves by the different

players. And when I make it into a normal form

game. I'm going to get this flat table.

And then, when I take a flat table, and turn that into an extensive form game.

It's going to be an extensive form game that only has 2 levels.

With all of this stuff in 1 big equivalence class.

And so, it's going to be an extensive form game that looks different from the

one that I started with. But, what is important is that it's

going to have the same strategy spaces, the same sets of pure strategies for both

agents. And it's going to have the same set of

Nash equilibria. So, although these games might look

different from the perspective of how they explicitly talk about time, they're

going to be strategically equivalent games.

And that's it for this video.