The row player's problem — choose a mixture maximising the worst case — is a linear programme, the column player's is precisely its dual, and so strong duality is the minimax theorem: the best guaranteed payoff equals the least enforceable loss, and the common optimum is the value of the game. A pure strategy is exploitable and a mixture is not, and the gap between the best pure guarantee and the value is exactly what mixing buys.
Core ideas
One hard idea: the two players are solving the same linear programme from opposite sides. Everything the minimax theorem says is what strong duality already said.
The worst case over the opponent's choices is a minimum of linear functions, which is not linear — so introduce a variable v for it and require v to be at most the expected payoff against every single column. Maximising v then maximises the worst case, and every constraint is linear. That substitution is the entire modelling step.
Take the dual of the row player's programme and out comes: minimise w subject to the expected payoff against every row being at most w, with the mixture weights summing to one. That is the column player's problem, with the dual variables of the column constraints turning out to be the column player's mixture. No second solver is involved.
v is what the row player can promise against any opponent at all, including one who sees the mixture. Against the optimal mixture no pure row does better than v and some do worse; what a pure row cannot do is promise v, because its own worst case is lower. On the two-by-two game the best pure promise is −1 and the value is 1/7.
The material
The substitution that makes a worst case linear, the dual that is the other player, and what a mixture buys that no single choice can.
A zero-sum game is a payoff matrix A: the row player chooses a row, the column player a column, and the row player receives Aᵢⱼ while the column player pays it. A mixed strategy is a probability distribution over one's own choices.
The value of the game is the largest expected payoff the row player can guarantee with a mixture, whatever the column player does — and, as the theorem below says, also the smallest expected payoff the column player can be held to.
Maximising a worst case looks nonlinear, and the fix is one variable. Let v stand for the guaranteed payoff. Requiring v to be no more than the expected payoff against each individual column is the same as requiring it to be no more than the minimum, and every one of those requirements is linear in the mixture. Then maximise v.
For every payoff matrix, the row player's programme and the column player's programme are duals of each other, both are feasible and bounded, and so their optima are equal. That common number v satisfies
v = max over mixtures p of min over columns j of the expected payoff = min over mixtures q of max over rows i of the expected payoff,
and it is the value of the game. Optimal mixtures exist for both players, and there is nothing left to prove: the theorem is strong duality with different nouns.
Two details of the programmes are worth naming, because they are where a careless formulation goes wrong. v must be declared free: a game can be worth a negative amount, and restricting v to be non-negative silently changes the problem. And the mixture constraint is an equality, which is what makes its dual variable free in turn — the value on the other side.
The three-by-three matrix with rows (0, −1, 1), (1, 0, −1) and (−1, 1, 0) is the familiar cycle: each choice beats one other and loses to one other. Its value is 0 and both optimal mixtures are (1/3, 1/3, 1/3).
Against q = (1/3, 1/3, 1/3) every pure row earns exactly 0, so no single choice is punished by playing it once. What a single choice cannot do is promise anything: each row's own worst case is −1, against an opponent who knows which row it is.
On (3, −1 / −2, 1) the value is 1/7 with p = (3/7, 4/7) and q = (2/7, 5/7). Against q, row 1 earns 3(2/7) − 1(5/7) = 1/7 and row 2 earns −2(2/7) + 1(5/7) = 1/7 — both exactly the value.
Now the guarantees. Row 1 played alone has worst case min(3, −1) = −1; row 2 alone has min(−2, 1) = −2. So the best a pure strategy can promise is −1. The mixture promises 1/7, and the difference, 8/7, is what mixing bought. On the other side, the column player's best pure enforcement is min(max(3, −2), max(−1, 1)) = 1, and the mixture brings that down to 1/7 as well. The value sits strictly between the two pure numbers, which is exactly the case in which mixing is necessary.
So the honest version of the claim is not that pure strategies do worse against the optimal mixture. Against q, every row in the support of p does exactly as well as v — that is complementary slackness, and it is forced. What pure strategies cannot do is guarantee v against an opponent who responds, and the lab's hint says exactly that: not one pure choice does better than the value, and most do worse.
On (4, 2 / 3, 1) the value is 2, with p = (1, 0) and q = (0, 1): both optimal strategies are pure. The best pure guarantee is max(min(4, 2), min(3, 1)) = 2 and the least pure enforcement is min(max(4, 3), max(2, 1)) = 2, and they agree.
That agreement is what a saddle point is, and when it happens mixing buys nothing at all. The lab reports this case as such, which matters: a reader shown only games that need mixing will over-generalise in the other direction.
Complementary slackness reads across to the game with no translation. A row played with positive probability forces the column player's constraint for that row to be tight — that row earns exactly v against q. A column played with positive probability forces the row player's constraint for that column to be tight — that column holds p to exactly v. And a row that earns strictly less than v against q must be played with probability zero. Those three sentences are the whole of how a claimed pair of mixtures is verified, and they are the previous certification lesson applied to different nouns.
A last note on scope, because a similarly named lesson exists elsewhere in this library. Dynamic Programming and Optimal Substructure, on the Algorithms path, has a lesson on games; it is about combinatorial games of perfect information and the classification of positions as winning or losing. It shares no object with this one — no payoff matrix, no mixture, no value — and neither cites the other for a result.
Interactive
both programmes solved exactly, and every single choice tested against the mixture
Method
One substitution, one dual, one solve, and then a verification that needs no solving at all.
Introduce v, require it to be at most the expected payoff against every column, add the mixture equality, and maximise v. Declare v free — a game can be worth a negative amount, and restricting it to be non-negative changes the problem.
One dual variable per column constraint, which is the column mixture, plus one for the mixture equality, which is the value. The dual is a minimisation of that value subject to every row earning at most it. You have not written a second model; you have written the same one from the other side.
One solve gives the row mixture and, from the dual values in its final tableau, the column mixture. The two objectives are equal, which is the minimax theorem on this instance and a check on the arithmetic.
Every row played with positive probability must earn exactly v against the column mixture, and every column played with positive probability must hold the row mixture to exactly v. Then play each pure strategy on its own: none beats v against the optimum, and each one's own worst case shows what mixing bought.
Two choices each, no best single one, and a value that is not a whole number. The verification at the end uses complementary slackness and no algorithm, which is what makes it worth writing out.
The verification block is the lesson's real payload. Four substitutions confirm a claimed solution to a game, using only the conditions from the certification lesson, and no simplex run is involved — which is the same trick that certified a production plan, applied to different nouns.
The final inequality is what distinguishes this game from one with a saddle point. On (4, 2 / 3, 1) the best pure guarantee and the least pure enforcement are both 2, they meet, and the optimal strategies are pure: mixing buys nothing. Strict inequality is the condition under which a mixture is necessary, and computing both pure numbers is how you tell in advance.
For a faded rehearsal, take the three-by-three cycle with rows (0, −1, 1), (1, 0, −1), (−1, 1, 0). The supplied move is that symmetry makes p = q = (1/3, 1/3, 1/3) the obvious candidate. Verify it by complementary slackness rather than by solving, compute each row's own worst case, and say what the mixture bought. Then try the four-by-four preset, whose value is 8/21, and confirm that every pure choice against the optimum earns exactly that.
You should be able to write the row player's programme with a free v, obtain the column player's as its dual, solve for the value and both mixtures, verify them by complementary slackness, and compute the best pure guarantee and the least pure enforcement to say whether mixing was necessary at all.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.