The corners are whole assignments

The anchor’s first rung takes a table of shares — every person doing a fraction of every task, with each person fully occupied and each task fully covered — and writes it as a lottery over whole assignments. That is a demonstration on one table, and it invites a question the demonstration cannot answer: does it always work, and why?

The answer is a statement about the shape of the set of such tables, and it is worth stating before proving.

The set of tables of shares is a convex body. Its corners are exactly the whole assignments. Everything else on this ladder is a consequence.

What “corner” means, exactly #

A point of a convex set is an extreme point — a corner — when it is not strictly between any two other points of the set. A square has four; a disc has infinitely many; a line segment has two.

The tables of shares form a convex set: mixing two of them in any proportion gives another, since the row and column sums mix along with everything else. The set lives in $n^2$ dimensions, is bounded — every entry is between nought and one — and is cut out by linear equations and inequalities, so it is a polytope: a bounded region with finitely many corners. That last word is a theorem rather than a definition, and it is what makes “the corners are the whole assignments” a finite statement worth proving.

Every point of a polytope is a mixture of its corners. That is Minkowski’s theorem, and it is what turns “the corners are whole assignments” into “every table of shares is a lottery over whole assignments”. The first rung’s demonstration is the second statement; this rung is the first.

The dependence runs only one way, and it is worth being clear which. Knowing that some particular table is a mixture says nothing about the corners; knowing the corners settles every table at once. A statement about the extreme cases is worth more than any number of statements about typical ones, which is the recurring reason convexity is useful — the whole body is determined by its edge.

Why the corners are the permutations #

The proof is short and worth carrying out, because it is a proof by exhibiting a direction to move in.

Suppose $M$ is a table of shares that is not a permutation matrix. Then some entry is strictly between zero and one. Its row must contain another such entry, since the row adds to one; that entry’s column must contain another; and so on. Following that chain, and since there are finitely many cells, it eventually revisits a cell — producing a cycle of cells, alternating between rows and columns, every entry of which is strictly between zero and one.

Now add a small $\varepsilon$ to alternate cells of the cycle and subtract it from the others. Every row and every column of the cycle contains exactly two of its cells, one gaining and one losing, so all the sums are unchanged. For small enough $\varepsilon$ every entry stays between zero and one.

So $M$ is the midpoint of $M + \varepsilon$ and $M - \varepsilon$, both in the set, and $M$ is not a corner. Conversely a permutation matrix has no such cycle — every entry is zero or one, and moving any of them breaks a sum — so it is a corner.

The chain-finding step deserves a second look because it is where the bipartite structure enters and the argument would otherwise be routine. Starting from a fractional entry, its row has another; move along the row. That entry’s column has another; move down the column. Alternating row-moves and column-moves is forced, and it is what makes the resulting cycle alternate between the two roles — which is what a bipartite graph is. The proof never mentions bipartiteness and uses nothing else.

That is Birkhoff’s theorem, proved in 1946 and independently by von Neumann. The argument is entirely combinatorial: it never uses that the entries are numbers beyond needing room to move, and it would work identically over any ordered field.

It is also, unusually for a theorem about a polytope in $n^2$ dimensions, an argument a reader can carry out on a specific table in a minute. Take a three-by-three table with a fractional entry, follow the chain, find the cycle, and perturb: the two neighbouring tables are there to be written down. A proof that can be executed on an instance is a different kind of possession from one that can be followed, and this is one of them.

What integrality buys #

The consequence is the reason the assignment problem is easy, and it is worth stating in the form that generalises.

Suppose the cheapest assignment is wanted: choose one task per person, one person per task, minimising the total cost. That is an integer problem — the variables must be zero or one — and integer problems are in general very hard.

Relax it. Allow the variables to be any numbers between zero and one, subject to the same row and column sums. That is a linear program, which is easy: the optimum of a linear objective over a polytope is attained at a corner, because moving in a direction that does not worsen the objective can always be continued until a constraint stops it.

And the corners are whole. So the relaxed problem’s answer is already an answer to the original, and the integer problem was never an integer problem.

