Game Theory - Fundamental Theory, Maximin and Minimax Principles
Welcome to the fascinating world of Game Theory! In this unit, we will explore the fundamental concepts of game theory, a mathematical framework used to analyze strategic interactions between rational decision-makers. We'll delve into situations where the outcome for one participant depends not only on their own actions but also on the actions of others. This is particularly relevant in fields like economics, politics, business, and even biology.
What is Game Theory?
Game theory is the study of mathematical models of strategic interaction among rational agents. A "game" in this context refers to any situation where two or more participants (called players) make decisions, and the outcome of each player's decision depends on the decisions made by other players. The key elements of a game are:
- Players: The decision-makers involved in the game.
- Strategies: The set of all possible actions a player can take.
- Payoffs: The outcomes or rewards (which can be positive or negative) that each player receives for each combination of strategies chosen by all players.
- Information: What each player knows about the game, including the other players' strategies and payoffs.
- Rationality: The assumption that players will act in their own self-interest to maximize their payoffs.
Types of Games
Games can be classified based on several criteria:
- Cooperative vs. Non-cooperative Games: In cooperative games, players can form binding agreements. In non-cooperative games, players act independently without binding agreements.
- Zero-Sum vs. Non-zero-Sum Games: In a zero-sum game, the total gains of the participants equal their total losses; one player's gain is exactly the other player's loss. In non-zero-sum games, the gains and losses do not necessarily sum to zero.
- Simultaneous vs. Sequential Games: In simultaneous games, players make their decisions at the same time, without knowing the other's choice. In sequential games, players make decisions in a specific order, with later players having knowledge of earlier players' moves.
- Perfect vs. Imperfect Information: In games of perfect information, players know all previous moves made by all other players. In games of imperfect information, players do not have complete knowledge of past moves.
Payoff Matrix
For games involving two players and a finite number of strategies, we often represent the payoffs using a payoff matrix. This is a table that shows the payoff for each player for every possible combination of strategies.
Let's consider a simple two-player, zero-sum game. Player 1 has strategies R1 and R2, and Player 2 has strategies C1 and C2. The matrix below shows the payoffs for Player 1. Since it's a zero-sum game, Player 2's payoffs are the negative of Player 1's payoffs.
Example Payoff Matrix (Player 1's payoffs):
| Player 1 \ Player 2 | Player 2 Strategies | |
|---|---|---|
| C1 | C2 | |
| R1 | 3 | -1 |
| R2 | -2 | 4 |
In this matrix:
- If Player 1 chooses R1 and Player 2 chooses C1, Player 1 gets a payoff of 3.
- If Player 1 chooses R1 and Player 2 chooses C2, Player 1 gets a payoff of -1.
- If Player 1 chooses R2 and Player 2 chooses C1, Player 1 gets a payoff of -2.
- If Player 1 chooses R2 and Player 2 chooses C2, Player 1 gets a payoff of 4.
The Fundamental Theory of Zero-Sum Games
The fundamental theorem of zero-sum games, also known as the Minimax Theorem, states that in any two-person, zero-sum game with a finite number of strategies, there exists a value V and a pair of strategies (one for each player) such that:
- Player 1 can guarantee a payoff of at least V, regardless of Player 2's strategy.
- Player 2 can guarantee that Player 1 receives a payoff of at most V, regardless of Player 1's strategy.
This value V is called the "value of the game." The theorem essentially guarantees that in such games, there's a stable outcome where neither player can improve their situation by unilaterally changing their strategy, assuming the other player sticks to their optimal strategy. This stable outcome is known as a Nash Equilibrium.
Maximin and Minimax Principles
To find this optimal strategy and the value of the game, we use the maximin and minimax principles. These principles are based on the idea of players trying to secure the best possible outcome under the worst-case scenario.
1. Maximin Principle (for Player 1)
Player 1 wants to maximize their payoff. However, Player 1 knows that Player 2 will try to minimize Player 1's payoff. Therefore, Player 1 adopts a conservative approach: for each of their strategies, they consider the worst possible outcome (the minimum payoff) that could occur if Player 2 plays optimally against that strategy. Then, Player 1 chooses the strategy that yields the maximum of these minimum payoffs.
Steps for Player 1 (Maximin):
- For each row (Player 1's strategy), find the minimum value.
- Identify the maximum of these minimum values. This is the maximin value.
Let's apply this to our example payoff matrix:
| Player 1 \ Player 2 | Player 2 Strategies | |
|---|---|---|
| C1 | C2 | |
| R1 | 3 | -1 |
| R2 | -2 | 4 |
Step 1: Find the minimum value in each row:
- For R1: min(3, -1) = -1
- For R2: min(-2, 4) = -2
Step 2: Find the maximum of these minimum values:
- Max (-1, -2) = -1
So, the maximin value for Player 1 is -1. This means Player 1 can guarantee a payoff of at least -1 by choosing strategy R1.
2. Minimax Principle (for Player 2)
Player 2 wants to minimize Player 1's payoff (which is equivalent to maximizing Player 2's own payoff, since it's a zero-sum game). Player 2 knows that Player 1 will try to maximize their payoff. Therefore, Player 2 adopts a conservative approach: for each of their strategies, they consider the worst possible outcome for them (the maximum payoff Player 1 could get) if Player 1 plays optimally against that strategy. Then, Player 2 chooses the strategy that yields the minimum of these maximum payoffs.
Steps for Player 2 (Minimax):
- For each column (Player 2's strategy), find the maximum value.
- Identify the minimum of these maximum values. This is the minimax value.
Let's apply this to our example payoff matrix:
| Player 1 \ Player 2 | Player 2 Strategies | |
|---|---|---|
| C1 | C2 | |
| R1 | 3 | -1 |
| R2 | -2 | 4 |
Step 1: Find the maximum value in each column:
- For C1: max(3, -2) = 3
- For C2: max(-1, 4) = 4
Step 2: Find the minimum of these maximum values:
- Min (3, 4) = 3
So, the minimax value for Player 2 is 3. This means Player 2 can ensure that Player 1's payoff is at most 3 by choosing strategy C1.
Saddle Point and Value of the Game
The Minimax Theorem states that for zero-sum games, the maximin value is equal to the minimax value. This common value is the "value of the game," and the corresponding strategy pair is called a "saddle point." A saddle point is an outcome in the payoff matrix where the entry is simultaneously the minimum of its row and the maximum of its column.
In our example:
- Maximin value (Player 1) = -1
- Minimax value (Player 2) = 3
Since the maximin value (-1) is NOT equal to the minimax value (3), this game does not have a saddle point in pure strategies. This means that the optimal strategies for the players involve randomization (mixed strategies), which we will discuss in further detail in later sections.
Example with a Saddle Point
Let's consider another payoff matrix where a saddle point exists:
| Player 1 \ Player 2 | Player 2 Strategies | ||
|---|---|---|---|
| C1 | C2 | C3 | |
| R1 | 1 | 2 | 0 |
| R2 | 3 | -1 | 4 |
| R3 | -2 | 0 | 1 |
Player 1 (Maximin):
- Row minimums: min(1, 2, 0) = 0 (for R1); min(3, -1, 4) = -1 (for R2); min(-2, 0, 1) = -2 (for R3)
- Maximin value = max(0, -1, -2) = 0. Player 1 can guarantee at least 0 by choosing R1.
Player 2 (Minimax):
- Column maximums: max(1, 3, -2) = 3 (for C1); max(2, -1, 0) = 2 (for C2); max(0, 4, 1) = 4 (for C3)
- Minimax value = min(3, 2, 4) = 2. Player 2 can ensure Player 1 gets at most 2 by choosing C2.
Again, Maximin (0) != Minimax (2). No saddle point in pure strategies. Let's adjust the matrix slightly to create a saddle point.
Example with a Saddle Point (Revised)
Consider this matrix:
| Player 1 \ Player 2 | Player 2 Strategies | ||
|---|---|---|---|
| C1 | C2 | C3 | |
| R1 | 5 | 2 | 3 |
| R2 | 1 | 4 | 6 |
| R3 | 3 | 0 | 2 |
Player 1 (Maximin):
- Row minimums: min(5, 2, 3) = 2 (for R1); min(1, 4, 6) = 1 (for R2); min(3, 0, 2) = 0 (for R3)
- Maximin value = max(2, 1, 0) = 2. Player 1 can guarantee at least 2 by choosing R1.
Player 2 (Minimax):
- Column maximums: max(5, 1, 3) = 5 (for C1); max(2, 4, 0) = 4 (for C2); max(3, 6, 2) = 6 (for C3)
- Minimax value = min(5, 4, 6) = 4. Player 2 can ensure Player 1 gets at most 4 by choosing C2.
Still no saddle point. Let's try one more time, focusing on creating a cell that is both a row minimum and column maximum.
Example with a Saddle Point (Final)
Consider this matrix:
| Player 1 \ Player 2 | Player 2 Strategies | ||
|---|---|---|---|
| C1 | C2 | C3 | |
| R1 | 1 | 7 | 2 |
| R2 | 6 | 3 | 5 |
| R3 | 4 | 8 | 3 |
Player 1 (Maximin):
- Row minimums: min(1, 7, 2) = 1 (for R1); min(6, 3, 5) = 3 (for R2); min(4, 8, 3) = 3 (for R3)
- Maximin value = max(1, 3, 3) = 3. Player 1 can guarantee at least 3 by choosing R2 or R3.
Player 2 (Minimax):
- Column maximums: max(1, 6, 4) = 6 (for C1); max(7, 3, 8) = 8 (for C2); max(2, 5, 3) = 5 (for C3)
- Minimax value = min(6, 8, 5) = 5. Player 2 can ensure Player 1 gets at most 5 by choosing C3.
Wait, I am struggling to create one on the fly. Let's use a standard example that is known to have a saddle point.
Standard Example with a Saddle Point
Consider the following payoff matrix for Player 1:
| Player 1 \ Player 2 | Player 2 Strategies | |
|---|---|---|
| C1 | C2 | |
| R1 | 4 | 1 |
| R2 | 2 | 3 |
Player 1 (Maximin):
- Row minimums: min(4, 1) = 1 (for R1); min(2, 3) = 2 (for R2)
- Maximin value = max(1, 2) = 2. Player 1's maximin strategy is R2.
Player 2 (Minimax):
- Column maximums: max(4, 2) = 4 (for C1); max(1, 3) = 3 (for C2)
- Minimax value = min(4, 3) = 3. Player 2's minimax strategy is C2.
Maximin (2) is not equal to Minimax (3). It seems I am having difficulty generating a simple saddle point example. Let's try one more time focusing on the definition. A saddle point is an element that is the smallest in its row and the largest in its column.
Corrected Example with a Saddle Point
Let's construct a matrix where a saddle point is guaranteed.
| Player 1 \ Player 2 | Player 2 Strategies | ||
|---|---|---|---|
| C1 | C2 | C3 | |
| R1 | 10 | 5 | 7 |
| R2 | 6 | 4 | 8 |
| R3 | 7 | 3 | 9 |
Player 1 (Maximin):
- Row minimums: min(10, 5, 7) = 5 (for R1); min(6, 4, 8) = 4 (for R2); min(7, 3, 9) = 3 (for R3)
- Maximin value = max(5, 4, 3) = 5. Player 1's maximin strategy is R1.
Player 2 (Minimax):
- Column maximums: max(10, 6, 7) = 10 (for C1); max(5, 4, 3) = 5 (for C2); max(7, 8, 9) = 9 (for C3)
- Minimax value = min(10, 5, 9) = 5. Player 2's minimax strategy is C2.
Here, Maximin value (5) = Minimax value (5). This means the game has a saddle point. The saddle point occurs at the intersection of Player 1's maximin strategy (R1) and Player 2's minimax strategy (C2). The value of the game is 5.
Let's check the cell (R1, C2) which has the value 5.
- Is 5 the minimum in its row (R1)? Yes, min(10, 5, 7) = 5.
- Is 5 the maximum in its column (C2)? Yes, max(5, 4, 3) = 5.
Since the element 5 is both the minimum of its row and the maximum of its column, it is a saddle point. The value of the game is 5. Both players have a pure optimal strategy: Player 1 plays R1, and Player 2 plays C2. Neither player can improve their outcome by unilaterally changing their strategy.
Significance of Saddle Point
A saddle point represents a stable equilibrium in a zero-sum game. When a saddle point exists, both players can determine their best course of action with certainty. Player 1 knows they can guarantee a payoff of at least V (the value of the game), and Player 2 knows they can limit Player 1's payoff to at most V. Neither player has an incentive to deviate from their strategy.
Limitations
The maximin and minimax principles, when applied to find pure strategy saddle points, are powerful. However, they are not sufficient for all games. As seen in earlier examples, many games do not have a saddle point. In such cases, the optimal strategies involve randomization, where players choose their actions according to certain probabilities. This leads to the concept of mixed strategies, which is a more advanced topic in game theory.
Game theory provides a rigorous way to think about strategic decision-making. Understanding the fundamental theory, along with the maximin and minimax principles, forms the bedrock for analyzing more complex strategic interactions and finding optimal solutions, especially in zero-sum scenarios.