Welcome to Game Theory!
Hello! Today we are diving into one of the most fascinating parts of Discrete Mathematics: Game Theory. While it sounds like it’s just about board games or video games, it’s actually a powerful tool used by economists, military planners, and even biologists to predict how people (or animals) will behave when their interests clash.
In this chapter, we focus on zero-sum games. This simply means a situation where one person's gain is exactly equal to the other person's loss. Imagine sharing a pizza: every slice you eat is a slice your friend doesn't get. The total "benefit" is constant, so the sum of gains and losses is zero.
Don't worry if this seems a bit abstract at first—we will break it down step-by-step!
1. Understanding and Constructing Pay-off Matrices (DF1)
To analyze a game, we need to organize the information. We use a pay-off matrix. This is a table that shows what happens for every possible combination of moves.
The Basics:
- Usually, we have two players: Player A (the "Row" player) and Player B (the "Column" player).
- The numbers in the matrix represent the pay-off for Player A.
- If a number is positive, Player A wins that amount and Player B loses it.
- If a number is negative, Player A loses that amount and Player B wins it.
Example: Imagine a simple game where Player A chooses Row 1 or 2, and Player B chooses Column 1 or 2.
\( \begin{pmatrix} 3 & -2 \\ -1 & 4 \end{pmatrix} \)
In this matrix, if A chooses Row 1 and B chooses Column 2, the pay-off is -2. This means Player A loses 2 points and Player B gains 2 points.
Quick Review: The matrix always shows the game from Player A's perspective. Player A wants the numbers to be as high as possible, while Player B wants them to be as low as possible (because a loss for A is a win for B).
2. The "Play-Safe" Strategy (DF2)
In game theory, we assume both players are smart and trying to protect themselves. This leads to the play-safe strategy. Instead of gambling on a big win, players look at the worst-case scenario for every move and pick the one that is the "least bad."
How Player A plays safe (Maximin):
- For every row, find the minimum value (the worst A could do in that row).
- From those minimum values, pick the maximum one.
- This is called the Maximin value.
How Player B plays safe (Minimax):
- For every column, find the maximum value (the worst B could do because high numbers are bad for B).
- From those maximum values, pick the minimum one.
- This is called the Minimax value.
Memory Aid: Player A is a Maximin-iser (wants the best of the worst). Player B is a Minimax-er (wants the lowest of the highs).
The Value of the Game: If the players use these strategies, the actual outcome is called the value of the game.
3. Stable Solutions and Saddle Points (DF3)
Sometimes, both players realize that a specific pair of moves is the best they can both hope for. This happens when the Maximin equals the Minimax.
Key Term: Saddle Point
If Maximin = Minimax, the game has a stable solution. The value at this point is called a Saddle Point. In a stable game, neither player has any reason to change their move if they play the game again.
Analogy: Think of a mountain pass (a saddle). It is the lowest point if you are traveling along the ridge (Player B trying to keep values low), but the highest point if you are climbing up from the valley (Player A trying to keep values high).
Takeaway: If Maximin \( \neq \) Minimax, there is no stable solution, and players might need to "mix" their strategies to stay unpredictable.
4. Dominated Strategies (DF4)
Before solving a complex game, you can often make the matrix smaller by deleting dominated strategies. A dominated strategy is a move that is so bad, a smart player would never choose it.
How to spot them:
- For Rows (Player A): If every number in Row 1 is less than or equal to the corresponding number in Row 2, then Row 1 is dominated. Player A will always prefer Row 2. Delete Row 1!
- For Columns (Player B): Remember, B wants small numbers. If every number in Column 1 is greater than or equal to the numbers in Column 2, then Column 1 is dominated. Player B will always prefer Column 2. Delete Column 1!
Common Mistake: Students often forget that for Player B, "bigger is worse." Always double-check your column deletions!
5. Mixed Strategies and Graphical Methods (DF5)
If a game has no saddle point, a player shouldn't just pick one move every time. If they did, the opponent would figure it out! Instead, they use a mixed strategy—playing different moves with certain probabilities.
For the AQA syllabus, you need to know how to solve this graphically for a \( 2 \times n \) or \( n \times 2 \) game.
Step-by-Step for Player A (2 Rows):
- Let the probability of Player A choosing Row 1 be \( p \).
- Therefore, the probability of choosing Row 2 is \( (1 - p) \).
- For each of Player B's options (columns), write an expression for the expected gain.
Example: If Column 1 has values 3 and 1, the expression is \( 3p + 1(1-p) \). - Simplify these expressions (e.g., \( 2p + 1 \)).
- Draw these as straight lines on a graph where the x-axis is \( p \) (from 0 to 1) and the y-axis is the Expected Gain.
- Find the lower boundary of all the lines (the "floor").
- The highest point on this lower boundary is the optimal strategy!
Did you know? This graphical method is essentially finding the "best of the worst" outcomes across all possible probabilities. It ensures that no matter what Player B does, Player A's average win is at least a certain amount.
Quick Review Box:
1. Stable Game: Maximin = Minimax. Use a pure strategy (one move).
2. Unstable Game: Maximin \( \neq \) Minimax. Use a mixed strategy (probabilities).
3. Rows: Higher is better. Delete if all values are smaller.
4. Columns: Lower is better. Delete if all values are larger.
Don't worry if the graphing feels slow at first. Once you've drawn a few, you'll start to see the "V" shapes or "mountain" shapes clearly. Practice identifying the lower boundary—it's the key to the whole process!