Computer Science – Artificial Intelligence
Scientific paper
2009-03-06
AAMAS 2008: 967-974
Computer Science
Artificial Intelligence
7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008)
Scientific paper
Complexity theory is a useful tool to study computational issues surrounding the elicitation of preferences, as well as the strategic manipulation of elections aggregating together preferences of multiple agents. We study here the complexity of determining when we can terminate eliciting preferences, and prove that the complexity depends on the elicitation strategy. We show, for instance, that it may be better from a computational perspective to elicit all preferences from one agent at a time than to elicit individual preferences from multiple agents. We also study the connection between the strategic manipulation of an election and preference elicitation. We show that what we can manipulate affects the computational complexity of manipulation. In particular, we prove that there are voting rules which are easy to manipulate if we can change all of an agent's vote, but computationally intractable if we can change only some of their preferences. This suggests that, as with preference elicitation, a fine-grained view of manipulation may be informative. Finally, we study the connection between predicting the winner of an election and preference elicitation. Based on this connection, we identify a voting rule where it is computationally difficult to decide the probability of a candidate winning given a probability distribution over the votes.
No associations
LandOfFree
Complexity of Terminating Preference Elicitation 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 Terminating Preference Elicitation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Terminating Preference Elicitation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-135616