A lottery over whole assignments

Three people and three tasks. A whole assignment gives each person one task and each task one person, and there are six of them. Now allow shares: person one takes four ninths of the first task, a third of the second, two ninths of the third, and so on, arranged so that every person’s shares add to one whole task and every task is exactly covered.

Such a table is called doubly stochastic, and it looks like a genuinely new kind of object: a division of labour with no whole assignment in it anywhere. Birkhoff’s theorem says the appearance is false. Every such table is a weighted average of whole assignments, so a schedule of shares is never more than a lottery over honest schedules — and running the lottery produces the shares in expectation.

What the theorem says, and what it is about #

Write the shares as a square array of non-negative numbers with every row sum and every column sum equal to one. Write a whole assignment as an array of zeros and ones with exactly one 1 in each row and column — a permutation matrix.

Birkhoff’s theorem. Every doubly stochastic matrix is a convex combination of permutation matrices.

Convex combination means the weights are non-negative and add to one, which is what makes the combination a lottery rather than an arbitrary sum.

The theorem is a statement about a shape. The doubly stochastic matrices of a given size form a bounded region carved out of a space by linear equations and inequalities — a polytope — and the theorem says its corners are exactly the permutation matrices. A polytope is the convex hull of its corners, so knowing the corners is knowing everything.

For $n$ people the polytope has $n!$ corners and dimension $(n-1)^2$, which is worth pausing on: six corners in four dimensions for $n = 3$, twenty-four corners in nine dimensions for $n = 4$. The number of corners outruns the dimension immediately, and that is why the decomposition of a point into corners is not unique — it is a statement about a shape with far more corners than it needs.

The proof, which is a procedure #

The argument is short and it is an algorithm, which is the best kind.

Look at the support of the table: the set of cells with a positive share. Claim: the support contains a whole assignment.

The claim is Hall’s condition applied to the support, and the verification is a count. Take any set $S$ of people. Their shares add to $|S|$, since each person’s shares add to one. All of those shares sit in the columns of tasks they have some share of — the neighbourhood $N(S)$ — and each of those columns holds a total of one across all people. So $|S| \le |N(S)|$, and Hall’s condition holds. The support therefore contains a complete matching, which is a whole assignment.

Now peel. Let $w$ be the smallest share along the assignment found. Subtract $w$ from each of those $n$ cells and record the pair $(w, \text{assignment})$. Every row and column has lost exactly $w$, so what remains is $(1-w)$ times a doubly stochastic table; and at least one cell has become zero, so the support has strictly shrunk. Repeat.

The support has at most $n^2$ cells and loses at least one per round, so the process stops, and the recorded weights add to one because each round removes exactly $w$ from every row total. The figures perform this in exact rational arithmetic and check the reconstruction entry by entry — which matters more than it sounds, because a floating-point zero would leave a residue of $10^{-17}$ that the next round would treat as a live cell and the loop would not terminate.

How many terms are needed? At most $n^2 - 2n + 2$, a bound of Marcus and Ree, and the figures check the count against it. The bound is attained, so a table of shares can genuinely require that many whole assignments; and it is much smaller than $n!$, so the decomposition is short even though the number of corners is astronomical. That is Carathéodory’s theorem in action: a point in a $d$-dimensional convex set needs at most $d+1$ corners, and the structure here does slightly better.

Why this is worth having #

Three uses, and they are different in kind.

Randomising makes a fractional plan executable. A schedule that gives someone two thirds of a task cannot be carried out; a lottery that gives them the whole task two times in three can. The theorem says any fractional plan meeting the row and column conditions can be realised this way, with the shares as the probabilities. That is the standard move in allocation problems where the objects are indivisible: solve the easy fractional problem, then round it by lottery, and the expected allocation is exactly the fractional one.

Fairness properties survive the rounding. If the fractional table gives everyone an equal share of the good tasks, the lottery gives everyone an equal chance at them; envy-freeness in expectation comes for free, in the sense that an envy-free division of a divisible good becomes an envy-free-in-expectation lottery over indivisible ones. What does not survive is anything about the realised outcome: some draw of the lottery will give one person all the good tasks.

Optimisation over the fractional set is optimisation over the whole one. A linear objective on the polytope attains its maximum at a corner, and the corners are the whole assignments — so a linear program over the shares gives an integral answer automatically.

That last consequence is the one with the widest reach. The assignment problem — choose a whole assignment maximising a total value — is a combinatorial problem over $n!$ options, and Birkhoff turns it into a linear program whose answer is automatically one of them. Nothing needs rounding. The same phenomenon has a general name, total unimodularity, and its other famous instance is the network flow problem, where integral capacities give integral optima for the same reason — the same structural luck that makes a matching problem’s linear relaxation tell the truth about whole matchings.

The all-or-nothing case, and why it is the same theorem #

There is a special case in which the shares are all equal, and it is worth separating because it is the combinatorial heart with the arithmetic stripped out.

Suppose each person is prepared to take exactly $k$ of the tasks and each task is wanted by exactly $k$ people, and shares are split evenly: each live cell holds $1/k$. That table is doubly stochastic, so Birkhoff applies, and the decomposition has a particularly clean form — $k$ whole assignments, each with weight $1/k$, using every live cell exactly once.

