Welcome to Game Theory!
In this chapter of Decision Mathematics 2, we are going to explore how to make the best possible decisions when you are in a "conflict" or competition with someone else. Whether it is a board game, a business negotiation, or two sports teams competing, Game Theory provides a mathematical way to find the "best" move.
Don't worry if this seems a bit abstract at first. We’ll break it down into simple steps, use plenty of analogies, and show you exactly how to handle the exam style questions. Let's get started!
1. The Basics: Two-Person Zero-Sum Games
In the Edexcel syllabus, we focus on two-person zero-sum games.
What does that mean?
1. Two-person: There are only two players (usually called Player A and Player B).
2. Zero-sum: Whatever one person wins, the other person loses. If I win £10, you lose £10. The "sum" of our gains and losses is zero: \( +10 + (-10) = 0 \).
The Pay-off Matrix
The outcomes of a game are shown in a table called a pay-off matrix.
Important Rule: By default, the numbers in the matrix show the gain for the Row Player (Player A).
Example: If the value in the table is 5, Player A wins 5 points and Player B loses 5 points. If the value is -3, Player A loses 3 points (meaning Player B wins 3 points).
Quick Review:
- Positive number = Row Player wins / Column Player loses.
- Negative number = Row Player loses / Column Player wins.
Key Takeaway: Always look at the game through the eyes of the Row Player first. If you are the Column Player, you want the numbers to be as small (or as negative) as possible!
2. Play-Safe Strategies and Stable Solutions
Imagine you are playing a game against a very smart opponent. You assume they will always try to ruin your plans. To protect yourself, you use a play-safe strategy.
Step-by-Step: Finding the Play-Safe Strategy
For Player A (Rows):
1. Look at each row and find the minimum value (the worst-case scenario for that move).
2. From those minimums, pick the maximum. This is called the Row Maximin.
Analogy: Player A is "maximising the minimums."
For Player B (Columns):
1. Look at each column and find the maximum value (the most Player B could lose).
2. From those maximums, pick the minimum. This is called the Column Minimax.
Analogy: Player B is "minimising the maximums."
Stable Solutions (Saddle Points)
If the Row Maximin = Column Minimax, the game has a stable solution.
The value where they meet is called a saddle point. In a stable game, neither player can improve their outcome by changing their strategy unilaterally.
Did you know? It's called a saddle point because it’s the minimum of one direction (the row) and the maximum of another (the column), just like the shape of a horse's saddle!
Common Mistake: Students often forget that Player B wants the smallest possible value in the matrix. Always double-check your Minimax calculation for the columns.
Key Takeaway: A game is stable if Row Maximin = Column Minimax. If they are different, the game is unstable, and we need a "mixed strategy" (keep reading!).
3. Reducing the Matrix: Dominance
Before solving a complex game, we can often "trim the fat" by removing bad options. This is called dominance.
Rule for Rows (Player A):
If every value in Row 1 is less than or equal to the corresponding value in Row 2, Row 1 is dominated by Row 2. Player A will never choose Row 1 because Row 2 is always better or equal. Delete Row 1.
Rule for Columns (Player B):
If every value in Column 1 is greater than or equal to the corresponding value in Column 2, Column 1 is dominated by Column 2. Remember, Player B wants low numbers. So, Column 1 is worse for Player B. Delete Column 1.
Memory Aid:
- Rows: Bigger is better (Keep the big, delete the small).
- Columns: Smaller is better (Keep the small, delete the big).
Key Takeaway: Always check for dominance first! It can turn a scary \( 3 \times 3 \) matrix into a much simpler \( 2 \times 2 \) matrix.
4. Optimal Mixed Strategies: Graphical Method
If a game has no saddle point, players shouldn't just stick to one move. They should use a mixed strategy—playing different moves with certain probabilities (e.g., "I'll play Rock 30% of the time and Paper 70% of the time").
In your exam, you may need to solve \( 2 \times n \) or \( n \times 2 \) games using a graph.
Step-by-Step for a \( 2 \times n \) Game:
1. Let Player A play Strategy 1 with probability \( p \) and Strategy 2 with probability \( (1-p) \).
2. Write an equation for the expected pay-off against each of Player B's options.
Example: If Row 1 is (2, 6) and Row 2 is (5, 1), the equations would be:
- Against Col 1: \( V = 2p + 5(1-p) = 5 - 3p \)
- Against Col 2: \( V = 6p + 1(1-p) = 1 + 5p \)
3. Draw these lines on a graph where the x-axis is \( p \) (from 0 to 1) and the y-axis is \( V \) (Expected Value).
4. Find the Lower Boundary of all the lines.
5. Find the highest point on that lower boundary. This is the optimal value of \( p \).
6. Solve the two equations that meet at that point to find \( p \) and the value of the game \( V \).
Why the "Highest point of the Lower Boundary"?
Because Player A is trying to maximise (highest point) the minimum expected gain (lower boundary). This is just Maximin again, but with probabilities!
Key Takeaway: For \( 2 \times n \) games, look for the highest point on the bottom. For \( n \times 2 \) games (where you graph Player B's probability \( q \)), you look for the lowest point on the top.
5. Optimal Mixed Strategies: Linear Programming
When the matrix is too large for a simple graph (like a \( 3 \times 3 \) with no dominance), we use Linear Programming and the Simplex Algorithm.
Setting up the Problem:
1. Make all values positive: If the matrix has negative numbers, add a constant \( k \) to every cell so all values are \( > 0 \). (Remember to subtract \( k \) from your final game value at the end!).
2. Let probabilities for Player A be \( p_1, p_2, p_3 \).
3. We want to maximise the value \( V \), subject to:
\( V \le \) (Expected value against Column 1)
\( V \le \) (Expected value against Column 2)
\( V \le \) (Expected value against Column 3)
\( p_1 + p_2 + p_3 = 1 \)
4. To make this easier for Simplex, we often divide everything by \( V \) and let \( x_i = \frac{p_i}{V} \). Our goal then becomes minimising \( \frac{1}{V} = x_1 + x_2 + x_3 \).
Don't worry if this seems tricky at first: The most common exam question asks you to formulate the problem (write the equations) rather than solve the whole Simplex tableau, but be prepared for both!
Quick Review Box:
- Saddle Point: Row Maximin = Column Minimax.
- Dominance: Delete rows that are always smaller; delete columns that are always larger.
- Graphical Method: Used for \( 2 \times n \) or \( n \times 2 \).
- Linear Programming: Used for larger, unstable games.
Key Takeaway: Linear Programming is the "heavy lifting" tool of Game Theory. It treats the game like a resource allocation problem to find the perfect balance of moves.