Correlated Voting

Debmalya Mandal, David C. Parkes

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:

  1. Conditional Mallows Model: Voters believe others' rankings are "noisy" versions of their own, with probability decreasing based on the Kendall-Tau distance (pairwise disagreements).
  2. 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.

Comparison of the probability mass function (pmf) for Kendall-Tau correlated beliefs (a) versus general c.i.i.d. beliefs (b). Shaded areas represent the probability of manipulability.

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

Abstract

We study the social choice problem where a group of n voters report their preferences over alternatives and a voting rule is used to select an alternative. We show that when the preferences of voters are positively correlated according to the Kendall-Tau distance, the probability that any scoring rule is not ex post incentive compatible (EPIC) goes to zero exponentially fast with the number of voters, improving over the previously known rate of 1/√n for independent preferences. Motivated by rank-order models from machine learning, we introduce two examples of positively-correlated models, namely Conditional Mallows and Conditional Plackett-Luce. Conditional Mallows satisfies Kendall-Tau correlation and fits our positive result. We also prove that Conditional Plackett-Luce becomes EPIC exponentially quickly.
BibTeX
@inproceedings{mandal2016correlated,
  author = {Debmalya Mandal and David C. Parkes},
  title = {{Correlated Voting}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure