Online Temporal Voting: Strategyproofness, Proportionality and Asymptotic Analysis
Researchers prove Perpetual Phragmén and Method of Equal Shares satisfy online strategyproofness, a major win for fair AI governance.
Computer scientists Allan Borodin and Tristan Lueger have published a foundational paper analyzing 'online temporal voting,' a framework where groups submit binary approvals for alternatives arriving sequentially over multiple rounds, with one winner chosen per round. This model is crucial for real-world sequential decision-making, such as funding allocations, content moderation queues, or AI safety council votes. The authors introduce and formalize online variants of core game-theoretic concepts: Online Strategyproofness (OSP) and Online Independence of Irrelevant Alternatives (OIIA). Their key theoretical result is proving that OIIA is a sufficient condition for a rule to be OSP.
They then apply this framework to analyze specific voting rules. A major finding is that the Perpetual Phragmén rule—the only known online rule satisfying the strong fairness guarantee of Proportional Justified Representation (PJR)—also satisfies OSP. Similarly, the semi-online Method of Equal Shares (MES), known for satisfying weak Extended Justified Representation (wEJR), is also proven OSP. The paper also introduces the 'price of manipulability' to quantify how strategic behavior degrades proportional outcomes and explores asymptotic guarantees, showing the Serial Dictator rule is fully strategyproof and satisfies PJR up to an additive constant. This work provides the mathematical rigor needed to deploy provably fair and strategy-resistant voting mechanisms in automated and AI-assisted governance systems.
- Proved OIIA is a sufficient condition for Online Strategyproofness (OSP), formalizing resistance to manipulation in sequential voting.
- Established that the Perpetual Phragmén rule satisfies OSP, combining it with its known Proportional Justified Representation (PJR) guarantee.
- Introduced the 'price of manipulability' metric to quantify the trade-off between strategyproofness and proportional representation in online settings.
Why It Matters
Provides a rigorous framework for designing fair, manipulation-resistant voting systems in sequential AI governance, funding allocation, and content moderation.