⬑ All Publications

A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment

Mar 2017 (Written: Apr 2015)

Raphael Reitzig, Sebastian Wild:

arxiv

| read herepdfarxivgithub |

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

In recent literature, there are two algorithms that implement divisor methods:

  • one by Cheng and Eppstein has worst-case optimal running time but is relatively complex and 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 worst-case guarantees.

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.