A scheduling approach to coalitional manipulation
The coalitional manipulation problem is one of the central problems in computational social choice. In this paper, we focus on solving the problem under the important family of positional scoring rules, in an approximate sense that was advocated by Zuckerman et al. [SODA 2008, AIJ 2009]. Our main result is a polynomial-time algorithm with (roughly speaking) the following theoretical guarantee: given a manipulable instance with m alternatives, the algorithm finds a successful manipulation with at most m - 2 additional manipulators. Our technique is based on a reduction to the scheduling problem known as Q|pmtn|Cmax, along with a novel rounding procedure. We demonstrate that our analysis is tight by establishing a new type of integrality gap. We also resolve a known open question in computational social choice by showing that the coalitional manipulation problem remains (strongly) NP-complete for positional scoring rules even when votes are unweighted. Finally, we discuss the implications of our results with respect to the question: "Is there a prominent voting rule that is usually hard to manipulate?" Copyright 2010 ACM.
