Game Theory

Welcome to the World of Game Theory!

In this chapter, we are going to explore Game Theory, which is a fascinating part of Discrete Mathematics. Don’t let the name fool you—while it can be used for board games, it’s actually a powerful tool used by economists, military leaders, and scientists to understand how people make decisions when they are up against an opponent.

By the end of these notes, you’ll be able to look at a "game," figure out the best move to make, and even predict if a game is "fair." Let’s dive in!

1. Zero-Sum Games and Pay-off Matrices

In Further Maths, we focus on zero-sum games involving two players. A zero-sum game is one where one person’s gain is exactly equal to the other person’s loss. Think of it like a cake: if I take a bigger slice, your slice gets smaller by exactly that much. The total "sum" of our gains and losses is always zero.

What is a Pay-off Matrix?

To analyze a game, we put the results into a grid called a pay-off matrix. Usually, we have two players: the Row Player (let’s call her Rose) and the Column Player (let’s call him Colin).

The numbers in the matrix represent the pay-off for the Row Player:

• A positive number means the Row Player wins points/money from the Column Player.
• A negative number means the Row Player loses (so the Column Player wins!).

Example: If a matrix entry is \(3\), Rose wins 3 and Colin loses 3. If the entry is \(-5\), Rose loses 5 and Colin wins 5.

Did you know?

Even if a game doesn't look zero-sum at first, we can often convert it by subtracting a constant value from every entry until the "wins" and "losses" balance out relative to a starting point.

Quick Review: In a pay-off matrix, Row wants the numbers to be as high as possible, while Column wants them to be as low (or as negative) as possible.

2. The Art of Dominance

Sometimes, a player has a move that is so bad they would never choose it. We use a "dominance argument" to simplify the game by deleting these bad options.

How to spot dominance:

• For the Row Player: Look for a row where every single number is less than or equal to the numbers in another row. Why play the "worse" row? Delete it!
• For the Column Player: Look for a column where every single number is greater than or equal to the numbers in another column. Remember, Column wants small numbers. If a column has higher numbers, it’s worse for him. Delete it!

Step-by-step:
1. Compare rows. If Row A \(\le\) Row B, delete Row A.
2. Compare columns. If Col X \(\ge\) Col Y, delete Col X.
3. Keep repeating until you can’t delete any more.

Key Takeaway: Reducing a matrix via dominance makes the math much easier later on!

3. Play-Safe Strategies and Stable Solutions

If you don't know what your opponent is going to do, you might want to "play safe" to guarantee yourself a minimum result no matter what. This is where we find the Maximin and Minimax.

The Row Player's Strategy (Maximin)

Rose looks at each row and finds the minimum she could win. Then, she chooses the maximum of those values. This is her Maximin (the "best of the worst").

The Column Player's Strategy (Minimax)

Colin looks at each column and finds the maximum he could lose. Then, he chooses the minimum of those values. This is his Minimax (the "least of the bad outcomes").

Stable Solutions (Saddle Points)

If the Maximin = Minimax, the game has a stable solution, also called a Saddle Point.
In a stable game, neither player can improve their outcome by changing their strategy alone. They have both found the "optimal" pure strategy.

Common Mistake: Students often mix up Row and Column logic. Just remember: Row wants to maximize the minimums; Column wants to minimize the maximums.

Quick Review: If Maximin \(=\) Minimax, the game is stable. If not, the players need a "mixed strategy."

4. Mixed Strategies: Being Unpredictable

What if there is no saddle point? If you always play the same move, your opponent will catch on! In this case, you should play different moves with certain probabilities. This is a mixed strategy.

Solving for 2x2 Games

If you have a \(2 \times 2\) matrix (after using dominance), you can calculate the perfect probability for each move.

Let’s say the Row Player plays Row 1 with probability \(p\) and Row 2 with probability \((1-p)\).
We calculate the Expected Value (E) for the Row player against each of the Column player's possible moves.

Example Process:
1. Write an equation for the expected win against Column’s Move 1.
2. Write an equation for the expected win against Column’s Move 2.
3. Set them equal to each other to find the value of \(p\) that makes you "unbeatable" regardless of what Column does.

The Graphical Method

Sometimes you might have a \(2 \times n\) matrix. You can plot the expected values as straight lines on a graph where the x-axis is \(p\) (from \(0\) to \(1\)).
1. Draw the lines for each of Colin’s options.
2. Since Rose wants the maximum of the minimums, look for the highest point on the lower boundary of all the lines.
3. The lines that cross at that "peak" tell you which two moves Colin should focus on.

Don't worry if this seems tricky at first! Just remember that \(p\) is just a percentage. If \(p = 0.7\), it means you should play that move \(70\%\) of the time. The optimum can even occur at the very edges (\(p=0\) or \(p=1\)) if one move is clearly better.

Key Takeaway: A mixed strategy uses probability to guarantee a specific "value of the game" in the long run, even if the opponent knows your overall plan.

Final Summary Checklist

• Can you identify a zero-sum game?
• Can you use dominance to delete useless rows or columns?
• Can you find the Maximin and Minimax to check for a Saddle Point?
• For games without a saddle point, can you set up simultaneous equations or a graph to find the optimal probabilities (\(p\))?

Master these four steps, and you’ll be a Game Theory pro!