Uncertainty in Preference Elicitation and Aggregation

Abstract

Uncertainty arises in preference aggregation in several ways. There may, for example, be uncertainty in the votes or the voting rule. Such uncertainty can introduce computational complexity in determining which candidate or candidates can or must win the election. In this paper, we survey recent work in this area and give some new results. We argue, for exam-ple, that the set of possible winners can be computationally harder to compute than the necessary winner. As a second ex-ample, we show that, even if the unknown votes are assumed to be single-peaked, it remains computationally hard to com-pute the possible and necessary winners, or to manipulate the election.