Multiwinner Temporal Voting with Aversion to Change

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.

Authors

• Valentin Zech
• Niclas Boehmer
• Edith Elkind
• Nicholas Teh

Keywords

No keywords are indexed for this paper.