Where the rounding runs out

The table inside every quota found that a table of seats for districts and parties can always be rounded so that every cell ends at the floor or the ceiling of its fair share and every district’s and party’s total is exact. The proof walked through the cells that were not yet whole, turning between rows and columns, and pushed seats round the loop it closed.

Legislatures sometimes ask for more than two families of totals. Seats for every district, seats for every party, and within every district and every party a balance between groups — two genders, or three language communities. That makes the table three-dimensional: a cell is a district, a party and a group, and the totals run along every line of the table.

Every total in this table is a whole number, and there is no way to round the halves to whole seats that keeps all of them. The guarantee two dimensions gave does not survive a third, and the reason is a loop of seven cells.

Totals along every line #

A three-way table has three kinds of line. Fixing a district and a party and running across the groups gives the seats that party wins in that district, whatever group they go to. Fixing a district and a group and running across the parties gives that group’s seats in that district. Fixing a party and a group and running across the districts gives that group’s seats on that party’s benches.

Prescribing every line total is prescribing all three at once: the seats for every district and party, as a two-dimensional apportionment would; and a balance of groups inside every district and inside every party. There are twenty-seven lines in a table of three by three by three, and the drawn table meets all twenty-seven with fair shares of a half — twenty-four lines need one seat and three need none.

A fractional table meeting the totals is what a continuous fit produces, exactly as the alternating scaling produced one in two dimensions; this one is built directly rather than fitted from votes, so that its shares are simple enough to follow by eye. The question is the same: can the fractions be rounded, each to its floor or its ceiling, so that every line still adds to its total? For a cell holding a half that means a seat or no seat, and for a cell holding nothing it means no seat.

The fractions are never the problem #

The difficulty is entirely in the whole numbers, and it helps to see that the fractional side of the problem stays easy in three dimensions.

The alternating scaling that fits a two-dimensional table of votes to its row and column totals extends without change to three families. Scale every line across the groups to its total, then every line across the parties, then every line across the districts, and repeat. Whenever some table of positive fractions meets all the totals, the alternation converges to one; Csiszár proved it in 1975, as part of a general theory of fitting tables to prescribed margins. So a three-way apportionment always has its fair shares, exactly as a two-way one does, and they meet every district-and-party, district-and-group and party-and-group total to any precision required.

What fails is the step from those shares to whole seats. The table of halves is not a pathology of the fitting; it is a perfectly good table of fair shares, meeting all twenty-seven totals, and the only thing wrong with it is that seats come in ones. Two dimensions hid that distinction, because there every table of fair shares could be rounded. Three dimensions expose it: the fair shares exist, the totals are whole numbers, and the rounding inside the shares does not.

Why two dimensions always round #

The two-dimensional answer is a parity argument, and it is worth seeing in the simplest table where it bites.

Every row holds two halves or none, and so does every column, because the totals are whole numbers. So each half has exactly one partner in its row and exactly one in its column. Start anywhere and step to the row partner, then to that cell’s column partner, then to the next row partner: the steps alternate row, column, row, column, and when they return to the start they have taken an even number of steps, since every row step is followed by a column step.

This is Hall’s condition in its easiest case: two halves in a row are a district asking for one seat from two cells, and a loop that alternates between districts and parties can always meet every such demand. A rounding inside every quota must give exactly one of the two halves in each row a seat, and exactly one of the two in each column. Round a cycle that alternates, that means seat, no seat, seat, no seat — which closes up precisely because the cycle is even. Two directions force every cycle to be even, and an even cycle can always be coloured alternately. That is the whole of the two-dimensional guarantee for halves, and the pushing argument of the two-dimensional essay is the same idea for general fractions.

Three partners, and a cycle of seven #

In three dimensions each half has three lines through it, one in each direction, and in the drawn table each of those lines holds exactly one other half. So each half has three partners, and nothing forces the steps between them to alternate in any pattern.

The marked cycle runs through the cells 212, 312, 322, 122, 123, 223 and 213, each written district, party, group. Its seven steps go across districts three times, across parties twice and across groups twice. Every step joins two halves on a line whose total is one seat, so a rounding inside quota must seat one end of every step and not the other. Going round the cycle the seats must therefore alternate — and seven alternations cannot return to where they started.

Follow it round explicitly. Suppose 212 gets a seat. Its line across districts holds 312 as well, with a total of one, so 312 gets none. The line across parties through 312 holds 322, which must then take that line’s seat; so 322 gets one, and 122, on the same line across districts, gets none. The line across groups through 122 forces a seat at 123; the line across districts through 123 forces none at 223; the line across parties through 223 forces a seat at 213. And the line across groups through 213 holds 212, which already has a seat — two seats on a line whose total is one. Starting instead with no seat at 212 fails the same way with every choice reversed.

That is the obstruction, and it is exactly the obstruction to colouring a map with two colours when some region borders an odd ring of others. A rounding inside quota is a two-colouring of the halves in which every join has one end of each colour, and a graph can be two-coloured exactly when it has no cycle of odd length. The two-dimensional graph never has one. The three-dimensional graph can, and this one does.

The nearest whole table #

The totals themselves can still be met in whole seats. What cannot be done is to meet them while keeping every cell inside its quota.

The best whole table, found by searching every way of placing seats that meets the twenty-seven totals, puts seven of its eight seats on halves and one in a cell whose fair share is nothing. That single seat is what breaks the odd cycle. The cell 222 lies on three lines, each with a total of one seat and two halves on it, and a seat at 222 gives all three lines their seat from outside the halves. Three joins are freed from alternating at once, and one of them, from 322 to 122, is a step of the cycle of seven.

