The seat that vanishes when the house grows

Five regions, lettered A to E, holding ten thousand people between them. Twenty-seven seats to divide among them in proportion to their populations. Nothing about that sentence looks as though it could go wrong.

The worksheet everything starts from #

A region’s quota is what it would get if seats could be cut into pieces: its population, times the house size, divided by the total population. For region A that is

$$\frac{5710 \times 27}{10000},$$

which is $154170/10000 = 15417/1000$, or $15.417$ if a decimal is wanted. The other four are $7209/1000$, $351/200$, $1431/1000$ and $297/250$ — that is, $7.209$, $1.755$, $1.431$ and $1.188$.

The fractions are not affectation. The whole of this subject is a comparison against a whole number: is this quota’s floor $1$ or $2$, is that remainder larger than this one. A quota written as a decimal has already been rounded once before the rule that is supposed to do the rounding gets to look at it, and the figures in this essay therefore carry every quota, every remainder and every divisor as an exact ratio of whole numbers, comparing two of them by cross-multiplying rather than by subtracting decimals.

Five numbers, summing to exactly $27$, none of them whole. Something has to give.

Twenty-five seats, and two nobody owns #

Take the floor of each quota. That is $15$, $7$, $1$, $1$ and $1$, and $15 + 7 + 1 + 1 + 1 = 25$. Two seats are unassigned.

That shortfall is not an accident of this instance, and the reason is a counting argument worth doing once. Each region’s quota exceeds its floor by less than one, so the five shortfalls add to less than five; and they add to a whole number, since the quotas add to the whole number $27$ and the floors are whole. So the number of spare seats is at least zero and at most four — at most one less than the number of regions.

There are therefore always strictly fewer spare seats than regions, which is the pigeonhole principle with the boxes and the objects the usual way round: fewer things than boxes means some box stays empty, so at least one region is certain to be left holding only its floor. The pigeonhole principle is normally reached for to prove that something must happen; here the same counting argument proves that somebody must be disappointed, and the entire subject is the question of who.

So a rule is needed. The oldest and most obvious one is to rank the regions by how much of a seat they were short — by their remainders — and give the spare seats to the largest. Here the remainders are $417/1000$, $209/1000$, $151/200$, $431/1000$ and $47/250$, so C at $0.755$ and D at $0.431$ take the two spare seats, and the result is $15, 7, 2, 2, 1$.

That rule is called Hamilton’s method, and it has one property that will matter for the rest of the essay: every region ends with either the floor or the ceiling of its own quota. A region entitled to $1.755$ seats gets one or two, never three and never none. That property has a name — the quota rule — and Hamilton’s method satisfies it by construction, since it starts from the floors and adds at most one.

Five rules and four answers #

Largest remainders is not the only reasonable rule. A whole family of alternatives says: pick a divisor $d$, give each region the number of seats its population divided by $d$ rounds to, and adjust $d$ until the seats sum to the house size. What separates one such method from another is only where the rounding happens.

Webster’s method rounds at the halfway point, the way arithmetic is normally taught. It gives $16, 7, 2, 1, 1$, and $16 + 7 + 2 + 1 + 1 = 27$. Region A gains a seat and region D loses one, on populations nobody has touched.

Adams’s method rounds every share up. Since that would award far too many seats at the natural divisor, the divisor has to rise until the total comes back to $27$, and the effect is to squeeze the largest region: $14, 7, 2, 2, 2$, which also sums to $27$ since $14 + 7 + 2 + 2 + 2 = 27$. Region A is entitled to $15.417$ seats and is given $14$.

Hill’s method rounds at the geometric mean $\sqrt{k(k+1)}$ rather than the arithmetic mean, and on this instance it agrees with Hamilton exactly: $15, 7, 2, 2, 1$. Five rules, four distinct answers, one set of populations. That much is only disagreement, and disagreement between reasonable rules is the normal condition of this whole field — it is what Arrow’s four conditions are about one anchor over. What follows is worse than disagreement.

The seat that vanishes #

Fix the populations. Fix the rule at Hamilton’s largest remainders. Vary only the size of the house.

Region D holds two seats when there are twenty-eight to give out, and one seat when there are twenty-nine. Nobody moved, nobody was born, and no rule was changed. The only thing that grew was the number of seats, and D’s share of it went down.

