Abstract
The Gibbard-Satterthwaite theorem famously proves that any non-dictatorial voting rule with three or more candidates is theoretically susceptible to strategic manipulation. However, this vulnerability often fails to manifest in large-scale real-world scenarios. This paper, originally presented at IJCAI-16, explores why. By modeling voter beliefs as positively correlated rather than independent, the authors demonstrate that the incentive for strategic lying vanishes at an exponential rate as the number of voters grows. This suggests that natural preference alignment acts as a powerful stabilizer for democratic processes.
Introduction: The Strategy-Proofness Dilemma
In social choice theory, the ideal voting system is "strategy-proof," meaning every voter's optimal strategy is to report their true preferences. The Gibbard-Satterthwaite theorem shatters this ideal for most practical systems. Previous attempts to find "average-case" robustness showed that under the assumption of independent and uniform voter preferences (Impartial Culture), the probability of a rule being manipulable decreases only at a slow polynomial rate of $1/\sqrt{n}$.
However, real-world preferences are rarely independent. In contexts like peer review or committee decisions, voters often share underlying values or expertise, leading to correlated beliefs. This research investigates whether such correlation makes voting systems more or less robust against strategic behavior.
Modeling Correlated Beliefs
The authors evaluate Scoring Rules (e.g., Plurality, Borda count) using the criterion of Ex Post Incentive Compatibility (EPIC). A rule is EPIC if truth-telling is the best response given a voter's beliefs about others' preferences. To capture realistic correlation, two models from rank-aggregation literature are employed:
- Conditional Mallows Model: Voters believe others' rankings are "noisy" versions of their own, with probability decreasing based on the Kendall-Tau distance (pairwise disagreements).
- Conditional Plackett-Luce Model: A flexible model where candidates have "strength" parameters, and ranking probabilities depend on these relative strengths.
The study utilizes probabilistic tools like Chernoff-Hoeffding bounds and the Berry-Esseen theorem to derive asymptotic bounds on manipulability.
Key Results: The Power of Correlation
The central finding is that positive correlation significantly deters strategic manipulation. When voters believe their peers likely agree with them, they perceive their favorite candidate as the "natural" winner, making a deceptive "nudge" unnecessary and potentially counterproductive.
Theoretical Bounds
- Theorem 1: Under Kendall-Tau correlated beliefs, the probability that a scoring rule is not EPIC vanishes at an exponential rate $O(e^{-cn})$. This is a massive improvement over the polynomial rates found in independent models.
- Theorem 5: For any general "conditionally independent and identically distributed" (c.i.i.d.) belief system, the probability of manipulability still goes to zero, but at a guaranteed minimum rate of $O(1/\sqrt{n})$.
- Plackett-Luce Robustness: Despite not strictly meeting Kendall-Tau criteria, the Plackett-Luce model also exhibits exponential convergence to EPIC.
Discussion and Future Directions
The jump from polynomial to exponential convergence suggests that many large-scale voting systems are naturally robust against manipulation due to the inherent correlation of voter preferences. However, several avenues for future research remain:
- Expanding Rule Sets: The current results focus on scoring rules. Future work should investigate if these exponential bounds apply to Condorcet-consistent rules like Schulze or Ranked Pairs.
- Complex Belief Networks: The assumption of c.i.i.d. beliefs may not capture the complexity of real-world social networks where opinions might cluster in non-identical ways.
- Refining Bounds: There remains a gap between the proven $1/\sqrt{n}$ rate and observed exponential behavior for "Top-Set" correlated beliefs that lack full Kendall-Tau correlation.
This work provides a theoretical foundation for the observed stability of large-scale voting systems, highlighting correlation as a key factor in democratic robustness.
Summary updated