Seats to parties and places at once

The fifth rung of this ladder ends with what reads like a closing statement. The subject is bounded above by Balinski and Young’s impossibility — no method stays inside quota and avoids the population paradox — and below by Huntington’s characterisation of the divisor methods, and nothing further adjudicates between the five that remain. There is a dial, its ends are known, and the choice along it is a value judgement rather than a mathematical one.

Every word of that is true about the question the ladder asked, and the question is one-dimensional. Every essay on it apportions seats among regions in proportion to one vector of populations.

Real legislatures are not one-dimensional. A country with regional constituencies and national parties has to give each region its due number of seats and each party its due number, at the same time, from one table of votes. The object is a matrix, the constraints are on its rows and its columns, and none of the previous rungs applies.

Why the one-dimensional answer fails #

The obvious approach is to do the familiar thing twice.

Apportion the house among the districts by population — that is the classical problem, solved. Then, within each district, apportion its seats among the parties by their votes there — the classical problem again, once per district.

The party totals then come out wrong, and there is no reason they should not. Each district’s rounding is done in ignorance of the others, so the national totals are sums of independently rounded numbers, and the errors do not cancel to order.

The hero figure measures it: the seats a party is due nationally and the seats it collects district by district differ, by an amount that no choice of rounding rule within districts fixes, because the constraint is not in the rule.

That is the whole difficulty. A one-dimensional method has one set of totals to hit and a dial to hit it with. A two-dimensional problem has two sets, and one dial cannot serve both.

The construction #

The answer is due to Michel Balinski and Gabrielle Demange, in 1989, and it is a single idea.

Multiply every entry of the vote table by two numbers: one belonging to its row, one belonging to its column. Then round. Choose the row multipliers and the column multipliers so that after rounding every row total and every column total is exactly right.

Written out, the seats in district $i$ for party $j$ are

$$s_{ij} = \operatorname{round}\big(\lambda_i \, \mu_j \, v_{ij}\big),$$

with the $\lambda$ and $\mu$ chosen to make the totals come out.

Three things about that shape are worth separating.

It is the divisor method, twice. A divisor method for the one-dimensional problem divides every population by one number and rounds; here every entry is divided by a row divisor and a column divisor. So the two-dimensional method is the natural extension of the classical one, and it inherits the choice of rounding rule — the same dial, with the same five settings on it.

It has the right number of degrees of freedom. There are $R$ row multipliers and $C$ column multipliers, and $R + C$ constraints on the totals — one too many, since the row totals and the column totals both add to the house, so one constraint is redundant. And the multipliers can all be scaled by a constant without changing anything, which removes one degree of freedom. The counts match.

And it does not obviously have a solution. Multiplying and rounding is not a continuous operation, so no fixed-point theorem applies directly, and the existence of multipliers making every total exact is a theorem. That is worth dwelling on: the same construction with the rounding removed is elementary and classical, and the whole difficulty of the two-dimensional problem is that the answer must be in whole seats. Rounding is where every difficulty in this subject lives, one dimension down as well as two.

Reading that figure against the hero is the cleanest statement of the difference. In one dimension there is a single list of shares and a single total to hit; the whole subject is where the rounding goes. In two dimensions there are $R + C$ totals to hit with one table, and the rounding of any entry is constrained twice.

A vector’s worth of rounding decisions has one accounting constraint; a matrix’s worth has two families of them, and the second family is what makes the classical machinery inapplicable rather than merely inconvenient.

Existence, and how it is proved #

Balinski and Demange proved that a solution exists, and is essentially unique, whenever the vote table is not degenerate.

The proof is not the obvious one. Making the unrounded products have exact row and column sums is a classical result — the iterative proportional fitting of Deming and Stephan, whose convergence has been known since 1940 — but rounding afterwards destroys the totals.

What works instead is a network-flow argument. Reformulate: an assignment of whole seats with the prescribed row and column totals is a flow in a bipartite network, districts on one side and parties on the other, with capacities. Such a flow exists by the max-flow min-cut theorem whenever an obvious counting condition holds. Then, among all such flows, the one that maximises a particular product of the vote entries is exactly the one produced by some pair of multipliers — which is the same duality that makes the assignment problem tractable.

