An algorithm for the coalitional manipulation problem under maximin Conference Paper uri icon


  • Abstract 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 1 2/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 1 1/2, ie, there are instances on which a 1 1/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 1 1/2, unless p= NP.

publication date

  • May 2, 2011