We will now consider the special case where one or both players has only two strategies. We will develop a graphical way of solving such games.

We begin with the case where player 1 has only two strategies, so that the game is given by a matrix \[A=\left(\begin{array}{rrrr} a_{11} & a_{12}&\cdots & a_{1q}\\ a_{21} & a_{22}&\cdots & a_{2q}\end{array}\right).\]

We should first check whether there is a pure Nash equilibrium, as the method we are going to describe may fail in that case. (Recall that this is easy to check directly from the matrix.)

Now suppose that there is no pure Nash equilibrium, and let player 1 use the mixed strategy \(\underline{x}=(x,1-x)\) for some \(0<x<1\). If player 2 chooses strategy \(j\) then the expected payoff to player 1 is \[\mathbb E_1(\underline{x},j)=x a_{1j}+(1-x)a_{2j}.\] If we plot a graph of \(y=\mathbb E_1(\underline{x},j)\) against \(x\) then the above is just the equation of a straight line through the points \((0,a_{2j})\) and \((1,a_{1j})\). We do this for each column \(j\) and consider

Definition 3.12

The lower envelope \[f(x)=\min_{1\leq j\leq q}\left(x a_{1j}+(1-x)a_{2j}\right).\] Then we define \(x^*\) to be the point where the maximum of \(f\) is achieved.

Example 3.13

Suppose that the various lines are as shown.

Example completed by hand in the lecture

We highlight the lower envelope and \(x^*\). For each point \(x\) between \(0\) and \(1\), if player 1 plays strategy \((x,1-x)\) then player 2 will play on the line \(\mathbb E_1(\underline{x},j)\) which givest the lowest value for that \(x\). Thus player 2 will always choose a strategy such that the value for player 1 lies on the lower envelope. Therefore player 1’s best choice is \(x^*\).

Further, when player 1 plays at \(x^*\), player 2 will use a mixed strategy involving the strategies labelled by lines intersecting with the lower envelope at \(x^*\). So we can eliminate the other columns and solve for the optimal strategy for player 2 in this simpler game (typically just \(2\times 2\)).

A similar method works if player 2 only has two strategies. If player 2 uses strategy \(\underline{y}=(y,1-y)\) then player 2 wants to minimise the quantity given by the upper envelope \[f(x)=\max_{1\leq i\leq p}\mathbb E_1(i,\underline{y})= \max_{1\leq i\leq p}\left(y a_{i1}+(1-y)a_{i2})\right).\]

Example 3.14

Consider the game

Strategy 1 Strategy 2 Strategy 3
Strategy 1 \(1\) \(-1\) \(3\)
Strategy 2 \(3\) \(5\) \(-3\)

Example completed by hand in the lecture

Example 3.15

Consider the game

Strategy 1 Strategy 2
Strategy 1 \(-1\) \(2\)
Strategy 2 \(3\) \(-4\)
Strategy 3 \(-5\) \(6\)
Strategy 4 \(7\) \(-8\)

Example completed by hand in the lecture

To conclude our survey of zero sum games, we consider the general case.

Linear programming* is a classical branch of optimisation theory — you may have come across it in one of your other modules — and deals with systems of linear inequalities.

One of the most famous methods in linear programming is the simplex algorithm which is widely used to optimize problems involving systems of inequalities.

A general zero sum game can be turned into such a problem, and hence can be solved using the simplex algorithm.