Games as Linear Programming Problems (AQA A-Level Further Maths): Revision Notes

Calculating Expected Payoff with Mixed Strategies

Suppose player A plays strategy A₁ with probability $p$ and strategy A₂ with probability $(1-p)$, while player B plays strategy B₁.

The expected payoff is: $E = (-3) \times p + 3 \times (1-p) = -3p + 3 - 3p = 3 - 6p$

Similarly, if player B plays strategy B₂:

The expected payoff is: $E = 5 \times p + (-1) \times (1-p) = 5p - 1 + p = 6p - 1$

The value of the game, $v$, cannot be more than either expected payoff, so: $v \leq 3 - 6p \quad \text{and} \quad v \leq 6p - 1$

Worked Example: Solving a 3×2 Zero-Sum Game Using the Simplex Method

Problem: Use the simplex method to solve this zero-sum game and find the optimal strategy for players A and B, and the value of the game.

Solution:

Step 1: Add 2 to each entry to make all entries non-negative.

Step 2: Let A play A₁, A₂, and A₃ with probabilities $p_1$, $p_2$, and $p_3$.

The linear programming formulation is:

Maximise

$P = v$

subject to

$v \le 2p_1 + p_2$

$v \le p_1 + 2p_2 + 3p_3$

$p_1 + p_2 + p_3 \le 1$

$v,\; p_1,\; p_2,\; p_3 \ge 0$

Step 3: Introduce slack variables and set up the initial tableau:

$P - v = 0$ $v - 3p_1 - 2p_2 - p_3 + s = 0$ $v - p_2 - 2p_3 + t = 0$ $p_1 + p_2 + p_3 + u = 1$

The initial simplex tableau is:

Step 4: Apply simplex algorithm (selecting pivot elements highlighted in yellow):

After multiple row operations (R5=R1+R6, R6=R2, R7=R3-R6, R8=R4, R9=R5+R11×3, R10=R6+R11×3, R11=R7/3, R12=R8-R11), the final tableau gives:

Solution: $v = 1.5$ when $p_1 = \frac{1}{4}$, $p_2 = 0$, $p_3 = \frac{3}{4}$

Step 5: Subtract the 2 we added initially:

$\text{Value of original game} = 1.5 - 2 = -0.5$

Optimal strategy for A: Play A₁ with probability 0.25 (or $\frac{1}{4}$) and A₃ with probability 0.75 (or $\frac{3}{4}$). Never play A₂.

For player B: The value of the game to B is 0.5. Suppose B plays B₁ and B₂ with probabilities $q_1$ and $q_2$.

If A plays A₁, B's expected payoff is: $-q_1 + 2q_2 = 0.5$ ... [1]

If A plays A₃, B's expected payoff is: $q_2 = 0.5$ ... [2]

From equations [1] and [2]: $q_1 = 0.5$ and $q_2 = 0.5$

Optimal strategy for B: Play B₁ and B₂ with equal probability (0.5 each).

Worked Example: Alternative Two-Variable Formulation

Problem: Solve the same game using only two probability variables.

Formulation:

Maximise: $P = v$

Subject to: $v \leq 3p_1 + 2p_2 + (1 - p_1 - p_2) \quad \rightarrow \quad v \leq 2p_1 + p_2 + 1$ $v \leq p_2 + 2(1 - p_1 - p_2) \quad \rightarrow \quad v \leq 2 - 2p_1 - p_2$ $v, p_1, p_2 \geq 0$

Introduce slack variables: $P - v = 0$ $v - 2p_1 - p_2 + s = 1$ $v + 2p_1 + p_2 + t = 2$

The simplex solution gives the same result: $v = 1.5$, so the value of the original game is $-0.5$, with optimal strategy $p_1 = \frac{1}{4}$, $p_2 = 0$, and $p_3 = 1 - p_1 - p_2 = \frac{3}{4}$.

Worked Example: Reducing the Game Using Dominance

Problem: Show that this zero-sum game requires a mixed strategy, and find A's best strategy and the value of the game.

Solution:

Step 1: Use dominance to reduce the table

Column 2 dominates column 3 because every entry in column 2 is better for B (worse for A) than column 3:

• For A₁: $-1 < -1$ (equal)
• For A₂: $0 < 1$ (B prefers column 2)
• For A₃: $1 < 2$ (B prefers column 2)

Since $-1 = -1$, $0 < 1$, and $1 < 2$, column 2 dominates column 3, so delete column 3.

The revised table is:

Step 2: Check for stable solution

Row minima: $-1, -1, -2$ with maximum $= -1$

Column maxima: $0, 1$ with minimum $= 0$

These are not equal, so the solution is not stable. We need a mixed strategy.

Step 3: Make all entries non-negative

Add 2 to all payoffs:

Step 4: Set up the linear programming problem

Suppose A plays A₁, A₂, and A₃ with probabilities $p_1$, $p_2$, and $p_3$.

If B plays B₁, A's expected pay-off is: $2p_1 + p_2$

If B plays B₂, A's expected pay-off is: $p_1 + 2p_2 + 3p_3$

Maximise: $P = v$

Subject to: $v \leq 2p_1 + p_2$ $v \leq p_1 + 2p_2 + 3p_3$ $p_1 + p_2 + p_3 \leq 1$ $v, p_1, p_2, p_3 \geq 0$

Step 5: Apply simplex algorithm

After introducing slack variables and applying the simplex method, the solution is:

$v = 1.5$

So the value of the original game is $1.5 - 2 = -0.5$

The optimal strategy for A is to play A₂ and A₃ with probabilities 0.75 and 0.25 respectively.

Worked Example: Solving a 3×3 Game Without Using Dominance

Problem: Solve this zero-sum game to find the optimal strategy for player A and the value of the game.

Solution:

The game cannot be reduced using dominance.

Step 1: Add 1 to all entries to make them non-negative:

Step 2: Suppose A plays A₁, A₂, and A₃ with probabilities $p_1$, $p_2$, and $p_3$.

The linear programming formulation is:

Maximise: $P = v$

Subject to: $v \leq 2p_1 + p_2 + 2p_3$ $v \leq 3p_2 + 2p_3$ $v \leq p_1 + 2p_2$ $p_1 + p_2 + p_3 \leq 1$ $v, p_1, p_2, p_3 \geq 0$

Step 3: Introduce slack variables:

$P - v = 0$ $v - 2p_1 - p_2 - 2p_3 + s_1 = 0$ $v - 3p_2 - 2p_3 + s_2 = 0$ $v - p_1 - 2p_2 + s_3 = 0$ $p_1 + p_2 + p_3 + s_4 = 1$

Step 4: After applying the simplex algorithm (which involves many row operations), the final solution is:

$v = 1.5$

Therefore, the value of the original game is $1.5 - 1 = 0.5$

The optimal strategy for A is to play A₁ and A₂ each with probability 0.5 (never play A₃).