Two out of three, and never all three

Three demands, each of which anyone would make of a rule for dividing seats, and none of which mentions the others.

Quota. Every region ends with the floor or the ceiling of its exact share. A region entitled to 15.417 seats gets fifteen or sixteen, never fourteen and never seventeen.

House monotonicity. Adding a seat to the house never takes one away from a region. Nobody should lose because the assembly got bigger.

Population monotonicity. If one region grows faster than another and neither shrinks, the faster-growing one does not lose a seat to the slower.

Each is a sentence long. Each is obviously desirable. No rule has all three, and that is not a statement about the five rules in the table.

Reading the table #

The table is the argument in the smallest form it fits into, and its shape is the shape of the theorem: three columns, five rows, and no row with three ticks.

Every cell was decided by a search, and it is worth being precise about what a tick and a cross each mean, because they are not the same kind of claim.

A cross is a found instance. The search generated a hundred and twenty instances of four regions, swept the house from four seats to thirty-nine, grew each region by nought, one or two per cent in every combination, and reported the first failure it found. A cross is therefore a proof: here is a census on which this method does that.

A tick is a search that found nothing, and by itself it establishes nothing at all. What upgrades three of the ticks to facts is a theorem: every divisor method is house monotone and population monotone, and the argument is one paragraph, given below. What upgrades Hamilton’s quota tick is a different theorem, and it is even shorter.

The distinction matters enough that the figure prints it. A table that rendered no counterexample was found and no counterexample exists with the same mark would be lying by layout, which is a way of being wrong that survives every check on the arithmetic. A picture that decides something by exhaustion has to say what was exhausted, or it is a picture of a belief.

Why divisor methods keep both monotonicities #

The priority formulation makes both arguments immediate, which is the best reason to prefer it.

A divisor method awards seats by listing the priorities $p_i / s(k)$ for every region $i$ and every $k$, sorting them downward, and handing out seats in that order until the house is full.

House monotonicity is then trivial. Growing the house by one seat means going one further down a list that has not changed. Nobody’s seat is taken back, because seats are only ever added. That is the whole argument.

Population monotonicity takes one more line. If region $i$ grows and region $j$ does not, every priority of $i$ rises and every priority of $j$ is unchanged. Rescaling to keep the total right multiplies every priority by the same factor, which preserves the order. So $i$’s seats cannot fall while $j$’s rise: the pair’s relative position in the list has moved in $i$’s favour, and nothing else has moved.

Both arguments use only that the method is a ranking, and neither mentions the signpost. So they hold for every method on the dial and for the two off it — for any rule at all that awards seats by sorting a list of priorities that depend on each region separately.

Why Hamilton keeps quota and nothing else #

Hamilton’s method takes the floor of every quota and hands the leftover seats to the largest remainders. Every region therefore ends with its floor or its floor plus one, which is the quota rule by construction. Nothing has to be proved.

What it loses is both monotonicities, and the mechanism is the same in each case: the remainders are compared with each other, so a change anywhere in the table can reorder them.

Grow the house and every quota grows; the floors grow unevenly and the remainders are recomputed from scratch. A region whose remainder was near the top can find itself near the bottom, and the seat it was given at the smaller house goes elsewhere at the larger. That is the vanishing seat, and the figure finds one.

Grow one region’s population and every other region’s quota falls slightly, because the total has risen. Their remainders change; the ranking changes; a region that grew can lose a seat to one that did not. The figure finds one of those too.

The comparison is exact. A divisor method decides each region’s seats from that region’s own population and the divisor, and the only interaction between regions is through the choice of divisor, which affects everybody the same way. Hamilton’s method decides the last few seats by a competition between regions, and a competition can be reordered by anything.

The property that makes Hamilton respect quota — that every region is anchored to its own floor — is the same property that makes it non-monotone, because the anchor moves when anything moves.

What a violation looks like from inside #

Neither monotonicity failure is a rounding artefact that a more careful implementation would remove, and it is worth seeing why not.

Take Hamilton’s method at some house size and add one seat. Every quota is multiplied by $(h+1)/h$, so every quota grows — but the floors grow by nought or one, and which regions get the extra whole seat depends on where each quota was sitting relative to the next integer. A large region’s quota grows by a large absolute amount and can cross an integer; a small region’s grows by very little and cannot. So the pool of leftover seats changes size, and the ranking of remainders that distributes them is computed afresh against a different pool.

None of that involves an approximation. The arithmetic is exact at every step — the figures compute it in whole numbers precisely so that nothing can be blamed on a float — and the paradox is a property of the rule. A rule that ranks a quantity computed from a total will reorder when the total moves, and both of Hamilton’s failures are that one sentence applied twice.

What Balinski and Young proved #

The table shows five methods each failing at least one demand. The theorem is stronger and it is not obtained by extending the table.

No apportionment rule whatever is both within quota and population monotone. Not the five here, not any rule with a name, not a rule not yet invented. The proof exhibits a small family of instances on which any rule satisfying both would have to contradict itself: the quota constraint forces certain allocations, population monotonicity forces certain comparisons between them, and the two sets of constraints have no common solution.

