One table, two lotteries

The first two rungs establish that a table of shares can always be written as a lottery over whole assignments. That is an existence statement, and existence statements have a habit of concealing the interesting question, which is: how many ways, and does the choice matter?

The answer is many, and yes.

Why the decomposition is not unique #

The reason is dimensional and immediate once the previous rung’s picture is in place.

The polytope of tables of shares for $n$ people has dimension $(n-1)^2$ and $n!$ corners. A point inside a polytope is a mixture of corners, and when the corners far outnumber the dimensions the mixture is not determined: there are $n!$ unknown weights, one equation per dimension plus one for the total, and $n! - (n-1)^2 - 1$ degrees of freedom left over.

For three people that is $6 - 4 - 1 = 1$ spare degree of freedom; for four it is $24 - 9 - 1 = 14$; for five, ninety-nine. The set of lotteries producing a given table of shares is itself a polytope, and it grows very fast.

The greedy algorithm the first rung uses picks one point of that set, and which one depends entirely on the order in which it considers the assignments — which is why running it forwards and backwards gives two answers.

It is worth noticing that the algorithm gives no sign of this. It runs, it terminates, it produces a decomposition that reconstructs the table exactly, and nothing in its output indicates that a different order would have produced something else. An algorithm that makes an arbitrary choice silently is indistinguishable, from its output, from one that had no choice to make, and the only way to find out is to run it differently — which is what the hero figure does.

Why the difference matters #

If the only thing anybody cares about is the shares, the choice is immaterial by definition. It is not the only thing.

A lottery is run once. The shares describe the average; what actually happens is one whole assignment, and the people involved experience that one. Two lotteries with the same shares can differ completely in which assignments are possible at all.

Correlations differ. In one decomposition, person one getting task A might always coincide with person two getting task B; in another, never. The marginal probability of each is the same in both, since the marginals are the table. Nothing in the table of shares records that, and it is exactly what matters when the tasks interact — when two people would rather be assigned to compatible jobs, or when a pair of assignments is jointly infeasible for a reason outside the model.

And the support differs. Some decompositions use few assignments and some many, so one lottery might give a person a small chance of a very bad outcome while another never assigns it at all. A guarantee about an average is not a guarantee about a worst case, and in a setting where the draw happens once and is not repeated, the worst case is what somebody with a bad outcome experiences.

That last point is worth separating from the others because it is where the mathematics and the ethics meet. Randomisation is often introduced precisely to be fair — nobody can complain about an unbiased draw — and the fairness it delivers is fairness of expectations. The person who draws badly has been treated fairly in that sense and badly in every other, which is a real and much-discussed tension and is not resolved by any theorem here.

The arithmetic of that gap deserves stating once, because it is what makes the whole rung necessary rather than pedantic. At three people there is one spare degree of freedom and the two decompositions in the hero figure differ modestly. At ten people the polytope has eighty-one dimensions and three and a half million corners, so a table of shares is consistent with a set of lotteries of dimension over three million.

Choosing among three million dimensions’ worth of possibilities is not a rounding decision. It is the design of the procedure, and publishing only the shares hands that design to whoever implements it.

What can be asked for instead #

Since the shares do not determine the lottery, a procedure has to specify more. Three kinds of extra requirement are standard, and they conflict.

Minimal support. Use as few whole assignments as possible, which matters when each one has a fixed cost to set up. The bound from the previous rung says $n^2 - 2n + 2$ suffice, and finding a decomposition achieving the minimum is NP-hard — proved by Dufossé and Uçar in 2016, which is a striking hardness result for a problem whose existence question is a classical theorem from 1946. Seventy years between “a decomposition exists” and “the shortest one is hard to find” is a fair measure of how differently the two questions behave.

Maximal fairness. Require that no person ever receives a task they rank below some threshold — that the lottery has no catastrophic draws, not merely a good average. That restricts the support to a subset of the assignments, and it may be impossible for a given table: the shares can force some weight onto an assignment somebody hates.

