play with a classmate
is your strategy equiprobabe ?
yes: why ?
no: what is your strategy ? how did you model your opponent ?
two players: row, column
payoffs for row column's strategies
r p s
r 0 -1 1
row's strategies p 1 0 -1
s -1 1 0
minimax value: the minimum, over all player/opponent strategy pairs, of the maximum the opponent can score
for 2-player 0-sum games (so op't score \+ player score = 0)
if each player plays a fixed strategy for the whole game, minimax value is easily computed
e.g. assume row plays equiprobable: rps each 1/3
assume col plays rps resp. probs y1 y2 y3
then expected row payoff 1/3(y2-y3) + 1/3(y1-y3) + 1/3(y2-y1) = 0
so row's minimax value is at least 0 (some other row strategy might do better)
but, by symmetry (payoff matrix is symmetric), col's expected value is 0 by playing equiprobable
so, for this game, row's minimax value is 0, and can be achieved by playing equiprobable
- assume col knows row's strategy
- then, for this row-strat, some pure col strategy is best for col
- so row wants to pick a mixed strategy that maximizes
the minimum score row gets, over all pure col strats
- so row wants to pick x1 x2 x3 to maximize
min x2 - x3, (row payoff against col strat r)
x3 - x1, (" " " " " p)
x1 - x2 (" " " " " s)
- so row wants to solve the LP
max z st
z <= x2 - x3
z <= -x1 + x3
z <= x1 - x2
x1 + x2 + x3 = 1
x1,x2,c3 >= 0
- similarly, col wants to solve an LP that turns out to be the dual of the above
- notice that the above LP has a feasible solution and z is bounded
- so the duality theorem of LP tells us that each problem has the same solution
- we have already seen that (1/3 1/3 1/3) is the primal solution
for 2-player 0-sum games, the above LP result implies that the minimax solution (assuming each player has a fixed mixed strategy for the whole game) is the only Nash equilibrium
if player's trust each other, they can cooperate and do better than the minimax value
but this combination of strategies is not a Nash equilibrium