Matpic
mathematics, in pictures
Concept

Minimax

The most a cautious chooser can guarantee, which in a zero-sum game is the same number the opponent can hold them to. For a zero-sum game the two players' guarantees coincide, which is what the minimax theorem establishes.

Named by 5 essays across 2 fields — each of them below, with the objects they name alongside it.

Two polytopes, two optima, one number. The feasible regions of a linear program and of its dual, side by side, each with its optimal vertex, and a number line on which the gap between the two optima closes to nothing.

Two numbers that have to meet

Every linear program has a shadow — a second program built from the same numbers read the other way, whose minimum can never fall below the first's maximum. That much is a one-line calculation; the theorem is that the two numbers are always exactly equal.

applied · Duality The value of a 2×3 zero-sum game, named from both sides. The row chooser's expected payoff against each column as a line over the mixing probability, with the lower envelope and its maximum, beside the same construction from the column chooser's side. Both give 19/15.

The value from both sides

Two choosers move at the same instant, and each asks the cautious question — how much can be guaranteed, whatever the other does. With pure choices the two answers are usually different numbers; allow a probability and they are forced to be the same one.

applied · Equilibrium Announcing a mixture is worth 5/3 more than any equilibrium. The leader's payoff against the probability it announces for its first action, for a leader with a dominant action that is better off not being seen to play it, with the follower's reply switching where the follower is indifferent. The best announcement is worth 11/3; the best equilibrium of the simultaneous game is worth 2.

Worth more for being seen first

Moving first sounds like a disadvantage, since the other side gets to see the move and answer it. When the move is a mixture that is announced and believed, it is never a disadvantage, it is worth exactly nothing in a game of pure conflict, and in other games it is worth more than any equilibrium — sometimes by announcing an action that would never be played in secret.

applied · Equilibrium The payoffs repetition makes available in the prisoner's dilemma. A plot of the two choosers' average payoffs, with the stage game's four cells marked, their convex hull drawn, the two minmax values shown as lines, and the region above both shaded.

Patience instead of a contract

Commitment had to assume an announcement binds. Play the same game again tomorrow and the assumption is unnecessary — the future does the binding. What it costs is that nearly every outcome becomes an equilibrium, so a theory that could not choose between two now cannot choose between infinitely many.

applied · Equilibrium How much the first player can guarantee, as the coin's bias moves. A plot of the first player's best guaranteed winning chance in Penney's game against the probability of heads, a third on a fair coin and rising past one half only when the coin is heavily biased.

A coin that lets the first player win

On a fair coin the second player in Penney's game always has a better pattern than the first, and the first can hold them to no worse than two to one. Bend the coin and every overlap is paid for in the letters it uses: the replies change, the first player's share swings between a third and a half, and past a heads chance of 1/∛2 the first player simply names HHH and wins.

probability · Expectation

Named alongside it

The objects these essays reach for when they reach for this one.

Zero-sum gameConvexityMixed strategyNash equilibriumBest replyCommitmentDominant strategyDualityEquilibrium selectionExistence proofLinear programConditional probability

All concepts