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.