Motivation
A decision can be predictable even when every action has some merit. In a zero-sum game, an opponent who knows a fixed action can choose a response that exploits it. Randomizing among actions can improve the guaranteed payoff. The mathematical question is not which random choice feels unpredictable, but which probability distribution gives the best guarantee against every opponent action.
Finite zero-sum games connect this question to linear programming. A mixed strategy is a probability vector, and a guarantee against each pure opponent action is a linear inequality. The equality of the players' best guarantees follows from linear-programming strong duality, which is stated as an external theorem here rather than proved from scratch.
Definitions
Definition 2.1.1
(Mixed strategies and expected payoff)
Let be a real payoff matrix with . The row player chooses a row and receives when the column player chooses column ; the column player pays that amount. A mixed row strategy is with and ; similarly a mixed column strategy is with and . Choices are sampled independently from these distributions. The expected payoff is .
Definition 2.1.2
(Guarantees and saddle points)
The row player's guaranteed payoff for is , because a probability-weighted average of column payoffs is at least their minimum and a minimizing pure column attains it. The column player's worst possible payment for is for the analogous reason. A pair is a saddle point in mixed strategies if for every feasible .
Theorems
Theorem 2.1.3
(Finite zero-sum minimax theorem)
For every finite real payoff matrix,
Both extrema are attained. Optimal strategies form a mixed saddle point, and the common value is the value of the game.
Theorem 2.1.4
(Certificates of optimality)
If feasible strategies and a real number satisfy for every column and for every row , then both strategies are optimal and the game value is .
Proof sketch or proof idea
Proof
(A weak bound, then linear-programming duality)
For any feasible , the row guarantee is at most , which is at most the column worst-case payment. Therefore the maximum row guarantee cannot exceed the minimum column worst-case payment. In particular, if the inequalities of the certificate hold, the expected payoff against is at least by the row inequalities and at most by the column inequalities. The two bounds meet, proving the certificate and saddle-point inequalities.
To establish existence in general, write the row player's optimization as the linear program
where is unrestricted in sign. Its dual is the column program
where is unrestricted. These programs are feasible: choose any pure strategy and a sufficiently low or high . Their objective values are bounded because the matrix has finitely many real entries. The finite-dimensional linear-programming strong-duality theorem says that these feasible bounded programs attain equal optima. The optimal constraints are precisely the certificate inequalities, giving the minimax equality and saddle point. This proof uses strong duality; it does not prove that theorem.
Proof X-ray
Why pure responses suffice for the constraints
For a fixed mixed strategy, expected payoff against a mixed response is a weighted average of payoffs against pure responses. Its minimum or maximum is attained at one of those pure responses. That is why the row program needs only one constraint per pure column and the column program one per pure row. The proof then has two parts: the chain row guarantee column payment gives the inequality between the two optima for free, and only the reverse inequality, together with attainment, is taken from linear-programming strong duality.
Worked examples
Worked example 2.1.5
(Matching pennies)
Let . Choosing either row with probability gives payoff zero against each pure column. The analogous column mixture gives payoff zero against each pure row. The certificate proves value zero. A fixed pure row has worst-case payoff , so randomization improves the row guarantee.
Worked example 2.1.6
(An asymmetric mixed equilibrium)
Let . If the row player chooses the first row with probability , its expected payoffs against the columns are and . Balancing them gives and guarantee . Choosing the first column with probability makes each pure row payoff . The certificate gives value .
Worked example 2.1.7
(A pure saddle point)
Let . This matrix has no pure saddle: the maximum row minimum is while the minimum column maximum is . In contrast, for , row two and column two give payoff . Row two guarantees at least and column two limits payment to at most , so the value is and no randomization is needed.
Common mistakes
Counterexample mode
A distribution is not a promise of a realized payoff
In matching pennies, equilibrium expected payoff is zero, but each realized play pays either or . The value describes an expectation and a worst-case guarantee over opponent strategies, not the outcome of every individual play.
Common mistake
(The minimax theorem is specific to finite two-player zero-sum games)
The minimax theorem concerns finite two-player zero-sum games. It does not assert that arbitrary multi-player or non-zero-sum games have the same value or that every strategy profile is an equilibrium. The independence of the two players' random choices is part of the product-distribution model used for .
Reading the linear programs
The row variable is a lower bound on the expected payoff against every pure column. The inequality indexed by column is . Maximizing chooses the best guaranteed lower bound. The row player does not choose the opponent's column; the constraints ensure the guarantee holds for all of them. Likewise, the column variable is an upper bound on the payoff against every pure row, and the column player minimizes that upper bound.
Common mistake
(Forcing the value to be nonnegative)
The variables and are allowed to be negative. This matters when every matrix entry is negative: for a one-by-one matrix , the value is . Requiring would make the row program infeasible even though the game is perfectly well-defined. Probability variables remain nonnegative and sum to one; the sign restriction on payoffs is a separate matter.
The duality step can also be checked through the Lagrangian. Associate a nonnegative multiplier with each row constraint . For the supremum over unrestricted to be finite, the multipliers must sum to one. The remaining supremum over row probability vectors is , whose upper bound is represented by . Minimizing this expression yields the column program. Strong duality supplies equality of the optimum values and attainment; weak duality alone gives only the inequality between them.
Worked example 2.1.8
(A negative-valued game)
Consider the one-by-two matrix . The row player has no choice and its guaranteed payoff is . The column player chooses the second column and ensures payment at most . These strategies certify value . The column player is minimizing the row payoff, so a more negative entry is preferable to it under this sign convention.
Concept lensGeometric
The value as the peak of a lower envelope
For two rows write . Each column gives a line , and the guarantee is the pointwise minimum of these lines, a concave piecewise-linear function on . The value is its highest point. For the lines are and ; the minimum peaks where they cross, at , with height .
Support and indifference
At an equilibrium, every pure action used with positive probability must be a best response to the opponent's equilibrium mixture. To prove this for the row player, suppose is optimal and some row used by gives strictly less than the value. Every row payoff against is at most the value by the column certificate. Their weighted average under would then be strictly below the value, contradicting the saddle-point payoff. The analogous argument shows that every column used with positive probability by has payoff exactly the value against .
Common mistake
(Indifference alone does not certify optimality)
This necessary condition explains the balancing calculation in the asymmetric example. Both columns are used at the displayed equilibrium, so they must give the same payoff against the row mixture; solving finds the candidate. But indifference alone is not a complete certificate. One must check nonnegative probabilities, total probability one, and all pure-action inequalities, including actions assigned probability zero. In larger games, balancing only a chosen pair of actions can miss an outside action that improves a player's response.
For example, if a third column with payoffs is added to the asymmetric matrix, the old row mixture still balances the first two columns at , but the third column yields . It is therefore not a guarantee of against the expanded game. The best-response inequalities, rather than the balancing equation alone, determine whether a proposed mixture is optimal.
A useful transformation
Adding a constant to every matrix entry shifts every expected payoff by , because probability weights sum to one. Thus the value increases by while the sets of optimal strategies remain unchanged. Multiplying every entry by a positive constant scales the value by that constant and also preserves optimal strategies. Multiplication by a negative constant reverses preference order and requires changing which player maximizes or minimizes; it cannot be treated as an ordinary positive rescaling.
This shift can make a numerical example easier to inspect, but it cannot be silently ignored in the final value. For instance, adding to the one-by-two example changes its value from to zero. The optimal column remains the second one. The transformation is valid for every mixed pair, not merely for the equilibrium pair, because .
Pure and mixed guarantees
The maximum of row minima is the best guarantee if the row player is restricted to a pure action. The minimum of column maxima is the column player's corresponding pure upper bound. If they meet at an entry, that row and column form a pure saddle point. If they differ, no pure saddle exists, but the finite minimax theorem still supplies mixed optimal strategies. The matching-pennies example has pure lower and upper bounds and , while its mixed value is zero.
A pure saddle certificate is particularly easy to check: the selected entry must be a minimum in its row and a maximum in its column. The row player then guarantees at least that entry by playing its row, and the column player caps the payoff at the same entry by playing its column. Ties are harmless and may create several pure saddle points. These row and column comparisons follow the convention that the row player maximizes and the column player minimizes; reversing the players' objectives reverses the comparisons.
The value is a guarantee against any mixed response chosen independently of the player's randomization. It does not require the opponent to use an optimal strategy. If the row player uses an optimal strategy, any opponent distribution gives expected payoff at least the value; against an optimal column strategy it gives exactly the value. This distinction helps interpret the certificate as a robust guarantee rather than a prediction that both players will actually randomize optimally.
Verifying a proposed solution
A practical calculation can be checked without solving the linear programs again. First verify that each probability vector has nonnegative entries summing to one. Next compute every component of and every component of . If the minimum of the former equals the maximum of the latter, their common number is the value and both vectors are optimal. The equality gives two-sided evidence: no row strategy can guarantee more against the displayed column mixture, and no column strategy can force less against the displayed row mixture.
Approximate calculations need a corresponding qualification. If the row strategy guarantees at least and the column strategy caps the payoff at , then and the true value lies between them. When the bounds do not coincide, they give an interval rather than an exact value. The width measures the remaining certificate gap; numerical rounding must be included before declaring the two numbers equal.
A mixed saddle point also makes the quantifiers explicit. The row inequality must hold for every possible column distribution, and the column inequality for every possible row distribution. Checking only the payoff of the proposed pair does not establish either assertion. The pure-response inequalities are a finite way to verify the universal conditions because every mixed response is a convex combination of pure responses.
Summary
A mixed strategy is a probability distribution over pure actions. Guarantees against all pure responses become linear constraints. Strong duality equates the best row guarantee and the best column upper bound, while matching feasible bounds provide a directly checkable optimality certificate.
Exercises
Quick check
(For matching pennies, calculate the payoff of the uniform row mixture against the first pure column.)
Use the entries of the first column.
Solution · Answer
The payoff is .
Quick check
(For , verify the two row payoffs against column mixture .)
Multiply each row by the column mixture.
Solution · Answer
The first row yields and the second yields , so neither exceeds .
Quick check
(For , verify that row two guarantees and column two caps payoff at .)
Take the row minima and the column maxima.
Solution · Answer
Row two pays either or , so its minimum is . Column two pays either or , so its maximum is . The certificate applies.
Quick check
(Why does a guarantee against every pure column imply the same guarantee against every mixed column?)
Write the mixed payoff as a weighted average.
Solution · Answer
The payoff against a mixed column is a convex combination of the pure-column payoffs. If each term is at least , their weighted average is also at least .