Computation and complexity of preference inference based on hierarchical models

Thumbnail Image
Wilson, Nic
George, Anne-Marie
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
AAAI Press / International Joint Conferences on Artificial Intelligence
Published Version
Research Projects
Organizational Units
Journal Issue
Preference Inference involves inferring additional user preferences from elicited or observed preferences, based on assumptions regarding the form of the user's preference relation. In this paper we consider a situation in which alternatives have an associated vector of costs, each component corresponding to a different criterion, and are compared using a kind of lexicographic order, similar to the way alternatives are compared in a Hierarchical Constraint Logic Programming model. It is assumed that the user has some (unknown) importance ordering on criteria, and that to compare two alternatives, firstly, the combined cost of each alternative with respect to the most important criteria are compared; only if these combined costs are equal, are the next most important criteria considered. The preference inference problem then consists of determining whether a preference statement can be inferred from a set of input preferences. We show that this problem is coNP-complete, even if one restricts the cardinality of the equal-importance sets to have at most two elements, and one only considers non-strict preferences. However, it is polynomial if it is assumed that the user's ordering of criteria is a total ordering; it is also polynomial if the sets of equally important criteria are all equivalence classes of a given fixed equivalence relation. We give an efficient polynomial algorithm for these cases, which also throws light on the structure of the inference.
Preference inference techniques , Artificial intelligence (AI) , AI technology , Preference Inference
Wilson, N., George, A.-M. and O'Sullivan, B. (2015) 'Computation and Complexity of Preference Inference Based on Hierarchical Models', IJCAI'15: Proceedings of the 24th International Conference on Artificial Intelligence, Buenos Aires, Argentina, 25–31 July, pp. 3271–3277. isbn: 978-1-57735-738-4
Link to publisher’s version
© 2015 International Joint Conferences on Artificial Intelligence.