And strategyproofness. Require that no person can improve their expected outcome by misreporting their preferences. That is a condition on the procedure rather than on any one lottery, and it is where the subject’s impossibility lives.

The impossibility #

The natural thing to want is a procedure taking each person’s preferences over tasks to a lottery, which is efficient — nobody can be made better off without somebody worse — and strategyproof, and treats people symmetrically.

No such procedure exists, for four or more people. That is Zhou’s theorem of 1990, and its shape is the familiar one from this field: three conditions each of which is individually reasonable, and no rule satisfying all three.

The two procedures actually used each give up one condition.

Random serial dictatorship puts the people in a random order and lets each take their favourite remaining task. It is strategyproof — a person’s report cannot change the order, and given the order their best move is to say what they want — and symmetric, since every order is equally likely. It is not efficient: the resulting shares can be dominated, meaning another lottery would give everybody at least as good a chance of everything they prefer and somebody a strictly better one.

Probabilistic serial has everybody “eat” their favourite available task at a uniform rate until it is exhausted, then move on; the fraction each has eaten when the clock stops is their share. It is efficient and symmetric, and it is not strategyproof: a person can gain by claiming to prefer a task that nobody else wants, eating it uncontested, and then moving on to what they actually want while others are still occupied.

Two procedures, two conditions each, and the third given up in opposite directions. That is what an impossibility theorem looks like once people have to build something anyway: not a dead end, but a fork with the cost of each branch known in advance.

It is worth being clear about what kind of impossibility Zhou’s is, since this field has several shapes of them.

It is not an impossibility of the Arrow kind, where the conditions are conditions on a rule and the conclusion is that only a dictatorship survives. Here symmetry is assumed, so dictatorships are already excluded, and the conclusion is that nothing at all survives.

It is also not tight in the number of people: for three people procedures satisfying all three conditions do exist, and the impossibility begins at four. An impossibility with a threshold is more informative than one without, because it identifies what has to be present for the obstruction to appear — here, enough people that a coordination failure can involve four of them at once.

The efficiency that is lost #

The failure of random serial dictatorship is worth exhibiting because it is counter-intuitive: a procedure that lets everybody choose freely produces an outcome everybody would rather trade away from.

The mechanism is a coordination failure. Under a random order, a person early in the queue takes their favourite even when somebody later wants it far more and would have given up something the first person values slightly. No individual is behaving badly and no draw is inefficient; what is lost is the trade that would have happened had the two known about each other. The lottery over orders averages that out and the average is dominated by a different lottery which never produces the bad matches.

The standard example needs four people and is worth the space. Two people rank the tasks A, B, C, D and two rank them B, A, D, C. Random serial dictatorship gives each of the four a half share of their top task and a scattering of the rest; probabilistic serial gives each a half share of their top and a half of their second, because the two groups eat different things and never compete for the third and fourth. Every person’s chances are better under the second, at every rank, and the first is what a strategyproof rule is forced to produce.

Efficiency here is about the lottery, not about any single draw. Every individual draw of random serial dictatorship is a perfectly good assignment — nobody could improve without somebody losing. What is dominated is the distribution, and that is a strictly stronger requirement, called ordinal efficiency, which the previous rungs’ notion does not distinguish.

That distinction between efficiency of the outcomes and efficiency of the distribution is what makes this subject harder than it looks, and it is the reason the impossibility exists at all.

What it costs to specify a lottery properly #

The description grows. A table of shares is $n^2$ numbers; a lottery is a list of assignments with weights, up to $n^2 - 2n + 2$ of them, each of which is $n$ numbers. So the honest specification is a factor of $n$ larger, which is why the shares are what get published — and the publication of the smaller object is exactly the loss of information this rung is about. The same trade appears wherever an average is published in place of a distribution.

Choosing a decomposition is itself a computation. The greedy method is fast and arbitrary; the minimum-support one is NP-hard; anything with a fairness requirement needs the requirement expressed as constraints and the resulting program solved. So specifying more than the shares moves the cost from the specification to the implementation.

