### When are elections with few candidates hard to manipulate?When are elections with few candidates hard to manipulate?

Access Restriction
Subscribed

 Author Conitzer, Vincent ♦ Sandholm, Tuomas ♦ Lang, Jrme Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2007 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Computational social choice ♦ Hardness of manipulation ♦ Voting Abstract In multiagent settings where the agents have different preferences, preference aggregation is a central issue. Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable. One could try to avoid manipulation by using protocols where determining a beneficial manipulation is hard. Especially among computational agents, it is reasonable to measure this hardness by computational complexity. Some earlier work has been done in this area, but it was assumed that the number of voters and candidates is unbounded. Such hardness results lose relevance when the number of candidates is small, because manipulation algorithms that are exponential only in the number of candidates (and only slightly so) might be available. We give such an algorithm for an individual agent to manipulate the Single Transferable Vote (STV) protocol, which has been shown hard to manipulate in the above sense. This motivates the core of this article, which derives hardness results for realistic elections where the number of candidates is a small constant (but the number of voters can be large). The main manipulation question we study is that of $\textit{coalitional}$ manipulation by $\textit{weighted}$ voters. (We show that for simpler manipulation problems, manipulation cannot be hard with few candidates.) We study both $\textit{constructive}$ manipulation (making a given candidate win) and $\textit{destructive}$ manipulation (making a given candidate not win). We characterize the exact number of candidates for which manipulation becomes hard for the $\textit{plurality},$ $\textit{Borda},$ $\textit{STV},$ $\textit{Copeland},$ $\textit{maximin},$ $\textit{veto},$ plurality with runoff, regular cup, and randomized cup protocols. We also show that hardness of manipulation in this setting implies hardness of manipulation by an individual in unweighted settings when there is uncertainty about the others' votes (but not vice-versa). To our knowledge, these are the first results on the hardness of manipulation when there is uncertainty about the others' votes. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2007-06-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 54 Issue Number 3

#### Open content in new tab

Source: ACM Digital Library