Preference inference based on hierarchical and simple lexicographic models
Loading...
Files
Published version
Date
2017
Authors
Wilson, Nic
George, Anne-Marie
O'Sullivan, Barry
Journal Title
Journal ISSN
Volume Title
Publisher
College Publications
Published Version
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, similarly 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 (which we call a simple lexicographic model); 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. We give a complete proof theory for the simple lexicographic model case, and analyse variations of preference inference.
Description
Keywords
Preference inference , Constraint logic programming , Hierarchical Constraint Logic Programming model
Citation
Wilson, N., George, A.-M., and O'Sullivan, B. (2017) 'Preference Inference Based on Hierarchical and Simple Lexicographic Models', Journal of Applied Logics - IfCoLog Journal, 4 (7), pp. 1997-2038.