A simple and fast linear-time algorithm for divisor methods of apportionment

Reitzig, Raphael and Wild, Sebastian ORCID: 0000-0002-6061-9177 (2023) A simple and fast linear-time algorithm for divisor methods of apportionment. Mathematical Programming, 203 (1-2). pp. 187-205.

Access the full-text of this item by clicking on the Open Access link.

Official URL: http://dx.doi.org/10.1007/s10107-023-01929-5

Abstract

<jats:title>Abstract</jats:title><jats:p>Proportional apportionment is the problem of assigning seats to states (resp. parties) according to their relative share of the population (resp. votes), a field heavily influenced by the early work of Michel Balinski, not least his influential 1982 book with Peyton Young (Fair representation, 2nd edn. Brookings Institution Press, Washington, D.C., 2001). In this article, we consider the computational cost of <jats:italic>divisor methods</jats:italic> (also known as <jats:italic>highest averages</jats:italic> methods), the de-facto standard solution that is used in many countries. We show that a simple linear-time algorithm can exactly simulate all instances of the family of divisor methods of apportionment by reducing the problem to a single call to a selection algorithm. All previously published solutions were iterative methods that either offer no linear-time guarantee in the worst case or require a complex update step that suffers from numerical instability.</jats:p>

Item Type:	Article
Uncontrolled Keywords:	Proportional apportionment, Selection algorithms, Divisor methods, d'Hondt method, Fair division, Rounding percentages
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	03 Mar 2023 10:52
Last Modified:	27 Feb 2024 17:45
DOI:	10.1007/s10107-023-01929-5
Open Access URL:	https://doi.org/10.1007/s10107-023-01929-5
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3168730