0:00

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.

Â