Welcome to the World of Game Theory!

In this chapter, we are going to explore Game Theory, specifically focusing on zero-sum games. This sounds like a complex topic, but at its heart, it’s just the mathematical study of decision-making. We use it to figure out the best move when you are playing against someone else who is also trying to win.

Why "Zero-Sum"? Imagine you are betting £5 with a friend. If you win, you gain £5 (+5) and your friend loses £5 (-5). If you add them together, the sum is zero! In these games, one person's gain is exactly equal to the other person's loss. There are no "win-win" situations here!

1. The Pay-off Matrix

Every game starts with a pay-off matrix. This is just a table that shows what happens for every possible combination of moves. In AQA Further Maths, we usually have two players: the Row Player (let's call her Rose) and the Column Player (let's call him Colin).

Important Rule: The numbers in the matrix always represent the pay-off to the Row Player.

  • If the number is positive, the Row player wins that amount.
  • If the number is negative, the Column player wins that amount (and the Row player loses).
Example:

Rose chooses between moves A and B. Colin chooses between moves X and Y.

\( \begin{pmatrix} & X & Y \\ A & 3 & -2 \\ B & -1 & 4 \end{pmatrix} \)

If Rose plays A and Colin plays X, Rose wins 3 points. If Rose plays A and Colin plays Y, Colin wins 2 points (because it's -2 for Rose).

Quick Review: Reading the Matrix

Rose (Row) wants the highest positive numbers possible.
Colin (Column) wants the most negative numbers possible (because that means he is winning!).

2. Finding a "Play-Safe" Strategy

Don't worry if this seems tricky at first; both players are just trying to protect themselves from their worst-case scenario. This is called the Play-Safe strategy.

For the Row Player (Rose):

  1. Look at each row and find the minimum value (the worst Rose could do in that row).
  2. Choose the move that has the maximum of those minimums.
  3. This is called the Maximin.

For the Column Player (Colin):

  1. Look at each column and find the maximum value (the worst Colin could do, as these are Rose's winnings).
  2. Choose the move that has the minimum of those maximums.
  3. This is called the Minimax.

Key Takeaway: Rose wants to maximize her minimum gain. Colin wants to minimize his maximum loss.

3. Stable Solutions and Saddle Points

Sometimes, the Maximin value equals the Minimax value. When this happens, we have a Stable Solution (also known as a Saddle Point).

If a game is stable, neither player has any reason to change their strategy. The value where they meet is called the Value of the Game.

How to prove a stable solution exists:

  1. Find the Row Minimums. Find the largest one (Maximin).
  2. Find the Column Maximums. Find the smallest one (Minimax).
  3. If Maximin = Minimax, the game is stable.
Did you know? Not every game has a stable solution. If Maximin doesn't equal Minimax, the players will need to "mix up" their moves to keep the opponent guessing!

4. Dominated Strategies

Before solving a big matrix, we check if any move is "rubbish." A strategy is dominated if there is another move that is always better or equal, no matter what the opponent does.

  • For Rose (Rows): Row A is dominated by Row B if every element in Row B is greater than or equal to the elements in Row A. Rose will never play A, so we can cross it out!
  • For Colin (Columns): Column X is dominated by Column Y if every element in Column Y is smaller than or equal to the elements in Column X. Remember, Colin wants smaller numbers! He will never play X, so cross it out.

Memory Trick: Rose likes big numbers, Colin likes small numbers. If a row is smaller than another, delete it. If a column is larger than another, delete it.

5. Optimal Mixed Strategies (Graphical Method)

If there is no saddle point, Rose shouldn't play the same move every time. Instead, she should play Move 1 with probability \( p \) and Move 2 with probability \( (1-p) \). This is a Mixed Strategy.

Step-by-Step for a 2xN Game:

  1. Set up expressions for Rose's expected winnings for each of Colin's moves.
    Example: If Rose plays A with prob \( p \) and B with prob \( 1-p \), and Colin plays X, the winnings might be \( 3p - 1(1-p) \).
  2. Simplify these to the form \( mp + c \).
  3. Plot these as straight lines on a graph where the x-axis is \( p \) (from 0 to 1).
  4. Find the Lower Boundary of all the lines (the "bottom" shape made by the lines).
  5. Find the highest point on this lower boundary. This is the Maximin point!
  6. Solve the equations of the two lines that cross at that point to find the optimal value of \( p \).

Common Mistake: Students often look for the highest point of the whole graph. Remember: Rose is maximizing her minimum, so you look for the highest point of the bottom lines.

6. Higher-Order Games and Linear Programming

When the matrix is larger than 2x2 (and cannot be reduced by dominance), we use Linear Programming. This connects back to the Simplex method you learned in the Linear Programming chapter.

How to convert a Game to a Linear Programming Problem:

  1. Make all values positive: If the matrix has negative numbers, add a constant \( k \) to every element so they are all \( > 0 \). This doesn't change the strategy, just the final value.
  2. Let Rose's probabilities be \( p_1, p_2, p_3 \).
  3. Rose wants to maximize the value \( V \).
  4. The constraints are formed by columns: \( (\text{Payoff}_1)p_1 + (\text{Payoff}_2)p_2 + ... \geq V \).
  5. We also know that \( p_1 + p_2 + ... = 1 \).

To solve this using the Simplex method, we usually rearrange the variables (letting \( x_i = \frac{p_i}{V} \)) to turn it into a standard maximization problem: Minimize \( \frac{1}{V} = x_1 + x_2 + x_3 \).

Summary Checklist

  • Can I construct a matrix from a word problem? (DF1)
  • Can I find the Maximin and Minimax to check for a saddle point? (DF2 & DF3)
  • Have I checked for dominated rows and columns to simplify the game? (DF4)
  • Can I draw a graph for a 2xN game and find the optimal \( p \)? (DF5)
  • Do I know how to set up the Linear Programming constraints for a 3x3 game? (DF6)

You've got this! Just remember: Rose wants to be as high as possible on the bottom floor, and Colin wants to be as low as possible on the top floor!