Zero-Sum Games
Motivation
A zero-sum game is a strategic interaction between two players in which one player’s gain is exactly the other’s loss. Chess, rock-paper-scissors, security games, and adversarial machine-learning settings (generator vs. discriminator in some formulations, robust optimization against an adversary) are all zero-sum.
The clean structure of zero-sum games allowed John von Neumann to prove the first major result of game theory, the minimax theorem (Neumann 1928): every finite zero-sum game has a well-defined value that both players can guarantee, even though they choose strategies independently. Both the value and the optimal strategies are computable by linear programming, and the LP-duality version of the minimax theorem is itself a celebrated illustration of LP duality.
This article describes the structure; the proof is in the minimax theorem article.
Setup
A two-player zero-sum game in normal form is specified by a payoff matrix \(M \in \mathbb{R}^{m \times n}\):
- The row player chooses a row \(i \in \{1, \dots, m\}\).
- The column player chooses a column \(j \in \{1, \dots, n\}\).
- The row player gains \(M_{ij}\); the column player loses the same amount.
The row player wants to maximize the payoff; the column player wants to minimize it.
Pure strategies
A pure strategy is a deterministic choice of a single row (or column).
If both players commit to pure strategies, the row player guarantees \[ \underline V_{\text{pure}} = \max_i \min_j M_{ij}, \] and the column player can guarantee \[ \overline V_{\text{pure}} = \min_j \max_i M_{ij}. \]
In general \(\underline V_{\text{pure}} \le \overline V_{\text{pure}}\), and the inequality is often strict — in rock-paper-scissors, \(\underline V_{\text{pure}} = -1\) and \(\overline V_{\text{pure}} = +1\). Pure strategies are not enough.
Mixed strategies
A mixed strategy for the row player is a probability distribution \(x \in \Delta^m = \{x \ge 0 : \sum_i x_i = 1\}\) over rows. Similarly \(y \in \Delta^n\) for the column player.
The expected payoff under mixed strategies is \[ x^\top M y = \sum_{i, j} x_i M_{ij} y_j. \]
The row player wants to maximize \(\min_y x^\top M y\); the column player wants to minimize \(\max_x x^\top M y\).
The value of the game
Theorem (minimax) (Neumann 1928). For any payoff matrix \(M\): \[ \max_{x \in \Delta^m} \min_{y \in \Delta^n} x^\top M y \;=\; \min_{y \in \Delta^n} \max_{x \in \Delta^m} x^\top M y. \]
The common value \(V\) is the value of the game.
Strategies that achieve the maxima/minima are called optimal mixed strategies, and the pair \((x^*, y^*)\) is a Nash equilibrium.
The proof appears in the minimax theorem article and follows from LP duality applied to the LP that computes the row player’s optimal strategy.
Solving zero-sum games via LP
The row player’s problem — find \(x \in \Delta^m\) maximizing \(\min_y x^\top M y\) — can be written as an LP. The inner minimization over \(y\) is achieved at a vertex of the simplex \(\Delta^n\), i.e., a pure column \(j\), so \(\min_y x^\top M y = \min_j (x^\top M)_j\). Introducing a scalar \(v\) for this minimum:
\[ \begin{aligned} \max_{x, v} \quad & v \\ \text{s.t.} \quad & (x^\top M)_j \ge v \quad \forall j \\ & \sum_i x_i = 1, \quad x \ge 0. \end{aligned} \]
This LP has \(m + 1\) variables and \(n + m + 1\) constraints. Its dual is the column player’s LP, with optimal value also \(V\) — strong duality is precisely the minimax theorem.
Examples
Rock-paper-scissors. \[ M = \begin{pmatrix} 0 & -1 & 1 \\ 1 & 0 & -1 \\ -1 & 1 & 0 \end{pmatrix}. \] By symmetry \(V = 0\), with optimal strategy \(x^* = y^* = (1/3, 1/3, 1/3)\).
Matching pennies. \[ M = \begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix}. \] \(V = 0\), \(x^* = y^* = (1/2, 1/2)\).
A 2x2 with non-trivial mixed equilibrium. \[ M = \begin{pmatrix} 3 & -1 \\ 0 & 2 \end{pmatrix}. \] The row player’s optimal mixed strategy makes the column player indifferent between columns. Solving, \(x^* = (1/3, 2/3)\), \(V = 4/3\).
Example: solving the 2×2 non-trivial game via LP
For the game \(M = \begin{pmatrix} 3 & -1 \\ 0 & 2 \end{pmatrix}\) the row player’s LP is:
\[ \max v \quad \text{s.t.}\quad 3x_1 + 0x_2 \ge v,\quad {-x_1} + 2x_2 \ge v,\quad x_1 + x_2 = 1,\quad x_1, x_2 \ge 0. \]
At optimality both column constraints are tight (the column player is indifferent):
\[ 3x_1 = v \quad \text{and} \quad -x_1 + 2x_2 = v. \]
Substituting \(x_2 = 1 - x_1\) and equating: \(3x_1 = -x_1 + 2(1 - x_1)\), giving \(3x_1 = 2 - 3x_1\), so \(x_1 = 1/3\), \(x_2 = 2/3\), and \(v = 3 \cdot 1/3 = 1\). Check: \(-1/3 + 2 \cdot 2/3 = -1/3 + 4/3 = 1 = v\) ✓.
The column player’s LP (dual) yields \(y_1 = 1/3\), \(y_2 = 2/3\) symmetrically, also achieving value \(1\). Strong duality confirms \(V = 1\).
Interpretation. If the row player always chose row 1 (value \(3\)), the column player would switch to column 2 (value \(-1\)). The mixed strategy \(x^* = (1/3, 2/3)\) removes this incentive — the column player gets the same payoff of \(1\) regardless of which column it picks.
Beyond two-player zero-sum
The minimax theorem is special to two-player zero-sum games. In non-zero-sum or multi-player games, the right solution concept is Nash equilibrium, which always exists in mixed strategies (Nash 1951) but is much harder to compute (PPAD-complete). Zero-sum is the rare case where game theory is computationally tractable and provides a single clean number — the value — to summarize the strategic situation.
Applications
- Online learning: many online learning algorithms can be analyzed by viewing the algorithm vs. nature as a zero-sum game; multiplicative weights is the canonical strategy for the player.
- Robust optimization: minimize the worst-case cost over an adversarial choice of the data — exactly a zero-sum game between optimizer and adversary.
- Generative adversarial networks: training is set up as a zero-sum game between the generator and discriminator (although in practice the equilibrium is harder to compute than in finite games).
- Security games: an attacker chooses targets, a defender allocates resources; many real-world deployments use computed game-theoretic strategies.