Loading...
Please wait, while we are loading the content...
Similar Documents
Complexity of manipulating elections with few candidates
| Content Provider | CiteSeerX |
|---|---|
| Author | Conitzer, Vincent Tuomas, S. |
| Description | In multiagent settings where the agents have different pref-erences, preference aggregation is a central issue. Voting is a general method for preference aggregation, but seminal re-sults have shown that all general voting protocols are manip-ulable. One could try to avoid manipulation by using pro-tocols 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 the more common setting 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 coali-tional manipulation is easy with unweighted voters. However, constructive coalitional manipulation with weighted voters is intractable for all of the voting protocols under study, except in the Cup protocol. Destructive manipulation tends to be eas-ier, except in the Single Transferable Vote protocol. Random-izing over instantiations of the protocols (such as schedules of a Cup) can be used to make manipulation hard. Finally, we show that under weak assumptions, if weighted coali-tional manipulation with complete information about the oth-ers ’ votes is hard in some voting protocol, then individual and unweighted manipulation is hard when there is uncertainty about the others ’ votes. 1. |
| File Format | |
| Language | English |
| Publisher Institution | In Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI’02 |
| Access Restriction | Open |
| Subject Keyword | Weak Assumption Central Issue Multiagent Setting Individual Manipulation Common Setting Derive Hardness Result General Method Different Pref-erences Voting Protocol Beneficial Manipulation Unweighted Voter Oth-ers Vote General Voting Protocol Constructive Coalitional Manipulation Seminal Re-sults Computational Agent Computational Complexity Cup Protocol Weighted Voter Others Vote Complete Information Destructive Manipulation Single Transferable Vote Protocol Preference Aggregation Coali-tional Manipulation Unweighted Manipulation |
| Content Type | Text |
| Resource Type | Article |
