Strategic Voting with Incomplete Information

Ulle Endriss, Svetlana Obraztsova, Maria Polukarov, Jeffrey S. RosenscheinIJCAI 2016

Abstract: Traditional social choice theory assumes voters possess perfect knowledge of others' preferences, leading to the conclusion that most voting rules are inherently manipulable. This paper investigates the impact of incomplete information—such as knowing only the current winner or the scoreboard—on strategic behavior. We demonstrate that limited information acts as a barrier to manipulation and, crucially, ensures that iterative voting processes converge to stable outcomes for several common voting rules.

Introduction: Beyond Perfect Information

The Gibbard-Satterthwaite Theorem is a cornerstone of social choice theory, stating that any non-dictatorial voting rule with more than two candidates is susceptible to strategic manipulation. However, this result hinges on the "complete information" assumption: a manipulator knows exactly how every other participant will vote. In practice, voters rarely have such granular data. Instead, they rely on polls, partial results, or historical trends.

This research explores how restricting a voter's information affects their ability to manipulate an election and whether such restrictions can lead to stable, convergent outcomes in iterative settings.

Modeling Incomplete Information

The authors introduce Information Functions (IFs) to formalize what a voter knows. A signal $\pi$ from an IF defines an "information set"—the collection of all possible voting profiles consistent with that signal. The paper focuses on three natural signals:

  1. Winner (W): Voters only know the identity of the current front-runner.
  2. Score (S): Voters know the current point totals for all candidates.
  3. Majority Graph (MG): Voters know the results of all head-to-head matchups.

A voter performs a $\pi$-manipulation only if the move is "safe": there must be at least one scenario in their information set where the change improves the outcome for them, and no scenario where it makes the outcome worse than their truthful vote.

Barriers to Manipulation

The study reveals that information can be a double-edged sword. While more data typically empowers a manipulator, it also introduces risk. If a voter knows too little, they may not find a "safe" move. Conversely, knowing too much might reveal that a seemingly beneficial move could backfire in certain edge cases.

Key findings include:

  • Immunity: The Veto rule is immune to manipulation when only the winner is known. Maximin is immune to Majority Graph-based manipulation if no "weak Condorcet winner" exists.
  • Susceptibility: Rules like $k$-approval, Copeland, and Maximin remain susceptible even with only "Winner" information, though the difficulty of finding a successful strategy increases.

Iterative Voting and Convergence

One of the most significant contributions of this work is the analysis of iterative voting. In this model, voters start by voting truthfully and then sequentially change their votes if they find a beneficial $\pi$-manipulation. A central question is whether this process settles into a stable outcome or loops indefinitely.

Figure 3: An illustration of iterative voting dynamics. While full information can lead to cycles of strategic moves, the paper proves that limited information often guarantees convergence to a stable winner.

The authors prove that under the "Winner" information function, the process is remarkably stable:

  • Copeland and Maximin are guaranteed to converge for any improvement dynamics.
  • Positional Scoring Rules (e.g., Borda, Plurality) converge if voters follow "conservative" dynamics—choosing the strategic move that deviates least from their true preferences.

This convergence is driven by "Function Monotonicity," where every strategic move by a voter tends to reinforce the standing of the winner, preventing the cycles often seen in full-information models.

Conclusion and Future Directions

By relaxing the assumption of perfect information, this paper provides a more realistic view of election dynamics. Limited information serves as a natural defense against strategic manipulation and promotes stability in iterative processes. Future research may look into "noisy" information sources, such as probabilistic polls, and the impact of coordinated group manipulation.

Summary updated

BibTeX
@inproceedings{endriss2016strategic,
  author = {Ulle Endriss and Svetlana Obraztsova and Maria Polukarov and Jeffrey S. Rosenschein},
  title = {{Strategic Voting with Incomplete Information}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure