View article

We consider how to combine the preferences of multiple agents despite the presence of incompleteness and incomparability in their preference relations over possible candidates. The set of preference relations of an agent may be incomplete because, for example, there is an ongoing preference elicitation process. There may also be incomparability as this is useful, for example, in multi-criteria scenarios. We focus here on the problem of computing the possible and necessary winners, that is, those candidates which can be, or always are, the most preferred for the agents. Possible and necessary winners are useful in many scenarios including preference elicitation. First, we show that testing possible and necessary winners is in general a computationally intractable problem for STV with unweighted votes and the cup rule with weighted votes, as is providing a good approximation of such sets. Then, we identify …