文章基本信息

标题：Cloning in Elections: Finding the Possible Winners
本地全文：下载
作者：E. Elkind ; P. Faliszewski ; A. Slinko 等
期刊名称：Journal of Artificial Intelligence Research
印刷版ISSN：1076-9757
出版年度：2011
卷号：42
页码：529-573
出版社：American Association of Artificial
摘要：We consider the problem of manipulating elections by cloning candidates. In our model, a manipulator can replace each candidate c by several clones, i.e., new candidates that are so similar to c that each voter simply replaces c in his vote with a block of these new candidates, ranked consecutively. The outcome of the resulting election may then depend on the number of clones as well as on how each voter orders the clones within the block. We formalize what it means for a cloning manipulation to be successful (which turns out to be a surprisingly delicate issue), and, for a number of common voting rules, characterize the preference profiles for which a successful cloning manipulation exists. We also consider the model where there is a cost associated with producing each clone, and study the complexity of finding a minimum-cost cloning manipulation. Finally, we compare cloning with two related problems: the problem of control by adding candidates and the problem of possible (co)winners when new alternatives can join.