Computer Science – Artificial Intelligence
Scientific paper
2010-07-05
Computer Science
Artificial Intelligence
To appear in Proceedings of 11th International Workshop on Computational Logic in Multi-Agent Systems (CLIMA XI 2010)
Scientific paper
When agents are acting together, they may need a simple mechanism to decide on joint actions. One possibility is to have the agents express their preferences in the form of a ballot and use a voting rule to decide the winning action(s). Unfortunately, agents may try to manipulate such an election by misreporting their preferences. Fortunately, it has been shown that it is NP-hard to compute how to manipulate a number of different voting rules. However, NP-hardness only bounds the worst-case complexity. Recent theoretical results suggest that manipulation may often be easy in practice. To address this issue, I suggest studying empirically if computational complexity is in practice a barrier to manipulation. The basic tool used in my investigations is the identification of computational "phase transitions". Such an approach has been fruitful in identifying hard instances of propositional satisfiability and other NP-hard problems. I show that phase transition behaviour gives insight into the hardness of manipulating voting rules, increasing concern that computational complexity is indeed any sort of barrier. Finally, I look at the problem of computing manipulation of other, related problems like stable marriage and tournament problems.
No associations
LandOfFree
Is Computational Complexity a Barrier to Manipulation? 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 Is Computational Complexity a Barrier to Manipulation?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Is Computational Complexity a Barrier to Manipulation? will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-215626