0:00

All right, folks it's Matt again. So we've been looking at nash equilibrium

Â and understanding play and, and setting where we make those kind of predictions.

Â and we've also been looking a little bit at dominance relations and, and now lets

Â talk about strictly dominated strategies and, and removal of those.

Â Which is another way to analyze a game. So when you're talking about game theory,

Â there's many different ways that people can think about

Â analyzing games in terms of stability, in terms of predicting.

Â What people are going to do, what logic can be applied and, this is, is, is

Â another important way of looking at games and may give us some insights.

Â So the idea of, when we start thinking about rationality in game theory, the

Â basic premise here has been, that players maximize their payoffs.

Â So they're basically trying to maximize their payoffs.

Â And again it doesn't necessarily mean that they're just greedy.

Â Payoffs could be that they, you know, that they are altruistic.

Â Public minded etcetera. But the, the, the premise here is that

Â there's something, some objective function that people have, and they tend

Â do things that'll give them higher pay offs rather than lower pay offs.

Â Okay. So in terms of iteration on this logic,

Â what we're going to be thinking about is what if all players know that others

Â maximize their pay offs, and we have an idea of, of what the structure of the

Â game is. Then what does that mean for the game?

Â Can, can we make, deduce something about what should be played in the game? And

Â what if all players know that all players know that, that players are rational in

Â this sense? so you can, you know, take this what if I know that you know that I

Â know, and, and so forth. You can take this ad, ad absurbum but

Â it's an important concept in, in understanding what it.

Â Yields give us some insight into games and gives us some predictability.

Â now, you know? Going through very, very high levels of this are, are

Â questionable. But nonetheless, the logic here and, the

Â predictions that are made will give us some understanding of games that we can

Â use, in analyzing equilibrium and doing other things with it.

Â So, you know, we can take this, logic, fully to a, to its full logic.

Â [INAUDIBLE] conclusion. Okay,

Â so in terms of strictly dominated strategies.

Â That means a strategy which, which is, Al-, there's some other strategy which

Â always does better than it. it can never be a best reply.

Â So, so we'll make that clear in a second. so, basically, that means, that, that if

Â this is a strategy that, that never does well.

Â There's something which does always better than this.

Â Against any strategy, of, of the other players.

Â Then basically it's never going to be played.

Â So this, this is essentially a strategy we can just, safely ignore if we think

Â players are rational. They should never play a strictly

Â dominated strategy. there's something else which does better

Â in all circumstances for them. So, we remove those from the game.

Â And the idea of iteration is we take those out, now we've got a simpler game.

Â Now let's do the same thing, right? So there might be something which is now

Â strictly dominated in this thing. So, a player should never player this

Â once we get to this reduced game. And, then we take those out and we get an

Â even further reduced game and so forth. And we just keep iterating on that that.

Â It leaves us with some prediction and then we think that the only thing that's

Â logical if there's rational players and they understand that other Players are

Â rational and so forth. They're going to be left inside that sub

Â par game. Okay, so, the running this process to its

Â termination is called the iterated, iterated removal of strictly dominated

Â strategies. So in terms of formal notation what, what

Â are we seeing here? A strategy A sub I for some player I is strictly dominated

Â by some other strategy of the same player, A prime I if if what's true.

Â The, the pay off that the person gets. From playing ai, the one that is strictly

Â dominated is worse strictly lower, 'kay? And it's important that this is as strict

Â in equality than the pay off that they would get by playing a prime, no matter

Â what the other players do. So, this is a for all sign for every

Â possible strategy of the other players. No matter what they do.

Â This one, ai is worse than the payoff for ai prime.

Â OK? So, no, there's no circumstance in which you can do as well.

Â It always does strictly worse. That means it's a, it's a strategy where

Â you're just strictly better off playing a prime i.

Â That's the concept of strict [INAUDIBLE]. Okay, so let's have a, a, an idea now of

Â iterative, iterated removal of strictly dominated strategies.

Â So, here's a game, a three by three game. it's got a bunch of different payoffs in

Â it. We look at it.

Â We begin to think, okay let's, suppose you want to find the, the Nash

Â equilibrium. [UNKNOWN] of this game, well it, it gets

Â a little complicated because you have to, you, if you're thinking about mixed

Â strategies or pure, and you, you have to consider all the possible combinations.

Â One thing we can begin to do is look for strictly dominated strategies, and just

Â get rid of those. So for instance in this game, what's

Â true, if we look at this game, we notice that R is strictly dominated by C.

Â Right. So the, the column player gets a strictly

Â lower payoff in every one of these entries than they get in every one of

Â these entries. So you would be strictly better playing C

Â than R no matter what the other player does.

Â Whether the other player goes up, middle or down.

Â Center always does better than, than R or even if the other player mixed.

Â So, whatever the other player does, you get a strictly higher pay off from the

Â center than R so we should just get rid of R altogether.

Â And now we have a simpler game. Right? So the idea is boom, we get rid of

