Matpic
mathematics, in pictures
Concept

Assignment

A way of giving each of several people exactly one of several tasks, with no task handed out twice. The count of them grows as a factorial, so which one is best is settled by structure — a matching condition, or the corners of a polytope — rather than by trying them all.

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

(p ∨ q) ∧ ¬r, drawn on the cube of 8 assignments. The assignments as corners of a cube, joined when they differ in one variable, with the satisfying corners filled.

A formula is a corner of a cube

A formula about three letters is a set of eight rows. Written as a table that is a list; drawn on a cube it is a shape — and the shape is what almost every later question in this field turns out to be about.

logic · Truth functions 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 The 6 corners, and nothing in between. The 6 permutation matrices of size 3, drawn as grids. A search over every table of shares on a fine grid finds these and only these as corners of the set.

The corners are whole assignments

A table of shares can be written as a lottery over whole assignments, which one worked example shows. The general statement is that the corners of the set of such tables are exactly the whole assignments, and that single fact is why the whole subject is easy.

applied · Assignment A cheapest assignment, and the proof that it is cheapest. A 4 by 4 cost table with the cheapest assignment marked, and a row price and column price beside each. Every used cell's two prices add to its cost, and the prices total the assignment's cost.

A price for every person and task

The cheapest assignment can be found without comparing it to any other. Attach a number to each person and each task so that no pair's two numbers exceed its cost, and if the numbers add to an assignment's total, that assignment is cheapest — proved, by an argument that never mentions the alternatives.

applied · Assignment One table of shares, two different lotteries. A doubly stochastic table decomposed into whole assignments twice, by two different orders, giving two mixtures that reconstruct the same shares.

One table, two lotteries

A table of shares says what fraction of each task each person does. It does not say how — the same table is a mixture of whole assignments in many different ways, and the differences are exactly what the people being assigned would care about.

applied · Assignment The corner that is a half on every edge. A 3-vertex graph beside a table of the 5 corners of its matching relaxation. 4 are whole and one assigns a half to every edge.

Where the corners stop being whole

The easy theory of assignment rests on one property — the relaxation of the assignment problem has whole-numbered corners. Add a single edge that closes an odd cycle and the property fails, a corner appears with a half in every coordinate, and the problem changes character completely.

applied · Assignment An auction for 4 objects, bid by bid, with increment 1/5. A 4 by 4 table of values beside the log of 12 bids of an auction with increment 1/5: bidder, object, the raise, and the prices after each bid; it ends with total value 26.

Prices the bidders raise

The cheapest assignment is certified by a price on every task, and those prices can be found without anyone in charge. Let each unassigned person bid for the task that suits them best at current prices, raise its price by a little more than it is worth to them over the next best, and wait. The bidding ends, and when the increment is small enough the prices it ends at are a proof of optimality.

applied · Assignment The core of a market with two houses and two buyers. The core of an assignment game drawn in the plane of buyer A's payoff against buyer B's, a polygon with vertices (0, 1), (0, 0), (1, 0), (4, 3), (2, 3); the buyers' best corner is (4, 3).

The prices nobody can break away from

When houses are sold to buyers who value them differently, there is a whole range of prices at which nobody wants to walk away, and it has a remarkable shape — one corner best for every buyer at once, one best for every seller at once, and the buyers' corner pays each buyer exactly what the market would lose without them.

applied · Assignment No prices clear a market for a pair worth 3. The plane of prices for items A and B, with the triangle pA + pB ≤ 3 where buyer 1 wants the pair and the square pA, pB ≥ 2 where buyer 2 wants neither; they do not meet.

Prices for things wanted only together

When every buyer wants one thing, there are always prices at which everyone is content with what they get. Let one buyer want two things together and there may be none — and whether there are is decided exactly by whether the market's best fractional allocation beats its best whole one.

applied · Assignment

Named alongside it

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

Linear programmingDualityMatchingConvexityMarket clearingPermutationPolytopeAlgorithmCertificateComplementary slacknessCoreFairness

All concepts