Preference inference based on lexicographic and Pareto models
Loading...
Files
Full Text E-thesis
Date
2019
Authors
George, Anne-Marie
Journal Title
Journal ISSN
Volume Title
Publisher
University College Cork
Published Version
Abstract
Preferences play a crucial part in decision making. When supporting a user in making a decision, it is important to analyse the user’s preference information to compute good recommendations or solutions. However, often it is impractical or impossible to obtain complete knowledge on preferences. Preference inference aims to exploit given preference information and deduce more preferences. More specifically, the Deduction Problem asks whether another preference statement can be deduced from a given set of preference statements. The closely related Consistency Problem asks whether a given set of user preferences is consistent, i.e., the statements are not contradicting each other. We present approaches for preference inference based on qualitative preference models that are based on lexicographic and Pareto orders. We consider user preference statements that are given in the form of comparisons of alternatives or alternative sets. For some model types and preference statements we formulate efficient algorithms; for others we show NP-completeness and coNP-completeness results. In particular, we find that the Deduction and Consistency problem are polynomial time solvable for comparative preference statements for lexicographic and simple Pareto preference models by a detailed analysis of the problem structures. The computational efficiency for these models makes them particularly appealing for practical uses. The Deduction and Consistency Problem are coNP-complete and NP-complete, respectively, for hierarchical and generalised Pareto models, which make these models less practical even for simple preference languages. However, we still formulate a quite efficient algorithmic approach to solve the Consistency Problem (and implicitly the Deduction) for hierarchical models. We also analyse deduction and consistency for preference statements that are (strongly) compositional under some set of preference models. (Strong) compositionality is a property of preference statements in connection with a set of preference models. It demands inference of preference statements for certain combinations of preference models. We find many interesting results for this case, which ultimately leads to a general greedy algorithm to solve the Consistency Problem for strongly compositional preference statements. This indicates that strong compositionality is an important property that can deliver immediate algorithmic approaches when present. We find many types of preference statements, e.g., conjunctions of strongly compositional statements, are strongly compositional. The considered comparative preferences statements are also strongly compositional for many of the discussed preference models - different lexicographic and hierarchical models. We can make use of the Deduction Problem to find a set of optimal alternatives, e.g., to be recommended to a user that are undominated with respect to different notions of optimality. We analyse this connection for general lexicographic models and find computationally efficient solutions.
Description
Keywords
Lexicographic , Pareto , Consistency , Deduction , Complexity , Algorithms , Preference inference , Preference modelling
Citation
George, A-M. 2019. Preference inference based on lexicographic and Pareto models. PhD Thesis, University College Cork.