Game Theory: Iterative Elimination of Strictly Dominated Strategies PDF

hi folks. Let's take a peek at a game now where we can begin to see whether iterative elimination of a strictly dominated strategies has any bite in, in application. And in order to do this we're going to look at an experiment that was done by Baldwin and Meese in the late 1970s and they were actual...

hi folks. Let's take a peek at a game now where we can begin to see whether iterative elimination of a strictly dominated strategies has any bite in, in application. And in order to do this we're going to look at an experiment that was done by Baldwin and Meese in the late 1970s and they were actually looking at social behavior in pigs. So, so this, the players in our game here are going to be pigs. and there's actually sort of an interesting discussion of this. This comes from Joe Harrington's book, Games, Strategies and Decision Making and it is, it, it is sort of interesting. you've got two pigs in a cage. Okay. So they're in a cage, a several meter cage. one of the pigs is larger then the other. We'll call that the dominant pig or [LAUGH] I mean, well, sorry for the terminology. So, we'll actually use the word let's say, the larger pig. and in, in, what they need to do is, is food arrives, but they need to press a lever to get the food to arrive. Okay? And the critical thing is that the lever is on one side of the cage, you go over, you press the lever. And then, the food arrives on the opposite side of the cage, okay? So the pigs are put in a cage. The cage, they, they learn eventually that if they hit this lever, food appears on the other side. So what they would have to do is if they want to eat they would have to move over, run over to one side of the cage, hit the lever, run back to the other side, get the food that comes out, eat the food a few pellets of food, then they go back hit the lever again, run back to the other side of the cage, get some food. Okay. Now, the difficult part is that there are two pigs in the cage so if we put two pigs in the same cage and one is large, then when they're both trying to the food which comes out and, and these are pigs the larger one will end up getting the food and the smaller one will get less food. Okay? So that's the basic idea here and we can analyze this as a game. so in particular, let's take a look in more detail at how the payoffs work here. So when the food comes out, there's ten units of food, ten say pellets of food that come out. And, let's look at what the typical split ends up being if there are two pigs in the cage, one is larger, one is smaller, and, if the larger one gets to the food first, then there's basically a 1,9 split. So that means that the small pig ends up with just, with one pellet, and the larger pig would end up with nine units of, of the food. so if that large one gets there first, it's very hard for the small one to get anything. They, they tend to get more on average, but no, close to nothing. if the small pig gets to the food first, then they end up with a 4,6 split. Okay? Then it's 40,60, so the, the small pig still gets less, the, the bigger pig still gets more, but the small pig at least has literally a fighting chance here. now if they get to the food at the same time, then the it's a 3,7 split, so the bigger pig gets a little more. And one other thing is that, that, you know, running over and pressing the lever actually consumes some calories, so let's take that they take it to say two units of food in terms of energy. Okay? So, so we've got these different splits and so forth. So what we can do is, is write it out a simple normal form game for that. So, given all these numbers here is the, the small pig over here, large pig over here, and now they have two choices. They can either run over and press the lever or they could sit there and sit by the food side and wait for the other pig to press the lever. Now, if you both go to press the lever, then they're, they get back to food at the same, it's going to be a 3,7 split, but it's a 3,7 split, and then you subtract off two for the cost of running back and forth, so they each loose two units of foods. So 3-2, we get the 1, 7-2 we get the 5, so we end up with 1,5 if they both do it at the same time. in a situation where say the small pig presses the lever and the big pig just waits there, then it's a 1,9 split, but the small pig ends up losing two units of energy, they actually end up with a negative, negative in that situation and so forth. So you can go through and put this into a normal form game, what we end up with is, is a simple matrix form 2x2 game, which looks like this. Okay. So we can analyze this game quite simply. Let's take it and let's analyze, analyze it via the iterative elimination of strictly dominated strategies. So what's true in this game? Well where does anyone have a strictly dominated strategy? the big pig, the large pig doesn't have a strictly dominated strategy. They would like to wait if the other one presses, they would prefer to, to press if the other one waits, so no domination here, but notice that the small pig always gets a higher payoff, four versus one, zero versus negative one, they would always prefer to wait. So, in this particular situation the small pig has a strictly dominated strategy of waiting. So we should get rid of press as a strategy for the small pig, and once, we've done that now and what's left the big pig should press. And so, what we end up with is when we iteratively eliminate strictly dominated strategies, we end up with a prediction that the small pig should wait and the big pig should be the one that presses the lever. Okay. So let's look how they actually behaved, the pigs in their, in the experiment. and so what they, they did here is they gave them 15 minutes of, of doing this they did ten tests where the pigs were alone in the cage. So the, you first, you, ten tests where the pig just sits there for 15 minutes and learns how to, to press the lever and get food. and then, they put the pigs together and do another ten tests, each for 15 minutes as well. Okay, so what they're doing here is this is the frequency of pushing the lever per 15 minutes. and we can look at what happens when the large pigs are, when, when the pigs are separated they're both alone, there we see roughly the large pigs going about 75 times per 15 minutes and pressing the lever. I mean these pigs are really moving back and forth to get the food. The small pig say 70 times running back and forth to get the, the, this, the food. so they're, they're both, if they're left alone, they go, they press the lever, they run back and forth. if they're together, then what happens? well, the prediction was the larger pig should do the pressing, right? They should do the pressing and the smaller pig should do the waiting and indeed how frequently do they push the lever? And the small pig is very seldomly, only five times now whereas the large pigs are doing it about 105 times. So indeed, we are see the, seen them pressing and waiting in conjuction and, as predicted by the theory. And in fact the, the large pigs are, are doing more pressing, and partly possibly because, they're getting fewer pellets out since the small pig is sitting there by and, and eating some of the pellets that the large pig is producing by pressing the levers. Okay. So what did we learn from this? Are pigs rational? do they, do they know game theory? well, they, they probably didn't sit down and solve the, the normal form game and iteratively eliminated strictly dominated strategies. and, and, and I think that iterative elimination of, of strictly dominated strategies is something which nice, nicely captures learning. So you learn not to play a strictly dominated strategy, right? Because it's always giving you a lower payoff, eventually, discard such strategies, so players won't be sitting there playing a strictly dominated strategy if they ever have some experience with other strategies. once, once they stop playing those, then you learn not to play strictly dominated strategies out of what remains. So the small pig can learn that it just doesn't pay to run over and press the lever because the big pig gets everything. So they stop pressing the lever, they just sit there and wait, and eventually, the big pig does the pressing. So, you learn not to play strictly dominated strategies out of what remains. And, and so the idea here is that learning evolution survival of the fittest, these are powerful game theoretic tools. And iterative elimination of strictly, strictly dominated strategies in games where, where there is some power to these things ends up you know, making some predictions, which can be quite powerful.