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.