Computation and complexity of preference inference based on hierarchical models

Thumbnail Image
Files
Date
2015-07
Authors
Wilson, Nic
George, Anne-Marie
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
AAAI Press / International Joint Conferences on Artificial Intelligence
Published Version
Research Projects
Organizational Units
Journal Issue
Abstract
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.
Description
Keywords
Preference inference techniques , Artificial intelligence (AI) , AI technology , Preference Inference
Citation
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
https://www.ijcai.org/Proceedings/2015
URI
https://hdl.handle.net/10468/10796
Collections
Computer Science - Conference Items
Insight Centre for Data Analytics - Conference Items
Copyright
© 2015 International Joint Conferences on Artificial Intelligence.