The sweep is exhaustive over the range drawn. Every house size from twenty to thirty-four was apportioned, the seat totals were checked against the house at each one, and the fifteen results were then searched for a step that goes downward. Exactly one exists. This is the house habit and it is worth naming: the figure is not an illustration of a paradox somebody else found, it is a report of a search, in the same spirit as the four-colour proof’s exhaustive case list — the drawing is the decision, not a picture of it.

A search that only ever finds something has not been tested, so here is the same machinery on populations that do not misbehave.

Five points going round a circle at different speeds #

The mechanism is completely transparent once the right object is looked at, and the right object is the remainder rather than the quota.

Region $i$’s quota at house size $h$ is $p_i h / T$, so its remainder is the fractional part of that. Increase $h$ by one and every remainder advances by exactly $p_i/T$ and wraps when it passes one. So each region is a point walking round a circle of circumference one, at its own constant speed, and the speeds here are $0.571$, $0.267$, $0.065$, $0.053$ and $0.044$. Those speeds sum to $0.571 + 0.267 + 0.065 + 0.053 + 0.044 = 1$, which they must, and that is why the number of spare seats stays small as the house grows: the five points collectively advance one full lap per extra seat.

Hamilton’s rule is then nothing but which of the five points are furthest round. And the answer to that question is not monotone in $h$, because the points move at wildly different speeds. Region B advances by $0.267$ each step and region D by $0.053$; between house $28$ and house $29$, B’s remainder went from $0.476$ to $0.743$ while D’s crawled from $0.484$ to $0.537$. D was third in the ranking and B was fourth; one step later B had swept past and D was fourth. Three spare seats were available at both sizes, and D was inside the top three at one and outside it at the other.

Nothing here is about seats. It is the behaviour of the fractional parts of multiples of a fixed number, which is exactly the object behind the three-gap theorem and behind arithmetic on a dial: points placed at $\{\alpha\}, \{2\alpha\}, \{3\alpha\}, \dots$ and the question of how they arrange themselves. The Alabama paradox is that arrangement changing order, and a subject that looks like a question about assemblies turns out to be a question about rotations of a circle.

Rounding by divisor instead #

A divisor method has no remainders to rank and therefore no ranking to reshuffle, and it is a theorem that no divisor method can produce the Alabama paradox at all: raising the house size can only lower the divisor, and lowering the divisor raises every region’s share at once, so no region’s seat count can fall. That is a genuine repair, and it is the reason the divisor family exists.

But a divisor method is usually presented dishonestly — “try a divisor near the ideal and adjust until the seats come out right” — which is true of the practice and silent about there being an exact answer.

There is one. Region $i$’s $(k+1)$-th seat is awarded exactly when the divisor is at most $p_i/s(k)$, where $s(k)$ is the method’s rounding signpost. So the seat total is a step function of the divisor whose steps sit precisely at those ratios, and the divisors awarding a given house size form an interval between two consecutive ones.

The interval is $(1335/4,\ 5710/17]$ — open at the bottom, closed at the top, which is how the arithmetic actually has it and not a convention. In decimals that is everything strictly above $333.75$ and at most about $335.88$. Sorting the candidate ratios and reading off two consecutive ones is the whole of the method, and comparing two such ratios exactly, by cross-multiplication rather than by decimals, is the same manoeuvre that builds every fraction exactly once and that decides how close a fraction can get to a target.

What a divisor costs #

Look at what Jefferson’s divisor did to region A. Its exact quota is $15417/1000$. The quota rule allows it $15$ seats or $16$. It is given $17$.

That is not a rounding error and it is not a near miss. The comparison is between whole numbers: the ceiling of A’s quota is $16$, and $17 > 16$. A region is handed a number of seats that its own entitlement does not round to in either direction, by a rule with no arbitrary steps anywhere in it. Adams’s method breaks the quota rule the other way on the same instance, awarding A only $14$ against a floor of $15$.

The break is systematic rather than incidental. Rounding every share down favours large populations, because a large region’s discarded fraction is a smaller proportion of what it keeps; rounding every share up favours small ones for the mirror reason. And no divisor method has any mechanism that could notice a region drifting outside its own band, because no divisor method ever computes the band — the quota rule is a statement about quotas, and a divisor method never looks at one.

Webster comes through this instance clean. That is a fact about these five numbers and not a guarantee — the method computes no band and can therefore give no undertaking about one — and the caption says so rather than letting a single clean case stand for a rule. Which is the standing difficulty with an instance: a small case that behaves is evidence of very little, and it is the same trap that a profitable lie sets one anchor over, where the misreports that pay are rare enough that a few hand-picked profiles suggest none exist.

