Abstract
Most analyses of manipulation of voting schemes have adopted two assumptions that greatly diminish their practical import. First, it is usually assumed that the manipulators have full knowledge of the votes of the nonmanipulating agents. Second, analysis tends to focus on the probability of manipulation rather than its impact on the social choice objective (e.g., social welfare). We relax both of these assumptions by analyzing optimal Bayesian manipulation strategies when the manipulators have only partial probabilistic information about nonmanipulator votes, and assessing the expected loss in social welfare (in the broad sense of the term). We present a general optimization framework for the derivation of optimal manipulation strategies given arbitrary voting rules and distributions over preferences. We theoretically and empirically analyze the optimal manipulability of some popular voting rules using distributions and real data sets that go well beyond the common, but unrealistic, impartial culture assumption. We also shed light on the stark difference between the loss in social welfare and the probability of manipulation by showing that even when manipulation is likely, impact to social welfare is slight (and often negligible).
Introduction
In computational social choice, manipulation occurs when voters misreport their true preferences to achieve a more favorable outcome. Traditional research has largely focused on the computational complexity of finding such strategies or the mathematical probability of their existence. However, these models often rely on the "Omniscience Assumption," where manipulators possess perfect knowledge of all other votes—a scenario rarely encountered in practice. Furthermore, success is typically measured as a binary outcome, ignoring the actual impact on social welfare. This paper addresses these gaps by introducing a Bayesian framework for manipulation under partial probabilistic knowledge and evaluating the resulting societal "regret."
Methodology
The authors propose a general optimization framework for Bayesian Manipulation. In this model, manipulators hold a belief distribution over possible vote profiles rather than knowing exact counts.
Optimal Bayesian Strategy and MIP Framework
The objective is to identify a set of votes that maximizes the probability of a preferred candidate winning. To handle complex voting rules where analytical solutions are elusive, the authors employ a sample-based approach. By sampling $T$ vote profiles from the belief distribution, they formulate a Mixed Integer Program (MIP) to find the strategy that succeeds across the maximum number of samples. Efficiency is enhanced through Positional Summary Matrices (PSM), which represent strategies by the count of rankings in specific positions rather than exhaustive permutations.
Datasets and Welfare Metrics
The framework was tested using:
- 2002 Irish Electoral Data: Specifically, the Dublin West constituency, using a Mallows mixture model to represent realistic prior beliefs.
- Synthetic Mallows Models: To test varying levels of voter consensus.
Social welfare is proxied by the "score" assigned by the voting rule (e.g., Borda). "Regret" is defined as the difference in score between the sincere winner and the manipulated winner.
Results and Analysis
The empirical results reveal a critical distinction between the likelihood of manipulation and its actual impact. As shown in the analysis of the Dublin West 2002 dataset, while the probability of successful manipulation can be quite high, the corresponding loss in social welfare is remarkably low.
Key findings include:
- Low Welfare Loss: Even when the probability of success reached 70-80%, the normalized regret was often less than 3%. This suggests that for a manipulator to succeed, their candidate must already be a close competitor, minimizing the societal damage of the change.
- Phase Transitions: Success probability drops rapidly as the number of sincere voters $n$ increases relative to the coalition size.
- Computational Feasibility: Pruning rules allowed the NP-hard MIP to be solved in seconds or minutes for real-world sized problems.
- The "Balanced Strategy": For $k$-approval voting, the optimal strategy often involves distributing the coalition's extra votes as evenly as possible among competitors.
Conclusion
This research demonstrates that while vote manipulation is often computationally tractable and likely to succeed in Bayesian settings, it is generally "safe" for society. The actual harm to social welfare is typically negligible because successful manipulation is usually confined to candidates who are already popular. Future work may explore the relationship between information entropy and manipulation success, as well as extending the framework to more complex rules like Single Transferable Vote (STV).
Summary updated