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.

Â