Strategic Voting Under Uncertainty About the Voting Method

Wesley H. Holliday, Eric PacuitarXiv 2019 · DOI

Abstract

Social choice theory traditionally assumes that strategic voters possess perfect information regarding the voting rules of an election. This paper explores a novel defense against manipulation: uncertainty about the voting method itself. By introducing the concepts of sure, safe, and expected manipulation, we analyze how choosing from an "uncertainty set" of voting rules can discourage voters from misrepresenting their preferences. Our results indicate that specific combinations of rules can significantly reduce or even eliminate the incentive for sure manipulation, providing a new tool for election design that maintains post-vote explainability.

Introduction

The Gibbard-Satterthwaite theorem establishes that any non-dictatorial voting system with at least three candidates is susceptible to strategic voting. In such systems, a voter may achieve a more desirable outcome by lying about their true preferences. While previous research has focused on voter uncertainty regarding the ballots of others, this study investigates the impact of uncertainty regarding the voting rule itself. If a voter is unsure whether the winner will be determined by Borda count, Plurality, or another method, the risk that a strategic lie might "backfire" could serve as a deterrent.

Theoretical Framework: Levels of Manipulation

To analyze strategic behavior under rule uncertainty, we define an uncertainty set $S$ of voting methods. A voter's incentive to manipulate is categorized into three levels:

  1. Sure Manipulation: A misrepresentation that is guaranteed to yield a better outcome than the truthful ballot, regardless of which rule in $S$ is selected.
  2. Safe Manipulation: A misrepresentation that never results in a worse outcome than the truth for any rule in $S$, and yields a strictly better outcome for at least one rule.
  3. Expected Manipulation: A misrepresentation that increases the voter's expected utility, assuming a probability distribution over the rules in $S$.

Methodology

The study evaluates 11 common voting methods, including Borda, Plurality, Hare, and Baldwin. To quantify manipulability, the authors utilize the Nitzan-Kelly index—the percentage of voting profiles where manipulation is possible.

  • Impartial Culture Model: Used as a benchmark where all candidate rankings are equally likely.
  • Exhaustive Search: Conducted for small-scale scenarios (e.g., 3 candidates, 4–8 voters).
  • Monte Carlo Simulations: Employed for larger scenarios (e.g., 4 candidates, up to 70 voters) using 10,000 random profiles per case to estimate manipulability.

Key Results

Eliminating Sure Manipulation

A primary finding is that uncertainty can effectively "cancel out" the incentive to manipulate. Certain pairs of rules are particularly effective; for instance, while Borda and Baldwin are individually manipulable, the uncertainty set {Borda, Baldwin} can completely eliminate sure manipulation in 3-candidate scenarios.

Heatmaps showing the percentage of profiles with sure manipulation (left) and safe manipulation (right) for pairs of voting methods (3 candidates, 7 voters).

As shown in the heatmaps above, several pairs of rules (indicated by 0% in red boxes on the left) successfully eliminate the possibility of a "sure" win through lying. For safe manipulation (right), while the percentages are higher, uncertainty still offers significant reductions. For example, moving from Plurality alone (29% manipulable) to the set {Plurality, Hare} reduces the percentage of manipulable profiles to 9%.

Persistence of Safe Manipulation

While sure manipulation can often be eliminated, safe manipulation proves more resilient. However, uncertainty sets still significantly reduce the frequency of these opportunities compared to single-rule systems.

Percentage of profiles with safe manipulation as the number of voters increases for various uncertainty sets.

The simulation data suggests that as the number of voters increases, the percentage of profiles susceptible to safe manipulation generally decreases for most uncertainty sets, though it remains higher than the rates for sure manipulation. This suggests that while rule uncertainty is not a silver bullet, it creates a substantial barrier to strategic behavior.

Discussion and Future Work

This approach offers a unique advantage: post-vote explainability. Unlike randomized lotteries, the designer can reveal the specific deterministic rule used after the votes are cast, providing a clear algorithmic justification for the winner. Furthermore, the authors demonstrate that the Duggan-Schwartz theorem, which suggests manipulation is unavoidable, does not apply to sets of methods in the same way it applies to single methods, opening a loophole for election designers.

Limitations

Current findings are largely based on computational searches for a limited number of candidates. Future research is required to provide general mathematical proofs for $n$ candidates and to model "hyper-sophisticated" voters who might attempt to predict the designer's choice. Additionally, a comprehensive model should integrate uncertainty about both the voting rules and the ballots of other participants to see if these barriers hold up as the number of voters grows toward infinity.

Summary updated

Abstract

Much of the theoretical work on strategic voting makes strong assumptions about what voters know about the voting situation. A strategizing voter is typically assumed to know how other voters will vote and to know the rules of the voting method. A growing body of literature explores strategic voting when there is uncertainty about how others will vote. In this paper, we study strategic voting when there is uncertainty about the voting method. We introduce three notions of manipulability for a set of voting methods: sure, safe, and expected manipulability. With the help of a computer program, we identify voting scenarios in which uncertainty about the voting method may reduce or even eliminate a voter's incentive to misrepresent her preferences. Thus, it may be in the interest of an election designer who wishes to reduce strategic voting to leave voters uncertain about which of several reasonable voting methods will be used to determine the winners of an election.
BibTeX
@misc{holliday2019strategic,
  author = {Wesley H. Holliday and Eric Pacuit},
  title = {{Strategic Voting Under Uncertainty About the Voting Method}},
  year = {2019},
  eprint = {1907.09110},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.09110},
}
Figure