Minimax

Minimax is a decision rule for minimizing the maximum possible loss, and the associated theorem — proved by John von Neumann in 1928 — is the mathematical foundation of zero-sum game theory. The minimax theorem states that in any finite two-player zero-sum game, there exists a pair of mixed strategies (probability distributions over pure actions) such that each player's expected payoff is maximized given the other's strategy. This is not merely a computational result; it is a structural claim about rational conflict: even under conditions of pure opposition, orderly strategic behavior is possible.

The theorem's limitations are as important as its power. It applies only to two-player zero-sum games — situations where one player's gain is exactly the other's loss. Most real strategic interactions are not zero-sum: trade, cooperation, and coordination all produce mutual gains that minimax reasoning cannot capture. The displacement of minimax by Nash equilibrium as the organizing concept of game theory reflected this recognition. Yet minimax persists in statistical decision theory, robust control, and adversarial machine learning, where the assumption of an intelligent opponent with opposite interests remains apt. The rule's persistence across domains suggests that zero-sum reasoning is not a special case but a baseline — the floor beneath which strategic rationality cannot fall.The minimax algorithm is the computational instantiation of the minimax theorem. Where the theorem guarantees the existence of optimal mixed strategies, the algorithm searches for them. The theorem is a statement about equilibrium; the algorithm is a statement about search. The gap between them — between existence and computability — is precisely the complexity-theoretic gap between the PPAD-completeness of finding a Nash equilibrium and the exponential complexity of exhaustive search. The theorem is a promise; the algorithm is the cost of redeeming it.

The minimax theorem is sometimes invoked as a proof that optimal play exists in chess, Go, and other games. This is a category error. Existence is not computability, and computability is not practicality. The theorem tells us that the game has a value; it does not tell us how to find it. The algorithm tells us how to search; it does not tell us that the search will complete. The intelligence of a game-playing system lies precisely in the gap between these two statements — in the heuristics, approximations, and bounded-rationality structures that make the intractable tractable.