Hello! Welcome to the second module of our course. In the previous module, we built a solid foundation for analyzing games, culminating in a method for finding both pure and mixed-strategy Nash Equilibria.
We ended by noting that in a mixed-strategy NE, a player's optimal strategy is designed to make the other player indifferent. This sets the stage perfectly for today's topic, where the adversarial nature of the game is front and center. We are moving into the special category of two-player zero-sum games.
This lesson corresponds to the first learning outcome in our "Zero-Sum Games and the Minimax Theorem" module: Define two-player zero-sum games and the associated maximin and minimax values.
Our focus will be on understanding the unique structure of these games and the conservative, worst-case reasoning that players employ, which is captured by the concepts of maximin and minimax. These ideas are the cornerstones of the famous Minimax Theorem, which we will prove in later lessons using the tools of linear programming.
1. What is a Two-Player Zero-Sum Game?
As the name suggests, a zero-sum game is a situation where the players' interests are in direct conflict. One player's gain is exactly the other player's loss.
To get a formal definition and see some classic examples, please watch the first couple of minutes of the following video.
(AGT1E4) [Game Theory] Two-Player Zero Sum Games
This video from Selcuk Ozyurt provides a clear definition of what makes a game 'strictly competitive' and, more specifically, 'zero-sum'.
Watch the beginning of the video, from 00:00 to 02:15. Focus on the core property: for any outcome, the sum of the players' payoffs is zero.
Representing Zero-Sum Games
Because Player 2's payoff is always the negative of Player 1's payoff, , we can represent the entire game with a single payoff matrix that shows only Player 1's utilities. This is a standard and very useful convention.
By convention:
- Player 1 is the row player. They want to maximize the value in the matrix.
- Player 2 is the column player. They want to minimize the value in the matrix (since their payoff is the negative of that value).
The following reading selection formalizes this definition and the matrix representation.
[PDF] CSC304 Lecture 6 Game Theory : Zero-Sum Games...
These lecture slides from the University of Toronto formalize the definition of a two-player zero-sum game and introduce the standard convention of representing the game using only Player 1's payoff matrix.
Please review slides 2 through 5. These are found under the headings 'Zero-Sum Games' and 'Rewards in Matrix Form'. Notice how a game like Rock-Paper-Scissors can be simplified into a single matrix, where the row player is the maximizer and the column player is the minimizer.
2. The Maximin Value: A Security Guarantee
Now, how should a player decide on a strategy in such a game? One powerful approach is to adopt a "worst-case" or "pessimistic" mindset.
A player might ask: "For every possible strategy I could choose, what is the worst possible outcome for me (assuming my opponent plays their best counter-move)? Given this, I will choose the strategy that makes my worst-case outcome as good as possible."
This line of reasoning leads to the maximin strategy.
- For each of their strategies, Player 1 finds the minimum payoff they could receive.
- They then choose the strategy that maximizes that minimum payoff.
This is Player 1's maximin value: the best payoff they can guarantee for themselves, no matter what Player 2 does.
The video below offers an excellent walkthrough of this concept, which it calls a "security strategy."
(AGT1E4) [Game Theory] Two-Player Zero Sum Games
Let's dive into the logic of a 'maximin' or 'security' strategy, where a player aims to maximize their minimum guaranteed payoff.
Watch from 2:53 to 11:36. Focus on: The intuition behind a pessimistic player analyzing their worst-case outcome for each strategy. The formal definition of the maximin problem: \max_{\sigma_1} \min_{\sigma_2} u_1(\sigma_1, \sigma_2). The crucial simplification explained around 9:30: to find the minimum payoff for your mixed strategy \sigma_1, you only need to check your opponent's pure strategies. This is because the expected utility function is linear in your opponent's probabilities, so the minimum will always be at one of the 'corners' (a pure strategy).
3. The Minimax Value: Limiting the Opponent
Player 2, the minimizer, engages in parallel reasoning. They ask: "For every possible strategy I could choose, what is the best my opponent could do against it? I will then choose the strategy that makes my opponent's best outcome as small as possible."
This is the minimax strategy.
- For each of their strategies, Player 2 finds the maximum payoff Player 1 could achieve.
- They then choose the strategy that minimizes that maximum payoff.
This gives us the minimax value: the lowest payoff that Player 2 can limit Player 1 to, assuming Player 1 plays their best response.
The following reading provides the formal, side-by-side definitions of these two crucial concepts.
[PDF] CSC304 Lecture 6 Game Theory : Zero-Sum Games...
These lecture slides provide concise, formal mathematical definitions for both the maximin and minimax values. Seeing them side-by-side clarifies their symmetric, adversarial relationship.
Please review slides 10, 11, and 12, under the headings 'Maximin Strategy' and 'Maximin vs Minimax'. Pay close attention to the mathematical formulations. Using A as the payoff matrix for Player 1: Maximin Value: \max_{x_1} \min_{x_2} x_1^T A x_2 Minimax Value: \min_{x_2} \max_{x_1} x_1^T A x_2 Note that both values are expressed in terms of Player 1's payoff.
4. A Worked Example
To make these abstract definitions concrete, let's walk through an example. A very intuitive way to think about maximin and minimax is to imagine a sequential game where one player must commit to and announce their strategy first.
- If Player 1 (Max) goes first, Player 2 (Min) will observe this and choose a best response to minimize the payoff. Player 1, knowing this, will choose their initial strategy to maximize this final outcome. This is the maximin problem.
- If Player 2 (Min) goes first, Player 1 (Max) will observe this and choose a best response to maximize the payoff. Player 2, knowing this, will choose their initial strategy to minimize this final outcome. This is the minimax problem.
The following resource provides an excellent walkthrough of this logic. It also demonstrates how finding the optimal mixed strategy for each player involves using the indifference principle you learned in the previous lesson.
[PDF] Zero Sum Games and the Minimax Thoerem
To solidify these concepts, let's walk through a concrete example. These notes use an intuitive 'player-goes-first' scenario to build up the logic for finding the maximin and minimax strategies.
Read slides 3 through 12, starting with the 'Presidential Election Game' example. Follow the reasoning: If Max goes first (slides 7-10): How does Max choose a mixed strategy p to maximize their payoff, knowing Min will respond optimally? This calculation yields the maximin value. If Min goes first (slides 11-12): How does Min choose a mixed strategy q to minimize Max's payoff, knowing Max will respond optimally? This yields the minimax value. Notice how the calculation to find the optimal mixed strategy p (or q) relies on making the other player indifferent between their choices.
In the example provided, you may have noticed that the maximin value and the minimax value turned out to be the same (1/7). This is not a coincidence, and it forms the basis of von Neumann's great theorem.
Conclusion
In this lesson, we have focused on the fundamental definitions for analyzing two-player zero-sum games.
Key Takeaways:
- A two-player zero-sum game is a game of pure conflict, where for any outcome . We can represent it with a single matrix of Player 1's payoffs.
- The maximin value is the best payoff Player 1 can guarantee. It is found by choosing the strategy that maximizes their payoff in the worst-case scenario: .
- The minimax value is the lowest payoff Player 2 can limit Player 1 to. It is found by Player 2 choosing the strategy that minimizes Player 1's best possible response: .
- These concepts represent a conservative, security-oriented approach to strategy, which is natural in a purely adversarial setting.
Preview of the next lesson:
We established the definitions of the maximin and minimax values. A natural question follows: what is the relationship between them? In our next lesson, we will prove that for any two-player zero-sum game, the maximin value is always less than or equal to the minimax value. This is often called the "easy" direction of the Minimax Theorem and is a crucial stepping stone toward the full result.