Dynamic Games of Complete Information: Backward Induction Guide

[Music] welcome to my course introduction to market structures

so we were doing game theory and we have completed the static game of complete information and now today we are going

to do dynamic games of complete information so in a dynamic game actually game is

played in multiple stages so in a static game game is played only once and it is played simultaneously here the players

may play the game sequentially one after another so in a simplest possible game if we

have two player so it can be something like this so player one first chooses an action

from chooses an action a i from a set of action that is a i

so that is stage 1 and player 2 observes the action chosen by player 1 and then player 2

chooses an action a 2 i from its set of action that is capital

a 2. so this is simplest you can say 2 stage game where this is in second

stage player 2 makes the decision and we define the utility function or a

payoff function for this ah for each player and for each outcome okay and now here what i have said

player 1 moves first player 2 moves second and player 2 while making

decisions knows what is the action chosen by player 1 so this is a complete information

and perfect information game why complete information because the payoff of each player for each outcome

is known by both the players so player 1 knows all the possible outcomes of player 2

and its own outcome payoffs and also player 2 knows

what are the possible payoffs in each of the outcomes in a player 2 player 1 and also itself ok

so they know both each others payoff so thats why it is a complete information and perfect because when player 2 is

choosing it knows the history so it knows what is the action

of player 1 ok because it is moving second so if because of that it is a perfect

information game so i again dynamic games are generally represented through a game three

and in the game tree we denote it through edges and nodes nodes are where each player is making some

decision or taking choosing their action and edges are to denote the movement of the game ok

so you will see one example here so this is suppose there are two players

two players ok and player 1

moves first player two

moves second so we represent the game in this way player one suppose the accent state

of player 1 is l and r something ok so this is you can say a 2 player

game where player 1 action set of player 1 is

this l and r so player 1 moves first so it is this node it is the starting point of the

game and so this is the stage 1 you can see and this

nords from here is stage 2 and here in stage 1 player can choose

any action from this set either it can choose l or it can choose r and in stage 2 player 2 knows either it

can be in this node or it can be in this note if r l is chosen it is in this note if r is chosen it is in player 2 is in

this not and here player 2's set of action is ls

and r dash it is same for in each situation or in in contingency okay and these are the payoffs

so this tree is the the first element is the ah payoff of player 1 and the second element is the playoff

of player 2. so like this so this is a terminal node in the terminal node we specify the

payoffs so these are the end of this game and these nodes are the decision nodes and these are the edges and based

on this edges we specify the movement or how sequence of in which the game is played

like first player 1 will choose player 2 is going to observe that and then player 2 is going to choose ok so

this is an example of two stage game which is played between two players and it is a perfect information why it is

perfect because it is player two knows what is in which note it is

when it is choosing and making a decision here again player 2 knows in which not it is lying when it is making

a decision ok next there can be another type of game and that is complete information and

imperfect information ok so it is a complete information why

because player 1 knows the payoffs of each outcome of itself and also the payoff of player

2. similarly player 2 knows what its payoff for each outcome and also the payoffs of player 1 for each outcome ok

so thats why it is a complete information but it may be imperfect because while

player 2 suppose the game is played between player 1 and player 2 and it is a 2 stage game where player 1 moves

first and player 2 moves second but while player 2 is moving or choosing its

action then player 2 does not observe the action chosen by player 1.

so if we take the similar game as we have discussed so it will look something like this this

is player 1 this player 2

l r l s

r s so ok so here player 1 has chosen and

player 2 is supposed to choose here and then we represent it through a like this and we write here

so player 2 knows that player 1 can choose either l or it knows or it can choose r it knows all these

outcomes all these payoffs but it does not know what is the exact choice of player 1 either l or l so

player 2 knows that it can be either in this node or it can be in this not okay so in this sense it is imperfect

information because it

doesn't know in which node it is lying okay

or what is the action chosen by player 1 or by the previous player so here also it is this is stage

one and this is stage two ok and

these are the decision nodes and this is the terminal nodes the game ends in this year

