2017/08/16 by Orgad Keller, Avinatan Hassidim, Keller, Orgad +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1708.04862
openalex publication_date 2017/08/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 α=(α1,…,αm): for some β=O(√(mlog m)), it obtains an additive approximation equal to W⋅ maxi | αi+β-αi |, 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 log m) ) approximation; in other words, if there exists a strategy enabling the preferred candidate to win by an Ω(k √(m log m) ) 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 log m) )-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.