Philosophy Faculty Database
Philosophy
Arts & Sciences
Duke University

 HOME > Arts & Sciences > Philosophy > Faculty    Search Help Login pdf version printable version 

Publications [#236266] of Vincent Conitzer

Duke :: Philosophy :: Faculty :: Vincent Conitzer

Journal articles or Book chapters PUBLISHED

  1. Xia, L; Zuckerman, M; Procaccia, AD; Conitzer, V; Rosenschein, JS, Complexity of unweighted coalitional manipulation under some common voting rules, IJCAI International Joint Conference on Artificial Intelligence (January, 2009), pp. 348-353.
    (last updated on 2024/03/29)

    Abstract:
    Understanding the computational complexity of manipulation in elections is arguably the most central agenda in Computational Social Choice. One of the influential variations of the the problem involves a coalition of manipulators trying to make a favorite candidate win the election. Although the complexity of the problem is well-studied under the assumption that the voters are weighted, there were very few successful attempts to abandon this strong assumption. In this paper, we study the complexity of the unweighted coalitional manipulation problem (UCM) under several prominent voting rules. Our main result is that UCM is NP-complete under the maximin rule; this resolves an enigmatic open question. We then show that UCM is NP-complete under the ranked pairs rule, even with respect to a single manipulator. Furthermore, we provide an extreme hardness-of-approximation result for an optimization version of UCM under ranked pairs. Finally, we show that UCM under the Bucklin rule is in P.


Duke University * Arts & Sciences * Philosophy * Faculty * Staff * Grad * Reload * Login