Â R altogether and now we've got a simpler game.

Â Okay, so let's iterate on that logic.

Â So now, there's no domina-, strict domination, any longer.

Â Between, for the, for the column player. Because the column player's actually

Â indifferent between left and center if the other player plays middle.

Â But one thing we do notice here, is that the middle strategy.

Â Of the, role-player is now dominated, right? So, the middle strategy does

Â strictly worse than the up strategy for the role-player, right? So, 3 is better

Â than 1, 2 is better than 1. No matter what happens, you're better off

Â playing up than middle. So M is strictly dominated by U.

Â In this case we can get rid of M together.

Â That collapsed the game further. So now we're iterating, we've got a

Â simpler game. Now, we see that, in this case now and

Â once we've done this removal, now C is dominated by L, right? So, the column

Â player would always get better playing L in this game, than

Â Sorry, would always be better off playing C than L in this game.So this, the payoff

Â is always higher playing C than playing L.

Â So, L is strictly dominated by C, we can get rid of L.

Â Simplify the game further. You can see where this is going.

Â Boom, we're down to a very simple game, now the, if this is the game that's left

Â the row player is better off playing down than up.

Â Boom, so what do we end up with. We end up with, down and center being the

Â only things that are left once we've done this full iteration.

Â So we started with a fairly complicated game We end up making a very simple

Â prediction that the only thing that is left after iteratively eliminating

Â strictly dominated strategies, is down for the role player, center for the

Â column player that leads to a pay off of 4 and 2 for the 2 players, okay.

Â So in fact. Giving that a player, if we're looking

Â for a nash equilibrium, there things have to be best replies we know they could

Â never be playing a strictly dominated strategies.

Â So we can rule those out. They can't actually be playing.

Â You can convince yourself they can't be playing something that's strictly

Â dominated and what's remaining and so forth.

Â So, the fact that we ended up with a unique prediction here.

Â actually tells us that this game has a unique Nash equilibrium and the only Nash

Â equilibrium is for players to play down and center, So, it actually, in this case

Â identifies a unique predicted play which coincides with the only Nash equilibrium

Â of this game. Okay,

Â so we've got the unique Nash equilibrium d c so that, that worked very well in

Â that game. Let's take a look at another game.

Â I would slightly change the payoffs of this matrix.

Â Let's try again. in this case you know r is still

Â dominated so in this case r always leads to 0 for the column player center, left

Â or center give higher payoffs. So, in this case r is dominated by either

Â l or c. We can get rid of r and then we, we can

Â go through again. Now, in this particular situation,

Â there's something that's interesting. So, now the, the column players in

Â different between the two. But when we looking at the row player, we

Â notice that the row player. doesn't have any pure strategy domination

Â relationships. So, you know, the, the player gets 3

Â here, 4 here, compared to 0 0, so neither of these strictly dominate the other.

Â they get 1 always by playing middle so, in this case they sometimes do better

Â than down If they're playing middle sometimes do better than up if they're

Â playing middle, so there's not strict domination when we're looking just at

Â pure strategies. but if players are willing to randomize,

Â one thing to notice in this game is that let's suppose that you played 1/2 on up

Â and 1/2 on down. What would your expected payoff be? So if

Â the other player went left and you're playing half, up half down, you get a

Â path of 1.5. If you were doing this and the other

Â player was playing C, you would get a half of 0 and a half of 4, you would get

Â 2. So there is, when we look at playing a

Â half, half then What would we end up with if we allow for that mixture.

Â Right? We put in a mixture. We would end up having

Â oops. How'd that happen.

Â we would end up with 1.51 and a 2, 1. So, we end up here.

Â With something which strictly dominates middle.

Â So playing a half on up and a half on down gives the role player a strictly

Â higher pay off than they would get by playing middle.

Â So in this case M is dominated by the mixed strategy that selects U and D with

Â equal probability. So in this case we can still get rid of

Â M. so in net, we're, we're down to a reduced

Â game. now this game doesn't really reduce any

Â further, the column players indifferent, the role player likes a better

Â [INAUDIBLE]. Column player goes left, it likes down

Â better, if the column player goes right so what's going to happen in this game

Â now you'd have to take, further analysis. And actually if you want to go through

Â and solve for the nash equilibria this game, there's a lot of them, right.

Â So there's in fact an infinite number of nash equilibria, given that the, column

Â player's fully indifferent in this game. So you can go through and analyze all the

Â [UNKNOWN] if you want. But the iterative elimination of strictly

Â dominated strategy still gave us a lot of predictive power in the sense that it

Â collapsed the game down to a much simpler game and then it's much easier to analyze

Â what's left. ok, so, iterative, removal of strictly

Â dominated strategies. one nice thing about this is it preserves

Â Nash equilibria. So, you can use it if, even if you're

Â just wanting to, to analyze Nash equilibria.

Â You can use it as sort of a preprocessing step, right? So before you try and