That is the whole trick, and it is not available in general. What makes it work here is a property of the constraint matrix called total unimodularity: every square submatrix has determinant $0$, $1$ or $-1$, which forces every corner to have whole coordinates. The assignment problem’s constraints have it; most constraints do not.

The size-two case is worth having in mind because it is completely transparent. A two-by-two table of shares is determined by one number: put $t$ in the top-left and the rest follows. So the set is a segment from $t = 0$ to $t = 1$, its corners are the two permutations, and “every table is a mixture of whole assignments” is “every number between nought and one is a mixture of nought and one”.

Every larger case is that statement in more dimensions, and the only thing that gets harder is exhibiting the mixture — which is what the first rung’s decomposition does.

The odd cycle, which is the whole difference #

The fractional corner in that figure is not an accident and its shape identifies exactly what the assignment problem has that general matching lacks.

The chain argument above finds a cycle of cells and perturbs alternately around it. In a bipartite setting — people on one side, tasks on the other — every cycle alternates between the two sides, so every cycle has even length, and alternating $+\varepsilon$ and $-\varepsilon$ round it is consistent.

In a general graph a cycle can be odd. Going round a triangle assigning alternate signs, the last edge is asked to be both plus and minus, so the perturbation does not close up, and the half-on-every-edge point cannot be perturbed away. It is a corner because the graph has an odd cycle.

That is the complete diagnosis. Bipartite matching is integral; general matching is not; the difference is odd cycles; and the same distinction decides whether a graph can be two-coloured. One structural fact governs three apparently separate subjects.

Edmonds’ matching polytope theorem repairs the general case by adding one inequality for every odd set of vertices — a set of $2k+1$ vertices can carry at most $k$ edges of a matching — which restores integrality at the cost of exponentially many constraints.

That ought to be fatal and is not, which is the surprising part. An exponential family of constraints can be optimised over in polynomial time provided there is a fast way of finding a violated one given a candidate point, and for the odd-set inequalities there is. The number of constraints is not what decides whether a linear program is tractable; the difficulty of spotting a violation is. That observation, due to Grötschel, Lovász and Schrijver, is one of the load-bearing results of the whole subject and it arrived from exactly this example.

Counting the corners, and counting the terms #

Two counts are worth doing because they are very different and the difference matters.

The number of corners is $n!$. Every permutation is a corner and every corner is a permutation, so the polytope of six-by-six tables has seven hundred and twenty corners, and the polytope for twenty people has more corners than there are atoms in a person.

The number of terms needed in a mixture is at most $n^2 - 2n + 2$. That is Carathéodory’s theorem sharpened for this polytope: a point in a $d$-dimensional convex set is a mixture of at most $d + 1$ corners, and the polytope of tables of shares has dimension $(n-1)^2$ because the row and column sums remove $2n - 1$ of the $n^2$ degrees of freedom.

So a lottery over an astronomically large set of outcomes needs a handful of them. For six people that is twenty-six terms against seven hundred and twenty corners, and for twenty people three hundred and sixty-two against a number with eighteen digits.

That gap is the practical content of the theorem. A description of a share table as “a mixture of whole assignments” would be useless if it needed all of them; it is useful because the number of terms grows as the square while the number of candidates grows factorially.

What it costs #

The polytope is enormous. The set of tables of shares for $n$ people has $n!$ corners, so the “mixture of corners” description is exponentially long in principle. In practice the decomposition needs at most $n^2 - 2n + 2$ terms by the counting argument above, so the representation is short even though the corner set is not — which is a distinction worth keeping, since a description of a polytope by its corners and a description of a point inside it are very different objects.

And enumeration is not the algorithm. The hero figure finds the corners by searching a grid, which is honest at size three and hopeless at size ten. The cheapest assignment is found by the next rung’s method, which never looks at a corner list. That is the ordinary relationship between a structural theorem and an algorithm: the theorem says the search space can be taken to be the corners, and the algorithm then avoids visiting them.