That is the same shape of argument as Arrow’s theorem and it should be read the same way. It does not say the known methods are inadequate and a better one should be sought. It says the search is over, and what remains is a choice about which demand to give up.

There is a second half worth knowing, because it says the impossibility is sharp rather than sweeping. Balinski and Young also constructed a rule that stays within quota and is house monotone — their quota method — which shows that the failing combination is the specific pair of quota and population monotonicity rather than any two of the three at once. Two out of three is achievable, in more than one way, and three is not.

Which one to give up #

The three demands are not equally weighty, and the argument about which to abandon is the whole practical content of the subject. It is the same argument Arrow’s four conditions force on the neighbouring problem, and it is settled the same way: by deciding which failure a reader will forgive.

Giving up quota is what every divisor method does. The cost is a region occasionally getting a seat more or less than the floor or ceiling of its share, which is a violation that is rare, is bounded in practice, and is invisible unless somebody computes the quota and checks.

Giving up house monotonicity is what Hamilton does. The cost is that a region can lose a seat when the assembly grows — a failure that is not rare, that is visible to everybody it happens to, and that provokes exactly the reaction the name of the paradox records.

Giving up population monotonicity is what Hamilton also does, and what no stable matching rule can avoid in its own setting either, and it is the worst of the three to explain: a region grows faster than its neighbour and hands the neighbour a seat.

Put like that the choice is not close, and the practice reflects it: divisor methods are what assemblies use. The reasoning is the one a cost-sharing rule is chosen by — not which rule is best, but which of its failures can be lived with. But the ranking above is a ranking of how embarrassing each failure is, not of how unfair, and those are different scales. A quota violation is a region being denied a seat it can prove it is owed; a house-monotonicity violation is a region losing a seat that nobody was owed in the first place. Which of those a reader finds worse is a question about what a share is, and the same question decides how a coalition’s winnings should be split.

What “no rule whatever” has to mean #

An impossibility about every rule needs the word rule defined, or it says nothing, and the definition is where the content is.

An apportionment rule here is a function from a list of populations and a house size to a list of whole seat counts adding to the house size. That is all. It need not be computable by any formula, it need not treat regions alike, it need not be describable in words. It may return a set of tied answers, and the theorem is stated so as to cover that case.

Two properties are usually built into the definition and are worth naming because they are doing work. The rule must be anonymous — relabelling the regions relabels the answer, and nothing else changes — and it must be homogeneous, so that doubling every population and keeping the house size gives the same answer. Both are so obviously desirable that they are rarely stated, and both are needed: a rule that consulted the alphabetical order of region names could satisfy quota and population monotonicity by tie-breaking dishonestly.

That is the general shape of every impossibility result. The theorem is only as strong as the definition of the objects it quantifies over, and reading one means reading the definition first. The four conditions on a voting rule are exactly the same kind of hypothesis, and the same warning applies: an “unreasonable” rule that escapes the theorem is usually escaping through the definition rather than through the argument.

What the pictures cannot show #

A tick is not a proof. The searches ran over a hundred and twenty instances of four regions, and a rule can fail a property on the hundred and twenty-first. Three of the ticks are backed by theorems stated in the text; none is backed by the search.

The theorem is about all rules and the table is about five. Five rows are not evidence that the fourth column is empty. They are the evidence that made somebody look, which is a different and much weaker thing.

The instance family is stated and it is not reality. Populations are drawn log-uniformly between twenty and about six thousand, which produces the skewed instances a quota violation needs; a uniform family finds none for Webster in twenty-two thousand tries. The family was stated before the search rather than adjusted until the answer came out, and that ordering is the difference between a search and a fit.

The population search is one family of second censuses. Every region grows by nought, one or two per cent, which is eighty-one censuses per instance at four regions. A rule could fail population monotonicity only outside that family and be marked with a tick here; three of the four ticks in that column are backed by the theorem above, and the fourth is Hamilton’s, which is a cross.

And the sharpness is described rather than drawn. The rule that keeps quota and house monotonicity exists and is not implemented here; no figure on this page shows the corner of the table that can be filled.

Where the ladder goes next #

The rung above stops asking which demands a method meets and asks what each method is for. Huntington’s question is whether any transfer of a seat between two regions would reduce the inequality between them — and a method is characterised by the measure of inequality under which its answer cannot be improved.

That reframing does something this rung cannot. It turns which method is right into which measure of unfairness is meant, and a question of that form has an answer as soon as somebody says what they want. The impossibility above stands; what changes is that the choice stops looking arbitrary.

What is worth carrying away #

An impossibility theorem is a statement about a search, and the useful reading of one is always the same: stop looking, and choose.

Three properties, each obviously desirable, each individually achievable, and no rule with all three. Every hour spent looking for a better apportionment method after 1982 was spent looking for something that does not exist — and the value of the theorem is exactly the hours it saves. The same service is done by every impossibility in this field: the result is not that a problem is hard but that a particular search has no object at the end of it. The demands were never in conflict as sentences; they became incompatible as constraints, and the only way to discover that was to write them down precisely enough to be contradicted.