A Simple and Fast Linear-Time Algorithm for Divisor Methods of Apportionment

This article is part of the special issue of Mathematical Programming B commemorating Michel L. Balinksi.

Proportional Apportionment

The problem of proportional apportionment arises whenever we have a finite supply of $k$ indivisible, identical resource units which we have to distribute across $n$ parties fairly, that is according to the proportional share of publicly known and agreed-upon values $v_1,\ldots,v_n$ (of the sum of these values).

A typical example is the assignment of seats in the US House of Representatives according to the population count of the states. The de-facto standard to compute such a division is the class of divisor methods.

Previous Results

There are two algorithms that implement divisor methods efficiently:

• one by Cheng and Eppstein has worst-case optimal running time but is relatively complex and (as we observe) causes problems when implemented with inexact floating point arithmetic,
• while the other—described by Pukelsheim— is simple and fast in practice but does not offer a linear-time worst-case guarantee.

Our Contribution

We propose a new algorithm that combines the strengths of both methods. Our algorithm is a generalization of the method we devised for the stick-cutting problem and uses a single call to a selection algorithm after elementary preprocessing.

We also empirically demonstrate that

• the Cheng-Eppstein algorithm is much slower than Pukelsheim’s method,
• there are (somewhat realistic) classes of input, where Pukelsheim’s method indeed needs super-linear time, and
• that our new algorithm is almost as fast as Pukelsheim’s method for most inputs, and significantly faster for inputs the latter struggles with.

A full-length technical report with more detailed proofs and further experiments is available here.