Convergence and Quality of Iterative Voting Under Non-Scoring Rules

Aaron Koolyk, Tyrone Strangway, Omer Lev, Jeffrey S. RosenscheinIJCAI 2017 · DOI

TL;DR

This paper investigates iterative voting, a dynamic process where voters strategically change their preferences until no one wants to switch. The authors demonstrate that for many common non-scoring voting rules, this process never converges to a stable outcome, even with simplified voter strategies. Empirically, they find that while cycles are rare in practice, the choice of voting rule and voter strategy significantly impacts convergence speed and the quality of the final outcome.

What Problem Does This Paper Address?

The field of social choice theory grapples with how to aggregate individual preferences into a collective decision. Traditional voting rules are often susceptible to strategic manipulation, as shown by the Gibbard-Satterthwaite theorem. Iterative voting offers a dynamic alternative: voters repeatedly adjust their ballots based on the current outcome, aiming for an equilibrium where no voter has an incentive to change. Previous research established that iterative voting does converge for simple rules like plurality and veto under "best response" dynamics (where voters always make the move that maximally improves their outcome). However, it was also shown that for scoring rules (a broad class including Borda, plurality, etc.), convergence is not guaranteed for most rules. This paper tackles two key open questions: 1) Does iterative voting converge for non-scoring rules (like Maximin, Copeland, STV, Ranked Pairs)? and 2) How do different voter strategies (beyond strict best response) and voting rules affect convergence and the quality of the outcome?

Methods

The paper employs both theoretical analysis and empirical simulation.

Theoretical: * Convergence Proofs: The authors formally prove that for several non-scoring rules (Maximin, Copeland, Bucklin, STV, Second Order Copeland, Ranked Pairs), iterative voting does not converge under standard "best response" dynamics. * Heuristic Dynamics: Recognizing that calculating the true best response can be computationally intractable (NP-hard) for many rules, they introduce and analyze several heuristic dynamics. These dynamics simplify voter behavior by restricting the types of changes they can make. Examples include: * TOP: Voters move their most preferred candidate to the top of their ballot. * TB: Voters move the current winner to the bottom and their preferred candidate to the top. * KT (Kendall-Tau): Voters choose a best response that minimizes the "distance" (Kendall-Tau distance) to their previous ballot. * SWAP: Voters can only make a single adjacent swap in their preference order. * They prove that even with these restricted dynamics, convergence is still not guaranteed for the non-scoring rules.

Empirical: * Simulation Framework: They extend an existing iterative voting simulation framework. * Settings: They simulate elections with 10 voters and 4 candidates, using both uniform and single-peaked preference distributions. * Methodology: For each voting rule and dynamic combination, they run 1000 games, repeating each game 100 times with different voter response orders. Games are run until equilibrium, a cycle is detected, or a maximum of 10,000 iterations is reached. * Metrics: They analyze: * Convergence: Whether the process reached an equilibrium or a cycle. * Equilibria Count: The average number of distinct equilibrium states reached. * Truthful Winner: The proportion of times the winner of the iterative process was the same as the winner under truthful voting. * Voter Utility (Borda Score): Using the Borda score as a proxy for voter utility, they compare the Borda score of the iterative winner to the Borda score of the truthful winner.

Datasets

Not discussed in the paper. The authors generate preference profiles synthetically for their simulations.

Key Insights and Ideas

  • Non-Scoring Rules are Problematic: The most striking theoretical result is that iterative voting, even with simplified voter strategies, fundamentally fails to converge for many common non-scoring rules. This suggests that the "best response" assumption, while useful for some rules, is insufficient for others.
  • Heuristics Don't Guarantee Convergence: Introducing more "realistic" or restricted voter strategies (like KT or SWAP) doesn't magically fix the convergence problem for these non-scoring rules. This highlights a deep structural issue with these rules in a dynamic, strategic setting.
  • Cycles are Rare in Practice: Despite theoretical proofs of non-convergence (implying cycles or infinite runs), the empirical simulations found very few actual cycles. This suggests that while theoretically possible, such scenarios might be rare in practice, or that the 10,000-iteration cutoff was sufficient to capture most outcomes.
  • Dynamics Matter for Speed, Rules for Outcome Quality: The choice of dynamic significantly impacts how quickly an equilibrium is reached and how many equilibria are explored. However, the voting rule itself is a stronger determinant of the quality of the outcome (e.g., how often the truthful winner or a Condorcet winner emerges).
  • Condorcet Winners are Resilient: Condorcet-consistent rules (like Maximin, Copeland, Ranked Pairs) are more likely to result in the truthful winner or a candidate with a high Borda score, especially when a Condorcet winner exists. This aligns with the intuition that these rules are designed to favor broadly acceptable candidates.
  • KT Dynamic is a Convergence Slowdown: The Kendall-Tau (KT) dynamic, while aiming for best responses with minimal ballot changes, consistently led to slower convergence and a higher number of equilibrium states across most voting rules.

Key Results

  • Theoretical Non-Convergence: Maximin, Copeland, Bucklin, STV, SOC, and Ranked Pairs do not converge under best response or several heuristic dynamics (BR, TOP, TB, KT, SWAP).
  • Empirical Convergence: In simulations, cycles were encountered infrequently. Most games converged within 10 steps, with fewer than 15 equilibria on average (except for SOC and KT).
  • Truthful Winner: Condorcet-consistent rules selected the truthful winner over 50% of the time, while non-Condorcet rules (STV, Bucklin) did so less than 45% of the time.
  • Borda Score Improvement: STV showed significant improvements in Borda scores under iterative voting, especially with single-peaked preferences. Bucklin also showed improvement. Maximin, however, often saw a decrease in Borda scores. Copeland winners' Borda scores were largely unchanged, likely due to the frequent emergence of the truthful (and often Condorcet) winner.
  • KT Dynamic: Led to significantly longer convergence times and more equilibrium states compared to other dynamics for most rules.

Limitations and Future Work

  • Limitations:
    • The empirical analysis was limited to a specific setting (10 voters, 4 candidates) and two preference distributions (uniform, single-peaked).
  • The Borda score is used as a proxy for voter utility, which is an approximation.
  • While cycles were rare, the theoretical proofs of non-convergence for certain rules and dynamics remain valid.
  • Future Work:
    • Analyze convergence conditions for more voting rules and dynamics.
  • Investigate broader impossibility results.
  • Expand empirical analysis to more distributions (e.g., Mallows model).
  • Explore heuristic dynamics that better reflect real-world voter behavior.
  • Analyze the properties of equilibria reached in realistic settings.

Summary updated

BibTeX
@inproceedings{koolyk2017convergence,
  author = {Aaron Koolyk and Tyrone Strangway and Omer Lev and Jeffrey S. Rosenschein},
  title = {{Convergence and Quality of Iterative Voting Under Non-Scoring Rules}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/39},
}
Figure