An Algorithm for the Coalitional Manipulation Problem under Maximin

We introduce a new algorithm for the Unweighted Coalitional Manipulation problem under the Maximin voting rule. We prove that the algorithm gives an approximation ratio of 12/3 to the corresponding optimization problem. This is an improvement over the previously known algorithm that gave a 2-approximation. We also prove that its approximation ratio is no better than 11/2, i. e. , there are instances on which a 11/2 -approximation is the best the algorithm can achieve. Finally, we prove that no algorithm can approximate the problem better than to the factor of 11/2, unless P = NP.

Authors

• Michael Zuckerman Piotr Faliszewski
• Omer Lev Ben-Gurion University of the Negev
• Jeffrey S. Rosenschein

Keywords

• Social choice theory
• Algorithms
• Approximation