So the existence is combinatorial and the multipliers are the dual variables. A construction that looks like arithmetic is really a flow problem in disguise, which is why it is solvable at all.

What the impossibility does not say #

The interesting part is what happens to Balinski and Young’s theorem.

It says: no apportionment method for the one-dimensional problem both stays within quota and avoids the population paradox. That is a statement about methods taking a vector of populations to a vector of seats.

The biproportional problem has different inputs and different outputs, so the theorem does not apply to it, and the natural analogues have to be examined afresh.

Quota becomes a two-dimensional condition and it can fail. A district’s party may receive a number of seats outside the interval around its share, and examples are easy to construct. So the biproportional method does not satisfy a two-dimensional quota, and that is a genuine cost.

The population paradox has an analogue that the method does avoid: increasing a party’s votes in a district cannot cost it a seat there while another party gains one, which is the two-dimensional statement of consistency.

And a new paradox appears that has no one-dimensional counterpart: adding seats to one district can move seats between parties in a different district, because the multipliers are global. That is unavoidable — the constraints are global, so the answer is — and it is the price of solving both problems at once.

Whether that last one should be called a paradox is a fair question. In the one-dimensional subject the paradoxes are failures of monotonicity, where more of something produces less of what it should buy. Here nothing of the kind happens: a party with more votes never does worse. What happens is that a change in one district propagates, which is the ordinary behaviour of a system with global constraints and looks strange only against the expectation, formed on the one-dimensional problem, that districts are independent. They were never independent; the one-dimensional method achieved that appearance by ignoring the party totals.

Where it is used #

This is not a hypothetical construction, which distinguishes it from most of the impossibility results on this ladder.

Switzerland adopted biproportional apportionment for cantonal elections beginning with Zurich in 2006, after the federal court ruled the previous system unconstitutional for wasting votes in small districts. Several other cantons followed. The method is known there as doppelter Pukelsheim, after Friedrich Pukelsheim, who worked out the practical algorithms.

The court’s reasoning is worth noting because it is the sort of thing a mathematical result rarely produces. The objection to the old system was that a party’s supporters in a small district had less chance of electing anybody than the same supporters in a large one, which is a statement about the ratio of votes to seats across districts. Biproportionality makes that ratio uniform by construction.

And the computation is routine. Cantonal results are computed by alternating scaling, converging in a handful of rounds, on tables of a few dozen rows and columns.

The algorithm, and why it needs care #

The practical method is alternating scaling and it is worth describing, because a naive version does not work and the reason is instructive.

Start with all multipliers at one. Adjust each row’s multiplier until that row’s rounded total is right; then adjust each column’s; repeat.

The naive version can cycle. Rounding is a step function, so adjusting a row can change a column’s total by a whole seat, and adjusting that column can undo the row — with the two chasing each other indefinitely. A version written for this rung’s figures did exactly that, which is why the figure searches the whole space instead.

The repair used in practice is to work with the tied-down form of the divisor method: instead of a multiplier per row, keep a divisor per row and adjust it to the exact value at which the row’s total changes, which is always one of finitely many candidate values determined by the entries. The iteration then moves between finitely many states and cannot cycle indefinitely, and Pukelsheim’s implementations do this.

The general lesson is that a continuous algorithm applied to a rounded problem needs the rounding built in, rather than applied afterwards — which is the same observation the divisor methods make one dimension down.

What it costs #

A voter cannot check the result. The one-dimensional divisor methods can be verified by hand: divide, round, check the total. The biproportional answer depends on multipliers found by an iteration, and reproducing it needs the whole table and a computer. That is a real objection in an electoral context and it was raised in Switzerland; the response adopted was to publish the multipliers alongside the result, so that anybody can verify the arithmetic even if reproducing the search is out of reach. Publishing the certificate rather than the algorithm is the standard answer to this class of objection, and it is the same move a dual solution makes in optimisation.

