Computer Science – Computer Science and Game Theory
Scientific paper
2002-05-29
Proceedings of the 18th National Conference on Artificial Intelligence (AAAI-02), Edmonton, Canada, 2002
Computer Science
Computer Science and Game Theory
In AAAI-02 plenary session
Scientific paper
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.
Conitzer Vincent
Sandholm Tuomas
No associations
LandOfFree
Complexity of Manipulating Elections with Few Candidates does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Complexity of Manipulating Elections with Few Candidates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Manipulating Elections with Few Candidates will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-100440