Decisions against an opponent
A plan optimized for one assumed response can fail when the other decision-maker chooses differently. A finite two-player zero-sum game models this tension: a matrix entry is the payoff to the row player, while the column player pays the same amount. The row player maximizes payoff and the column player minimizes it. The matrix is fixed and known; mixed strategies describe independent random choices made without observing the opponent's realized action.
This unit connects game guarantees to the previously developed linear-programming duality.
From a guaranteed payoff to an LP
A row strategy has and . Against pure column , its expected payoff is . If every one of these values is at least , then the same is true against any column mixture : its payoff is a convex combination . Hence the row player can choose the best guarantee by solving
The scalar is unrestricted in sign: a game with all negative entries has a negative value. It is an error to impose without changing the problem. Similarly, a column mixture with guarantees payoff at most to the row player if . The column player minimizes under these inequalities.
Proof X-ray
Why pure responses suffice for a guarantee
Fix . For a mixed response , the expected payoff is , a weighted average of the pure-column payoffs. It cannot be smaller than their minimum, and a pure column attaining that minimum realizes it. The same argument with rows and a maximum applies to the column player's guarantee. No independence between different plays, and no claim that an opponent chooses randomly, is needed for this single-play bound.
A certificate, and when equality exists
For any feasible row guarantee and column guarantee , multiply by and by . Since both strategies sum to one,
Thus matching feasible guarantees prove both strategies optimal, without enumerating all mixed strategies. Finite LP strong duality applies to the two displayed programs: they are feasible, the row objective is bounded above and the column objective is bounded below by finite matrix-entry bounds. It gives optimal strategies with equal guarantees, called the value of the finite game. This conclusion concerns expected payoff in the stated simultaneous zero-sum model; it is not a claim that every individual play pays exactly that amount.
Worked example
Let . Write . Its expected payoffs against the two pure columns are and . The worst response gives , maximized at their intersection , with value : for the minimum is , while for it is .
For the column player take . Against either row, the expected payoff is . The row strategy guarantees at least against both columns; the column strategy guarantees at most against both rows. The matching bounds certify the value. A pure row alone guarantees zero, illustrating why allowing a mixture can improve the worst-case guarantee.
Counterexample mode
A mixed strategy does not promise a fixed outcome
With the certified strategies above, the four possible matrix entries are still , , , and . Their probabilities are products of the row and column probabilities, and the expected payoff is . Observing one payoff of zero does not contradict the guarantee: the guarantee is about expectation over the row player's random choice against each allowed opponent response.
A safe transformation
Adding the same constant to every entry adds to the payoff of every pair of mixed strategies, because both probability vectors sum to one. It shifts the value by and leaves optimal strategies unchanged. This can make payoffs positive for a chosen formulation, but the shift must be subtracted when reporting the original value. Adding different constants to different rows or columns generally changes strategic incentives and is not the same transformation.
Exercises
Quick check
(For above and , find the worst pure-column payoff. Is this strategy optimal?)
Solution · Answer
The two payoffs are and ; the worst is , so it is not optimal.
Quick check
(Verify both pure-row payoffs against and use them to certify an upper bound.)
Solution · Answer
The first row gives and the second gives . Every row mixture is their weighted average, so the column strategy gives an upper bound .
Quick check
(Add to every entry of . State the new value and one pair of optimal strategies.)
Solution · Answer
The value is ; both strategies remain .
Quick check
(For , find a pure-strategy certificate for the value. Why must the row LP permit negative ?)
Solution · Answer
Row one guarantees , while column two holds both rows to at most . The value is ; requiring would incorrectly remove this feasible game guarantee.