Growing faster and losing the seat #

The third failure needs two censuses rather than two house sizes.

Fifty more people in A and ten more in D. Region D’s population goes from $530$ to $540$, a rise of $54/53$, which is about $1.887\%$. Region A’s goes from $5710$ to $5760$, a rise of $576/571$, about $0.876\%$. D grew more than twice as fast as A, and D lost a seat to A.

The second census is not hand-picked, and that is the part worth insisting on. A family of censuses is stated in advance — each region may gain nothing, ten, twenty, and so on up to eighty people — and the whole family is walked. That is $9^5 = 59049$ censuses, every one apportioned and tested, ordered so that the census reported is the smallest growth in the family that produces the reversal. The paradox is not lurking at the edge of some contrived example; it is sixty people away from where the instance started.

Every comparison in that walk is exact. Asking whether D grew faster than A means asking whether $540/530 > 5760/5710$, and the figure answers it by cross-multiplying into $54 \times 571 = 30834$ against $576 \times 53 = 30528$ — whole numbers, no decimals consulted, in the same spirit as the exhaustive certification that settled the thirty-six officers.

What these pictures cannot show #

Three paradoxes have now been exhibited on one instance, and it is necessary to be exact about what has and has not been established, because the gap is large.

What the drawings settle is finite and complete. The Alabama sweep is exhaustive over these five populations and over these fifteen house sizes; within that rectangle the claim is not that a fall was found but that exactly one exists. The divisor interval is exact and closed on both ends, verified by re-deriving the seat counts at both endpoints and at a point between them. The census walk is exhaustive over a family of $59049$ censuses that was written down before the search began. Each of those is a decided question, and a reader can redo any of them.

What the drawings do not touch is the claim the subject is famous for. Balinski and Young proved in 1982 that no apportionment method whatever is both within quota and free of the population paradox. That is a statement quantified over every rule that could ever be written down, including the ones nobody has thought of, and a search over five named methods is not a sample of it — it is not even a start. No finite computation reaches a claim of that shape, and this collection has been here before: transcendence is the same difficulty in a different field, where a search over a hundred and sixty thousand polynomials is honest evidence and no part of a proof.

So the honest division is this. The figures prove that these five named methods fail in these particular stated ways on this particular instance. The theorem that the failure is unavoidable is an argument in prose, made by a route the pictures do not take — and the situation is precisely the one where a counting argument establishes that something must exist without any picture producing it.

One more limit, smaller and real. Every ranking in these figures breaks ties by region index, stated once and applied everywhere. A genuine tie in the remainders or in the divisor priorities is possible, and the figures settle it by fiat rather than by argument. A rule that had to be adopted rather than drawn would need to say something about that, and saying something about it is not a mathematical question.

The names, and the theorem #

The methods carry the names of the people who proposed them, and the dates are worth stating because they explain why five rules exist rather than one. Alexander Hamilton’s largest-remainder method and Thomas Jefferson’s round-everything-down method were both put forward in the 1790s; Daniel Webster’s arithmetic-mean rule followed in 1832, John Quincy Adams’s round-everything-up rule in the same decade, and Joseph Hill’s geometric-mean rule in 1911. The Alabama paradox got its name in the 1880s, when it was noticed as a property of a computation rather than derived from anything.

Michel Balinski and Peyton Young settled the matter in 1982, and the shape of their result is the one this collection keeps meeting. It does not say that the existing methods are bad or that a better one should be sought. It says the search is over: staying inside quota and being immune to the population paradox are incompatible demands, and any rule satisfying the first must fail the second on some instance. Which half to give up is a decision, and it is not a decision arithmetic can make.

Where the ladder goes next #

The subject looks like a question about assemblies and is a question about rounding. Five numbers, none of them whole, have to be replaced by five whole numbers with the same total, and every consequence in this essay — the vanishing seat, the region above its own quota, the faster-growing region that loses — follows from that requirement and from nothing else. Change the five numbers and the paradoxes move; they do not go away, because the requirement has not.

What this anchor establishes is the pattern the rest of the field runs on. A rule for choosing is stated exactly; its consequences are computed rather than argued about; and the consequences turn out to include things nobody writing the rule down would have predicted. Arrow’s theorem and the profitable misreport are the same story told about preferences instead of populations, and both end where this one does: with a trade that has been proved unavoidable, and a choice about which half to keep.