Computer Science – Artificial Intelligence
Scientific paper
2009-11-19
Computer Science
Artificial Intelligence
Proceedings of the CARE'09 International Workshop on Collaborative Agents -- REsearch and Development, Melbourne 2009
Scientific paper
For many voting rules, it is NP-hard to compute a successful manipulation. However, NP-hardness only bounds the worst-case complexity. Recent theoretical results suggest that manipulation may often be easy in practice. We study empirically the cost of manipulating the single transferable vote (STV) rule. This was one of the first rules shown to be NP-hard to manipulate. It also appears to be one of the harder rules to manipulate since it involves multiple rounds and since, unlike many other rules, it is NP-hard for a single agent to manipulate without weights on the votes or uncertainty about how the other agents have voted. In almost every election in our experiments, it was easy to compute how a single agent could manipulate the election or to prove that manipulation by a single agent was impossible. It remains an interesting open question if manipulation by a coalition of agents is hard to compute in practice.
No associations
LandOfFree
Manipulability of Single Transferable Vote 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 Manipulability of Single Transferable Vote, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Manipulability of Single Transferable Vote will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-452617