4Non-cooperative games
IB Optimisation
4.2 The minimax theorem
There is a special type of game known as a zero sum game.
Definition (Zero-sum game). A bimatrix game is a zero-sum game, or matrix
game, if q
ij
= −p
ij
for all i, j, i.e. the total payoff is always 0.
To specify a matrix game, we only need one matrix, not two, since the matrix
of the other player is simply the negative of the matrix of the first.
Example.
The rock-paper-scissors games as specified in the beginning example
is a zero-sum game.
Theorem (von Neumann, 1928). If P ∈ R
m×n
. Then
max
x∈X
min
y∈Y
p(x, y) = min
y∈Y
max
x∈X
p(x, y).
Note that this is equivalent to
max
x∈X
min
y∈Y
p(x, y) = − max
y∈Y
min
x∈X
−p(x, y).
The left hand side is the worst payoff the row player can get if he employs the
minimax strategy. The right hand side is the worst payoff the column player
can get if he uses his minimax strategy.
The theorem then says that if both players employ the minimax strategy,
then this is an equilibrium.
Proof.
Recall that the optimal value of
max min p
(
x, y
) is a solution to the linear
program
maximize v such that
m
X
i=1
x
i
p
ij
≥ v for all j = 1, · · · , n
m
X
i=1
x
i
= 1
x ≥ 0
Adding slack variable z ∈ R
n
with z ≥ 0, we obtain the Lagrangian
L(v, x, z, w, y) = v +
n
X
j=1
y
j
m
X
i=1
x
i
p
ij
− z
j
− v
!
− w
m
X
i=1
x
i
− 1
!
,
where w ∈ R and y ∈ R
n
are Lagrange multipliers. This is equal to
1 −
n
X
j=1
y
j
v +
m
X
i=1
n
X
j=1
p
ij
y
j
− w
x
i
−
n
X
j=1
y
j
z
j
+ w.
This has finite minimum for all
v ∈ R, x ≥
0 iff
P
y
i
= 1,
P
p
ij
y
j
≤ w
for all
i
,
and y ≥ 0. The dual is therefore
minimize w subject to
n
X
j=1
p
ij
y
j
≤ w for all i
n
X
j=1
y
j
= 1
y ≥ 0
This corresponds to the column player choosing a strategy (
y
i
) such that the
expected payoff is bounded above by w.
The optimum value of the dual is
min
y∈Y
max
x∈X
p
(
x, y
). So the result follows from
strong duality.
Definition (Value). The value of the matrix game with payoff matrix P is
v = max
x∈X
min
y∈Y
p(x, y) = min
y∈Y
max
x∈X
p(x, y).
In general, the equilibrium are given by
Theorem.
(
x, y
)
∈ X × Y
is an equilibrium of the matrix game with payoff
matrix P if and only if
min
y
0
∈Y
p(x, y
0
) = max
x
0
∈X
min
y
0
∈Y
p(x
0
, y
0
)
max
x
0
∈X
p(x
0
, y) = min
y
0
∈Y
max
x
0
∈X
p(x
0
, u
0
)
i.e. the x, y are optimizers for the max min and min max functions.
Proof is in the second example sheet.