🔍
Lecture 28: Solving General Extensive Form Games-Modification in Backward induction - YouTube
Channel: unknown
[9]
So, now as I discussed right, I said right
in the beginning that we are interested in
[14]
getting the solution concept, how to solve
a general extensive form game.
[20]
So, for that,of course, we have backward induction but weare going to modify it little bit.
[24]
What do we have, that start from the smallest subgame
containing the terminal nodes of the game
[30]
tree. Remember, what happens when we have
thissmallest subgame with the terminal nodes?
[37]
In most of the cases there is no strategic
interaction left, applier decides and game
[43]
ends. So, there player can very easily decides.
Now, of course, what we will have, determine
[53]
the action that a rational player would choose
at that action node, just before the terminal
[60]
node.Replace the subgame with the payoff corresponding
to the terminal node that would be reached
[66]
if the action were played. And, repeat until
there are no action left. So, this would be
[73]
clear when we do it.
[74]
Let us do it for this game.For example, here,
we know this is the subgame. So, we will do
[81]
it for the,we will do it here; player 2 would
take this game in this direction. So, this
[89]
subgame can be replaced by here,p (2, 3),
why? Because player 1 knows player 2 is rational
[98]
and given a chance, player 2 is going to take,
decides in this direction.
[103]
Now, we have the whole game, how would we
solve it?Ok. So, very simple, we will do the
[112]
normal form of the game. We will do the normal
form of the game, and I had already modified
[117]
this. I had put it as 2. We can get the normalform
game. And, what would be the normal form game?
[123]
Again, let me point out here; let us say,
x;let us give them name –left, centre and
[132]
right; and here, A B, A B.
And, we can make the table,as we have already
[140]
learned in the one of the previous modules,
that player 1 has how many action now? L C
[147]
R 3,here we do not have to worry about. So,
player 1 is going to take action L C R. How
[157]
many strategies player 2 has? In fact, 2 here
and 2 here, 2 multiplied by 2, so, 4. But
[165]
we do not have to take care of the 4 because
we know if game reaches to this point, this
[170]
is what player 2 is going to do. So, we will
take a reduced game in which this game tree
[176]
is replaced by the outcome from this smallest
sub game.
[181]
So, what we will do? Here, in this,in the
reduced form, player 2 has either A or B.
[189]
So, if player 1 plays L and player 2 playsA,
game will reach to this. So, payoff would
[197]
be 4, 1. And, similarly, let me write 0, 2;
here 5,1; here 1, 0. And, if player 1 plays
[207]
R, no matter what player 2 does. Here we will
have 2, 3; 2, 3. Notice, I,we got rid of this
[215]
one.
And then we solve. How do we solve? Just for
[218]
your reason, we try to obtain the nash equilibrium,
what do we get? If player 1 believes that
[226]
player 2 is going to play A, the best response
of player 1 is to play C. If player 1 thinks
[232]
that player 2 is going to play B, the best
response is R.
[238]
Now, if player, we let us do it for, from
player 2’s perspective. If player 2 thinks
[246]
that player 1 is going to play L, then the
best response is B. And similarly, we get
[251]
here this, and here this. So, we get 2 Nash
equilibrium, (C, A) and (R, B). Notice, that
[262]
player 1, player 2does not have any strategies
named A or B. Player 2 has a strategy named,
[269]
if we put here x and y, then player 2 has
a strategies named, A x, B x, A y and B y.
[279]
So, how can we give the equilibrium? It is
very clear that player 1, one equilibrium
[287]
would be that player 1 plays C,and player
2 plays here A. But here we do no matter player
[298]
2 is always going to play y, so, we can say
player 2 is going to play, A y.And similarly,
[305]
here we can say, what? Player 1 plays R and
player 2 plays B, and of course, here y, so,
[316]
B y.These will be the 2 solutions that we
can get, that player 1 takes the strategy
[324]
C, and player 2 takes the strategy A y; or
player 1 takes strategy R and player 2take
[333]
the strategy B y.
[334]
In fact, we did the modified backward induction,
this is what we call sub game perfect equilibrium.
[343]
What is subgame perfect equilibrium? First
of all, we, to understand subgame perfect
[350]
equilibrium let us understand the continuation
strategy, what do we mean by a continuation
[355]
strategy? A strategy for the original game
also defines a strategyfor each of its subgames,
[362]
sometimes called a continuation strategy.
So, what we meant here that when we have B
[371]
y,and this particular subgame has reached,
what would be the continuation strategy in
[381]
this subgame, only y. Similarly, for A y,
the continuation strategy would be only y.
[387]
Now, a strategy profile of a sequential game
is a subgame perfect equilibrium. In short,
[396]
it iscalled SPE; in some books it is also
called SP any. It includes a Nash equilibrium
[405]
for every subgame of the original game. So,
if we treat subgames of the original games
[413]
as independent game then subgame perfect equilibrium
should induce Nash equilibrium not only in
[420]
thewhole game, but also in all the subgames.
So, in other word, the strategy is perfect
[427]
even if player never goes to the that part
of tree.
[432]
An imperfect equilibrium is like a strategy
that would not be optimal if the other player
[439]
did something different. Remember, we talked
about the mistakes, what a player makes a
[445]
mistake,in that case if a strategy profile
is subgame perfect equilibrium no problem,
[451]
but if a Nash equilibrium is not subgame perfect
equilibrium then you would not get the optimal result
[458]
Of course, by now you must have noticed that
[461]
any subgame perfect equilibrium is Nash equilibrium,
but not all Nash equilibrium of the gameare
[473]
subgame perfect equilibrium. Although, wherever
we can obtain result from backward induction
[478]
technique, backward induction equilibriumdefinitely
is subgame perfect equilibrium.
[485]
What, again, this is something I am saying,
but I will revisit this statement in other
[493]
modulewhere we will talk about credibility.
A Nash equilibrium that fails to be subgame
[500]
perfect is also known as Nash equilibrium
supported by non-credible equilibrium.
[507]
if I want to give you the basic rule, how
to obtain subgame perfect equilibrium, use
[512]
backward induction first; if you can use backward
induction well and good; the equilibrium that
[518]
you are getting would be subgame perfect equilibrium,
if you are mind full of the strategies of
[524]
players;do not just write outcome as the equilibrium.
Equilibrium always means the strategy profile
[532]
equilibrium should give 1 strategy for all
of the players involved in the strategic interaction.
[538]
if backward induction techniquefails, use
techniques learned from the normal form game
[544]
in the remaining game, not sub game, in remaining
games.
[551]
Let us take an example.This example is given
inprofessor Martin Osborne’s a very famous
[558]
book “An Introduction to Game Theory”.
What we have here, that we have player 1;
[564]
player 1 can take one of these 3 actions – C,
D, or E. If player 1 takes action C, then
[570]
player 2 can take action F or G. And similarly,
I have written if player 1 takes action D,
[577]
then player 2 is can take action H or I.
Similarly, if player 1 takes action E, then
[583]
player 2 can take action Jor K. Here, backward
induction, the vanilla form,the earlier backward
[591]
induction has a problem, why? For player 2,
it is optimal to take any one of these 2action.
[599]
Even if player 2 takes For he takes G, his
payoff would remain same.
[604]
So, next, here player 2 again can take either
H or I,in both cases his payoff would be1.
[616]
Here it is clear that player 2 would take
K not J because K gives 3 and J gives 2. So,
[623]
this is not possible; we can get rid of this
right in the beginning. Mind you, how many
[628]
subgames do we have in this game? One subgame
starting here, the whole game; then, another
[633]
subgame starting here; another subgame starting
here; and another subgame starting here; so,
[638]
we have a total of 4 subgames.
[642]
How should be proceed now?This we have already
indicated. Notice, that we can say, the best
[650]
response from player 2; what would be the
best response from player 2, no matter what
[655]
player 1 is doing, best response would be
F HK.What is F H K? Play F if given a chance
[664]
in this node, play H if given a chance in
this node, play K given a chance is this node.
[670]
But, this is not the only one,only best response.
What are the other best response? F I K.
[681]
What else? G H K and G I K. These are the 4 best
responses from player 2, anyway I have written
[694]
it here; these are the optimal strategies
for player 2.
[699]
Given this optimal strategy, what would be
the optimal strategy for player 1? If let
[703]
us say, player 1 thinks that player 2 is going
to play F H K. So, if you play C, he gets
[711]
3. If player 1 plays D, he gets 1; if he plays
E he gets 1. So, of course, his better off
[721]
by playing C. So, (C, F H K) can be unequilibrium.
And, it is also subgame perfect that although
[730]
the paths that game would follow is going
to be this, but even in this subgame this
[737]
is going to follow this path which is optimal,
and here this path. So, this is sub game perfect.
[746]
I will give you one more subgame perfect and
then request you to obtain all the subgame
[751]
perfect equilibrium of this game. What, let
us say, if player 2 playsG H K, what would
[763]
happen? If player 1 plays C, then he gets
1; if player 1 plays D, then he gets 1; and
[771]
if he plays E, then he gets 1. So, here we
have, he is indifferent between playingC,
[780]
D or E. So, all are equilibrium,(C, G H K),
(D, G H K) and (E, G H K).
[798]
Here I have written all the (C,F H K),(C,
G H K),(D, G H K),(E, G H K),and you can obtain
[806]
all other subgame perfect equilibrium. So,
I hope now, bynow you have learnt how to figure
[814]
out the subgame perfect equilibrium S P E
or S P any of a unextensive form game.
[821]
In the next module, we will start talking about
some of the application of extensive form game
[828]
Thank you.
Most Recent Videos:
You can go back to the homepage right here: Homepage