Online Proportional Apportionment

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.