New Approximation for Borda Coalitional Manipulation

We study the problem of Borda Unweighted Coalitional Manipulation, where k manipulators try to manipulate an election on m candidates under the Borda protocol. This problem is known to be NP-hard. While most recent approaches to approximation tried to minimize k, the number of manipulators needed to make the preferred candidate win (thus assuming that the number of manipulators is not limited in advance), we focus instead on minimizing the maximum score obtainable by a non-preferred candidate. We provide a randomized, additive O(k √(m log m) ) approximation to this value; 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, where the addition of an extra manipulator implied (with respect to the original k) a strategy that provides an Ω(m)-additive approximation to a runner-up's score: when k is o(√(m/log m)), our strategy provides a stronger approximation. Our algorithm can also be viewed as a (1+o(1))-multiplicative approximation since the value we approximate has a natural Ω(km) lower bound.

Our methods are novel and adapt techniques from multiprocessor scheduling by carefully rounding an exponentially-large configuration linear program that is solved by using the ellipsoid method with an efficient separation oracle. We believe that such methods could be beneficial in approximating coalitional manipulation in other election protocols as well.

• Algorithms and Theory

• Economics and Electronic Commerce