Matpic
mathematics, in pictures
Concept

Linear program

The problem of making a weighted sum as large or as small as possible subject to finitely many straight-line inequalities. Its optimum is always at a corner of the feasible region, which is what makes searching corners a complete method.

Named by 5 essays across one field — 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 What one more unit of constraint 1 is worth. The optimum of a linear program plotted against one of its right-hand sides, as an exact piecewise linear graph, with the breakpoints marked and each piece's slope named as a dual variable.

What a constraint is worth

The rung below settled that a linear program and its dual reach the same number. This one asks what the dual's variables are, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.

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 A table of shares written as a lottery over 3 whole assignments. A doubly stochastic table of shares, and beneath it the permutation matrices and weights that add up to it exactly, each drawn as a grid with one marked cell per row.

A lottery over whole assignments

A table of shares in which every person's shares add to one task and every task is exactly covered is never anything more than a mixture of whole assignments — and finding the mixture is a matter of taking one complete assignment out at a time.

applied · Assignment A signal both can see, and neither wants to disobey. A two-by-two game with a distribution over its four cells, drawn as the weight on each. Obeying the recommendation is a best reply for both choosers, and the pair collects 21/2 between them.

A signal both can see

Two choosers who randomise privately can reach a set of outcomes that is smaller, and worse, than the set they reach when a device draws one cell and whispers each of them their half of it. Nothing is enforced and nobody is bound, and the arrangement is stable anyway.

applied · Equilibrium

Named alongside it

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

ConvexityDualityCorrelated equilibriumExistence proofFeasible regionMinimaxMixed strategyNash equilibriumVertex enumerationZero-sum gameAssignmentBest reply

All concepts