Abstract
We study the problem of coalitional manipulation—where $k$ manipulators try to manipulate an election on $m$ candidates—under general scoring rules, with a focus on the Borda protocol. We do so both in the weighted and unweighted settings. We focus on minimizing the maximum score obtainable by a non-preferred candidate. In the strongest, most general setting, we provide an algorithm for any scoring rule as described by a vector $\vec{\alpha}=(\alpha_1,\ldots,\alpha_m)$: for some $\beta=O(\sqrt{m\log m})$, it obtains an additive approximation equal to $W\cdot \max_i \lvert \alpha_{i+\beta}-\alpha_i \rvert$, where $W$ is the sum of voter weights. For Borda, both the weighted and unweighted variants are known to be $NP$-hard. For the unweighted case, our simpler algorithm provides a randomized, additive $O(k \sqrt{m \log m} )$ approximation. For the weighted case, our generalized algorithm provides an $O(W \sqrt{m \log m} )$-additive approximation. Our methods are based on carefully rounding an exponentially-large configuration linear program that is solved by using the ellipsoid method with an efficient separation oracle.
Introduction
Coalitional manipulation is a central problem in computational social choice, describing scenarios where a group of voters coordinates their ballots to ensure a preferred candidate wins. While many voting rules, including the Borda count, are NP-hard to manipulate, the actual difficulty of finding an effective strategy varies.
This paper shifts the focus from the traditional question—"how many manipulators are needed to win?"—to a more practical optimization goal: given a fixed number of manipulators $k$, how can they vote to minimize the maximum score of any competitor? By minimizing this maximum score, the coalition maximizes the margin by which their preferred candidate can win. This approach provides the first provable additive approximation guarantees for general scoring rules.
The Configuration LP Framework
The core innovation of this work is the application of Configuration Linear Programming (C-LP). This technique, often utilized in multiprocessor scheduling (such as the "Santa Claus problem"), allows the problem to be modeled by focusing on the distribution of scores rather than individual ballot permutations.
1. Modeling Configurations
In a scoring rule, candidates receive points based on their rank in a ballot. A "configuration" describes the set of scores a single candidate receives across all $k$ manipulator ballots. By treating the problem as assigning configurations to candidates, the authors can more effectively balance the total scores assigned to non-preferred candidates.
2. Solving via the Ellipsoid Method
Because the number of possible configurations is exponential relative to the number of candidates, the LP cannot be solved using standard methods. The authors utilize the Ellipsoid Method combined with a custom Separation Oracle. This oracle identifies violated constraints by solving variations of the Knapsack problem:
- Unweighted Voters: Addressed via a "k-multiset knapsack."
- Weighted Voters: Addressed via a "k-sequence knapsack."
3. Randomized Rounding and Validation
After obtaining a fractional solution from the LP, the algorithm uses randomized rounding to select specific configurations for each candidate. To ensure these selections form a valid set of ballots (e.g., ensuring that the "rank 1" score is not used more times than there are voters), the authors implement a re-indexing and adjustment step. This "fixing" step ensures the final strategy is valid while preserving the theoretical approximation guarantees.
Key Insights and Results
Theoretical Bounds
For the Borda rule, the algorithm provides an additive approximation of $O(k\sqrt{m \log m})$ for unweighted cases and $O(W\sqrt{m \log m})$ for weighted cases (where $W$ is the total weight). This is a significant improvement over previous methods that often imposed restrictions on voter weights or only provided $O(m)$ approximations.
Overcoming Greedy Limitations
The authors demonstrate that standard greedy heuristics, such as the "REVERSE" algorithm, can fail significantly. Specifically, they prove that REVERSE can fail even when a manipulation strategy exists that allows the preferred candidate to win by a margin as large as $m/3$. The C-LP approach avoids these local optima by considering the global distribution of scores.
Empirical Performance
The algorithm was evaluated using synthetic datasets under the Impartial Culture model, focusing on the "sweet spot" where $n = 2k$ and $k \approx \sqrt{m}$. In these experiments:
- The C-LP algorithm consistently outperformed the "AVERAGE FIT" and "REVERSE" heuristics.
- In many instances, the rounded algorithm achieved results identical to the fractional LP bound, proving that the algorithm frequently finds the absolute optimal strategy.
Conclusion
By importing techniques from scheduling theory into social choice, this research provides a robust framework for coalitional manipulation. The move toward score-margin optimization offers a more granular understanding of election integrity. Future research may focus on developing more efficient combinatorial algorithms to replace the computationally intensive Ellipsoid method and extending C-LP to other domains like fair division.
Summary updated