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.