The value from both sides

Two choosers move at the same instant. The row chooser picks a row, the column chooser picks a column, each knows the whole table of numbers, and neither learns what the other has done until both have done it. The row chooser is paid whatever sits in the chosen cell, and in a zero-sum game the column chooser pays exactly that: one number describes the whole outcome, a gain to one side and a loss to the other.

Now put the cautious question to each of them separately. How much can be guaranteed, whatever the other one does? One answer is a floor and the other is a ceiling, and there is no evident reason the two should be related at all.

The two cautious questions #

The matrix above pays the row chooser $+1$ when the two choices agree, in the cells AX and BY, and $-1$ when they disagree.

The row chooser reasons: take row A and the worst that can happen is $-1$, since the column chooser may pick Y; take row B and the worst is $-1$ again. So the guarantee is

$$\max_i \min_j a_{ij} = -1,$$

the maximin, the best of the worst cases. The column chooser reasons from the other end — column X lets the row chooser extract as much as $+1$, and so does Y — so the least that can be conceded is

$$\min_j \max_i a_{ij} = +1,$$

the minimax, the worst of the best cases.

One number is $-1$ and the other is $+1$, and between them lies a gap of two whole units in which neither chooser has any claim. That gap is not an artefact of a badly chosen example. It is what happens whenever the order of the two quantifiers matters, and the order of quantifiers almost always matters.

Why one can never exceed the other #

Half of the relation between the two numbers is free, and it is the half the rest of the essay is trying to close.

Fix any row $i$ and any column $j$. The worst outcome in row $i$ is no better than the outcome at $(i,j)$, which in turn is no better than the best outcome in column $j$:

$$\min_{j'} a_{ij'} \ \le\ a_{ij} \ \le\ \max_{i'} a_{i'j}.$$

The left end does not mention $j$ and the right end does not mention $i$, so taking the maximum over $i$ on the left and the minimum over $j$ on the right preserves the inequality:

$$\max_i \min_j a_{ij} \ \le\ \min_j \max_i a_{ij}.$$

The maximin never exceeds the minimax. That is three lines, it holds for every matrix of every shape, and it is exactly the argument that two numbers that have to meet calls weak duality: one quantity bounded above by another for a reason so cheap it feels as though nothing has been proved. What is left is the expensive half — whether the two ever actually touch. A quantity squeezed between bounds that are then shown to coincide is the manoeuvre by which two injections make a bijection, and the whole content sits in showing that nothing is left in between.

What a probability buys #

That gap is real as long as each chooser must name one row or one column. So allow something else: a mixed strategy, a probability distribution over the rows, fixed before the play and not revealed.

A row chooser putting weight $p$ on row A and $1-p$ on row B expects, against column X,

$$p \cdot a_{1X} + (1-p) \cdot a_{2X},$$

which is a straight line in $p$; against column Y there is another straight line. Whatever the column chooser does — including mixing in turn, since a mixture of columns averages the column lines and so can do no worse than the worst of them — the row chooser is guaranteed at least the lower envelope of those lines, their pointwise minimum over the columns.

The gap of two units has closed to nothing. Half and half guarantees the row chooser an expected $0$ against either column, and half and half on the other side concedes an expected $0$ against either row — a number neither can be argued out of and neither can improve on.

The lower envelope, and where it peaks #

The two-column case is too symmetric to show the mechanism, so here is the general shape of it, with three columns and no symmetry anywhere.

The picture is a proof of its own claim, once three things about it are noticed. The lower envelope is concave, as a pointwise minimum of straight lines always is, since the region under all of them is a convex set. It is piecewise linear, so its maximum sits either at an endpoint of the unit interval or where two of the lines cross — a finite list of candidates, which the figure searches in full and reports as an exact rational rather than a decimal. And at that maximum at least two lines meet, so at least two of the column chooser’s pure replies hold the row chooser to the same amount.

The third point is the hinge. Where the lines for X and Y cross, the row mixture $8/15$ and $7/15$ pays the same against X as against Y — the arithmetic comes out at

$$(8/15) \times 5 + (7/15) \times (-3) = 19/15$$

against X and at $(8/15) \times (-2) + (7/15) \times 5 = 19/15$ against Y — so the column chooser is left indifferent between them. That indifference is what lets the other side be built: a column mixture chosen to make the row chooser indifferent between A and B pins the ceiling down at the same height.

