From a Payoff Matrix to Two Linear Programs
In a finite zero-sum game, one player’s gain is the other player’s loss. Fix the convention that the row player receives the payoff and tries to maximize it, while the column player tries to minimize it. Let \(A\) be the \(m\times n\) payoff matrix, where \(A_{ij}\) is the payoff to the row player when row \(i\) and column \(j\) are chosen. A mixed strategy is a probability vector: write \(x\in\mathbb{R}^m\) for the row player and \(y\in\mathbb{R}^n\) for the column player. Their expected payoff is \(x^T A y\).
The row player wants a strategy whose expected payoff is high no matter which column is chosen. The column player wants a strategy that keeps the payoff low no matter which row is chosen. These guarantees can be expressed with linear inequalities. The key is that a guarantee against every pure action of the opponent also holds against every mixture of those actions: an average of numbers each at least \(v\) is at least \(v\), and an average of numbers each at most \(w\) is at most \(w\).
The row constraints say that the payoff against each pure column is at least \(v\); the objective makes this guaranteed payoff as large as possible. The column constraints say that the payoff from each pure row against \(y\) is at most \(w\); the objective makes this upper bound as small as possible. The normalization and nonnegativity constraints make \(x\) and \(y\) probability vectors.
Why These Programs Are Dual
The two formulations are not merely similar ways to compute a game. They are a primal-dual pair of linear programs. One way to see the dual constraints emerge is to form an upper bound on the row player’s objective. Take any \(y\ge0\) with \(\mathbf{1}_n^T y=1\), and any real \(w\) such that \(Ay\le w\mathbf{1}_m\). For a feasible row strategy \(x\), the expression \(v+y^T(A^T x-v\mathbf{1}_n)+w(1-\mathbf{1}_m^T x)\) is at least \(v\): the first added term is nonnegative, and the last is zero. Rearranging gives \(v\le x^TAy\le w\). Thus every feasible column pair \((y,w)\) supplies an upper bound on every feasible row value.
This construction also explains the dual objective. In the expression above, the coefficient of \(v\) is \(1-\mathbf{1}_n^T y\), so it vanishes when \(y\) is a probability vector. The coefficient of each nonnegative component of \(x\) is the corresponding component of \(Ay-w\mathbf{1}_m\), which is nonpositive under the column constraints. The resulting bound is \(w\), and minimizing that bound gives the column program.
For the first claim, multiply the row player’s payoff guarantees by the probabilities in \(y\). Since \(y_j\ge0\) and its entries sum to one,
The last inequality follows because each \((Ay)_i\le w\), while \(x_i\ge0\) and \(\sum_i x_i=1\). This proves weak duality, including the direction of the inequality: a feasible row guarantee cannot exceed a feasible column upper bound.
For equality of the optimal values, use the strong duality theorem of linear programming: if a finite-dimensional linear program and its dual are feasible and have finite optimal values, both optima are attained and are equal. The row program is feasible, for example by taking any probability vector \(x\) and choosing \(v\) no greater than the smallest component of \(A^Tx\). Its objective is bounded above by \(\max_{i,j}A_{ij}\), because every payoff against a column is an average of entries of \(A\). The column program is feasible by taking any probability vector \(y\) and choosing \(w\) no smaller than the largest component of \(Ay\); its objective is bounded below by \(\min_{i,j}A_{ij}\). The programs displayed above are a primal-dual pair, so strong duality applies. Their optimal values therefore agree and are attained. Together with the payoff interpretation of the constraints, this common optimum is the game value. \(\square\)
Worked Strategy Certificates
A useful practical consequence is that exact optimality can often be established without solving every constraint algebraically. A feasible row strategy with guarantee \(v\) and a feasible column strategy with upper bound \(w\) certify that the game value lies between \(v\) and \(w\). If \(v=w\), weak duality forces both strategies to be optimal.
Worked Example: Matching Pennies
Consider the payoff matrix \(\begin{pmatrix}1&-1\\-1&1\end{pmatrix}\). Let \(p\) be the probability that the row player chooses row 1, so \(x=(p,1-p)^T\). The payoffs against columns 1 and 2 are respectively \(p-(1-p)=2p-1\) and \(-p+(1-p)=1-2p\). The row player’s program is therefore to maximize \(v\) subject to \(v\le2p-1\), \(v\le1-2p\), and \(0\le p\le1\). At \(p=1/2\), both payoffs equal zero, so \(v=0\) is feasible. No \(p\) can give a positive guarantee: the two column payoffs sum to zero, so their minimum is at most zero.
Now let \(q\) be the probability that the column player chooses column 1. The payoffs for rows 1 and 2 against \(y=(q,1-q)^T\) are \(2q-1\) and \(1-2q\). At \(q=1/2\), both equal zero, so \(w=0\) is feasible for the column program. The feasible row and column strategies have matching bounds, \(v=w=0\). By weak duality and strong duality, the value is zero, and both equal-probability strategies are optimal.
Worked Example: Unequal Payoffs in a Two-by-Two Game
Let \(A=\begin{pmatrix}4&0\\1&3\end{pmatrix}\). If the row player chooses row 1 with probability \(p\), the payoffs against columns 1 and 2 are \(4p+1(1-p)=1+3p\) and \(0p+3(1-p)=3-3p\). The row program maximizes \(v\) subject to \(v\le1+3p\), \(v\le3-3p\), and \(0\le p\le1\). Choosing \(p=1/3\) makes both bounds equal to \(2\), so the row player guarantees \(v=2\).
For the column player, let \(q\) be the probability of column 1. The payoffs for rows 1 and 2 are \(4q\) and \(q+3(1-q)=3-2q\). The column program minimizes \(w\) subject to \(4q\le w\), \(3-2q\le w\), and \(0\le q\le1\). At \(q=1/2\), both payoffs equal \(2\), so \(w=2\) is feasible. Since the feasible strategies give the same bound, the game value is \(2\), with optimal strategies \(x=(1/3,2/3)^T\) and \(y=(1/2,1/2)^T\).
Worked Example: A Three-by-Two Game and a Redundant Row
Consider \(A=\begin{pmatrix}3&0\\0&2\\1&1\end{pmatrix}\). Write the row strategy as \(x=(x_1,x_2,x_3)^T\). The two column payoffs are \(3x_1+x_3\) and \(2x_2+x_3\), so the row program requires both to be at least \(v\). Choose \(x=(2/5,3/5,0)^T\). The payoffs are \(3(2/5)=6/5\) and \(2(3/5)=6/5\), giving a feasible guarantee \(v=6/5\).
For a column strategy \(y=(q,1-q)^T\), the payoffs for the three rows are \(3q\), \(2(1-q)\), and \(1\). Choose \(q=2/5\). These are \(6/5\), \(6/5\), and \(1\), respectively, so every row payoff is at most \(w=6/5\). This column strategy and the row strategy give matching bounds. The value is \(6/5\), and both strategies are optimal. The third row is not used by this optimal row strategy; the certificate shows that its payoff against the optimal column mixture, \(1\), does not force the column player’s upper bound above \(6/5\).
Using Feasibility as a Certificate
The strategy interpretation makes linear programming useful beyond producing numerical answers. A proposed row strategy can be checked by calculating its payoff against each pure column and taking the smallest result. A proposed column strategy can be checked by calculating the payoff from each pure row and taking the largest result. These calculations give lower and upper bounds, respectively. If the bounds match, no unexamined strategy can improve either player’s position, because weak duality applies to every feasible pair.
State clearly which player receives \(A_{ij}\), so the directions of maximization and minimization are fixed.
For each column \(j\), require \((A^Tx)_j\ge v\), together with \(x\ge0\) and \(\mathbf{1}_m^Tx=1\).
For each row \(i\), require \((Ay)_i\le w\), together with \(y\ge0\) and \(\mathbf{1}_n^Ty=1\).
Verify every inequality using the proposed probability vectors. Matching feasible values certify the game value and the optimality of both strategies.
A common mistake is to reverse one set of inequalities. The row player maximizes a payoff guarantee, so every column payoff under \(x\) must be at least \(v\), not at most \(v\). The column player minimizes an upper bound, so every row payoff under \(y\) must be at most \(w\), not at least \(w\). Another mistake is to check only the opponent’s pure actions that appear likely to be chosen. A valid certificate must check every pure action; a mixed opponent can then be handled because its expected payoff is a probability-weighted average of those checked payoffs.
Check Your Understanding
Use the payoff convention that the row player maximizes the entries of \(A\).
- Explain why the row player’s constraint for column \(j\) is \((A^Tx)_j\ge v\).
- For any feasible pair \((x,v)\) and \((y,w)\), identify the two probability-weighted averages that prove \(v\le w\).
- What does a feasible row strategy with guarantee \(v=1.4\) establish about the game value?
- Suppose a feasible column strategy has upper bound \(w=1.4\) as well. What can be concluded?
- Why is it sufficient to check the column player’s upper-bound constraint against each pure row, rather than every possible mixed row strategy separately?