Minimax theorem

The minimax theorem states that every finite two-player zero-sum game has a value: each player can choose a strategy guaranteeing the same expected payoff, even when strategies are randomized.

Zero-sum game: A game in which one player’s gain is exactly the other player’s loss. The theorem applies to this class of games.
Payoff matrix: A table listing the outcomes associated with each pair of actions in a game. Finite games can be represented by entries whose row and column choices determine payoffs.
John von Neumann: A mathematician who made foundational contributions to set theory, quantum mechanics, computing, and game theory. He proved the finite zero-sum minimax theorem in 1928.
Linear programming formulation of zero-sum games: A representation of a finite zero-sum game as linear programs for its players’ optimal strategies. It converts the theorem into a computational method for finding strategies and value.
Pure strategy: A strategy that selects one available action with certainty. The theorem may require randomization when no pure strategy pair guarantees its value.
Mixed strategy: A probability distribution over a player’s available actions in a game. Randomized strategies let each player secure the theorem’s guaranteed payoff.
Convex set: A set containing every line segment between any two of its points. Mixed strategies form a convex set of probability distributions.
Theory of Games and Economic Behavior: A 1944 book by John von Neumann and Oskar Morgenstern that established modern game theory. It developed the theorem’s role in the mathematical theory of strategic interaction.
Nash equilibrium: A strategy profile in which no player can improve their payoff by changing strategy alone. In two-player zero-sum games, minimax strategies form a Nash equilibrium.
Nash bargaining solution: A solution concept that selects an efficient agreement from a set of possible cooperative outcomes. Unlike minimax, it models mutually beneficial bargaining rather than opposing zero-sum payoffs.

Linked from 10 pages