A family of lines replaced by their pointwise minimum turns up elsewhere in this collection in quite a different costume: the plane divided by whoever is nearest is the lower envelope of a family of distance functions, its cells the regions where one member beats all the rest.

The column that is never used #

Column Z is drawn and never used, which makes it the most instructive line in the figure. Its line, $1 + 2p$, sits strictly above the lower envelope at every single mixture. It falls below X’s line only when $p \ge 2/3$ and below Y’s line only when $p \le 4/9$, and no weight satisfies both, so Z is never the minimum anywhere. Against the optimal row mixture it pays $(8/15) \times 3 + (7/15) \times 1 = 31/15$, which is a good deal more than $19/15$ — the column chooser would be handing over more than the value by choosing it.

So the optimal column mixture puts $7/15$ on X, $8/15$ on Y and nothing at all on Z. A whole strategy is available, is never strictly dominated in the sense that iterated elimination would detect, and is nonetheless assigned probability zero.

There is a name for that arrangement and it is not a coincidence of this matrix. A strategy paying strictly more than the value against the opponent’s optimum gets weight zero in one’s own; a strategy carrying positive weight pays exactly the value. The two halves are one statement read in two directions, and in the language of linear programming it is called complementary slackness — the business of the second rung of the duality anchor rather than of this one.

A whole game in one fraction #

The value need not be a round number, and that it is nonetheless exact is worth one more matrix.

The pure numbers here are $-1$ and $+1$ again, the same gap as before, and it closes onto $1/5$ — a number appearing nowhere in the matrix. Checking it takes one line: $(2/5) \times 2 + (3/5) \times (-1) = 1/5$ against column X, and the same against column Y.

Every quantity in the construction is a ratio of whole numbers, because the peak is the intersection of two lines whose coefficients are the matrix entries. The figure carries that arithmetic exactly and turns it into a coordinate only in the last step, which matters more than it sounds: the theorem consists of an equality, and a value off by a rounding error fails it.

Where a probability is not needed #

The theorem is a claim about every finite zero-sum game, which means it also covers the games where it says nothing new.

Row A pays more than row B in both columns and column Y concedes less than column X in both rows, so cell AY is a saddle point: at once the smallest entry in its row and the largest in its column. The maximin is $2$ and the minimax is $2$ before any probability is introduced. The construction still runs and the envelopes still meet, but at a corner of the interval instead of at an interior crossing.

That is the honest shape of a theorem true everywhere: it must also hold where it is uninteresting. All the figure adds here is that mixing cannot hurt — no weight strictly inside the interval guarantees more than the corner does, over all 61 mixtures of the sweep.

Other games settle themselves without any probability at all, by elimination alone.

A strategy is strictly dominated when another belonging to the same chooser pays strictly more against every reply still in play. Nobody would ever use one, so it can be struck, and striking it can expose a second. Where the process ends in a single cell, that cell is a pure equilibrium, and the figure asserts as much rather than saying it in prose. Note what it does that a worked example would not: it runs every order of elimination there is and compares the endpoints, in the same spirit as the census of every matching one anchor across.

But elimination usually stops early. On the matching-pennies matrix at the top of this essay it strikes nothing whatever — no row beats the other in both columns — and leaves everything standing. That is precisely where a probability has to come in, and it is why the minimax theorem is a theorem about mixed strategies and would be false without them.

What the picture cannot show #

The figures decide a finite thing and the theorem is an infinite one, and the distance between the two should be stated plainly.

Every mixed figure here draws a matrix with two rows. That is not a stylistic preference: with two rows the row chooser’s mixture is a single number, so a guarantee is a function of one variable and can be drawn as a curve. With three rows the mixture lives in a triangle, the envelope becomes a surface and there is no side view. The value still exists — von Neumann’s theorem does not care about the shape of the matrix — but finding it becomes a linear program, and the drawing would be a drawing of a procedure rather than of the claim.

So the general theorem needs an argument these pictures do not contain. The standard one separates two convex sets by a hyperplane: what the row chooser can guarantee forms a convex set, what the column chooser will concede forms another, and were the two numbers different there would be room for a hyperplane between them that no mixture could cross — which contradicts how the sets were built. Equivalently, the whole thing is a corollary of linear-programming duality. Either route is a real argument; neither is drawn here.

