Multiwinner Temporal Voting with Aversion to Change
This addresses incremental improvements in computational social choice for committee elections with time-varying preferences, relevant to researchers in voting theory.
The paper tackles the problem of selecting a committee in two-stage elections with dynamic voter preferences, aiming to minimize changes between stages, and shows that this is tractable only for Approval Voting among Thiele rules, with experimental analysis on average changes and ties.
We study two-stage committee elections where voters have dynamic preferences over candidates; at each stage, a committee is chosen under a given voting rule. We are interested in identifying a winning committee for the second stage that overlaps as much as possible with the first-stage committee. We show a full complexity dichotomy for the class of Thiele rules: this problem is tractable for Approval Voting (AV) and hard for all other Thiele rules (including, in particular, Proportional Approval Voting and the Chamberlin-Courant rule). We extend this dichotomy to the greedy variants of Thiele rules. We also explore this problem from a parameterized complexity perspective for several natural parameters. We complement the theory with experimental analysis: e.g., we investigate the average number of changes in the committee as a function of changes in voters' preferences and the role of ties.