Zero-Sum Games & the Minimax Theorem

Zero-sum games capture pure competition: whatever one player gains, the other loses exactly. This structure is restrictive enough to admit a clean fundamental theorem — von Neumann's minimax theorem — yet rich enough to model everything from chess endgames to GAN training. The theorem's proof through linear programming duality makes it one of the most elegant connections between game theory and convex optimization.

Concepts

In chess, when you choose a move, your opponent will respond with the move that hurts you most. Then you respond with the move that hurts them most given their choice. Zero-sum games formalize this alternating reasoning: your gain is their loss exactly, so there is no room for mutually beneficial deals. Von Neumann's minimax theorem says this adversarial recursion always has a definite answer — a unique value that both players can guarantee simultaneously, no matter how deep the reasoning goes.

Zero-Sum Games and Matrix Representation

A two-player zero-sum game satisfies $u_1(a) + u_2(a) = 0$ for all action profiles. Since payoffs sum to zero, the game is fully described by the row player's payoff matrix $A \in \mathbb{R}^{m \times n}$, where $m = |A_1|$ and $n = |A_2|$. Row player maximizes, column player minimizes.

Under mixed strategies $x \in \Delta^m$ (row) and $y \in \Delta^n$ (column), the expected payoff to the row player is $x^\top A y$. The game reduces to:

$\max_{x \in \Delta^m}\ \min_{y \in \Delta^n}\ x^\top A y \quad \text{vs.} \quad \min_{y \in \Delta^n}\ \max_{x \in \Delta^m}\ x^\top A y.$

The Minimax Theorem (von Neumann, 1928)

For any finite matrix game $A$:

$\max_{x \in \Delta^m}\ \min_{y \in \Delta^n}\ x^\top A y = \min_{y \in \Delta^n}\ \max_{x \in \Delta^m}\ x^\top A y = v$

where $v$ is called the value of the game. The minimax equals the maximin — the order of optimization does not matter. Both players have optimal mixed strategies that achieve $v$ simultaneously.

The equality of maximin and minimax is not obvious — in general, $\max \min \leq \min \max$ (weak duality), and the gap can be strict. The zero-sum condition is what forces the gap to close: the row player's maximin LP and the column player's minimax LP are LP duals of each other, and LP strong duality says their optima coincide. Without zero-sum, the two players' optimization problems are not dual, and the game value need not exist.

Proof via LP Duality

The row player's optimization can be written as a linear program. Let $v$ be the guaranteed payoff:

Primal (row player):

Dual (column player):

Strong LP duality (which follows from the separating hyperplane theorem for convex sets) gives primal optimum $=$ dual optimum, i.e., maximin $=$ minimax $= v$. The dual variables $(y^*, w^*)$ are exactly the column player's optimal mixed strategy and the game value. LP duality is thus precisely the minimax theorem.

Saddle Points

A pair $(x^*, y^*)$ is a saddle point if

$x^\top A y^* \leq x^{*\top} A y^* \leq x^{*\top} A y \quad \forall x \in \Delta^m,\ y \in \Delta^n.$

Saddle points in zero-sum games correspond exactly to Nash equilibria. The minimax theorem guarantees at least one saddle point exists in mixed strategies. In pure strategies, saddle points exist only when $\max_i \min_j A_{ij} = \min_j \max_i A_{ij}$ — otherwise mixing is required.

Alpha-Beta Pruning

In two-player zero-sum perfect-information games (chess, Go), the minimax value can be computed by full tree search, but the tree is exponential in depth. Alpha-beta pruning maintains bounds $[\alpha, \beta]$ — the best values guaranteed for MAX and MIN respectively — and prunes subtrees that cannot affect the root value:

• At a MAX node: if any child value $\geq \beta$, prune remaining children (MIN would never allow this).
• At a MIN node: if any child value $\leq \alpha$, prune remaining children (MAX would never choose this path).

With optimal move ordering, alpha-beta reduces the branching factor from $b$ to $\sqrt{b}$, enabling search to twice the depth for the same computation.

Worked Example

Rock-Paper-Scissors

The payoff matrix (row player's perspective, encoding win=1, loss=-1, draw=0):

$A = \begin{pmatrix} 0 & -1 & 1 \\ 1 & 0 & -1 \\ -1 & 1 & 0 \end{pmatrix}$

Claim: $x^* = y^* = (1/3, 1/3, 1/3)$ is the unique Nash equilibrium with value $v = 0$.

Verification. Under $y^* = (1/3, 1/3, 1/3)$, the row player's expected payoff from Rock is $(1/3)(0) + (1/3)(-1) + (1/3)(1) = 0$, and by symmetry Scissors and Paper also give 0. So the row player is indifferent — any mixed strategy is a best response, including $x^* = (1/3, 1/3, 1/3)$. Symmetric argument applies for the column player. Value $v = 0$: the game is fair.

Solving a 2×3 Matrix Game via LP

Consider:

$A = \begin{pmatrix} 3 & 1 & 0 \\ 0 & 2 & 4 \end{pmatrix}$

Row player primal (let $x_1 = p$, $x_2 = 1-p$):

Binding constraints determine $p$. Setting $3p = 2 - p$ gives $p = 1/2$, $v = 3/2$. Check: $4(1-1/2) = 2 > 3/2$ — column 3 is not in support. The row player's optimal mix is $(1/2, 1/2)$ with value $v = 3/2$. The column player mixes only over columns 1 and 2; solving $3q_1 + q_2 = 2q_2$ (both columns in support must give equal payoff to row player's mix) yields $q_1 = 1/4$, $q_2 = 3/4$.

Alpha-Beta on a Depth-3 Tree

Consider a game tree where the root is a MAX node at depth 0, two MIN nodes at depth 1, four MAX nodes at depth 2, and eight leaves. Leaves (left to right): 3, 5, 2, 9, 1, 7, 4, 6.

• Depth-2 MAX nodes compute: max(3,5)=5, max(2,9)=9, max(1,7)=7, max(4,6)=6.
• Left MIN node: evaluates first child (value 5), sets $\beta = 5$. Evaluates second child (value 9). Since $9 > 5$, MIN will never choose 9 — but both children needed here. Left MIN value = min(5,9) = 5.
• Root MAX: after left child gives 5, sets $\alpha = 5$.
• Right MIN node: evaluates first child (value 7). Since $7 \geq \alpha = 5$, MIN will choose $\leq 7$. Evaluates second child (value 6). Right MIN = min(7,6) = 6. Root MAX = max(5,6) = 6.

In this example no pruning occurred because values were favorable. With worse ordering, the second depth-2 subtree under right MIN could have been pruned if its first leaf were $\leq 5$.

Connections

Where Your Intuition Breaks

The minimax theorem guarantees that optimal mixed strategies exist — but it says nothing about convergence. In GAN training, $G$ and $D$ run simultaneous gradient descent on $\min_G \max_D V(D,G)$. The saddle point exists (von Neumann guarantees it), but simultaneous gradient descent does not converge to saddle points in zero-sum games unless the objective is convex-concave. In Rock-Paper-Scissors, gradient descent cycles perpetually around the $(1/3,1/3,1/3)$ equilibrium without ever reaching it. GAN training instability is exactly this: the minimax theorem is a theorem about existence, not dynamics. The gap between "a Nash equilibrium exists" and "gradient descent finds it" is where all the difficulty lives.