That statement, translated back into graphs, is the theorem that a $k$-regular bipartite graph decomposes into $k$ perfect matchings, which is König’s edge-colouring theorem. The two results are the same result at different resolutions: the graph version handles the case where all the numbers are equal, and the matrix version handles arbitrary shares by peeling the equal case off repeatedly.

The direction of implication runs both ways, which is the useful part. Proving Birkhoff needs Hall, and Hall’s condition on the support is supplied by the row and column sums. Proving König’s edge colouring needs Birkhoff applied to the evenly split table, or Hall applied $k$ times. Whichever is taken as primitive, the content is the counting argument in the previous section, and everything else is arrangement.

What the weights are worth #

A lottery is not the only thing the decomposition provides, and the extra thing is worth stating because it is what makes the theorem useful in a negotiation rather than merely in an algorithm.

The weights are a certificate. Handed a table of shares and a claim that it is achievable by lottery, a sceptic can be given the list of whole assignments and their weights, and checking the claim is then arithmetic on at most $n^2 - 2n + 2$ arrays — no search, no trust. That is the same asymmetry that makes a refutation worth more than an assertion of unsatisfiability: hard to find, easy to check.

The weights also answer questions the fractional table cannot. How often does person two get task three? is the share, and the table already says so. How often do person two and person four get their favourite tasks at the same time? is not a function of the shares at all — it depends on the lottery — and different decompositions of the same table give different answers. So the choice of decomposition is a real choice with consequences, and the theorem’s silence about which to pick is a genuine gap rather than a technicality.

That gap is where the applied literature lives: decompositions minimising the number of terms, decompositions respecting side constraints, decompositions that can be computed one draw at a time without materialising the whole list. All of them start from the peeling procedure and constrain which assignment is taken at each step.

What the theorem does not say #

Uniqueness fails, and badly. The decomposition found depends on which assignment is peeled off first, and different orders give different lotteries with different numbers of terms. The theorem asserts existence, not a canonical form.

Nothing is said about which lottery is best. If the aim is a lottery that never gives a particular pair of tasks to the same person, or that uses as few distinct assignments as possible, the peeling procedure may not find it, and the minimum-terms question is a separate optimisation.

Three or more dimensions break it. The analogue for three-index arrays — every line in each of three directions summing to one — is false: there are such arrays that are not combinations of the corresponding permutation objects, and the polytope has corners that are not integral at all. The two-dimensional case works because its constraint matrix has a special structure that vanishes at the next size.

The row and column sums must both be one. Relax the columns and the object is a stochastic matrix, whose corners are the matrices with a single one in each row and no condition on columns — a much bigger and less interesting family.

Where it came from #

Birkhoff published in 1946, in a Spanish-language journal, as a result about matrices; von Neumann proved it independently in the same period while studying the assignment problem as a game, which is why the theorem carries both names. Neither was first: König and Egerváry’s work on bipartite matching from 1931 contains the essential combinatorics, and the peeling argument is a repackaging of it.

The result sits at a junction. From the combinatorial side it is Hall’s theorem with the counting supplied by the numbers rather than assumed. From the geometric side it is a description of the corners of a polytope, which is the question linear programming duality is built to answer. From the probabilistic side it is a statement that a distribution over a complicated set can be represented as a distribution over simple ones. Each community found it separately, which is the usual sign of a fact rather than a construction.

What the pictures cannot show #

Every figure here is $3 \times 3$ or $4 \times 4$, and the phenomena the theorem is about are at scale. Twenty-four corners can be drawn; a hundred and twenty cannot, and $10!$ is three and a half million. The reader has to take on trust that the decomposition stays short — at most $n^2 - 2n + 2$ terms — while the number of corners explodes, and that gap is the whole practical value of the theorem.

Nor can a picture show the polytope. The doubly stochastic $3 \times 3$ tables form a four-dimensional convex body with six corners, and its shape is not drawable; what the figures show are its corners as arrays and one interior point as an array, which is a list of coordinates rather than a picture of a solid.

And the lottery is not drawn at all, because a lottery has no picture. What is drawn is a set of outcomes and a set of weights, and the fact that drawing from those weights reproduces the shares in expectation is arithmetic that a static figure states rather than shows.

The ladder from here #

Below: Hall’s theorem, which supplies the whole assignment inside the support and is the only ingredient the proof needs, and stable matching, which asks a different question about the same grid. Sideways: duality, where the corner-attaining property of a linear objective comes from, and fair division, where randomising is the standard route from a divisible answer to an indivisible one. Above: total unimodularity, network flows, and the three-dimensional case where all of this fails.

What is worth carrying away #

The theorem is an instance of a pattern worth naming: a hard discrete set is the corner set of an easy continuous one.

When that happens, three things follow at once. Optimising a linear objective over the discrete set becomes a linear program. Any fractional solution can be written as a lottery over discrete ones, so fractional reasoning is legitimate even when only whole outcomes can be delivered. And the geometry of the continuous object — its dimension, its corners, its faces — becomes a language for talking about the combinatorics.

The pattern is not universal, and knowing where it stops is as useful as knowing where it holds. The travelling salesman problem’s tours are the corners of no polytope anybody can describe with polynomially many inequalities; the three-dimensional assignment problem’s corners are not the whole assignments. Where the pattern does hold, it holds for a reason in the constraint matrix, and finding that reason is the difference between a lucky example and a theorem.