The Minimax Theorem and Optimal Mixed Strategies
This article provides a concise explanation of the Minimax Theorem, a foundational concept in mathematical game theory proved by John von Neumann in 1928. It explores the mechanics of two-player zero-sum games, defines the critical difference between pure and mixed strategies, and illustrates how the theorem mathematically guarantees an optimal strategy that locks the game into a stable equilibrium.
Understanding Two-Player Zero-Sum Games
To understand the Minimax Theorem, one must first understand the environment in which it operates: the two-player zero-sum game. In mathematics, this is a situation of pure conflict where one player's gain is exactly equal to the other player's loss. If you add up the total gains of both players and subtract the total losses, the sum is always zero.
During the game, Player A attempts to maximize their payoff, while Player B attempts to minimize Player A's payoff (thereby maximizing their own).
What is the Minimax Theorem?
The Minimax Theorem states that in any finite, two-player, zero-sum game, there exists a specific numerical value (denoted as \(V\)) and an optimal strategy for each player such that:
- Player A can guarantee an expected payoff of at least \(V\), regardless of what Player B does.
- Player B can guarantee that Player A's expected payoff is no more than \(V\), regardless of what Player A does.
The name "Minimax" comes from the convergence of two objectives: Player A wants to maximize their minimum possible gain (Maximin), and Player B wants to minimize the maximum possible loss they can suffer (Minimax). The theorem proves that the Maximin value is always equal to the Minimax value.
Pure vs. Mixed Strategies
If players are restricted to making a single, deterministic choice—known as a pure strategy—the Minimax Theorem does not always hold.
Consider the game of Rock-Paper-Scissors. If you choose the pure strategy of always playing Rock, your opponent will quickly realize this and always play Paper, guaranteeing your loss. There is no single deterministic move that is optimal.
To solve this, von Neumann introduced the concept of a mixed strategy. A mixed strategy assigns a probability to each available pure strategy. Instead of choosing one fixed action, a player randomly selects an action based on a specific statistical distribution. In Rock-Paper-Scissors, the optimal mixed strategy is to play each option randomly one-third of the time.
How the Theorem Guarantees an Optimal Mixed Strategy
The Minimax Theorem guarantees an optimal mixed strategy by shifting the mathematics of the game from discrete choices to continuous probabilities. It achieves this guarantee through three main mechanisms:
1. Elimination of Exploitation A mixed strategy conceals a player's intentions. Because the player's next move is determined by a probability distribution rather than a predictable pattern, the opponent cannot exploit their behavior. By mathematically tuning these probabilities, a player can make themselves completely indifferent to whichever strategy the opponent chooses.
2. Convexity and the Saddle Point When players use probabilities (which range continuously from 0 to 1), the set of all possible expected payoffs forms a continuous, geometric shape known as a convex set. Von Neumann applied topology—specifically Brouwer's fixed-point theorem and the properties of convex sets—to prove that the payoff surfaces of both players must intersect at a specific point.
This intersection is called a saddle point (later generalized by John Nash as a Nash Equilibrium). At the saddle point, the highest floor Player A can build under their winnings meets the lowest ceiling Player B can place over their losses.
3. Security Against the Worst-Case Scenario The theorem guarantees optimality because it assumes your opponent is infinitely rational and trying to do maximum damage to your payoff. By calculating the probability distribution that equalizes the expected payoff across all of the opponent's possible counter-moves, a player locks in the value \(V\).
Once a player adopts this optimal mixed strategy, the opponent's actions become mathematically irrelevant to the expected outcome. If the opponent deviates from their own optimal strategy, they can only do worse, never better. Thus, the Minimax Theorem proves that in a finite zero-sum conflict, there is always a mathematically perfect way to play.