Online Proportional Apportionment

Society for Industrial and Applied Mathematics eBooks, pp. 4846–4860

Abstract

Traditionally, the problem of apportioning the seats of a legislative body has been viewed as a oneshot process with no dynamic considerations. While this approach is reasonable for some instances of the problem, dynamic aspects play an important role in many others. In this paper, we initiate the study of apportionment problems in an online setting. Specifically, we introduce an online algorithmic framework to handle proportional apportionment with no information about future events. In this model, time is discrete and there are \(n\) parties that receive a certain share of the votes at each time step. An online algorithm needs to irrevocably assign a prescribed number of seats at each time, ensuring that each party receives its fractional share rounded up or down, and that the cumulative number of seats allocated to each party remains close to its cumulative share up to that time.

Authors 4

1. Javier Cembrano

   Max Planck Society · Max Planck Institute for Informatics · University of Chile

   Affiliation as printed

   Max Planck Institut für Informatik

   Universidad de Chile

2. José Correa

   University of Chile

   Affiliation as printed

   Universidad de Chile

3. Svenja M. Griesbach Aachen

   University of Chile · RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University

   Universidad de Chile

4. Víctor Verdugo
   Affiliation as printed

   Institute for Mathematical and Computational Engineering and Department of Industrial and Systems Engineering