12.3 Two-person zero-sum games
In a two-person zero-sum game, a row player chooses one of \(m\) strategies and a column player one of \(n\), simultaneously, and the column player pays the row player \(a_{ij}\). The row player can guarantee at least \(\max _i\min _ja_{ij}\) (the maximin), and the column player can hold the loss to at most \(\min _j\max _ia_{ij}\) (the minimax); always maximin \(\leq \) minimax. If they are equal, the game has a saddle point, an entry that is the smallest in its row and the largest in its column, and both players should play it.
Most games have no saddle point, and the players must randomise. A mixed strategy for the row player is a probability vector \(p\); against the column player’s mixed strategy \(q\) the expected payoff is \(p^{\mathsf T}Aq\). Against a fixed \(p\), the column player’s best reply is a pure strategy, so the row player can guarantee \(\min _j(A^{\mathsf T}p)_j\).
Theorem 12.3.1 (Minimax theorem; von Neumann, 1928). For every matrix \(A\), \[ \max _p\min _qp^{\mathsf T}Aq = \min _q\max _pp^{\mathsf T}Aq , \] the maxima and minima being over probability vectors. The common value is the value of the game, and strategies attaining the outer optima are optimal strategies.
Proof. The row player’s problem is the LP: maximise \(v\) subject to \(\sum _ip_ia_{ij} \geq v\) for all \(j\), \(\sum _ip_i = 1\), \(p \geq 0\) (\(v\) free). The column player’s problem is: minimise \(w\) subject to \(\sum _ja_{ij}q_j \leq w\) for all \(i\), \(\sum _jq_j = 1\), \(q \geq 0\). Writing out the dual of the first by the rules of the section on duality (a free variable \(v\) gives an equality constraint, the equation \(\sum p_i = 1\) a free variable) gives exactly the second. Both are feasible and bounded (any pure strategy is feasible, and \(v\), \(w\) lie between \(\min a_{ij}\) and \(\max a_{ij}\)), so by strong duality (Theorem 5.2.2) their optimal values are equal. The first value is \(\max _p\min _jp^{\mathsf T}Ae_j = \max _p\min _qp^{\mathsf T}Aq\) and the second \(\min _q\max _i(Aq)_i = \min _q\max _pp^{\mathsf T}Aq\). □
So every finite zero-sum game is solved by linear programming, and the optimal strategies are the primal and dual solutions (Software 12.4.3). Complementary slackness says that a pure strategy used with positive probability earns exactly the value against the opponent’s optimal strategy, and one that would earn less is never used. For small games there are shortcuts:
- Dominance: a row whose entries are all no larger than those of another row (or of a mixture of rows) can be deleted, and likewise a column whose entries are all no smaller than another’s.
- \(2 \times 2\) games without a saddle point, \(A = \begin {pmatrix} a & b \\ c & d \end {pmatrix}\), have \(p_1 = \frac {d - c}{a - b - c + d}\), \(q_1 = \frac {d - b}{a - b - c + d}\) and value \(\frac {ad - bc}{a - b - c + d}\), found by making the opponent indifferent between its two strategies.
- \(2 \times n\) and \(m \times 2\) games are solved graphically: plot the payoff of each of the opponent’s pure strategies as a line in \(p_1\), and find the highest point of their lower envelope.
Example 12.3.2. The game \(A = \begin {pmatrix} 3 & -1 \\ -2 & 4 \end {pmatrix}\) has maximin \(-1\) and minimax \(3\): no saddle point. The formula gives \(p = (0.6, 0.4)\), \(q = (0.5, 0.5)\) and value \(\frac {12 - 2}{10} = 1\). The game \(\begin {pmatrix} 2 & -1 & 3 \\ -1 & 3 & -2 \\ 1 & 0 & 1 \end {pmatrix}\) has value \(\frac 57\), with optimal strategies \(p = q = (\frac 47, \frac 37, 0)\): the third row and the third column are never used, although neither is dominated by a single other row or column.
Games that are not zero-sum, in which the players’ interests partly coincide, need the concept of a Nash equilibrium (1950), a pair of strategies each a best reply to the other; such equilibria always exist in mixed strategies but need not be unique or efficient, as the prisoner’s dilemma shows.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.