Minimax Theorem and Nash Equilibrium

1. Von Neumann's Minimax Theorem

The proof that maximin ≤ minimax was quite general. The much more profound result, which applies specifically to finite, two-player, zero-sum games, is that these two values are in fact equal.

This is the celebrated Minimax Theorem.

The Minimax Theorem: For any finite two-player zero-sum game with payoff matrix $A$ for the row player (Player 1), the following equality holds:

Here, $x$ and $y$ are the mixed strategy vectors for the row and column players, respectively.

This common value is called the value of the game, often denoted by $v$. It represents the best possible guaranteed expected payoff for Player 1, assuming both players play optimally. Since the game is zero-sum, Player 2's payoff is then $-v$.

To see a formal statement of this theorem, you can consult the following resource.

The equality of maximin and minimax is a powerful concept. It implies that in a zero-sum game, there's no advantage to playing second or having your opponent know your strategy, provided you are both playing optimally. The outcome is pre-determined by the game's structure. Visually, this corresponds to the idea of a "saddle point" on the payoff surface.

Proving this theorem is non-trivial. As foreshadowed by your course goal, we will construct a full proof in a later module using the Strong Duality Theorem of Linear Programming. For now, we will take the theorem as given and explore its profound implications.

2. The Link Between Minimax Solutions and Nash Equilibrium

We now have two central solution concepts:

1. Nash Equilibrium (NE): A strategy profile where no player can unilaterally deviate and improve their payoff.
2. Minimax Solution: A pair of strategies $(x^{\ast },y^{\ast })$ where $x^{\ast }$ is a maximin strategy for Player 1 and $y^{\ast }$ is a minimax strategy for Player 2.

What is the relationship between them? For two-player zero-sum games, they are fundamentally the same. A pair of maximin/minimax strategies is a Nash Equilibrium, and vice-versa.

Let's explore why a minimax solution must be a Nash Equilibrium. Let $(x^{\ast },y^{\ast })$ be a pair of maximin/minimax strategies. By the Minimax Theorem, we know:
${\max }_x{\min }_y{x}^{T}Ay={\min }_y{\max }_x{x}^{T}Ay=v$
From the definitions of $x^{\ast }$ and $y^{\ast }$:

1. ${\min }_y(x^{\ast }{)}^{T}Ay=v$. This means that if Player 1 plays $x^{\ast }$, their payoff is guaranteed to be at least $v$, no matter what $y$ Player 2 chooses. $(x^{\ast }{)}^{T}Ay\ge v$ for all $y$.
2. ${\max }_x{x}^{T}A{y}^{\ast }=v$. This means that if Player 2 plays $y^{\ast }$, Player 1's payoff can be at most $v$, no matter what $x$ Player 1 chooses. $x^{T}A{y}^{\ast }\le v$ for all $x$.

Now, let's check the conditions for Nash Equilibrium for the profile $(x^{\ast },y^{\ast })$, where the payoff is $(x^{\ast }{)}^{T}A{y}^{\ast }$. From the properties above, we know that $v\le (x^{\ast }{)}^{T}A{y}^{\ast }\le v$, which implies the payoff must be exactly $v$.

• Can Player 1 do better? If Player 1 deviates to some other strategy $x$, their payoff will be $x^{T}A{y}^{\ast }$. But we know from property (2) that $x^{T}A{y}^{\ast }\le v$. Since their current payoff is $v$, there is no incentive to deviate.
• Can Player 2 do better? If Player 2 deviates to some other strategy $y$, Player 1's payoff will be $(x^{\ast }{)}^{T}Ay$. From property (1), we know this payoff is $\ge v$. Since this is a zero-sum game, Player 2's payoff is the negative of Player 1's. A higher payoff for Player 1 means a lower payoff for Player 2. Since Player 2's current payoff is $-v$, and any deviation leads to a payoff of $\le -v$, there is no incentive for Player 2 to deviate.

Since neither player can improve their payoff by unilaterally changing their strategy, the minimax solution $(x^{\ast },y^{\ast })$ is a Nash Equilibrium.

The following reading provides a concise summary of this crucial argument.

3. The Uniqueness of the Value of the Game

A game can have multiple Nash Equilibria. For example, some pure strategy profiles might be equilibria, and there might also be a mixed strategy equilibrium. However, in a zero-sum game, a remarkable property emerges: the payoffs are the same in all Nash Equilibria.

This directly connects the value $v$ from the Minimax Theorem to the payoffs in any Nash Equilibrium.

The following resource formally states this property and uses it to define the value of a game.

As the text states, the value of a zero-sum game is precisely the unique payoff that the row player receives in any of the game's Nash equilibria. This beautifully ties together the minimax solution concept and the Nash Equilibrium concept. The value $v$ we find via the minimax equality is not just an abstract quantity; it is the concrete payoff outcome at equilibrium.

Conclusion

Today, we've explored one of the cornerstones of game theory and its relationship with Nash Equilibrium.

Key Takeaways:

• Von Neumann's Minimax Theorem: For any finite, two-player, zero-sum game, the maximin value equals the minimax value. This common value is known as the value of the game ($v$).
• Minimax and NE Equivalence: A pair of maximin/minimax strategies constitutes a Nash Equilibrium in a zero-sum game.
• Value of the Game and NE Payoffs: The value of the game, $v$, is the unique payoff for Player 1 across all possible Nash Equilibria of the game. The corresponding payoff for Player 2 is $-v$.

Preview of the next lesson:

We've established that a minimax solution is a Nash Equilibrium. To complete the picture, in our next lesson we will formalize this relationship by proving the full equivalence: a strategy profile in a zero-sum game is a Nash equilibrium if and only if it is a minimax solution. This will cement the interchangeability of these concepts, a crucial step before we learn how to compute these solutions using linear programming.