Ties and near-ties are awkward. Where the scaling has several solutions the choice among them is arbitrary, and legislation has to specify a tie-break. The one-dimensional methods have the same problem in a simpler form.

The result can be counter-intuitive locally. A party with more votes than another in a district can receive fewer seats there, if the second party’s national total requires it. That is arithmetically forced and it reads, to somebody looking only at their own district, like an error.

And the two-dimensional quota failure is genuine. A party can receive, in a district, a number of seats that no reasonable reading of its local vote share would give it — because its national total has to come out. Whether that is acceptable is a political question, and the honest answer is that biproportionality trades local proportionality for global proportionality by construction.

What a court asked for, and what it got #

The Swiss case is worth setting out because it is a rare instance of a mathematical construction being adopted because a legal argument required exactly it.

The Zurich cantonal parliament was elected from districts of very unequal size. In a district returning three seats, a party needed roughly a quarter of the vote to win one; in a district returning twenty, roughly a twentieth. So the value of a vote depended on where it was cast, and the federal court held in 2002 that this violated the constitutional guarantee of equal voting power.

The court’s requirement was not a method but a property: every vote should count the same towards the composition of the parliament, whatever district it came from. That is a constraint on the column totals — parties nationally — while the constitution’s separate requirement that each district be represented in proportion to its population is a constraint on the row totals.

Two families of constraints, imposed by two different clauses, and no one-dimensional method can satisfy both. Biproportional apportionment was proposed as the construction that does, and adopted.

That sequence — a legal requirement that turns out to be a pair of constraints, an existing impossibility that does not apply because the shape is different, and a construction from a 1989 paper — is unusually clean. It is also the reason the method has a name in German legislation, which is not a fate most theorems meet.

What the pictures cannot show #

The multipliers are not drawn. The hero shows the table of seats and the votes it came from, and the two families of numbers that produced it are computed and not displayed. Displaying them would show a row of numbers whose meaning is entirely in what they do.

And the search is not the algorithm. The figure confirms a table exists by examining every possibility, which is honest at four districts and three parties and is not what anybody runs. The real method is an alternating scaling, and its convergence is a theorem rather than a search.

The comparison figure is a different anchor’s. The picture of the five one-dimensional rules is shown here to make a point about inheritance, and it is measuring a quantity — a notion of unfairness among regions — that the two-dimensional problem has no agreed analogue of. Reading it as though it ranked biproportional methods would be reading it wrongly.

Nor can a picture show what fails. The two-dimensional quota violation is a statement about a table that is not drawn, produced by votes chosen to exhibit it. Every figure here shows the method working.

Where the ladder goes next #

The anchor’s own first five rungs are now joined by a second dimension, and the obvious continuations are dimensional again: three-way apportionment — seats to districts, parties and, say, a gender quota at once — where existence can fail, and the question of which combinations of prescribed totals are achievable at all.

Named here as a debt: the two-dimensional quota violation, described above and not exhibited. Constructing an example takes a table chosen for the purpose, and it is the honest counterweight to the rest of this rung.

Also named as a debt: three-way apportionment, where a third family of constraints — a gender quota, a language quota — is added and existence can genuinely fail, so that the two-dimensional case is the last one where a solution is guaranteed. Nothing above touches it, and the pattern of a condition being satisfiable in two dimensions and not in three recurs across this collection.

Sideways, the flow argument that proves existence is the same duality the assignment problem runs on, the rounding rule is the one-dimensional dial, and the impossibility that does not apply is Balinski and Young’s.

What is worth carrying away #

An impossibility theorem is a statement about a class of problems, and changing the shape of the input can leave the class entirely.

Balinski and Young’s theorem closes the one-dimensional subject, and it closes it completely — the ladder’s fifth rung is right about that. What it does not do is close apportionment, because a problem with two families of constraints is not in its scope, and the two-dimensional problem has a solution, a proof, an algorithm and a country using it.

The habit worth taking is to check what an impossibility quantifies over. “No method does this” always has an implicit “for problems of this shape”, and the shape is often the assumption most worth questioning — here, the assumption that the thing being apportioned is a list.