Papers › New Approximations for Coalitional Manipulation in General Scoring Rules
New Approximations for Coalitional Manipulation in General Scoring Rules
Orgad Keller, Avinatan Hassidim, Noam Hazon
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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 α⃗=(α₁,…,αₘ): for some β=O(√(mlogm)), it obtains an additive approximation equal to W·maxᵢ |αᵢ₊ᵦ-αᵢ |, 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 √(m logm) ) approximation; in other words, if there exists a strategy enabling the preferred candidate to win by an Ω(k √(m logm) ) margin, our method, with high probability, will find a strategy enabling her to win (albeit with a possibly smaller margin). It thus provides a somewhat stronger guarantee compared to the previous methods, which implicitly implied a strategy that provides an Ω(m)-additive approximation to the maximum score of a non-preferred candidate. For the weighted case, our generalized algorithm provides an O(W √(m logm) )-additive approximation, where W is the sum of voter weights. This is a clear advantage over previous methods: some of them do not generalize to the weighted case, while others---which approximate the number of manipulators---pose restrictions on the weights of extra manipulators added. 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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections