Online Proportional Apportionment
Preprint
Abstract
Traditionally, the problem of apportioning the seats of a legislative body has been viewed as a one-shot process with no dynamic considerations. While this approach is reasonable for some settings, dynamic aspects play an important role in many others. We initiate the study of apportionment problems in an online setting. Specifically, we introduce a framework for proportional apportionment with no information about the future. 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. We study deterministic and randomized online apportionment methods. For deterministic methods, we construct a family of adversarial instances that yield a lower bound, linear in $n$, on the worst-case deviation between the seats allocated to a party and its cumulative share. We show that this bound is best possible and is matched by a natural greedy method. As a consequence, a method guaranteeing that the cumulative number of seats assigned to each party up to any step equals its cumulative share rounded up or down (global quota) exists if and only if $n\leq 3$. Then, we turn to randomized allocations and show that, for $n\leq 3$, we can randomize over methods satisfying global quota with the additional guarantee that each party receives, in expectation, its proportional share in every step. Our proof is constructive: Any method satisfying these properties can be obtained from a flow on a recursively constructed network. We showcase the applicability of our results to obtain approximate solutions in the context of online dependent rounding procedures.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- In This Apportionment Lottery, the House Always WinsOperations Research, 2026
- Approximate Random Allocation MechanismsReview of Economic Studies, 2020
- Strategyproof peer selection using randomization, partitioning, and apportionmentArtificial Intelligence, 2019
- Approximation Algorithms for Stochastic and Risk-Averse OptimizationSIAM Journal on Discrete Mathematics, 2018
- Sampling-Based Approximation Algorithms for Multistage Stochastic OptimizationSIAM Journal on Computing, 2012
- Network flow methods for electoral systemsNetworks, 2011
- Divisor methods for proportional representation systems: An optimization approach to vector and matrix apportionment problemsMathematical Social Sciences, 2008
- An Axiomatic Approach to Proportionality Between MatricesMathematics of Operations Research, 1989
- Algorithms for proportional matrices in reals and integersMathematical Programming, 1989
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973