Game Theory Iterative Removal PDF

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...

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 up better If the 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 nash equilibria 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.