Finding the decomposition is a separate algorithm. Knowing a mixture exists does not produce one; the standard method repeatedly extracts a whole assignment from what is left, which needs a perfect matching at each step, and the existence of that matching at each step is Hall’s condition applied to the support. So the constructive half rests on a different theorem from the existential half.

Nor does integrality make every question easy. The cheapest assignment is easy; the cheapest assignment subject to an extra constraint — say, that two particular people are not both used, or that the total cost falls in a range — generally is not, because the extra constraint destroys the unimodularity. Adding one row to a totally unimodular matrix usually makes it not, and there is no partial credit: the corners are whole or they are not.

Two names, two purposes #

The theorem carries two names and the two discoverers wanted it for opposite reasons, which is worth knowing because it explains why it is stated in two different vocabularies.

Birkhoff published it in 1946 in a paper on lattice theory, as a structural fact about a convex body — the doubly stochastic matrices — that he was studying for its own sake. In that reading the theorem describes an object.

Von Neumann proved it independently, in work on a two-person game and on the assignment problem, and wanted it as a tool: it converts a search over assignments into a linear program, which was the point of the whole exercise. In that reading the theorem is a licence.

Both readings are in use and they emphasise different halves. “The doubly stochastic matrices are the convex hull of the permutations” is Birkhoff’s; “the assignment problem’s linear relaxation is exact” is von Neumann’s; and they are the same sentence.

The tool reading is the one that generalised. Asking which integer problems have integral relaxations produced the theory of total unimodularity in the 1950s and, later, the whole subject of polyhedral combinatorics — in which a combinatorial problem is understood by describing the polytope of its solutions, and an algorithm is a way of optimising over that description. The assignment problem is that subject’s first and cleanest example, and the reason it is taught first — a subject’s first example is usually the one where every ingredient is visible at once, and here the polytope, the integrality, the duality and the algorithm all fit on a page.

What the pictures cannot show #

The polytope is nine-dimensional at size three. Every figure draws its corners as small grids rather than as a shape, because the shape does not fit anywhere. The convexity, the mixing and the extremeness are all statements about a body nobody can see.

The six grids are corners of a nine-dimensional body and are drawn as six separate pictures. Nothing in the figure indicates that they are related, that the body they are corners of is connected, or that every other table lies between them. Those are the three facts the rung is about.

The search is over a grid and the set is continuous. The hero figure examines tables whose entries are multiples of one-sixth, finds the corners among those, and reports them. That is a complete verification of a discretisation, and the theorem is about the continuous set — where the argument is the cycle-perturbation of the middle section.

The fractional corner is drawn as a table of halves and its significance is arithmetic. What matters about it is that its total exceeds every whole matching’s, and that comparison is a number in the caption rather than anything visible in the grid.

And the perturbation is not drawn. The proof moves $\varepsilon$ around a cycle of cells; the figure shows corners and not the movement that establishes non-corners. Drawing it would need a table with a highlighted cycle and two neighbours, which is three tables to make one point.

Where the ladder goes next #

The next rung asks how the cheapest assignment is actually found, and finds that the answer comes with its own proof: a price for every person and every task, certifying the answer without examining any alternative.

Named here as a debt: Edmonds’ odd-set inequalities, mentioned above as the repair for general matching, which turn an exponential family of constraints into a polynomial algorithm and are not developed here.

Sideways, the bipartite structure that makes the cycles even is what Hall’s theorem is about, the flow formulation of the same problem is the bottleneck story, and the first rung’s decomposition is the lottery.

What is worth carrying away #

An integer problem is easy exactly when its relaxation has whole corners, and whether it does is a property of the constraints rather than of the problem’s difficulty.

The assignment problem looks like a combinatorial search over $n!$ possibilities and is a linear program whose answer happens to be whole. Nothing about the search was clever; the constraints were.

The habit worth taking is to relax an integer problem and look at the corners. If they are whole, the problem was linear all along; if one of them is a half, the fractional corner usually shows exactly which structural feature — here an odd cycle — is causing the trouble.