  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 voting
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. We derive
hardness results for practical multiagent settings where the number of
candidates is small but the number of voters can be large. We show that with
complete information about the others' votes, individual manipulation is easy,
and coalitional manipulation is easy with unweighted voters. However,
constructive coalitional manipulation with weighted voters is intractable for
all of the voting protocols under study, except for the nonrandomized Cup.
Destructive manipulation tends to be easier. Randomizing over instantiations of
the protocols (such as schedules of the Cup protocol) can be used to make
manipulation hard. Finally, we show that under weak assumptions, if weighted
coalitional manipulation with complete information about the others' votes is
hard in some voting protocol, then individual and unweighted manipulation is
hard when there is uncertainty about the others' votes.