Two smaller limits belong beside it. A probability is not a thing a drawing can exhibit: what is plotted is the expected payoff, a statement about a long run nobody in the picture ever plays, and one simultaneous choice produces one cell and says nothing about whether the mixture was right — much as a bell curve assembled out of coin flips says nothing about any single flip. And the sweeps, 61 mixtures on one side and 91 on the other, check one matrix at a lattice of points rather than proving anything about a continuum. They can refute the drawn value and cannot establish it; what establishes it is the exact comparison against every pure reply, which is finite and complete.

The same theorem, in the other language #

Here is the connection that makes this essay’s position on the ladder what it is, and it is the strongest one in this field.

The minimax theorem and the duality theorem of linear programming are the same theorem. Not analogous, not related by a shared mood — the same statement, translated. A zero-sum game turns into a pair of linear programs, one asking for the largest guarantee and the other for the smallest concession, each the dual of the other; the equality of their optima is the equality of maximin and minimax. Run the translation backwards and any pair of dual programs becomes a zero-sum game whose value is their common optimum.

That is why two numbers that have to meet is a prerequisite here rather than a neighbour. It writes the identical fact in the language of two polytopes: a maximum over the vertices of one, a minimum over the vertices of another, a gap that shrinks to nothing, and every vertex of both enumerated to prove it. This essay writes it as two envelopes meeting on a page. A vertex enumeration and a line crossing have no visual resemblance whatever, and both figures are pictures of one theorem — which is the whole of what this collection means by the same thing twice.

Convexity does the work in both. There it is the feasible region; here it is the concavity of the lower envelope and the convexity of the upper one. Two convex objects that can neither pass through each other nor stay apart have exactly one place to be, and that place is the value.

The connection was noticed almost at once. Von Neumann proved the minimax theorem in 1928 by a topological argument resting on a fixed-point theorem of the kind that says something always stays put; elementary proofs followed in the 1930s. When George Dantzig described linear programming to him in 1947, von Neumann is said to have recognised the structure immediately and sketched the duality theorem on the spot, out of the game theory he already had. The published proof came from Gale, Kuhn and Tucker in 1951.

Where the equality stops #

The theorem is about zero-sum games, and the moment the sum is not zero the whole apparatus loses its subject.

Each cell now carries two numbers that do not sum to zero, so “the value of the game” has nothing to refer to: there is a payoff to the row chooser and a payoff to the column chooser, and no reason for one to be minus the other. Both AX and BY are equilibria, they pay differently, and no argument from caution picks between them. What survives the loss of the zero-sum condition is the Nash equilibrium — a profile from which no single chooser gains by moving alone — and John Nash proved in 1950 that every finite game has at least one in mixed strategies, by a fixed-point argument rather than by any envelope.

The minimax theorem is the zero-sum special case in which the Nash equilibria all pay the same, and that common payment is the value. The generalisation costs the picture: existence is proved without exhibiting anything, as six people at a party guarantees a monochromatic triangle without saying where. And “no single chooser gains by moving alone” has the same negative shape as stability in a matching — a condition defined entirely by what it forbids, which is why the side that proposes wins reads as an argument about the same kind of object.

One boundary is worth stating outright, because the word “game” is shared and nothing else is. Games in Conway’s sense — alternating moves, perfect information, no chance anywhere, positions with values that add — are a different subject, and another site in this fleet owns them: every argument here needs simultaneity and a probability, and every argument there needs alternating moves and has no probability in it at all.

Where this anchor goes next #

The value exists, both sides name it, and neither can be argued out of it. That is a statement about what caution can secure, and it says nothing at all about whether the resulting arrangement is any good.

Both flows in that figure are equilibria in the sense this essay has been describing — nobody improves by moving alone — and the second one is strictly worse for every single participant than the first, which existed before a costless option was added. Guaranteeing what caution can guarantee is not the same as arriving anywhere good, and the distance between the two is the road that makes everyone later, the second rung of this anchor.

One question this rung raises and does not answer is a question about work: finding the value of a large game means solving a linear program, and how much effort that takes as the matrix grows is a matter of cost, which another site in this fleet owns. What belongs here is the structural fact, complete as it stands — the two numbers are equal, exactly, for every finite zero-sum matrix, and the drawings above are what that equality looks like when there are two rows to draw it with.