Metrics
17 Record Views
Journal article
Incompleteness and incomparability in preference aggregation: Complexity results
Artificial intelligence, Vol.175(7), pp.1272-1289
05/2011
Web of Science ID: WOS:000290822300010
Abstract
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 general properties of the preference aggregation function, such as independence to irrelevant alternatives, which are sufficient for such sets to be computed in polynomial time. Finally, we show how possible and necessary winners can be used to focus preference elicitation. We show that it is computationally intractable for the cup rule with weighted votes in the worst-case to decide when to terminate elicitation. However, we identify a property of the preference aggregation function that allows us to decide when to terminate elicitation in polynomial time, by focusing on possible and necessary winners.
Details
- Title
- Incompleteness and incomparability in preference aggregation
- Publication Details
- Artificial intelligence, Vol.175(7), pp.1272-1289
- Resource Type
- Journal article
- Publisher
- Elsevier B.V
- Number of pages
- 18
- Copyright
- © 2011 Elsevier B.V. All rights reserved.
- Identifiers
- WOS:000290822300010; 99380590496606600
- Academic Unit
- Hal Marcus College of Science and Engineering ; Intelligent Systems and Robotics; Institute for Human and Machine Cognition
- Language
- English