Welcome to Game Theory!

Welcome to one of the most fascinating chapters in Discrete Mathematics. While the name might make you think of board games or video games, Game Theory is actually a powerful tool used by economists, military strategists, and biologists to model conflict and cooperation.

In this chapter, you will learn how to analyze situations where two "players" make decisions, and the outcome for each depends on the choices of the other. Don't worry if it feels a bit like a logic puzzle at first—we'll break it down step-by-step!


1. The Pay-off Matrix and Zero-Sum Games

Every game we study here is a zero-sum game. This means that whatever one player wins, the other player loses. The total "wealth" in the game stays at zero.

We represent these games using a pay-off matrix. By convention, the numbers in the matrix show the gain for the Row Player. If a number is negative, it means the Row Player loses that amount (and the Column Player wins it).

Key Concepts:

  • Row Player (R): Always tries to maximise their winnings.
  • Column Player (C): Always tries to minimise the pay-off to the Row player (because R's gain is C's loss).
Example: Imagine Store A (Row) and Store B (Column) are choosing whether to advertise. If the matrix shows a '5', Store A gains 5% market share and Store B loses 5%.
Quick Takeaway:

The matrix is always written from the Row Player's perspective. High numbers are good for Row; low numbers are good for Column.


2. Reducing a Matrix: The Dominance Argument

Sometimes, a matrix is bigger than it needs to be. We can simplify it using dominance. A strategy is "dominated" if there is another strategy that is always better or equal, no matter what the opponent does.

How to reduce:

  1. For Rows: If every element in Row 1 is less than or equal to the corresponding element in Row 2, Row 1 is dominated. Delete it! (The Row player would never choose it).
  2. For Columns: If every element in Column 1 is greater than or equal to the corresponding element in Column 2, Column 1 is dominated. Delete it! (Remember: the Column player wants smaller numbers).

Memory Trick: Rows = "Bigger is Better." Columns = "Smaller is Smarter."

Key Takeaway:

Always look for dominance first. It saves you a lot of calculation time later!


3. Pure Strategies: Play-Safe and Stable Solutions

Before jumping into complex math, we check if there is a pure strategy. This is when both players find a single move they will always stick to.

The Play-Safe Strategy:

  • Row Player (Maximin): For each row, find the minimum value. Then, choose the maximum of those minimums.
  • Column Player (Minimax): For each column, find the maximum value. Then, choose the minimum of those maximums.

Stable Solutions (Saddle Points):

If Maximin = Minimax, the game has a stable solution or a saddle point. In this case, neither player has any incentive to change their move. This value is also called the Value of the Game (V).

Did you know? A saddle point is named after the shape of a mountain pass (a saddle)—it is the lowest point along the ridge but the highest point between the valleys!

Nash Equilibrium:

A Nash Equilibrium is a set of strategies where no player can benefit by changing their strategy while the other players keep theirs unchanged. In a zero-sum game with a stable solution, the saddle point is the Nash Equilibrium.

Key Takeaway:

If Maximin = Minimax, the game is solved! No further calculation is needed.


4. Mixed Strategies: When There is No Stable Solution

What if Maximin is not equal to Minimax? In this case, players shouldn't stick to just one move, or their opponent will predict it. Instead, they use a mixed strategy, playing different moves with certain probabilities.

A. Solving 2x2 Games (Simultaneous Equations)

Suppose the Row player plays strategy \(R_1\) with probability \(p\) and \(R_2\) with probability \((1-p)\). We want to find a value of \(p\) such that the expected pay-off is the same, regardless of what the Column player does.

Step-by-Step:

  1. Assign \(p\) and \((1-p)\) to the Row player's options.
  2. Calculate the expected pay-off if the Column player plays \(C_1\).
  3. Calculate the expected pay-off if the Column player plays \(C_2\).
  4. Set these two expressions equal to each other and solve for \(p\).
Example: If Column playing \(C_1\) gives \(3p + 1(1-p)\) and playing \(C_2\) gives \(2p + 4(1-p)\), we solve: \(3p + 1 - p = 2p + 4 - 4p\).

B. Solving 2xN Games (Graphical Method)

If Row has 2 options but Column has many, we use a graph.

  1. Let the x-axis be \(p\) (from 0 to 1).
  2. For each of Column's strategies, draw a line representing the expected pay-off to Row.
  3. Find the lower boundary of all these lines (since Column will try to minimise Row's gain).
  4. The highest point on this lower boundary is the optimal \(p\) for the Row player.

Don't worry if this seems tricky at first! Just remember: Row wants the "highest point of the lowest part" of the graph.

Key Takeaway:

Mixed strategies are used to keep the opponent guessing. We calculate the probabilities that ensure a guaranteed average "Value of the Game."


5. Advanced Strategy: Simplex Method Reformulation

For games larger than 2x2 or 2xN, simple algebra and graphs aren't enough. We have to turn the game into a Linear Programming problem that can be solved with the Simplex Algorithm.

The Process:

  1. Add a constant to all elements in the matrix to ensure they are all positive (this doesn't change the strategy, just the final value).
  2. Define variables \(x_1, x_2, ... x_n\) where \(x_i = \frac{p_i}{V}\).
  3. The goal becomes to Maximise \(P = x_1 + x_2 + ... + x_n\) (which is equivalent to minimising the Value of the Game).
  4. Set up constraints based on the columns of the matrix.

Common Mistake: Forgetting to add a constant to make all values positive. Simplex cannot handle negative "Value" variables directly in this setup!

Key Takeaway:

Large games are just complex optimisation problems. We use Simplex to find the "best mix" of many different strategies.


Final Quick Review

  • Zero-sum: My gain = Your loss.
  • Dominance: Delete "bad" rows (low) and "bad" columns (high).
  • Play-Safe: Maximin for Row, Minimax for Column.
  • Saddle Point: When Maximin = Minimax. The game is stable.
  • Mixed Strategy: Use probabilities (\(p\) and \(1-p\)) when there is no saddle point.
  • Value (V): The average amount the Row player expects to win if both play perfectly.

Encouraging Phrase: You've got this! Practice identifying saddle points first—they are the "low-hanging fruit" of Game Theory questions!