Â compute Nash Equilibria, get rid of all the strictly dominated strategies, and

Â iterate on that. Some games like the first one we looked

Â at tend to be solvable with this technique.

Â That's called dominant solvability. If it, if it actually collapses to a

Â single point, you were able to solve that game just by using dominance arguments.

Â some games won't be, but it still could be useful to, to, to analyze these

Â things. what about the order of, removal? So, you

Â know, I, we, we did things in a very particular order, so just noticing that

Â the, the calm player had one, you know, the, the, the, right play was, was

Â strictly dominated and so forth. What if we started with the, with a, a

Â different player, or, would it would it make a difference? if we're dealing with

Â strictly dominated strategies, then order doesn't matter.

Â So no matter how you do this, whatever order you do it in, you'll end up with

Â the same solution. you can spend some time trying to

Â convince yourself of that. Think carefully about it, So that's

Â something that can, you'd have to prove. but in, in fact order does not matter in

Â eliminating strictly dominated strategies.

Â So the logic is, is very tight in that respect.

Â there's another type of domination which also makes some intuitive sense and

Â people use in games. And that's to weaken the domination

Â relationship and instead of, of strict domination we can consider weekly

Â dominated strategies. What's the idea of weekly domination?

Â it's very similar to what we had before. But instead of having the strict

Â inequality hold everywhere, right? So instead of having this hold for all A

Â minus I, it just has to hold some, sometimes, and you just need to weaken

Â equality for all strategies of the others.

Â So the idea of a, of a weekly dominated strategy.

Â Is that it always does A prime always does at least as well as A and sometime

Â strictly better. So you, this is still a strategy, you

Â could say, okay A prime's really a [INAUDIBLE] Dominates a because it always

Â does at least well, and sometimes strictly as well so if I'm uncertain at

Â all, I might as well go with the one which always does as well and sometimes

Â does strictly better. So weekly dominated strategies can be

Â eliminated as well. You can go through, you can iterate, you

Â know, just go through games exactly like we did before, same kind of thing.

Â but, one thing that's true about weekly dominated strategies, is that sometimes

Â they could be best replies, right, so, a strategy could be weekly dominated, and

Â still turn out to be a best reply. Reply how could that happen let's suppose

Â for instance we look at a very simple game where the role player can go up or

Â down. If they go up they get a path of one

Â against left and right of the column player and you know here they get two

Â here they get three. So, this would be a situation where down

Â weekly dominates up, right, you always get this high a payoff, and sometimes

Â strictly higher. but none the less, it could be for

Â instance that if left is the is, is the strategy that's actually chosen by the

Â calm player Then upper still best reply, right.

Â So for instance, if we put in payoffs here of, of 1 1, so the column player is

Â exactly indifferent between these, these 2 strategies.Then this is actually a Nash

Â Equilibrium. And so eliminating that, actually

Â eliminates one of the Nash equilibri of the game, right? So depending on what

Â those pay offs are, we could end up eliminating the Nash equilibrium of the

Â game. And you know so this is, is a situation

Â where you know, the...uh, we end up eliminating something which could be part

Â of the equilibrium what is true is at least 1 equilibrium is always preserved.

Â what's unfortunate is that the order of removal can matter.

Â So which order you remove things in can begin to, to matter.

Â there are some games which is useful to using, so for instance if you remember

Â the Keynes Beauty contest game that we talked about earlier where people were

Â naming injured between zero and a hundred think about trying to solve that

Â iterative elimination of Weekly Dominated Strategies.

Â What do you end up with so it can still be a useful logic and that logic can help

Â you in analyzing some games but you do have to it is not as tight as [UNKNOWN]

Â domination because there are situations where you might want to play a weekly

Â dominated strategy. If you are sure, that the other player,

Â was, was going to, you know, go in a certain direction.

Â So for instance here if we put in two, one then then if we eliminate the column

Â players dominated strat, weekly dominated strategy first, right, so they.

Â Left weekly dominates right, we get rid of right, then what are we left with,

Â we're left with a situation where the column then, I'm sorry the row player is

Â indifferent between the 2 strategies right, so if we, sort of say okay look,

Â this left dominates right so we get rid of this.

Â Then we end up with a situation where up and left is still left.

Â But if we removed, the row player's things first, we would remove, up first,

Â and then, we would end up with down left. So, so, depending on, on how you go

Â through this. You get different, different things that

Â are left. so there are, are things that, you know,

Â where the order matters and that's somewhat problematic.

Â Okay, iterative strict and rationality, players maximize their payoffs.

Â They don't play strictly dominated strategies, they don't play strictly

Â dominated strategies given what remains. we iterate on that, nash equilibria Our

Â subset of what remains, so it's a nice, simple solution concept that helps us, us

Â throw things out of the game and simplify what we're looking at.

Â We can also ask whether or not we see such behavior in reality.

Â Do people really act in ways that are consistent with eliminating strictly

Â dominated strategies and more over iterating on that process.

Â