ok so this is a way to represent games in a complete information dynamic games

that is it can be a perfect information and it can be of imperfect information ok so first we will discuss perfect

information and then later on we will do imperfect information okay so from here what do we get that in

while specifying a dynamic game or an extensive game we should first specify the players

we should specify when each player has the move that is in this game we know that or in this game

we know that player 1 moves first and player 2 moves second similarly here also we know player 1 moves first and

then player two moves and then we have to specify the action sets so each player can do at

what each player can do at each of these his or her opportunities opportunities to move when it is making a decision

what it can choose from the set of actions ok that has to be specified and also we have to specify what each player

knows at each of his or her opportunities to move so here if

this is required because it can be of this nature because here player 2 does not know whether it is in this node or

in this not because player 2 has not observed the action taken by player 1 but in this game player 2 has observed

the action of player 1 in stage 1. so player 2 knows whether it is in this node or it is in this node while making

a decision in stage 2. so we have to specify that this

thing and we call this as the information set of this player we will specify

the specifically define the information set later on ok and we have to also specify the payoffs

if we do not specify the payoffs then we will not be able to play the game ok so it is something like this so we have to

specify that for example if we take another game like this player 1

player 2 player 2 player 1's action set is l r

so game ends here here suppose this is a game between three

players player one player two player three so the sequence is this is stage one

this is stage two this is stage 3. so stage 3 may be played or may not be played ok depending on what is the

action chosen by player 1 ok so this is stage 1

this is stage two and this is stage

three ok so we have specified the players player 1 3 we have specified their action set so player 1's action

set is r player 2's action set is

l s r dash again player trees action set is l double dash r double dash

in this scheme and now we specify and again we have specified the moves who moves first who

move second who moves third we have also specified who knows what like

when player 2 is choosing making a decision here it knows the action of player 1.

when player 2 is making an decision here it knows the action of player 1. again player 3 knows the action of player 1

and also knows the action of player 2. again player 3 knows the action of player 2 and also player 1. so all this

and we specify the payoffs here suppose a 1 b 1 c 1 a 2 b 2 c c2 and this is

a3 b3 c3 and this is

a4 b4 c 4 and this is suppose

a 5 b 5 c 5 and this is

a 6 b 6 c 6

ok so this and here

interestingly we may can make this game further complicated so we can do like this

suppose here we again so if player 1 chooses haldas then player 1 can again move

and suppose it is and the game ends here so it is

a 1 b 1 c 1 and this is a 7 b7 c7 ok so then the

action set of player 1 is a 1 and we we have another action set and that is

a dash that is and this action set is here in stage 3 so in

stage 3 we may have either this game being played or this game or this game ok

so we can have different ways in which we can represent a game depending on what is our

objective ok now the question is how to solve this problem

what is the solution concept so we use something called a backward induction

matter ok what do we do in a backward induction so let us take the simplest case that is

we have two player player 1 and player 2 player 1 moves first and player 2 moves second while player 2 moving or choosing

it knows the action of player 1. so this is a simple game like this

player 1 has moved first player 2 has moved second in stage 2 it knows the action chosen by player 1 while so it

knows that it is either in this node or it is in this not ok so

here what player 1 will do so so

player 2 first suppose player 1 has chosen an action from its set that is a one

then then in stage two so the when we say we are using backward induction then it

means that we are moving from backwards so we will first go to the last stage that is in this case stage two

so we know suppose player one has chosen an action this in stage one then

player two is going to do what it is going to maximize its payoff function such that by choosing an

action which belongs to his set of action ok so given a action of player 1 that is

a 1 i in stage 2 player two is going to maximize this ok

with such that this action belongs to this set of x ok so then it means what then

we will have a solution to this optimal problem and we assume that there is a unique solution okay we assume that

there is a unique solution ok so then what do we get we get a function like this and we call this a reaction

function so we plug in the value of a 1 i that is a choice of action choi or the action of player 1 and then

we get the optimal choice of player 2. so this is a reaction function of player 2. so it is

