Maintaining Proportional Committees with Dynamic Candidate Sets

Multiwinner voting is the study of electing a fixed-size committee given individual agents' preferences over candidates. Most research in this field has been limited to a static setting, with only one election over a fixed set of candidates. However, this approach overlooks the dynamic nature of applications, where candidate sets are subject to change.We extend the study of proportionality in multiwinner voting to dynamic settings, allowing candidates to join or leave the election and demanding that each chosen committee satisfies proportionality without differing too much from the previously selected committee. We consider approval preferences, ranked preferences, and the proportional clustering setting. In these settings, we either give algorithms making few changes or show that such algorithms cannot exist for various proportionality axioms. In particular, we show that such algorithms cannot exist for ranked preferences and provide amortized and exact algorithms for several proportionality notions in the other two settings.

We investigate how to choose committees that represent the electorate in settings with dynamic candidate sets. This is important because so far (i) committees are elected to proportionally represent the electorate, but(ii) when new candidates become available or elected candidates want to give up their seat, the resulting proportionality violations may not be easily fixable.We study three settings where candidates can one by one become available, give up their seat, or either of the two scenarios could happen in each time step. We provide proportional algorithms for these dynamic settings that require a small number of changes to the committee in each round, or lower bounds on the changes per round to prove that this is not possible.