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 Dual problem in linear programs > Lemma.

Sidenote

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