a function of the action of player 1 ok now since it is a complete information

game so player 1 1 will know this reaction function so player 1 knows that if i choose a 1 i

then what is going to be the decision of or what is going to be the choice of the player 2 in stage 2 based on this

reaction function so in stage 1 what player 1 will do will plug in this

in case of a 2 i ok here

and then it will choose a 1 i such that it maximizes its payoff function

so and also it should belong to the set of actions okay and

we assume that it has a unique solution otherwise it is a problem and then we get a

like this ok an optimal charge so the backward

induction outcome is that a 1 is always a is always going to choose a 1 star and player 2 is going to choose a 2 star

which is always equal to a 1 star like this so this is the backward induction

outcome okay so now let's solve some examples so we have already specified one type of

game let us take that game player one moves first l

r player two move second lds

r dash ok so this is the game so this is the in stage 1 player 1 makes a decision and in

stage 2 after observing the action of player 1 player 2 makes a decision ok so the sec so lets start with the second

stage here or here so in second stage we can have decision can be taken in this node at all

decision can be taken in this node ok so suppose this is a mistaken in this so player 2 knows that player 1 has

chosen l so it is in this note so here player 2 is always going to choose r dash because it's compared to

r 2 and 1 so r dash is so

what we do in this portion we represent that the optimal

choice of player 2 given that player 1 has chosen l is to choose r dash so the outcome is this

so we delete this portion and we write

it is going to be this okay so it is this

now suppose player 1 has chosen r then player 2 is here if it is here

it will compare between one and zero if it plays i'll dash it gets one if it plays r dash it gets zero

so player two is going to choose l dash

so so so player 1

while it is choosing it knows how player 2 is going to behave if it chooses l player 2 is going to

choose r so this is outcome if it chooses r player 2 is here player 2 is going to choose l dash so it is

outcome is this so player 1 will choose based on this so it will choose r

this so backward induction outcome in this game

is actually ok so backward induction outcome is this

and this this path

this path is the backward induction outcome ok

now lets do another example so suppose the game is played between two player player one moves first

and its action is l and r this so

suppose so this is a game played between two player player 1 and player 2 player 1 moves first it is this is

stage 1 this is stage 2 and this is stage 3 okay so in if player 1 chooses l then the

game ends if player 1 chooses r then player 2 can move it can choose either l dash or r dash if player 2 chooses l

dash then again the game ends if it chooses r dash then again player 1 get a chance to

move and it can choose from l dash l double dash and r double dash okay and these are the payoffs ok so first

element is the payoff of player 1 and the second element is the payoff of player 2.

so lets since we are using now backward induction lets start from this stage so that means we have to start from this

ok here so when player 1 is here suppose it is

making a decision from here it is always going to choose this because tree is greater than zero

so here we can write this so here

it is going to get player 2 is going to get because player 1 is going to choose l double dash so it is going to

now here player 2 is making a decision player 2 it will compare if it chooses l dash it

is going to get 1 if it chooses r dash it is going to choose going to get 0. so here player 2 will choose l dash

because 1 is greater than 0. so so it is this

becomes this so player 1 is always going to choose l this

rather than this right because 2 is greater than 1. so in this game

the backward induction outcome is that the game is only

played by player 1 and that is also only once so these edges represents its action

okay and the movement who moves what ok so the backward induction

outcome here it is this so player 1 is always going to choose r and the game ends instead the game could

have been played for 3 stages but actually if we use backward induction as a solution concept the game is played

only once and that is in only one first is okay so this is one example

now let us do another example and this is a slightly bigger game ok

ok let me use blue color so

okay so this is the game and this is a three stage game why so in the first phase player one makes a decision so

this is stage one in stage two player two makes a reason either in this note or in this node so

this is stage two so the game may end at stage two if player one chooses u and player two is

choose choosing either u or d but here we can have another stage and that

is from here for this in stage 3 player 2 chooses or moves

if player 1 choose chooses d and so then they will be in this path and

the player 2 will get the chance to make decision so then we will have third stage okay

