Invited Talk: Francesca Rossi

Francesca Rossi Department of Pure and Applied Mathematics University of Padova Italy

Incomparability and Uncertainty in Preference Aggregation

We consider multi-agent settings where agents' preferences, which can be partially ordered, need to be aggregated. Moreover, such preferences may be incomplete. For example, agents may hide some of their preferences for privacy reasons, or we might be in the process of eliciting the agents' preferences. In the context of partially-ordered preferences, we study properties such as fairness and non-manipulability, and we show that suitable extensions of classical voting theory results continue to hold.

Moreover, we study the computational complexity of the problem of computing possible and necessary winners, that is, those candidates which can be or always are the most preferred among the agents. Possible and necessary winners are useful bounds to the exact set of winners, that can be known only when incompleteness will be resolved. For example, they help guiding preference elicitation in an efficient way. We show that computing possible and necessary winners is in general a difficult problem, and we identify sufficient conditions on the aggregation function that allow us to compute them in polynomial time.

We then consider the complexity of winner determination in a specific preference aggregation rule: sequential majority voting. Here, uncertainty can arise for two reasons: the choice of the agenda or incomplete preferences. We show that computing possible and necessary winners for this rule is easy. However, if we are interested only in balanced agendas, where the number of competitions for the candidates is as balanced as possible, then winner determination is difficult. This means that, by posing this restriction, this rule is difficult to manipulate.

This is joint work with Jérôme Lang, Maria Silvia Pini, K. Brent Venable, and Toby Walsh.