And people may not be able to check it. Verifying that a stated lottery produces stated shares is easy arithmetic; verifying that a procedure produced the lottery it claimed is not, unless the randomness is public. Every practical implementation therefore has to publish its random seed or run its draw observably, which is an engineering requirement produced by a mathematical one.

Where this is a live question #

The subject is not academic, and knowing the applications explains which of the conditions people actually give up.

School choice. Assigning children to schools from stated preferences is exactly this problem, at the scale of a city, with tens of thousands of people and hundreds of tasks. Several large systems use a variant of random serial dictatorship — strategyproof, so families can safely state true preferences — and accept the inefficiency, on the grounds that a mechanism families can be told to be honest with is worth more than a marginally better allocation. The alternative had been a system where stating an unpopular school first improved one’s chances, which turned the problem into a guessing game and disadvantaged families with less information about it.

Course allocation. Universities assigning students to over-subscribed courses face the same problem with the additional feature that students take several courses at once, so the object being allocated is a bundle rather than a single item. That breaks the assignment structure entirely and makes the problem genuinely hard, and the mechanisms in use are approximations with their own literature.

And organ exchange. Kidney exchange chains are a matching problem with the additional constraint that transplants in a cycle must happen simultaneously, which bounds the cycle length to two or three and, again, destroys the polytope’s integrality — bounded-length cycle cover is NP-hard, and the field’s algorithms are integer programs rather than the clean method of the rung below.

The pattern across the three is that the clean theory covers the simplest case and every real system adds a constraint that breaks it. What survives is the vocabulary — efficiency, strategyproofness, symmetry — and the knowledge of which pairs are compatible, which is what an impossibility theorem is for.

What the pictures cannot show #

Two decompositions are drawn and there are infinitely many. The set of lotteries producing a given table is a polytope in its own right, of dimension at least one for three people and at least fourteen for four. The figure exhibits two of its points, chosen because a simple algorithm run in two directions finds them.

Correlations are the point and are not drawn. What distinguishes two lotteries is which assignments co-occur, and a picture of two lists of weighted permutations does not display that: a reader has to compare the lists item by item.

The shares are drawn and preferences are not. Everything in this rung’s second half is about people’s rankings of the tasks, and no figure carries one. The polytope pictures are about the space of lotteries; the impossibility is about a map from preference profiles into that space, which is an object of a different kind entirely.

And nothing here shows the impossibility. Zhou’s theorem is about all procedures on all preference profiles, and the figures show one table of shares and two of its decompositions. The theorem’s evidence is a proof, and the two named procedures are what a picture of the situation would have to compare.

Where the ladder goes next #

The last rung on this pass asks what happens when the constraint structure is slightly larger, and integrality — the property everything here rests on — stops holding: where the corners stop being whole.

Named here as debts. Zhou’s theorem itself, stated above and not proved. And the minimum-support decomposition, whose hardness is a modern result and whose statement — the easy existence question has a hard optimisation question sitting on top of it — is a shape worth having.

Also named as a debt: the joint distribution, which is what a lottery really is and which nothing here measures. Two lotteries with the same marginals differ in their correlations, the correlations are what matter, and no figure or number above reports one.

Sideways, the polytope whose corners are being mixed is the previous rung’s, the fairness conditions are the same family as those a division of a shared value must satisfy, and the original decomposition is the anchor’s first rung.

Sideways: the objection nobody can make louder is the same question about a coalition rather than an assignment, and envy-free up to one item is what fairness becomes when the goods cannot be split at all.

What is worth carrying away #

A specification by averages under-determines a procedure, and the residue is usually what the people involved actually care about.

The table of shares is a complete description of the marginals and says nothing about the joint distribution. Two procedures matching it can differ in which outcomes are possible, in what co-occurs with what, and in whether anybody can gain by lying — and none of those differences is visible in the object being specified.

The habit worth taking is to count the degrees of freedom a specification leaves. Here it is $n! - (n-1)^2 - 1$, which is small for three people and enormous for ten, and a specification leaving that much room is a specification of something other than the thing being built.