So the totals can be met and the quotas cannot. In two dimensions the two were compatible for every table; in three, a table as small as this one separates them. Any method for three-way apportionment that is required to meet every total exactly must, on tables like this, place a seat where the fair share says none belongs — not because the method is careless, but because nothing else meets the totals.

How small the obstruction can be #

The search runs through every arrangement of halves with none or two on each line, in every box up to three cells on a side, and asks of each whether its graph has an odd cycle. The three smaller boxes, each with a side only two cells long, never produce one: there are only 1, 3 and 15 arrangements in them, and every one rounds inside quota. The search establishes that; it does not explain it, and no short reason is offered here.

In the three-by-three-by-three box, 54 of the 255 arrangements cannot be rounded inside quota, and the smallest of them uses sixteen of the twenty-seven cells. The drawn table is one of those smallest. Among boxes up to three on a side, the obstruction first appears when every side is three long — when every line can hold two halves and still leave a cell empty, in all three directions at once.

What a legislature is left with #

The obstruction does not say three-way apportionment is impossible. It says that one particular pair of demands — every total exact, and every cell inside its fair share — cannot always be met together, and so any real system with three families of totals has to give one of them up somewhere.

There are only a few ways to do that, and each is a choice about which kind of unfairness to accept. The totals can be kept exact and a cell allowed outside its share, as the nearest whole table does with its one seat at 222. One family of totals can be allowed to miss by a seat, keeping the cells inside their shares and letting a district’s group balance or a party’s be off by one. Or the apportionment can be done in stages — districts and parties first, where two dimensions guarantee everything, and the groups fitted afterwards to whatever balance the first stage leaves room for.

None of those is forced by the mathematics and none is ruled out by it. What the table of sixteen halves contributes is the proof that the choice has to be made at all, and a measure of how small a table already forces it.

When the totals cannot be met at all #

The drawn table always had some whole table meeting its totals. In larger three-way tables even that can fail.

Deciding whether whole numbers can meet a prescribed list of three-way line totals is, in general, a hard problem in the precise sense of computational complexity: Irving and Jerrum proved it NP-complete in 1994. And De Loera and Onn showed in 2004 that the tables meeting three-way line totals are as varied as any shapes cut out by linear inequalities can be — every such shape, with its fractional corners and its missing whole points, turns up as the set of tables meeting some list of totals for a table only three layers deep. So there are totals that fractional tables meet and no whole table meets at all.

The special case with every line total equal to one is familiar under another name. A whole three-way table of zeros and ones with one seat on every line is a Latin square: the layer holding the seat in row $i$ and column $j$ is the symbol in that cell. For three rows, three columns and three symbols there are exactly twelve such squares, and each is a whole three-by-three-by-three table with one seat on every one of its twenty-seven lines. Completing a partly filled Latin square is exactly the problem of meeting such totals with some cells already decided, and it is also NP-complete. The difficulty of three-way apportionment and the difficulty of finishing a Latin square are the same difficulty.

The same parity elsewhere #

The contrast between two directions and three is not special to seats.

In two dimensions a table of fractional shares with every total equal to one is a lottery over whole assignments: it can be written as an average of whole tables, each meeting the same totals. Nothing like that decomposition survives into three dimensions inside quota — the table of halves has the right totals and no whole table inside its quotas to be an average of. In two dimensions a table with prescribed row and column totals is a flow, and every corner of the region of such tables is a whole-number table — the integrality that makes rounding always possible. Where the corners stop being whole shows the same integrality failing when a matching problem acquires a triangle, an odd cycle, and a corner appears with a half in every coordinate. The table of sixteen halves is that phenomenon one step further on: the third family of totals creates odd cycles among the cells, and a half is exactly where the region’s corners stop being whole.

And the same pattern turns up in geometry. The theorem that has no version in space is a statement true in the plane and false one dimension up, and the reason there too is that a third direction gives a structure room to close up in a way two directions cannot.

What the tables cannot show #

The halves were built, not fitted from votes. A real three-way apportionment would start from votes and a continuous fit, whose shares are rarely exactly a half. The drawn table is the cleanest instance of the obstruction, and a fitted table can contain the same odd cycle among cells whose shares are merely fractional; the parity argument needs only that each line’s total forces one seat among two cells, which is weaker than every share being a half.

The search stops at three cells a side. It establishes that no smaller box with sides of two or three carries the obstruction, and that the three-by-three-by-three box does. Boxes with longer sides allow more arrangements, and the counts grow too fast to list completely.

And the hardness results are quoted, not demonstrated. A figure can exhibit one table whose totals cannot be met inside quota; it cannot exhibit that no efficient method decides every such question, which is a theorem about all tables and all methods.

Still open: which three-way totals are fair to ask for #

For two families of totals the mathematics is settled: a table inside every quota exists, a method that meets the totals and behaves well as votes change exists, and the two need not coincide. For three families there is no such settlement, and the questions that remain are partly mathematical and partly about what a legislature should ask for.

Which lists of three-way totals admit a table inside every quota is decidable for any given list and hard in general. Whether some method for three families keeps the properties the biproportional method has in two — seats that never fall as votes rise, and parts of the table apportioned as they would be alone — while always meeting every total, is not settled by anything drawn here. What the table of sixteen halves does settle is that any such method must sometimes put a seat where the fair share is nothing, because on some tables every whole table that meets the totals does.

Two directions close evenly, three need not #

A rounding that has to respect totals along lines is a choice, for every line, of which fractions to round up. In two directions the choices link the cells into loops that alternate between the directions, and alternating loops are even. In three directions the loops can use the directions in any order, an odd loop can form, and no alternation fits round it.

When a guarantee holds for tables and fails for three-way tables, look for the odd cycle. It is what separates the integrality of flows from the hardness of Latin squares, and here it separates a fair share that can always be honoured from one that sometimes cannot.