TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 22.11.2018


Page Content

to Navigation

Preference Inference Based on Lexicographic and Pareto Models

Anne-Marie George (TU Berlin)


Preferences play a crucial role in any decision making process and are analysed to compute good recommendations or solutions. However, often it is impractical or impossible to obtain complete knowledge on user preferences. Preference inference aims to exploit given incomplete 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 under different assumptions of qualitative user preference models that are based on lexicographic and Pareto orders. Here, we consider user preference statements that are given in the form of comparisons of alternatives or sets of alternatives. For some model types and preference statements we formulate efficient algorithms; for others we show NP-completeness and coNP-completeness results. The algorithmic approaches are based on a detailed analysis of the problem structures. 

We also analyse deduction and consistency for preference statements that are (strongly) compositional under some set of preference models. (Strong) compositionality is a property that demands inference of preference statements for certain combinations of preference models. We find many interesting results for this case, which ultimately lead to a general greedy algorithm for solving the Consistency Problem for strongly compositional preference statements for arbitrary preference models. The considered comparative preferences statements are strongly compositional for many of the discussed preference models.



Anne-Marie George
TEL 512

Back to the research colloquium site.

To top


Quick Access

Schnellnavigation zur Seite über Nummerneingabe