Game Theory 4 PDF

We will now speak about Maxmin strategies. These make particular sense in the context of zero sum games, but actually are particular quite to all games. What is a Maxmin strategy? It simply puts a players strategy that maximizes their payout assuming the Other player is out to get them. We will we w...

We will now speak about Maxmin strategies. These make particular sense in the context of zero sum games, but actually are particular quite to all games. What is a Maxmin strategy? It simply puts a players strategy that maximizes their payout assuming the Other player is out to get them. We will we will concentrate primarily on the 2 player, case here, again because, when we get to some games they really only make sense with the case of 2 players. but keep in mind 1 could define this more generally, when we speak about maxmin strategy. So, the maxmin strategy, is a strategy that maximizes my worse case outcome. And, my maxmin value, or safety level, is, that payoff, that's guaranteed by the, maxmin strategy. And, here it is defined, formally. The maxmin strategy for player i, is the strategy. Is one that maximes the minimum that the other player, remember the -i is the player other than i, would hold player 1 down 2. And the maximum value is defined similarly to be the value, of that maxmin strategy. Now, why, why would we want to think about the maxmin strategy? one can think of it either, as a, simply, sort of a certain cautionary, maybe, the other people will make the mistake and not act in their best interest. maybe, I'm not sure exactly what their payoffs are. There are a lot of interpretations. Or you can simply be, Paranoid about about, about them and think that they out to get you. And you know the, know the saying, you know even be paranoid of enemies. That's a max min strategy. And, just to confuse things, we'll also speak about the minmax strategy. The minmax strategy is strategy against if you wish the other player in a two player game is the strategy that minimizes their payoff, on the assumption that they're trying to maximize it. And so here is the formal definition. The minmax strategy for player i is playing against the other guy, we'll pre-known by -i is, the strategy that minimizes, the maximum payoff as attempted by the other guy. Of the payoff to the other guy. And the minmax value is simply the value of that minmax strategy, the value to player 1. Now, why why would player one want to want to harm, harm the other guy? Well you could, he could just be out to get him. That, that's a possibility, or they could be playing a zero-sum game. And in a zero-sum game hurting the other guy is tantamount to improving your own your own payoff. And so in the setting of zero-sum games, maxmin and minmax strategies make a lot of sense, and in fact, in a very famous theory due to Jean von Neumann it proved that, in a zero-sum game, by definition you consider only two player, such games, any Nash Equilibrium, the player sees a payoff that's is equal to both his maxmin value and his minmax value. And that means that so we'll call that the value of the game. The value for player one's called the value of the game, and that means that the, the set of maxmin strategies are really the same as set of the minmax strategies. That is, trying to improve your worse case situation is the same as trying to minimize the other guys best course, case situation. And any maxmin strategy profile or minmax strategy profile, because they're the same constitutes a Nash Equilibrium. And furthermore, those, all the Nash equilibria that exists. And so the payoff for all nash equilibria is the same may be the value of the game. One way to get a concrete feel for it graphically, and here is the game of matching pennies. This is a game where you, each of us chooses heads and tails, not probability, and if we if it comes up either if we both, if, if, if the result of my randomization I end up choosing But if we both chose a head or both chose tails I win. And so here are the payoffs you see here the strategy spaces. this is player 2 is kind of increasing the probability of playing heads and this is. Player one and let this dimension you have the value of the game PF 2, player one and the only natural equilibrium is for both to itemize fifty fifty, it's right clear if you conveniently look by slicing. the the the 3 dimension look, structure this way. And you sort of see that, it, it, it's gotta be in equilibrium in the sense that player, player 1 could be moving along this this curve but if he does it his payoffs would only drop. And so he's trying to maximize the he wouldn't do it. And conversely, player two can only traverse around, along this But if he does that, the payoffs would only increase, and he's trying to minimize the value so so you get a stable point, which is, which for, obvious reasons is called a saddle point. In general, we can use the minmax theorom, to compute, the equilibria of zero-sum game, and we do it by simply laying out a linear program that captures the game. And here it is. So, u1* is going to be the value of the game. That is the payoff to player 1 in equilibrium. And so, we're going to specify from player's two point of view. We could have done it the other way around also. So what player two is saying, is simply, says for each of the actions of player one, each action that player one Might consider. I want to find a mixed strategy s2, so here's my mixed strategy s2. It will look at all my 2 strategies k and make sure that, that probability, this probability distribution over the sum, the sum to 1 and they're not negative. So what I'd like to do, is that the best response to my strategy by player one for any of these actions will never exceed this value of the game, because I am trying to minimize it. So I am going to find the lowest u that has a property that player 1 doesn't have a preferable deviation by any of his, of his of his pure strategies. So when I look at the payoff For player 2. When I play, A2K, and he plays A1J. That would, that J that I'm considering right now. And I multiply the probability of, in my mixed strategy playing, A2K. I don't want that player one, to have a profile deviation so its got to be that expected pay off will be no greater than the value you want to start so clearly this is a correct formulation of the game and it is a linear program as we know linear programs are efficiently solvable. In theory by a interior method that is provably polyomial in practice by procedures that are worst case exponential, but in practice work well.