  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.
