Abstract
Iterative voting is a dynamic process where voters strategically update their ballots to achieve preferred outcomes. While this process often leads to infinite cycling, this paper establishes sufficient conditions for convergence using two novel mathematical frameworks: Function Monotonicity (FM) and Set Monotonicity (SM). These frameworks allow for the first-ever proof of convergence for the Bucklin rule and provide a unified approach to analyzing stability across various voting rules, including Borda, Veto, and Maximin, under restricted dynamics.
Introduction
In social choice theory, the Gibbard-Satterthwaite theorem establishes that any non-dictatorial voting rule with more than two candidates is inherently susceptible to strategic manipulation. In practice, voters often adjust their ballots based on the current state of the election. Iterative voting formalizes this behavior as a game where voters take turns changing their votes to improve the current winner from their perspective.
The primary challenge in iterative voting is ensuring stability. Without restrictions on voter moves, the process can enter infinite loops (cycling). Previous research has identified convergence for simple rules like Plurality, but more complex rules—such as Borda, Copeland, or Bucklin—have either been proven to cycle or lacked formal stability proofs. This research seeks the "sweet spot": the minimal set of restrictions on voter dynamics required to guarantee convergence.
Theoretical Framework: FM and SM
The authors define an iterative voting procedure as a pair $(F, D)$, where $F$ is the voting rule and $D$ represents the "dynamics" or the set of allowed moves. To analyze these procedures, two distinct conditions are introduced:
- Function Monotonicity (FM): This approach utilizes a potential function argument. If a function (typically based on the winner's score and tie-breaking rank) can be shown to never decrease along any improvement path, the process must terminate.
- Set Monotonicity (SM): This focuses on the "set of potential winners" for each voter. If these sets shrink or remain stable over time—meaning a candidate who loses the potential to win under a specific voter's move never regains it—the process is guaranteed to converge.
Crucially, the authors demonstrate that FM and SM are not equivalent; they are complementary tools that capture different aspects of voting stability.
Restricted Dynamics and Convergence
To achieve convergence for complex rules, the paper introduces specific restricted dynamics:
- Upgrade: A voter moves a preferred potential winner to a higher position in their ranking.
- Unit Upgrade: A voter moves a preferred potential winner up by exactly one position.
Key Results for Specific Rules
- Positional Scoring Rules (PSRs): All unit-gap PSRs (including Borda, Veto, and $k$-approval) are shown to converge under "Unit Upgrade" dynamics. For Borda, restricting moves to single-position shifts is essential to maintaining monotonicity.
- The Bucklin Rule: The Bucklin rule presents a unique challenge because the winner's score can decrease during the process, invalidating standard potential function arguments. By applying the Set Monotonicity framework, the authors provide the first proof of convergence for Bucklin under Unit Upgrade dynamics.
- Maximin and Copeland: The paper identifies "maximal" dynamics for these rules, defining the maximum degree of freedom voters can have before cycling becomes possible.
Conclusion and Future Work
This research provides a robust theoretical foundation for understanding stability in iterative voting. By moving beyond rule-specific analysis to general frameworks like FM and SM, the authors have mapped out the boundaries of convergence for several major voting systems.
Future work will focus on the quality of outcomes. While convergence ensures the process stops, the resulting stable state is not necessarily a Condorcet winner or a pure Nash Equilibrium. Investigating the "Dynamic Price of Anarchy" will be critical to understanding the trade-offs between stability and social welfare in restricted iterative voting.
Summary updated