Online Temporal Voting: Strategyproofness, Proportionality and Asymptotic Analysis
This work addresses the challenge of fair and strategic voting in dynamic, multi-round settings, which is incremental by extending known properties to online variants.
The paper tackles the problem of designing online temporal voting rules that are resistant to strategic manipulation while ensuring proportional representation, showing that Perpetual Phragmén and the Method of Equal Shares satisfy online strategyproofness, and that Serial Dictator achieves proportional justified representation up to an additive constant.
We study online temporal voting, where a group of voters submit 0/1 approvals on sets of alternatives that arrive online over multiple rounds and a single alternative is chosen in each round. We introduce online variants of two well-known game theoretic properties, strategyproofness (SP) and independence of irrelevant alternatives. We show that online independence of irrelevant alternatives (OIIA) is a sufficient condition for online strategyproofness (OSP), and that several known online voting rules satisfy OIIA and thus OSP, but that they are not SP. In particular, we show that Perpetual Phragmen, the only known online voting rule to satisfy PJR, satisfies OSP. The Method of Equal Shares (MES), a semi-online voting rule knwon to satisfy wEJR, also satisfies OSP. We then introduce the price of manipulability, which quantifies the effect of strategic behaviour on proportional representation guarantees. Finally, we introduce asymptotic satisfaction of proportional representation and show that an online voting rule, Serial Dictator, is fully strategyproof and satisfies proportional justified representation (PJR) up to an additive constant.