so since we are using backward induction lets start from the third stage so suppose here suppose player 1 has

chosen d and player 2 has chosen u and so it is here so player 3 so first element is the

payoff of player 1 second element is the payoff of player 2 and third element is the payoff of player three

so zero to six so player three is always going to choose u dash because six is greater than

so this game becomes so

so here if player 1 chooses d and player 2 chooses u player 3 is always going to

choose u dash because 6 is greater than 0 so here it is 1 2

6. ok now we have this

portion here player 3 if it chooses you dash it gets

1 if it chooses d dash it gets 3 so player 1 is going to choose d dash okay

so this so

ok so the game is now like this we have only two stage now we have played the third stage

so in stage two if player 2 is if player 1 has move chosen d if it is here it knows if it

plays u it is going to get 2 if it plays d it is going to get 3 so player 2 is going to choose

d here it is going to choose d so it is this

and here if player 1 chooses u player 2 is going to choose

d because 3 is greater than 1. it is this and player 2 is going to choose b here

because 4 is greater than 1. so the backward out induction outcome of

this game is so

so so so the backward induction outcome here

it is like this player 1 chooses d

player 2 chooses p and player 3 chooses

u dash okay so this path shown by this yellow colored edges

gives me the backward induction outcome in the skin ok

so these are some of the examples of to solve a dynamic game with complete information and also

perfect information using backward induction okay now

we will specify the complete information game of perfect and imperfect information in a more precise way by

using a concept called information set and what is an information set information set is actually a collection

of dots for each player ok so each player will have some

information so for each so you can unders understand information set as that for each stage we will have one

information set and for one player ok so depending on the player who is moving or making decision in that stage

so so it is a collection of nodes so it gives the player has the move at every

node in the information so since it is a collection of nodes so in each node which belongs to an

information set a specific player has to move or has to make a decision in each of these nouns

and if there are many nodes in a information set the player

so information set is specific to a player so the player will never know in which not it it is lying or because

player 1 will not observe the history if there are multiple nodes in an information set all the previous

histories so when the play of the game reaches a nod in the information set so you have an information set and the game

while playing it has reached a nor like that then the players with the moves does not know which node in the

information set has been reached ok so these definitions have been taken from gibbons a primary in game theory

you can follow from there also ok so

if we take this scheme suppose okay

and suppose the payoffs are like this okay so this is the two-stage game and it is

a game between two player player one and player two player one moves first player two moves second and player to observe

this year so what we can say that the information set of player one is only this not so

here we have to number the nodes also suppose nodes are numbered in again in a

ah 1 2 3 this way ok

so player 2 it is only nod 1 information set information set of player 2 it has 2 information set this

and this so why player 2 has 2 information set

because see player 2 knows that it is in this note again here player 2 knows that it

is in this knot but if we place all these these two nodes because player two has

two nodes in which it is it can make decision in a same information set then it means that player two

will not know whether it is in this node game as the game is being played whether it

is it has reached this node or it has reached this not ok but in this game player 2 knows that it is

in this whether it is in this node or in this note so that is why we have to separate this and these are singleton

sets so if all the information sets are singleton then it is a game of perfect

information and if it is not singleton then it is a game of

imperfect information so it is like this suppose same game take

but it is like this so here player 1's information set is only this node that is not 1 this node

is not 2 and this node is not tree ok so but here player 2 player 1 can choose u

or it can choose d if it has chosen u player 2 is in this node if it has chosen d it is in this

node game has played will move in this path again game may move in this path

but player 2 does not observe the action of player 1 but it knows player 1 can choose either d or it can choose u it

can be either in this note or in this note but it is not sure whether it is in this node or it is in this one so that

is why we mark like this ok we mark it in this form or another way to

mark it is in this form is to make a dotted line like this if connect this nodes

by a dotted line then it means that player 2 does not know whether it is in this

node or written this now that means player 2 has not observed the action of player 1. so here information set of

player 1 is not 1 this because player 1 moves first ok

