We're going to look at the simplest kind of games that involve time, which are called perfect information extensive-form games. So, recall that normal form games model situations in which all of the players take action simultaneously. and that means that it's difficult to use them to think about cases where people really are doing something in sequence, where there's some kind of explicit time in the setting. Here, we're going to look at another game representation called the extensive-form, which makes the temporal structure explicit so it allows us to think more naturally about time. There are two different kinds of extensive form games that we'll talk about in this course, perfect information extensive form and imperfection information extensive form. We'll start with the first case. Basically, they differ by whether the players are able to reason about everything the other player does or whether sometimes they can't observe it. So, a perfect information game in extensive form is defined in a way that's much more complicated than normal form games were. We need a lot more pieces to make it work. So, we need all of these different pieces here. And intuitively what's going on here is that we have a set of players, as we did before. We have a set of actions, which now is just a single set for all of the players rather than having a a different action-set for everybody. And then, all the rest of this stuff, is going to be used to define the utility function. And in order to get to utilities, we need to think about the temporal structure of the game. So, we're going to build up effectively a game tree, where players take turns taking actions in the game tree. And eventually, they end up at some node where the game ends. and we're going to have a utility marking that node. So, let's formalize that intuition. We'll start with a set of choice nodes. So, these are going to be the nodes in the tree where players take an action, where something happens. And, we're going to call that set of choice nodes H. Now, to make the choice nodes work, we need to assign to a choice node all of the different actions that can be taken in that choice node. So, we have a function called the action function, chi which assigns to each choice node which actions it is that are available to a player in that choice node. And we also have a player function. And the player function tells us for every choice node who it is that gets to make the choice in that node. That's the choice nodes. We have another kind of nodes which are the nodes where the game ends, and we call these terminal nodes. So, this is a different set of nodes, it's disjoint from H and we call it Z. So, this gives us all of the different nodes in our game tree, now we need the edges in the game tree. And we build those up using the successor function. So, the way the successor function works is that it's a mapping from a choice node and an action that was taken in that choice node, to a new node. And that new node can be either a choice node, another choice node, or a terminal node. And what we want is that the successor function combined with the nodes defines a tree. And, in order for that to happen, we need to say that there's only one way of getting to any given new node. So, the way we say that formally is that for all pairs of choice nodes, and for all pairs of actions that could be taken, the only way that it can be that the successor function is equal in both of those cases is if the two, whoops. If the two choice nodes were the same, and the two actions were the same. So, these this condition means that the choice nodes form a tree, which is what we want. So now, at this point, we can finally talk about what the player's utilities are in the game. And so, we're going to have a utility function for every player and it's going to assign a number to every terminal node. So, and for each player, for each terminal mode, we're going to associate a real value, which is going to tell us how happy that player is if they end up in that terminal mode. Let's look at an example. This is the sharing game that talks about a situation where a brother and a sister want to decide between each other how they're going to share $2. So, they have $2 bills. And it begins with the brothers saying how he proposes to divide the money. So he, he starts out in this first choice node here. The brother's player 1. And so, he has three actions that he can take in the first choice node. His first action is labeled 2-0, what that means is that he keeps $2 and he gives nothing to his sister. His second action is labeled 1-1, and that means that he offers to split the 50/50 with his sister. And the last action is labeled 0-2, and that means that he proposes to give all of the money to his sister. In each of these cases, after the brother takes his action, we transition to a new choice node where the sister gets to act. And she gets to take one of two actions. In each case, she has the same two actions. She gets to accept the offer that he made or she gets to reject it. And the way this works is just what you would expect. So, if she rejects the offer, then both of them get a payoff of zero. Whereas, if she accepts the offer, then both of them get the payoffs corresponding to what the better proposed.
