hello everyone with this episode we're going to start analyzing studying extensive form games or solving extensive forum games so we already talked about earlier uh what we mean by extensive form game the idea is very simple one player moves and then this other player moves so there's a sequentiality of the moves whether the second player observes the first player's actions or not it's irrelevant it's unimportant what matters i mean it is important for the solution of the game obviously but what matters is that the you know one player moves and then after that the second player moves and then after that maybe one player uh the same first player or maybe another player moves so there's this a sequence of orders we talked about how we write the strategies in such games remember strategy is nothing but a function which maps every information set to a to an action that is available at that information set well in this episode uh we are going to uh make uh you know some more definitions basically the idea is to clarify what we mean by game tree well the game tree remember extensive form games are represented as game tree such as this one we previously learned how to represent this game's tree as a normal form or a strategic form but now we're going to look at the extensive form or the game tree and sort of try to understand our new solution concepts over the game trees so again our purpose in this episode is to clarify what we mean by game tree there should be a set of rules right not all tree like structure is a game tree so here are the rules okay so first off well game tree is nothing but in mathematics what's called directed graph if you if you don't know what it is just fine but if you know what it is uh well yes game tree is a directed graph well game tree consists of nodes that are connected by branches so this is for example a node this is another node this is another node and those are branches that are connecting the nodes um sometimes this is also called nodes uh it's it's gonna be called terminal node uh so these brackets are basically the end of the game and and here are the payoffs of the players so each branch is an arrow in a sense although we do not drove them like an arrow but you can think of them as an arrow is a one way arrow though so you always go downwards uh there's no upward uh movement all right because that represents the first player and then the second player or the third player i mean the the next player in the sequence and then the next players in the sequence and so on all right so each branch is an arrow which connects two notes well you can start from a given note and trace through the tree by following the arrows right so you can start from a given node and trace through all the way till the end of the game later we're going to call it path but i'll come to it all right so the two words which are very important and we're going to use them a lot successors predecessors so successors are basically those that follow predecessors so i mean just remember it from the pre so predecessors are those that are followed so for example uh in in you know you know there's elections in the united states so you can think of donald trump was it was was the successor for obama and obama was the predecessor is the predecessor of uh donald trump okay so these words are important you'll see why all right a node x all right is a successor of y if and only if y is a predecessor of x all right so if you can if you think this as x node x and node y so here x is predecessor of y if and only if y is a successor why is it oh okay so here i'm sorry the um the the x and y has been changed so let me i mean here x is a successor of y but here y is a successor of x so be careful about so here if this is if this node is x and this node is y well then y is a successor of x and therefore x is a predecessor of of y all right so um i hope that's clear and i i hope i did not confuse you with this uh you know switch in notation all right so if a decision note x is a predecessor of y and y is a predecessor of z well then x must be predecessor of z all right so this idea of successor being successor or predecessor is some sort of a transitive relation okay okay well a game tree starts with what we call initial note all right so for example this is the initial note it basically represents the beginning of the game or the first player that moves in this game and and then each game each game tree ends at some terminal note so this is a terminal note which uh we represent the payoffs here that means there is going to be no more uh strategic interaction after this point it's the end of the game this is another um terminal node this one too so in this for example game we have one two three four five six uh terminal notes okay so once again each game tree starts with an initial note just one initial note we can't have two initial notes all right um yes i mean we usually don't have two initial notes but i'm going to take it back i mean some some weird games or some interesting games may have actually two initial notes um so but definitely there might be there will be more than one terminal nodes all right well what else a path is a sequence of nodes that has the following properties one it starts with the initial note okay um for sake of simplicity in the argument you can assume that there's uh only one initial note okay um a second uh the the path ends with a terminal note and then three successive nodes in the sequence are immediate successors of each other all right so in this game i'm gonna use a different color so this is one path okay it basically connects three nodes x y and z all right and clearly z is an immediate successor of y y is an immediate successor of x etc all right so there are many paths in this game let me use a different color this is also a path all right so if you count how many paths are there well this is one this is two this is thirty this is four this is five this is six so there are six paths well is this related to number of terminal nodes well yes normally and it's it's what we should have the number of terminal nodes determine the number of paths in the game all right however this is not a path uh so let's say we take this and then this that's it so this is not a path so let me so this is not a path it's sort of impartial you have to reach to a terminal node in order to define a sort of path so it has to be full path you see what i mean all right so now let's talk about rules so what are the rules uh for all these nodes and branches to satisfy and fulfill the concept of game tree well rule number one is the following every node is a successor of the initial node right every node is a successor of the initial node doesn't have to be immediate successor but successor nevertheless and initial node is the only node with this property all right so the initial node is not a successor of uh anything else any other notes all right rule number two says um by the way i already posted these lecture notes so you don't uh if you can't read them or if you can't take notes don't worry the lecture notes will be posted on the course website so the second rule says the following each decision note sometimes we call them just decision note sometimes decision note so they mean the same thing so each note except the initial note has exactly one immediate predecessor the initial note has no predecessor so that's very important for example this terminal node has only one immediate predecessor which is z this also has one immediate predecessor which is z again that's fine but the thing is you cannot have for example a node here and it's it has predecessors uh immediately it has three or two predecessors this can't happen all right any any structure a tree structure satisfying something like this will not be i will not be game three all right okay what else rule number three oh by the way the initial note has no predecessor okay so rule number this is why we call it initial note rule number three says multiple branches extending from the same notes have different action labels all right so here uh pick any note other than obviously the terminal nodes right by the way if a node is not a terminal node we call it non-terminal non-terminal node so here in this game we have one two three four five non-terminal notes okay so for any non-terminal note there's going to be a bunch of branches right for example this y this guy has two branches this guy also has two branches those branches basically tells us uh you know the different action uh that that are available for this player to select okay rule number four says each information set so we know what information said we in in our earlier uh sections and videos we talked about information set basically information set is a consists of at least two decision nodes so here all information sets have single decision nodes all right so each non-terminal decision note is also an infoset information set however we may have something like this you know some textbooks puts dots some circled them it basically means these two decision notes are in this information set or are this are in the same information set all right so each information set contains at least two decision notes for only one of the players what does that mean that means for any given information set you cannot have notes that belong to two or more people it has to i mean all the decision notes must belong to one and only one player okay rule number five and our final rule says the following all nodes in a given information set must have the same number of immediate successors and they must have the same set of action labels on the branches leading to these successors well it basically says the following if these two decision nodes are in the same info set well then we have to have two branch if we have two branches here we also must have two branches here i mean this is for instance not a game tree very quickly another example so this is initial note let's say this these two decision notes are in the same info set and the game is over so the payoffs all right so this is not a game tree if this and this decision notes are in the same info set which are which they are well then the number of error branches that follow these decision notes must be the same if you have two here you must have two here if you have three here you must have three here okay so let's suppose both decision notes has three branches that means remember branches are sort of different labels for available actions and if here the available actions are called a b c while here you can't call them x y z they also z they also must be called with same letter all right a b c so here a means for example jump up here b means hide away and c means scream well then here that means one of the actions available for you is screaming one of them is jumping the other one is hiding out you see what i mean so the set of available actions in each decision those nodes must be the same okay three notions are important the first one is the idea of perfect recall so we are actually talking about in this course uh games with perfect recall what it what does that mean it means all players can perfectly recall all their all their own previous actions they may not observe their opponent's previous actions but they perfectly observe and remember their own actions all right so meaning players do not forget anything that's that's very important so this is not a game this is more like a decision problem but if you consider this so player one is acting uh choosing between a b and c and then later he is choosing again between x and y okay so again this is not really a game because we don't have the second player but i mean if you like you can make this you know more than one person decision problem by adding a second player somewhere but here the idea is the following the first guy is first choosing a b and c but then later he can't remember whether he selected b or c all right so he forgets his own action so we are never going to look at games like this so each player remembers his or her own previous actions all right so in such games we call perfect recall we know i mean i know in reality by the way this is not really the case we make a move and then we forget it after a while and so we are forgetful in fact and that certainly influence our sort of behaviors in real life but the reason we ignore these games are because they cause us uh sort of interesting technical complications ariel rubinstein has a very nice paper with michael pikiani if i am pronouncing his or her name correctly they are sort of looking at games with imperfect recall but you know there's a lot of so it's a it's a very uh unfamiliar territory for game theorists i must admit all right well we distinguish extensive form games into two class games with perfect information and games with imperfect information so games with perfect information is basically all info sets or all information sets are singleton okay and if this is not true well then the game is a game with imperfect information which means there exists at least one information set with two or more uh decision notes okay so what does that mean for example if this is player one this is player two this is a perfect recall game but this is a game with imperfect information because here in this game there is an information set that is not singleton so all info sets are singleton means basically each player can perfectly observe each previous actions all right so here um if you want to make this game perfect information game this is what you would do player 2 player 3 or you know you can put player 2 as well doesn't matter so here player 2 can perfectly observe the first players the previous player's action all right so once again if all the information sets are singleton that means everybody can perfectly observe all the previous actions and hence we call these games perfect information however if this is not the case meaning if there is at least one information set including two or more notes well then this game has imperfect information okay