then player 2 information set is this not true so there are two nodes it does not know

whether it is in whether while making a decision whether it is in this node or in this not but

here player 2 knows who knows that whether it is in this node or it is in this not so that is why we have to make

two separate information set for player 2 but here we do not need so then in this way we can define the complete

information imperfect information game and come information complete in a perfect

information game how if all the information set of each player is singleton then it is perfect information

if there exist at least one information set which is not singleton then of any player then it is an

imperfect information game okay and further we require one more thing suppose if there are two nodes in one

information set and in each node the number of actions are different then also player will be able to distinguish

so the action set

should be same for each nodes in a information set ok so it is something like this

and suppose so this is an imperfect information game because player 2 does not know whether

it is in this set not or this but suppose player 1 knows player 1 plays this u

then ideally since it is connected by the dotted line these two

nodes so player 2 should not be able to distinguish between this node and s naught but here

if it is here then the action set is this so that is player 2 will know that okay

but if it is here the action set is udk so that it has two different actions set

all right so if player 1 plays this d then the action set that the player 1 has to choose from

is d k

d u d k and here this action set is only u and d

so it does not matter whether player 2 observes the action of player 1 or not

if it knows that whether it has to choose from this or it has to choose from this

then because it it it will come to know right moment it is here its action set is this

action sp or you can say action space is this if it is here its action space is this so it can distinguish between these

two so here even if player 2 has not observed the action of player 1 it can make this distinction and it will from

here it will know whether it is in this node or it is in this not so that is why if we are in a

information set there are multiple nodes or nodes more than one

then the actions space or the set of actions available should be same for so here its we should

remove this k ok so

the action space in each node should be same if this nodes belongs to the same information

set ok so in this game in this complete or dynamic games

we defined it through a game tree and

we have multiple stages now here we we bring in another concept that is sub game

and sub game here if we take this game so

ok sub game here it is defined in this way that the sub

game should begin at a decision node not numbered and any number that is a single turn information set ok so

a sub game should start from a game here either it is can start from here or it can start from here but it should not be

the top most that is the first node okay so game

it should not be the first decision not okay and it should include all the niches

this is the not following from it so if we have a game like this suppose it ends here

ok suppose it this is the game so it is a street stage game so here a game

this is a sub game because it starts from a decision not which is not the first one and

again this is a sub game again this is a sub game and this is also a sub game because from here it all

these nodes which follows it belongs to this game only so it will have this

this is one sub game this is one other sub game this is another sub game

and we will have another sub game like this ok

so this game has one two three four sub game this has only two sub game this is one and this

is one okay so sub games are that it does it

includes all decisions and terminal decision not and terminal not following an in the game three so if you start

from any node then all the nodes that follows it it should belong to that a game ok

and it should not cut any information set so this means that

if the game is suppose of this nature okay

okay okay now

suppose player 3 also moves here okay player 2 always moves u and d u and d player one means ah three l r

l r l r so the game is something like this

ok so here player 1 moves either it can choose u or

d then player 2 moves it can choose u d if it is here player 2 if it chooses d then player 3 can make a choice

again player 2 here ah it can choose either u and d and then

player 3 can choose from here so in this ca what you can see the sub games are only one sub game that is

actually it has no sub game because if you start from here what happens

it this and this so but this games ends here but if you start from

there it belongs to this information set and this information here we don't have any information set but this if we start

the game from here then this node also belongs to this information set but this node is not in

this path of the game plane this is this node is from this path right so that's why this is

there is no sub game in this game ok because if we start from this ea then we move here or remove here but here this

node it belongs to this information set and and these nodes are not in the path that

follows from here but if you look at this if the game starts here then all the paths

you can go to all the all the nodes that follows you from here it but from here you cannot go to this which are in the

information set this information so that is why there is no sub game in this game

okay so this is way we define the sub game and then we will use the concept that is subgame perfect nash equilibrium

and that we will do in the next class okay so thank you and for this you can read chapter 2 or chapter 9 from

this book okay [Music] you