Two-person Zero-sum Games

Suppose two players are playing a game
Player1 chooses index and Player2 chooses index .
Then Player1 gets payoff while Player2 gets payoff .
We want to find a distribution of choices for Player1 which gives:

the largest possible
(where is the expected payoff for Player1 given that Player2 plays ).

Introduce and reframe this into a Linear Program:
” Maximise subject to , , . ”

The Lagrangian is

Now so and so .
Also , so
i.e. is a distribution.
Now the dual problem is:
” Minimize subject to , and . ”
Note that this is exactly the problem of finding the optimal strategy for Player2.

Suppose we have optimal strategies and .
Complimentary Slackness for gives:

Also in an optimal strategy (by Strong Duality).
Hence, we arrive at the following theorem:

Theorem

Suppose and are strategies for Player1 and Player2 respectively,
and is a value satisfying:

• primal feasible
• dual feasible
• Complimentary Slackness
  Then these are all optimal, and is the value of the problem.

Proof

See Lemma.

Sidenote

If strategies and are optimal
(where and are standard basis vectors),
then is called the saddle point of the matrix.