Hi, I'm William Spaniel. Let's learn some game theory! Today's topic is the iterated elimination
of strictly dominated strategies. I cover this in lesson 1.2
of 'Game Theory 101: the complete textbook'.
Check the video description for more information about that. So,
remember in the last video, we looked at the Prisoner's Dilemma
and the solution to this game was for both the players to confess, and the
reason for that is 'Confess'- strictly dominated 'Keep Quiet'. 'Keep Quiet' was a
strictly dominated strategy; it was never in the player's best interest to
individually 'Keep Quiet'. 'Confess' always produced a better outcome than 'Keep Quiet'.
We saw that because,
for example,... if Player 2 were to 'Keep quiet', then Player 1 should 'Confess',
because 0 is greater than -1, and
if Player 2 were to 'Confess', then Player 1 will still want to 'Confess', because -8
is better than
-12.
Now, in most games it's not going to be the case that one strategy is always better
for each player, it's going to be
the case that the other players might wanna change their
strategies based off of what the other guy is doing
and so, if that's the case then you can't just easily agree to a solution, where one
player is always going to play 'Confess', and it doesn't matter what's going on the other
player's side; the other player's always going to also want to play 'Confess', because its always in
her best interest as well.
That's usually not the case. And so, how do we go about solving games when that's not the case?
Well, here's an example of how we can do that.
We're going to use something called 'Iterated Elimination of Strictly Dominated Strategies'.
This is a much more complicated game than what we saw in the Prisoner's Dilemma.
Each player has three strategies. Player 1 has 'Up', 'Middle', 'Down', Player 2 has 'Left', 'Centre', 'Right'
and that leads to 9 different outcomes. Now I want you to notice something about Player 1's
strategies here. If Player 2 were to go left, then Player 1's best strategy
is to play 'Up', because 13 is greater than 4 or -1. But, if
Player 2 were to play 'Center', then
then Player 1 should wanna play 'Middle', because 3 is greater than 1 or 2. And if,
Player 2 were to play 'Right', then Player One would
want to play 'Down', because 8 is better than 7 or 6. So, based off of
what Player 2 is doing, Player 1 has a better
or different best response, given what Player 2 is doing.
Player 1 is always wanting to change his strategy based off of what Player 2 is going to do.
And so, again, if we only looked at the Prinsoner's Dilemma before
and we didn't have any other tools to work with, we would be sorta "screwed" here
'cause we wouldn't know what Player 1 would want to do in this situation
However, we can get around this, if we're really clever about how we go about
solving this game. So instead of looking at Player 1, let's instead look at
Player 2's strategies.
For instance, let's start here:
Would Player 2 ever want to play 'Right'? The answer is no. That's because 'Center'
strictly dominates 'Right'; 'Right' is always worse for Player 2 than
'Center'.. because 'Center' is always producing a greater
payoff for her. Why is that? Well this 4 is greater than this 3, if Player 1
were to go 'Up'.
if player one were to go 'Middle', then 3 is greater than 2 and if
Player 1 were to go 'Down', 8 is greater than -1. So regardless of what
Player 1 does, Player 2
should never want to play 'Right', because 'Right' is always worse than 'Center'.
So, when Player 2 is thinking about what to do in this game, she should just
not think about 'Right'; she should essentially ignore it
and instead of thinking about this bigger game, she should just be thinking about the smaller
game, where she only has two strategies.
Now, Player 1 should be
able to understand that Player 2 is super smart and be able to respond to that
accordingly. So,
if Player 1 knows that Player 2 is super smart, then Player 1 is going to infer that
that Player 2 will never play 'Right', and that has an interesting implication for him.
So if Player 2 is never going to play 'Right',
should Player 1 ever play 'Down'?
The answer is no. Why is that? Because 'Middle' strictly dominates 'Down'.
This 4 is greater than -1, if Player 2 were to go 'Left'
and if Player 2 were to go 'Center' then this 3 is greater than this 2.
So regardless of whether Player 2 plays 'Left' or 'Center', the only two reasonable
strategies for her because 'Right' again is not reasonable, then
then that means Player 1 should never want to play 'Down', which means
instead of looking at this game, we should be looking at the smaller game.
Okay. So based
off the fact that Player 2 is super intelligent and wouldn't play 'Right',
and Player 1 knows Player 2 is super intelligent and wouldn't want to play 'Right', that means
he wouldn't want to play 'Down'.
Then that means Player 2 can now infer that Player 1 would never play 'Down',
which means she can look at her strategies between 'Left' and 'Center', and decide
that, well,
"I would never want to play 'Left' if I were Player 2". Why is that the case? Well,
if Player 1 were to play 'Up', then 'Center' is better than 'Left'; 4 is greater than 3.
And if Player 1 were to play 'Middle', then 'Center' again is better than 'Left'.
and so that's because 3 is greater than 1. And so, this 'Left' strategy now,
is no longer sensible for Player 2; its only 'Center' which is sensible for her.
herself
So that means, we know she is going to play 'Center'.
and if that's the case, if Player 1 knows that Player 2's super smart and won't
play 'Right', and that causes him to never play 'Down', which means she
infers that he's never going to play 'Down',
which means she's never going to play 'Left', which leaves her just playing
'Center'. That means this is just a simple optimization problem for Player 1,
where now Player 1 is left between choosing 'Middle' or 'Up', and 3 is greater than 1,
So that means he's going to play 'Middle' and not 'Up'. And that leaves us
with the solution here, of 'Middle-Center', and they're going to get 3 points a piece
in this game. And the reason we did that, again, is because the players were
inferring a lot about each other. They were
inferring their intelligence, inferring that they wouldn't play particular
strategies based off of that, and
that allowed us to go through the cycle where we started at
'Right', then eliminating 'Right', and then eliminating 'Down', and then eliminating 'Left', and then
eliminating 'Up'. And that eventually takes us to 'Middle' and 'Center'.
So, we call this process
'Iterated Elimination of Strictly Dominated Strategies'. That's why this
IESDS
is here, that's the abbreviation of 'Iterated Elimination of Strictly Dominated Strategies'
It gets that name because we went through a bunch of strictly-dominated strategies.
First 'Right' was dominated, then 'Down' was strictly-dominated, then 'Left' was strictly-dominated,
and then 'Up' was strictly-dominated, once we're eliminating these
strategies. Hence the name 'Iterated Elimination of Strictly Dominated Strategies.
Really a straight forward name there, once you understand what we're doing.
Now, going forward
if you ever see a 'strictly-dominated strategy', you should eliminate it immediately.
That means if you see any sort of game, whether it's a simpler game, like a 2x2
game, or a much larger game like a 3x3 game, or even something like,
a 6x6 game. If you ever see a strictly-dominated strategy,
eliminate it immediately.
Now, a couple of quick points about this. What do I mean by eliminating it immediately?
You know you could be in a situation, where you see multiple strategies that are strictly dominated
at the same time
and as it turns out, the order doesn't matter here. So you might be wondering whether you should
eliminate strategy No.1 first? or strategy No.2 first? And as it turns out, it doesn't matter
if you eliminate either strategy, it's going to be the
case of the other one is strictly dominated afterward. And so,
if IESDS is going to lead you to a single outcome like it did in this game,
the solution, if you will, where we
know that the players are going to play 'Middle-Center'. It really doesn't matter if you
eliminate one strategy first, or the other strategy first. You'll still arrive
at that one single outcome. And that's why 'Iterated Elimination of Strictly Dominated Strategies'
is really, really useful. Now,
unfortunately, again, most games will not be able to solve
using IESDS. Most games don't have
dominated strategies like this
and so, if you are in a situation like that, you might be
wondering, "Well, how on Earth are we going to solve that game?!" And we'll tackle that
subject in the next video,
when we talk about the 'Stag Hunt' and the 'Pure Strategy - Nash Equilibrium'.
Join me in the next video.