Preference Inference Based on Pareto Models

Abstract

In this paper, we consider Preference Inference based on a generalised form of Pareto order. Preference Inference aims at reasoning over an incomplete specification of user preferences. We focus on two problems. The Preference Deduction Problem (PDP) asks if another preference statement can be deduced (with certainty) from a set of given preference statements. The Preference Consistency Problem (PCP) asks if a set of given preference statements is consistent, i.e., the statements are not contradicting each other. Here, preference statements are direct comparisons between alternatives (strict and non-strict). It is assumed that a set of evaluation functions is known by which all alternatives can be rated. We consider Pareto models which induce order relations on the set of alternatives in a Pareto manner, i.e., one alternative is preferred to another only if it is preferred on every component of the model.

We describe characterisations for deduction and consistency based on an analysis of the set of evaluation functions, and present algorithmic solutions and complexity results for PDP and PCP, based on Pareto models in general and for a special case. Furthermore, a comparison shows that the inference based on Pareto models is less cautious than some other types of well-known preference model.

1 Introduction

Preference deduction can be valuable in many fields like recommender systems [3, 9] and multi-objective optimization [8], where one wants to reason over user preferences. It is often difficult or excessively time-consuming to elicit all user preferences. Thus, only an incomplete picture of the user’s preferences is given and there is therefore uncertainty regarding the user’s preferences. In the Preference Deduction Problem (PDP), the idea is to elicit only a few preferences from the user and infer other preferences; this might then be used in a conversational recommender system, for example, to help choose which items to show to the user next. Here, it is important to check if the given user statements are consistent. Otherwise, it would be possible to deduce any arbitrary preference statement. The Preference Consistency Problem (PCP) decides if a set of given user preference statements is consistent, i.e., the statements do not contradict each other. PDP and PCP have been studied under different order relations such as lexicographic orders [9, 11, 12], hierarchical orders [5, 13] and weighted sums [3, 4, 8]. Under these order relations PDP and PCP are mutually expressive, i.e., PDP can be solved using algorithms for PCP and vice versa. For Pareto models, PDP and PCP are not mutually expressive. While Pareto orders are widely studied in fields like voting theory [10] (unanimity), allocation problems [1] (Pareto optimality), decision making, database queries [2, 7] (skyline operator) and economics (Pareto efficiency), there exists no general study of PDP or PCP based on Pareto orders so far. Pareto orders give a natural way of comparing alternatives; one alternative is better than another if it is better on all relevant evaluation functions (different criteria by which the alternatives can be evaluated). In recommender systems and multi-objective decision making frameworks as well as the other aforementioned fields it is a reasonable assumption, that the user expresses her preferences (direct comparisons of two alternatives) in a Pareto manner. Here, one tries to find a set of optimal alternatives, i.e., alternatives that are undominated w.r.t. Pareto order.

This form of order relation leaves no room for compromises or tradeoffs between evaluation functions. Consider different holiday packages which include travel and hotel. We can evaluate the different alternatives by four criteria; the distance from the hotel to the city center, the distance from the hotel to the beach, the costs for the hotel and the travel costs. One user could consider the distance from the hotel to the beach and the costs for the hotel as the only relevant aspects. Then she prefers a package $\alpha$ to another package $\beta$, if $\alpha$ is closer or equidistant to the beach than $\beta$ and the costs of the hotel for $\alpha$ are lower or equal to the costs of the hotel for $\beta$. There is no compromise possible of, e.g., paying a little bit more in order to get a hotel closer to the beach. We generalise this type of order relation by considering groups of evaluation functions; only between the evaluation functions within the same group tradeoffs are possible. Consider different holiday packages again. One user could divide the four criteria into the aspects location and costs, such that one alternative is better than another if it is better in both the location and the costs. To evaluate the location, the two values for distance are combined by some operator $\oplus$ (e.g., addition). Similarly, the cost of the hotel and the travel costs are combined by $\oplus$ to evaluate the costs in total. This comparison allows tradeoffs between the distances from the hotel to the beach and to the city center, and between the costs for travel and for the hotel. Another user might want to divide the criteria into the aspects hotel and travel. The only allowed tradeoffs are between the hotel costs and the distance from the hotel to the beach and to the city center.

Since only partial information on the user preferences is known, we must consider the set of all Pareto models that satisfy the given preferences, i.e., that are possible candidates for the user’s true preference model. Only if there exists such a model, is the given set of preference statements consistent. Only if all these Pareto models satisfy another statement $\varphi$, can we deduce $\varphi$ with certainty.

In the next section we give basic definitions of Pareto models and the two problems of Preference Deduction and Preference Consistency. In Sect. 3, we first describe properties for the special case of consistency and deduction based on Pareto models that don’t allow tradeoffs between evaluation functions. These properties are exploited to formulate polynomial time algorithms for PDP and PCP. We then develop similar properties for the case of consistency and deduction based on the general form of Pareto models, and show that PCP and PDP based on general Pareto models are NP-complete and coNP-complete, respectively. In the fourth section, we compare the cautiousness of the inference based on Pareto models with other types of order relations. The last section concludes. A longer version of this paper including further proves and examples can be found under http://ucc.insight-centre.org/nwilson/ParetoInferenceProofs.pdf.

2 Preference Consistency and Deduction

To formally define the problems PDP and PCP in a Pareto context, we first define preference structures and Pareto models. Furthermore, we describe the language in which preference statements are expressed.

Definition 1

(Preference Structure). A preference structure is a tuple $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$. Here, $\mathcal{A}$ is a (finite) set of alternatives and $\mathcal{C}$ is a (finite) set of evaluation functions $c: \mathcal{A}\longrightarrow \mathbb {Q}^{\ge 0}$ by which the alternatives can be rated with non-negative rational numbers (the lower, the better; 0 is the best possible rating). The evaluation functions can be combined by the associative, commutative and strictly monotonic operation $\oplus$ on $\mathbb {Q}^{\ge 0}$, where strict monotonicity means $x \oplus y < z \oplus y$ if and only if $x < z$. Here, $\textit{e}$ is the neutral element such that $\textit{e}\oplus x = x$ for all $x \in \mathbb {Q}^{\ge 0}$.

Note, that $\oplus$ has been defined in a similar context to be only monotonic (not strictly monotonic) [13]. However, the strict monotonicity property is needed to establish some important theoretical results in Sect. 3. This excludes operators like maximum or minimum, but still allows interesting operators like addition with neutral element 0 which is a natural for combining, e.g., costs, distances, etc. In the special case of strictly positive evaluation functions $\mathcal{A}\longrightarrow \mathbb {Q}^{> 0}$ multiplication can also be used as operator with neutral element 1. For computational and complexity results, we assume that $x \oplus y$ can be computed in logarithmic time for $x, y \in \mathbb {Q}^{\ge 0}$.

	$\alpha$	$\beta$	$\gamma$
$d_c$	0	2	1
$d_b$	1	1	2
$c_h$	2	1	0
$c_t$	2	1	1

Example 1

Consider the choice of holiday packages $\alpha$, $\beta$ and $\gamma$. We rate the holiday packages by the distance from the hotel to the city center $d_c$, the distance to the beach $d_b$, the costs for the hotel $c_h$ and the travel costs $c_t$. The distances are categorised into far (2), medium (1) and near (0). The costs are categorised into high (2), medium (1) and low (0). The values of the four criteria for the alternatives $\alpha$, $\beta$ and $\gamma$ are given by the table on the right.

To combine evaluation functions, consider the operator $\oplus$ that is the standard addition on the natural numbers. Then $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$ is a preference structure, where $\mathcal{A}= \{\alpha , \beta , \gamma \}$ is the set of alternatives and $\mathcal{C}=\{d_c, d_b, c_h, c_t\}$ is the set of evaluation functions.

Let $\mathcal{L}_{\le }^\mathcal{A}$ be the set of non-strict preference statements $\alpha \le \beta$, and $\mathcal{L}_{<}^\mathcal{A}$ be the set of strict preference statements $\alpha < \beta$, over all $\alpha , \beta \in \mathcal{A}$. Let $\mathcal{L}^\mathcal{A}= \mathcal{L}_{\le }^\mathcal{A}\cup \mathcal{L}_{<}^\mathcal{A}$. We write $\varphi \in \mathcal{L}^\mathcal{A}$ as $\alpha _\varphi < \beta _\varphi$, if $\varphi$ is strict, and as $\alpha _\varphi \le \beta _\varphi$, if $\varphi$ is non-strict. For a set $\varGamma$ of strict and non-strict preference statements in $\mathcal{L}^\mathcal{A}$, define $\varGamma ^{(\le )}$ to be the non-strict version of $\varGamma$, i.e., $\varGamma ^{(\le )}= \{\alpha _\varphi \le \beta _\varphi \mid \varphi \in \varGamma \}$. Furthermore, define $\overline{\varphi }$ for a preference statement $\varphi$ to be the statement $\alpha _\varphi > \beta _\varphi$ if $\varphi$ is the non-strict statement $\alpha _\varphi \le \beta _\varphi$, and $\alpha _\varphi \ge \beta _\varphi$ if $\varphi$ is the strict statement $\alpha _\varphi < \beta _\varphi$.

Definition 2

(Pareto Model). For a preference structure $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$, a Pareto model M is a set of pairwise disjoint subsets of evaluations. More specifically, $M = \{C_1, \dots , C_r\}$ with $r \ge 0$ and pairwise disjoint sets $C_i \subseteq \mathcal{C}$ for $i=1, \dots , r$.

Let $\mathcal{P}_\mathcal{C}$ denote the set of all Pareto models over the set $\mathcal{C}$ of evaluations. We will abbreviate this notation to $\mathcal{P}$, when the set of evaluations $\mathcal{C}$ is clear from the context. Informally, a Pareto model corresponds to a grouping of evaluation functions. In the context of votes, one can interpret each evaluation function to express the preferences from one individual. In a Pareto model, the individuals form groups in which they come to a decision together (by applying the operator to their preference functions). The collective prefers one alternative $\alpha$ over another alternative $\beta$, if all groups agree that $\alpha$ is at least as good as $\beta$. So, each Pareto model $M=\{C_1, \dots , C_r\}$ induces an order relation on the set of alternatives $\mathcal{A}$ by comparing the combination of evaluations in the sets (by operator $\oplus$) in a Pareto manner. Formally, we define:

• $\alpha \le _{M} \beta$ if $\bigoplus _{c \in C_i} c(\alpha ) \le \bigoplus _{c \in C_i} c(\beta )$ for all $i = 1, \dots , r$. (M satisfies $\alpha \le \beta$ , written $M \vDash _\mathcal{P}\alpha \le \beta$ .)

• $\alpha <_{M} \beta$ if $\alpha \le _{M} \beta$ and there exists $j \in \{1, \dots , r\}$ such that $\bigoplus _{c \in C_j} c(\alpha ) < \bigoplus _{c \in C_j} c(\beta )$. (M satisfies $\alpha < \beta$ / M strictly satisfies $\alpha \le \beta$ , written $M \vDash _\mathcal{P}~\alpha ~<~\beta$ .)

• $\alpha \equiv _{M} \beta$ if $\alpha \le _{M} \beta$ and $\beta \le _{M} \alpha$. (M satisfies $\alpha \equiv \beta$ , written $M \vDash _\mathcal{P}\alpha \equiv \beta$ .)

Example 2

(Continued). Consider the preference structure described in Example 1. The Pareto model $M=\{\{d_c,d_b\},\{c_h,c_t\}\}$ describes the situation in which a user allows tradeoffs between the distance to the city center and the distance to the beach, and tradeoffs between the cost of the hotel and the travel costs. This Pareto model satisfies $\gamma <_M \beta$ since $d_c(\gamma ) \oplus d_b(\gamma ) = 1 + 2 = 2 + 1 = d_c(\beta ) \oplus d_b(\beta )$ and $c_h(\gamma ) \oplus c_t(\gamma ) = 0 + 1 < 1 + 1 = c_h(\beta ) \oplus c_t(\beta )$. Furthermore, the induced order relation of M leaves the pairs of alternatives $\alpha , \beta$ and $\alpha , \gamma$ incomparable. A user that considers Pareto model $M'=\{\{d_b, c_h\},\{c_t\}\}$ to describe her preferences allows tradeoffs between the distance to the beach and the costs of the hotel. Here, the user considers the travel costs separately and disregards the distance of the hotel to the city completely. This Pareto model satisfies $\gamma \equiv _{M'} \beta <_{M'} \alpha$.

Let $\mathcal{M}$ be a set of some preference models, e.g., $\mathcal{M}= \mathcal{P}$. In the following we define $\mathcal{M}$-PDP and $\mathcal{M}$-PCP.

$\mathcal{M}$-Preference Deduction Problem ( $\mathcal{M}$-PDP): Given a preference structure $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$, a set of preference statements $\varGamma \subseteq \mathcal{L}^\mathcal{A}$ and a preference statement $\varphi \in \mathcal{L}^\mathcal{A}\setminus \varGamma$, the Preference Deduction Problem asks whether all preference models in $\mathcal{M}$ that satisfy all statements in $\varGamma$ also satisfy $\varphi$, written $\varGamma \vDash _{\mathcal{M}} \varphi$.

Definition 3

( $\mathcal{M}$ -Consistency). For a preference structure $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$ and a set of preference models $\mathcal{M}$, the preference statements $\varGamma \subseteq \mathcal{L}^\mathcal{A}$ are $\mathcal{M}$ -consistent if there exists a preference model in $\mathcal{M}$ that satisfies all statements in $\varGamma$.

$\mathcal{M}$-Preference Consistency Problem ( $\mathcal{M}$-PCP): Given a preference structure $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$ and a set of preference statements $\varGamma \subseteq \mathcal{L}^\mathcal{A}$, the Preference Consistency Problem asks whether there exists a preference model in $\mathcal{M}$ that satisfies all given statements $\varGamma$.

In Sect. 3, we consider properties and complexity of the problems PCP and PDP based on Pareto models $\mathcal{P}_\mathcal{C}$ in general and based on the special classes of Pareto models $\mathcal{P}_{\mathcal{C}}(1)$ and $\mathcal{P}_{\mathcal{C}}^s$ defined as follows. The class $\mathcal{P}_{\mathcal{C}}(1)$ consists of Pareto models with only singleton sets, i.e., $\mathcal{P}_{\mathcal{C}}(1) = \{ \{C_1, \dots , C_r\} \in \mathcal{P}_{\mathcal{C}} \mid |C_i|=1 \textit{ for all } i =1, \dots , r\}$. The class $\mathcal{P}_{\mathcal{C}}^s$ consists of Pareto models that contain only a single set, i.e., $\mathcal{P}_{\mathcal{C}}^s = \{ \{C\} \in \mathcal{P}_{\mathcal{C}} \mid C \subset \mathcal{C}\}$. We adjust the notation where Pareto models in $\mathcal{P}_{\mathcal{C}}(1)$ or $\mathcal{P}_{\mathcal{C}}^s$ are considered to avoid confusion, and omit the set of evaluations $\mathcal{C}$ when this is clear from the context.

Example 3

(Continued). Consider the preference structure described in Example 1 and the set of preference statements $\varGamma = \{\alpha < \beta , \alpha \le \gamma \}$. The set $\varGamma$ is consistent (for $\mathcal{P}$ in general and in particular for $\mathcal{P}(1)$ and for $\mathcal{P}^s$) and the following Pareto models satisfy $\alpha < \beta$ and $\alpha \le \gamma$:

$\{\{d_c\}\}$, $\{\{d_c, d_b\}\}$, $\{\{d_c, c_t\}\}$, $\{\{d_c, d_b, c_h\}\}$, $\{\{d_c, d_b, c_t\}\}$, $\{\{d_c\}, \{d_b\}\}$, $\{\{d_c, c_t\}, \{d_b\}\}$. Furthermore, $\varGamma \not \vDash _{\mathcal{P}} \gamma \le \beta$ and $\varGamma \not \vDash _{\mathcal{P}(1)} \gamma \le \beta$ since the Pareto model $\{\{d_c\},\{d_b\}\} \in \mathcal{P}(1) \subseteq \mathcal{P}$ satisfies $\varGamma$ but not $\gamma \le \beta$. However, $\varGamma \vDash _{\mathcal{P}^s} \gamma \le \beta$ since the Pareto models $\{\{d_c\}\}$, $\{\{d_c, d_b\}\}$, $\{\{d_c, c_t\}\}$, $\{\{d_c, d_b, c_h\}\}$ and $\{\{d_c, d_b, c_t\}\}$ in $\mathcal{P}^s$ all satisfy $\varGamma$ and satisfy $\gamma \le \beta$.

3 Properties and Solutions for PCP and PDP

For many order relations like lexicographic orders, hierarchical models and weighted sums, PDP and PCP are mutually expressive [4, 13]. More specifically, for $\mathcal{M}$ being the set of all feasible preference models due to one of the aforementioned order relations, $\varGamma \vDash _{\mathcal{M}} \varphi$ if and only if $\varGamma \cup \{\overline{\varphi }\}$ is $\mathcal{M}$-inconsistent (i.e., there exists no model in $\mathcal{M}$ that satisfies all statements in $\varGamma \cup \{\overline{\varphi }\}$). The following example shows that the “$\Leftarrow$”-direction does not hold for Pareto models. Thus, we need to find algorithms to solve PCP and PDP separately.

	$\alpha$	$\beta$	$\gamma$
$c_1$	5	3	1
$c_2$	0	1	3
$c_3$	1	3	4

Example 4

Let the operator $\oplus$ be the standard addition on $\mathbb {Q}^{\ge 0}$. Consider the table on the right of values for evaluation functions $c_1,c_2,c_3$ evaluated at alternatives $\alpha ,\beta ,\gamma$. Let the set of given preference statements be $\varGamma = \{\beta < \gamma \}$ and let $\varphi$ be the strict statement $\alpha < \beta$, so that $\overline{\varphi }$ is $\alpha \ge \beta$. The following Pareto models satisfy $\varGamma$: $\{\{c_2\}\}$, $\{\{c_3\}\}$, $\{\{c_2\},\{c_3\}\}$, $\{\{c_2, c_3\}\}$, $\{\{c_1, c_2\},\{c_3\}\}$, $\{\{c_1, c_2, c_3\}\}$. However, none of the $\varGamma$-satisfying models satisfies $\alpha \ge \beta$. Thus, the set $\varGamma \cup \{\overline{\varphi }\} = \{\alpha \ge ~\beta , \beta < \gamma \}$ is $\mathcal{P}$-inconsistent. Also, $\varGamma \not \vDash _{\mathcal{P}} \varphi$, as the Pareto model $\{\{c_1,c_2\},\{c_3\}\}$ satisfies $\varGamma$ but not $\varphi$.

However, we can show that $\varGamma \vDash _{\mathcal{P}} \varphi$ implies $\varGamma \cup \{\overline{\varphi }\}$ is $\mathcal{P}$-inconsistent.

Proposition 1

Let $\varGamma \subseteq \mathcal{L}^\mathcal{A}$ and $\varphi \in \mathcal{L}^\mathcal{A}\setminus \varGamma$ be preference statements. If $\varGamma \vDash _{\mathcal{P}} \varphi$, then $\varGamma \cup \{\overline{\varphi }\}$ is $\mathcal{P}$-inconsistent.

Proof

Suppose $\varGamma \cup \{\overline{\varphi }\}$ is $\mathcal{P}$-consistent, i.e., there exists a Pareto model $M = \{C_1, \dots , C_m\}$ that satisfies $\varGamma$ and $M \vDash _{\mathcal{P}} \overline{\varphi }$. Suppose $\varphi$ is the strict statement $\alpha <\beta$. Since $M \vDash _{\mathcal{P}} \overline{\varphi }$, for all $i = 1, \dots , m$, $\bigoplus _{c \in C_i} c(\alpha ) \ge \bigoplus _{c \in C_i} c(\beta )$. Thus, $M \not \vDash _{\mathcal{P}} \varphi$, and $\varGamma \not \vDash _{\mathcal{P}} \varphi$. Analogously, we can show $\varGamma \not \vDash _{\mathcal{P}} \varphi$ for non-strict $\varphi$.    $\square$

3.1 Singleton Models

In this section, we find a simpler representation of the Pareto inference restricted to the class $\mathcal{P}(1)$ by using set relations on sets of evaluation functions. We define the set $C_{\alpha \le \beta }=\{c \in \mathcal{C}\mid c(\alpha ) \le c(\beta )\}$ of evaluations that satisfy $\alpha \le \beta$. Similarly, $C_{\alpha< \beta }=\{c \in \mathcal{C}\mid c(\alpha ) < c(\beta )\}$ and $C_{\alpha = \beta }=\{c~\in ~\mathcal{C}~\mid ~c(\alpha )~=~c(\beta )\}$. For better readability we abbreviate the notation of a model $M = \{\{c_1\}, \dots , \{c_r\}\}$ in $\mathcal{P}_\mathcal{C}(1)$ to $\{c_1, \dots , c_r\}$.

Note, that the empty Pareto model $\{\}$ always satisfies non-strict statements, i.e., a set $\varGamma \subseteq \mathcal{L}_{\le }^\mathcal{A}$ is always $\mathcal{P}(1)$-consistent. We can prove the following characterisation of $\mathcal{P}(1)$-consistency.

Proposition 2

Let $\varGamma \subseteq \mathcal{L}^\mathcal{A}$ be a set of preference statements that includes at least one strict statements. $\varGamma$ is $\mathcal{P}(1)$-consistent if and only if for all $\varphi ' \in \varGamma \cap \mathcal{L}_{<}^\mathcal{A}$ there exists an evaluation c that satisfies $\varGamma ^{(\le )}$ and strictly satisfies $\varphi '$, i.e., $C_{\varphi '} \cap \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi \ne ~\emptyset$.

Proof

Suppose, $\varGamma$ is $\mathcal{P}(1)$-consistent and let $M=\{c_1,\dots , c_k\}$ be a $\varGamma$-satisfying model in $\mathcal{P}(1)$. Since M satisfies every statement $\varphi \in \varGamma$, $c(\alpha _\varphi ) \le c(\beta _\varphi )$ for every $c \in M$, i.e., $c \in \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi$. Furthermore, for every strict statement $\varphi ' \in \varGamma \cap \mathcal{L}_{<}^\mathcal{A}$ there exists a $c \in M$ such that $c(\alpha _{\varphi '}) < c(\beta _{\varphi '})$, i.e., $c \in C_{\varphi '} \cap \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi \ne \emptyset$. Conversely, suppose $C_{\varphi '} \cap \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi \ne \emptyset$ for all $\varphi ' \in \varGamma \cap \mathcal{L}_{<}^\mathcal{A}$. Consider the set $M=\bigcup _{\varphi ' \in \varGamma \cap \mathcal{L}_{<}^\mathcal{A}} (C_{\varphi '} \cap \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi )$. For every evaluation $c \in M$ and every statement $\varphi \in \varGamma$, $c \in \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi$, i.e., $c(\alpha _\varphi ) \le c(\beta _\varphi )$. Furthermore, for every strict statement $\varphi ' \in \varGamma \cap \mathcal{L}_{<}^\mathcal{A}$ there exists a $c \in M$ such that $c \in C_{\varphi '} \cap \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi$, i.e., $c(\alpha _{\varphi '}) < c(\beta _{\varphi '})$. Thus M is a Pareto model in $\mathcal{P}(1)$ that satisfies $\varGamma$, i.e., $\varGamma$ is $\mathcal{P}(1)$-consistent.    $\square$

Following Proposition 2, we formulate the algorithm Singleton-Pareto-Con- sistency that solves $\mathcal{P}(1)$-PCP in polynomial time $O(|\varGamma ||\mathcal{C}|)$.

We can prove criteria for strict and non-strict Pareto inferences based on $\mathcal{P}(1)$ models by utilising the following lemma.

Lemma 1

Let $\varGamma \subseteq \mathcal{L}^\mathcal{A}$ be a set of $\mathcal{P}(1)$-consistent preference statements over preference structure $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$. For every evaluation $c \in \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi$ there exists a $\varGamma$-satisfying Pareto model in $\mathcal{P}(1)$ that contains c. Furthermore, for every $\varGamma$-satisfying Pareto model M in $\mathcal{P}(1)$, $M \subseteq \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi$.

Proof

Let M be a $\varGamma$-satisfying Pareto model in $\mathcal{P}(1)$ that does not contain some $c \in \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi$. Since $c(\alpha _\varphi ) \le c(\beta _\varphi )$ for all $\varphi \in \varGamma$, $M \cup \{c\}$ is a $\varGamma$-satisfying Pareto model in $\mathcal{P}(1)$. Thus, for every evaluation $c \in \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi$ there exists a $\varGamma$-satisfying Pareto model in $\mathcal{P}(1)$ that contains c. Furthermore, for every evaluation $c'$ in M and every $\varphi \in \varGamma$, $c'(\alpha _\varphi ) \le c'(\beta _\varphi )$, i.e., $c \in C_{\alpha _\varphi \le \beta _\varphi }$. Thus, $M \subseteq \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi$ for every $\varGamma$-satisfying Pareto model M in $\mathcal{P}(1)$.    $\square$

Proposition 3

Let $\varGamma \subseteq \mathcal{L}^\mathcal{A}$ be a set of $\mathcal{P}_{\mathcal{C}}(1)$-consistent preference statements over preference structure $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$. We can deduce a preference statement $\alpha \le \beta$ from $\varGamma$ ($\varGamma \vDash _{\mathcal{P}_{\mathcal{C}}(1)} \alpha \le \beta$) if and only if all evaluation functions $c \in \mathcal{C}$ that satisfy $\varGamma ^{(\le )}$ also satisfy $c(\alpha ) \le c(\beta )$, i.e., $\bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi \subseteq C_{\alpha \le \beta }$. Also, $\varGamma \vDash _{\mathcal{P}_{\mathcal{C}}(1)} \alpha < \beta$ if and only if $\bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi \subseteq C_{\alpha \le \beta }$ and $\varGamma$ is $\mathcal{P}_{C_{\alpha = \beta }}(1)$-inconsistent for the set $\mathcal{P}_{C_{\alpha = \beta }}(1)$ of $\mathcal{P}(1)$ models on evaluations $C_{\alpha = \beta }$, i.e., no $\varGamma$-satisfying model satisfies $\alpha \equiv \beta$.

Proof

Consider the case of non-strict inference. For every evaluation c involved in a $\varGamma$-satisfying Pareto model in $\mathcal{P}_{\mathcal{C}}(1)$, $c(\alpha ) \le c(\beta )$. By Lemma 1, the set of evaluations involved in a $\varGamma$-satisfying Pareto model in $\mathcal{P}_{\mathcal{C}}(1)$ is $\bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi$. Thus, $\varGamma \vDash _{\mathcal{P}_{\mathcal{C}}(1)} \alpha \le \beta$ is equivalent to $c \in C_{\alpha \le \beta }$ for all $c \in \bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi$, i.e., $\bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi \subseteq C_{\alpha \le \beta }$.

Now, consider the case of strict inference. For every evaluation c involved in a $\varGamma$-satisfying Pareto model in $\mathcal{P}_{\mathcal{C}}(1)$, $c(\alpha ) \le c(\beta )$, and there exists no $\varGamma$-satisfying Pareto model M such that $M \vDash _{\mathcal{P}_{\mathcal{C}}(1)} \alpha \equiv \beta$. Thus, $\varGamma \vDash _{\mathcal{P}_{\mathcal{C}}(1)} \alpha < \beta$ is equivalent to $\bigcap _{\varphi \in \varGamma ^{(\le )}} C_\varphi \subseteq C_{\alpha \le \beta }$ and there exists no $\varGamma$-satisfying Pareto model $M \in \mathcal{P}_{\mathcal{C}}(1)$ with $M \subseteq C_{\alpha = \beta }$, i.e., $\varGamma$ is $\mathcal{P}_{C_{\alpha = \beta }}(1)$-inconsistent for the set $\mathcal{P}_{C_{\alpha = \beta }}(1)$ of $\mathcal{P}(1)$ models on evaluations $C_{\alpha = \beta }$.    $\square$

Following Proposition 3 and using the algorithm Singleton-Pareto-Consistency we formulate the algorithm Singleton-Pareto-Deduction that solves $\mathcal{P}_{\mathcal{C}}(1)$-PDP in polynomial time $O(|\varGamma ||\mathcal{C}|)$.

3.2 Pareto Inference

In this section, we want to find characterisations for Pareto inference in general by using set relations similar to those in the previous section. We define the set $\mathcal{C}_{\alpha \le \beta }=\{B \subseteq ~\mathcal{C}\mid \bigoplus _{c\in B} c(\alpha ) \le \bigoplus _{c\in B} c(\beta )\}$ of sets of evaluations that satisfy $\alpha \le \beta$. Similarly, $\mathcal{C}_{\alpha< \beta }=\{B \subseteq ~\mathcal{C}\mid \bigoplus _{c\in B} c(\alpha ) < \bigoplus _{c\in B} c(\beta )\}$ and $\mathcal{C}_{\alpha = \beta }=\{B \subseteq ~\mathcal{C}\mid \bigoplus _{c\in B} c(\alpha ) = \bigoplus _{c\in B} c(\beta )\}$.

As mentioned previous section before Proposition 2, a set $\varGamma \subseteq \mathcal{L}_{\le }^\mathcal{A}$ is always $\mathcal{P}(1)$-consistent and thus $\mathcal{P}$-consistent. We can prove the following characterisation of $\mathcal{P}$-consistency.

Proposition 4

Let $\varGamma \subseteq \mathcal{L}^\mathcal{A}$. $\varGamma$ is $\mathcal{P}$-consistent if and only if $\bigcap _{\varphi \in \varGamma } \mathcal{C}_\varphi \ne \emptyset$.

Proof

Suppose, $\bigcap _{\varphi \in \varGamma } \mathcal{C}_\varphi \ne \emptyset$. Then any set in $\bigcap _{\varphi \in \varGamma } \mathcal{C}_\varphi$ is a $\varGamma$-satisfying Pareto model. Now suppose that $\varGamma$ is $\mathcal{P}$-consistent, i.e., there exists a $\varGamma$-satisfying Pareto model $M = \{C_1, \dots , C_r\}$. For every set $C_i \in M$ and every $\varphi \in \varGamma$, $\bigoplus _{c \in C_i} c(\alpha _\varphi ) \le \bigoplus _{c \in C_i} c(\beta _\varphi )$, and for all $\varphi \in \varGamma \cap \mathcal{L}_{<}^\mathcal{A}$ there exists $C_j \in M$ with $\bigoplus _{c \in C_j} c(\alpha _\varphi ) < \bigoplus _{c \in C_j} c(\beta _\varphi )$. Let $C' = \bigcup _{i = 1, \dots , r} C_i$. By strict monotonicity of $\oplus$, $\bigoplus _{c \in C'} c(\alpha _\varphi ) \le \bigoplus _{c \in C'} c(\beta _\varphi )$ for $\varphi \in \varGamma ^{(\le )}$, and $\bigoplus _{c \in C'} c(\alpha _\varphi ) < \bigoplus _{c \in C'} c(\beta _\varphi )$ for all $\varphi \in \varGamma \cup \mathcal{L}_{<}^\mathcal{A}$. Thus $C' \in \bigcap _{\varphi \in \varGamma } \mathcal{C}_\varphi \ne \emptyset$.    $\square$

Remember, that $\mathcal{P}^s = \{ \{C\} \in \mathcal{P}_{\mathcal{C}} \mid C \subset \mathcal{C}\}$ contains all Pareto models that consist of only a single set. The proof of Proposition 4 directly implies the following equivalence.

Corollary 1

Let $\varGamma \subseteq \mathcal{L}^\mathcal{A}$. $\varGamma$ is $\mathcal{P}$-consistent if and only if $\varGamma$ is $\mathcal{P}^s$-consistent.

Consider the relation of $\mathcal{P}$ and $\mathcal{P}^s$ for deduction. $\varGamma \vDash _{\mathcal{P}} \varphi$ implies $\varGamma \vDash _{\mathcal{P}^s} \varphi$ because $\mathcal{P}^s \subseteq \mathcal{P}$. However, Example 3 shows the contrary is not true.

To find characterisations for preference deduction for $\mathcal{P}_\mathcal{C}$, for a given set $B\subseteq \mathcal{C}$, define $\varGamma _{< B}$ to be the set of statements in $\varGamma$ that are strictly satisfied by evaluations $B \subseteq \mathcal{C}$, i.e., $\varGamma _{< B}=\{ \varphi \in ~\varGamma \mid \bigoplus _{c \in B} c(\alpha _\varphi ) < \bigoplus _{c \in B} c(\beta _\varphi )\}$. Similarly, $\varGamma _{= B}=\{ \varphi \in ~\varGamma \mid \bigoplus _{c \in B} c(\alpha _\varphi ) = \bigoplus _{c \in B} c(\beta _\varphi )\}$. Recall, that the non-strict version of preference statements $\varGamma$ is denoted by $\varGamma ^{(\le )}$. Thus, $\varGamma _{\leftrightarrow B} = (\varGamma \setminus \varGamma _{< B}) \cup \varGamma _{< B}^{(\le )}$ replaces the preference statements in $\varGamma$ that are strictly satisfied by B with their non-strict versions.

The following two propositions give characterisations for deduction of non-strict statements and strict statements, respectively. Both propositions can be proven by technical constructions.

Proposition 5

Let $\varGamma \subseteq \mathcal{L}^\mathcal{A}$ be a $\mathcal{P}$-consistent set of preference statements and let $\alpha \le \beta \notin \varGamma$ be a non-strict statement. $\varGamma \not \vDash _{\mathcal{P}_\mathcal{C}} \alpha \le \beta$ if and only if there exists a set $B \in \bigcap _{\psi \in \varGamma ^{(\le )}} \mathcal{C}_\psi \cap \mathcal{C}_{\alpha > \beta }$ such that $\varGamma _{\leftrightarrow B}$ is $\mathcal{P}_{\mathcal{C}\setminus B}$-consistent, i.e., the ($\alpha \le \beta$)-opposing set B can be extended to a $\varGamma$-satisfying Pareto model.

Proposition 6

Let $\varGamma \subseteq \mathcal{L}^\mathcal{A}$ and let $\alpha < \beta \notin \varGamma$ be a strict statement. $\varGamma \not \vDash _{\mathcal{P}} \alpha < \beta$ if and only if $\varGamma \not \vDash _{\mathcal{P}} \alpha \le \beta$ or $\bigcap _{\psi \in \varGamma } \mathcal{C}_\psi \cap \mathcal{C}_{\alpha = \beta } \ne \emptyset$.

Note, that the characterisation for deduction and consistency can be realised as algorithms for $\mathcal{P}$-PCP and $\mathcal{P}$-PDP, but cannot be implemented in polynomial time. In fact, we can prove the following complexity results for PCP and PDP.

Theorem 1

The $\mathcal{P}$-Preference Consistency Problem is NP-complete.

Proof

For any given Pareto model we can check in polynomial time if it satisfies all given preference statements. Thus, PCP is in the class NP. We prove NP-completeness by a reduction from SAT. Let $\mathcal{B}=K_1, \dots , K_m$ be a set of clauses in conjunctive normal form with clauses $K_i = (l_{i,1} \vee \dots \vee l_{i,k_i})$ for $i = 1, \dots , m$, where the literals $l_{i,j}$ are chosen from the set of Boolean variables $\mathcal{X}=\{x_1, \dots , x_n\}$. In the following, we construct an instance of PCP from the SAT instance $\mathcal{B}$. Let $s \in \mathbb {Q}$ with $s > \textit{e}$ and $\oplus$ be an associative, commutative and strictly monotonic operation with neutral element $\textit{e}$. For every Boolean variable $x_j$, we construct three evaluations: $p_j$ (corresponding to $x_j = 1$), $n_j$ (corresponding to $x_j = \textit{e}$) and the auxiliary evaluation $h_j$. The set of evaluations $\mathcal{C}= \{p_j, n_j, h_j \mid j=1, \dots , n\}$ has cardinality polynomial in n. We define the function Q that maps the literals involved in $\mathcal{B}$ to the evaluation functions $\mathcal{C}$ by $Q(x_j) = p_j$ and $Q(\lnot x_j)=n_j$. Let the set of alternatives be $\mathcal{A}= \{\alpha _i, \beta _i \mid i=1, \dots , m\} \cup \{\gamma _j, \delta _j, \epsilon _j, \zeta _j, \eta _j, \theta _j \mid j=1, \dots , n\}$. Then the cardinality of $\mathcal{A}$ is polynomial in the given sizes m and n. Let the values of the evaluation functions on the alternatives be given by the following tables. For $i=1, \dots , m$ and $j=1, \dots , n$,

	$\alpha _i$	<	$\beta _i$
Q(l) with $l \in K_i$	e		s
others	e		e

	$\epsilon _j$	<	$\zeta _j$	$\eta _j$	$\le$	$\theta _j$
$p_j$	e		s	s		e
$n_j$	e		s	s		e
$h_j$	e		e	e		s
others	e		e	e		e

The set $\varGamma = \{\alpha _i<~\beta _i \mid i = 1, \dots , m\} \cup \{\epsilon _j < \zeta _j, \eta _j \le \theta _j \mid j=1,\dots ,n\}$ of preference statements on $\mathcal{A}$ is polynomial in the given sizes m and n.

In the following we prove that there exists a $\varGamma$-satisfying Pareto model with evaluations in $\mathcal{C}$ if and only if there exists a satisfying truth assignment for $\mathcal{B}$. Because of the equivalence between $\mathcal{P}$- and $\mathcal{P}^s$-consistency stated in Corollary 1, we can restrict the following considerations to Pareto models in $\mathcal{P}^s$.

Suppose there exists a $\varGamma$-satisfying Pareto model $M=\{C\}$ with $C \subseteq \mathcal{C}$. In the following, we prove that for each $j=1, \dots , n$, the set C contains either $p_j$ or $n_j$ and not both. Suppose for some $j \in \{1, \dots , n\}$, $p_j \notin C$ and $n_j \notin C$. Then, the $\oplus$-combination of evaluations in C evaluates to $\textit{e}$ for both $\epsilon _j$ and $\zeta _j$. This contradicts $M \vDash \epsilon _j < \zeta _j$. Thus, for all $j=1, \dots , n$, either $p_j \in C$ or $n_j \in C$. Now suppose, for some $j \in \{1, \dots , n\}$, that $h_j \notin C$. Then, C evaluates to be $\ge s$ on $\eta _j$ and to be $\textit{e}$ on $\theta _j$. This contradicts $M \vDash \eta _j \le \theta _j$. Thus, $h_j \in C$ for all $j=1, \dots , n$. Suppose, for some $j \in \{1, \dots , n\}$, both $p_j \in C$ and $n_j \in C$. Because $h_j \in C$, C evaluates to be $s \oplus s (>s)$ on $\eta _j$ and to be s on $\theta _j$. Again, this contradicts $M \vDash \eta _j \le \theta _j$. Hence, for each $j=1, \dots , n$, M contains either $p_j \in C$ or $n_j \in C$ but not both.

Thus, for a $\varGamma$-satisfying model $M \in \mathcal{P}^s$ the assignment A, with $A(l_{i,k})=1$ if and only if $Q(l_{i,k}) \in M$, is well defined. Furthermore, we can show that M contains at least one evaluation Q(l) with $l \in K_i$ for every clause with $i=1, \dots , m$. Suppose otherwise. Then, $\bigoplus _{c \in C} c(\alpha _i) = \textit{e}\oplus \dots \oplus \textit{e}= \bigoplus _{c \in C} c(\beta _i)$. This is a contradiction to $M \vDash \alpha _i < \beta _i$. Thus, A is a satisfying truth assignment of the SAT instance $\mathcal{B}$.

Conversely, let A be a satisfying truth assignment of the Boolean formula $\mathcal{B}$. Consider the Pareto model $M=\{C\}$ with $h_j \in C$, and $p_j \in C$ if and only if $A(x_j) = 1$, and $n_j \in C$ if and only if $A(x_j) = 0$. We show $M \vDash _{\mathcal{P}} \varGamma$:

• $\alpha _i <_{C} \beta _i$: Since A satisfies $\mathcal{B}$, there exists $l \in \{l_{i,1}, \dots , l_{i,k_i}\}$ for every clause $K_i$ with $A(l)=1$. Thus, $Q(l) \in C$ and $\bigoplus _{c \in C} c(\alpha _i) = \textit{e}< s \le \bigoplus _{c \in C} c(\beta _i)$.

• $\epsilon _j <_{C} \zeta _j$: Every variable $x_j$ is assigned to be true or false. Thus either $p_j \in C$ or $n_j \in C$ (not both), and $\bigoplus _{c \in C} c(\epsilon _j) = \textit{e}< s = \bigoplus _{c \in C} c(\delta _j)$.

• $\eta _j \le _{C} \theta _j$: Either $p_j \in C$ or $n_j \in C$ but not both, and $h_j \in C$. Thus, $\bigoplus _{c \in C} c(\eta _j) = s = \bigoplus _{c \in C} c(\theta _j)$.

Hence, we have shown, that there exists a satisfying truth assignment for $\mathcal{B}$ if and only if there exists a $\varGamma$-satisfying Pareto model in $\mathcal{P}_\mathcal{C}^s$, which is if and only if there exists a $\varGamma$-satisfying Pareto model in $\mathcal{P}_\mathcal{C}$.    $\square$

Theorem 2

The $\mathcal{P}$-Preference Deduction Problem is coNP-complete.

Proof

For any given Pareto model we can check in polynomial time if it satisfies all given preference statements $\varGamma$ and does not satisfy $\varphi$. Thus we can verify in polynomial time that $\varGamma \not \vDash \varphi$ for some instance of PDP. Hence, PDP is in the class coNP. We prove coNP-completeness by a reduction from SAT. For a set of clauses $\mathcal{B}=K_1, \dots , K_m$, consider the preference structure and statements as constructed in the proof of Theorem 1. In the following, we will define a preference statement $\varphi : \rho < \sigma$ such that no $\varGamma$-satisfying model satisfies $\varphi$. Hence, $\varGamma \vDash _{\mathcal{P}} \varphi$ if and only if $\varGamma$ is $\mathcal{P}$-inconsistent, which by the previous proof is if and only if $\mathcal{B}$ is not satisfiable. For every evaluation function $c \in \mathcal{C}$ let $c(\rho )=c(\sigma )=\textit{e}$. Then every Pareto model M satisfies $M \vDash \rho =\sigma$, because every set in M evaluates to $\textit{e}$ on both $\rho$ and $\sigma$. Thus, $M \not \vDash \rho <\sigma$.    $\square$

4 Relation with Other Preference Models

In this section we compare the cautiousness of inference based on Pareto models with inference based on other well-known preference models. Here, we compare the sets of undominated alternatives for the order relations induced by the different preference models. In applications like recommender systems or multi-objective optimisation it can be very helpful to use inferences that keep the number of undominated alternatives small, so that the user is not overwhelmed when she is presented with them. First, we define HCLP models, lexicographic models and weighted average models as in [4, 13].

Definition 4

(HCLP Model). For a preference structure $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$, an HCLP model H is an ordered partition of a subset of evaluations. More specifically, $H = (C_1, \dots , C_r)$ with $r \ge 0$ for pairwise disjoint sets $C_i$ such that $\bigcup _{i = 1, \dots , r} C_i \subseteq ~\mathcal{C}$.

An HCLP model forms a hierarchy on a subset of evaluation functions. Let $\textit{H}CLP$ denote the set of all HCLP models. Each HCLP model $H=(C_1, \dots , C_r)$ induces an order relation on the set of alternatives $\mathcal{A}$ by comparing the combination of evaluations in the sets (by operator $\oplus$) in a lexicographic manner.

• $\alpha <_{H} \beta$ if there exists $j \in \{1, \dots , r\}$ such that $\bigoplus _{c \in C_i} c(\alpha ) = \bigoplus _{c \in C_i} c(\beta )$ for all $1 \le i < j$ and $\bigoplus _{c \in C_j} c(\alpha ) <\bigoplus _{c \in C_j} c(\beta )$. (Written $H \vDash _{\textit{H}CLP} \alpha < \beta$ .)

• $\alpha \le _{H} \beta$ if $\bigoplus _{c \in C_i} c(\alpha ) = \bigoplus _{c \in C_i} c(\beta )$ for all $1 \le i \le r$; or $\alpha <_{H} \beta$. (Written $H \vDash _{\textit{H}CLP} \alpha \le \beta$ .)

• $\alpha \equiv _{H} \beta$ if $\alpha \le _{H} \beta$ and $\alpha \ge _{H} \beta$. (Written $H \vDash _{\textit{H}CLP}\alpha \equiv ~\beta$ .)

Definition 5

(Simple Lexicographic Model). For a preference structure $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$, a simple lexicographic model or LEX model $L = (c_1, \dots , c_r)$ is an ordered subset of evaluations $\{c_1, \dots , c_r\} \subseteq \mathcal{C}$ with $|\{c_1, \dots , c_r\}| = r \ge 0$.

LEX models form a special case of HCLP models in which sets are restricted to contain only one evaluation. The order relations $\le _{L}$ and $<_{L}$ induced by a LEX model $L = (c_1, \dots , c_r)$ are defined analogously. Let $\textit{L}EX$ denote the set of all simple lexicographic models. Then $\textit{L}EX\subseteq \textit{H}CLP$.

Definition 6

(Weighted Average Model). For a preference structure $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$, a weighted average model or WA model ${\varvec{w}}$ is a normalised weights vector ${\varvec{w}} \in \mathbb {R}^{|\mathcal{C}|}$ such that for each $i \in \{1, \ldots , |\mathcal{C}|\}$, ${\varvec{w}}_i \ge 0$, and $\sum _{i=1}^{|\mathcal{C}|} {\varvec{w}}_i = 1$.

Let $\textit{W}A$ be the set of all weighted average models. Each ${\varvec{w}}\in \mathbb {R}^{|\mathcal{C}|}$ induces an order relation on $\mathcal{A}$ by comparing weighted sums of evaluations $\mathcal{C}=\{c_1, \dots , c_{|\mathcal{C}|}\}$:

• $\alpha \le _{\varvec{w}} \beta$ if $\sum _{i=1}^{|\mathcal{C}|} {\varvec{w}}_i c_i(\alpha ) \le \sum _{i=1}^{|\mathcal{C}|} {\varvec{w}}_i c_i(\beta )$. (Written ${\varvec{w}} \vDash _{\textit{W}A} \alpha \le \beta$ .)

• $\alpha <_{\varvec{w}} \beta$ if $\sum _{i=1}^{|\mathcal{C}|} {\varvec{w}}_i c_i(\alpha ) < \sum _{i=1}^{|\mathcal{C}|} {\varvec{w}}_i c_i(\beta )$. (Written ${\varvec{w}} \vDash _{\textit{W}A} \alpha < \beta$ .)

• $\alpha \equiv _{\varvec{w}} \beta$ if $\sum _{i=1}^{|\mathcal{C}|} {\varvec{w}}_i c_i(\alpha ) = \sum _{i=1}^{|\mathcal{C}|} {\varvec{w}}_i c_i(\beta )$. (Written ${\varvec{w}} \vDash _{\textit{W}A} \alpha \equiv \beta$ .)

For a *-consistent set of strict and non-strict preference statements $\varGamma \subseteq \mathcal{L}^\mathcal{A}$ with $* = \textit{L}EX, \textit{W}A, \textit{H}CLP, \mathcal{P}$ or $\mathcal{P}(1)$, we define order relations $<_\varGamma ^{*}$ and $\ll _\varGamma ^{*}$ on the set of alternatives $\mathcal{A}$ in the following way. For $\alpha , \beta \in \mathcal{A}$, $\alpha <_\varGamma ^{*} \beta$ if and only if $\varGamma \vDash _{*} \alpha \le \beta$ and $\varGamma \not \vDash _{*} \beta \le \alpha$. For $\alpha , \beta \in \mathcal{A}$, $\alpha \ll _\varGamma ^{*} \beta$ if and only if $\varGamma \vDash _{*} \alpha < \beta$. For a set $S \subseteq \mathcal{A}$, let Opt($S,\prec$) denote the set of undominated elements in S w.r.t. an irreflexive and acyclic relation $\prec$, i.e., Opt($S,\prec$) is the set of elements $\alpha \in S$ such that for every $\beta \in S$, $\beta \not \prec \alpha$. Then Opt($S,\prec$) represents the alternatives that could be optimal for a user under the assumption that the users preference model is an order relation of the form $\prec$. In [4] the following relations were established between weighted average (WA) and lexicographic (LEX) models. Here, $\not \subseteq$ signifies that the set relation $\subseteq$ dos not necessarily hold for every $S \subseteq \mathcal{A}$ and $\varGamma \subseteq \mathcal{L}^\mathcal{A}$ (but might hold for some). On the other hand $\subseteq$ means that the relation is true for any arbitrary $S \subseteq \mathcal{A}$ and $\varGamma \subseteq \mathcal{L}^\mathcal{A}$.

In the following, we extend these results by:

Note, that the relations Opt($S,<_\varGamma ^*$) $\subseteq$ Opt($S,\ll _\varGamma ^*$)) follow directly from the implication $\varGamma \vDash _* \alpha < \beta$ $\Rightarrow$ $\varGamma \vDash _* \alpha \le \beta$ and $\varGamma \not \vDash _* \beta \le \alpha$, which is true for any $* = \textit{L}EX, \textit{W}A, \textit{H}CLP, \mathcal{P}$ or $\mathcal{P}(1)$. Furthermore, the relations (III) and (IV) follow directly from the inclusions $\mathcal{P}(1) \subseteq \mathcal{P}$ and $\textit{L}EX\subseteq \textit{H}CLP$, respectively. The relations marked with (I) are a consequence of Proposition 7.

Proposition 7

Let $\varGamma \subseteq \mathcal{L}^\mathcal{A}$ and $\varphi \in \mathcal{L}^\mathcal{A}$. If $\varGamma \vDash _{\textit{H}CLP} \varphi$, then $\varGamma \vDash _{\mathcal{P}} \varphi$.

Proof

Assume that $\varGamma \vDash _{\textit{H}CLP} \varphi$. Consider a model $M = \{C_1, \dots , C_m\} \in \mathcal{P}$ with $M \vDash _{\mathcal{P}} \varGamma$; we will show that $M \vDash _{\mathcal{P}} \varphi$, thus proving that $\varGamma \vDash _{\mathcal{P}} \varphi$. For any permutation $\pi$ on the set $\{1, \dots , m\}$, $H_\pi = (C_{\pi (1)}, \dots , C_{\pi (m)})$ is an HCLP model with $H_\pi \vDash _{\textit{H}CLP} \gamma$ for all $\gamma \in \varGamma$. Since $\varGamma \vDash _{\textit{H}CLP} \varphi$, $H_\pi \vDash _{\textit{H}CLP} \varphi$ for all permutations $\pi$. Also, in a $\varphi$-satisfying HCLP model, the first level C set must satisfy $\bigoplus _{c \in C} c(\alpha _\varphi ) \le \bigoplus _{c \in C} c(\beta _\varphi )$. Thus, for every set $C \in M$, $\bigoplus _{c \in C} c(\alpha _\varphi ) \le \bigoplus _{c \in C} c(\beta _\varphi )$. In case $\varphi$ is a strict statement, there exists a set $C \in M$ such that $\bigoplus _{c \in C} c(\alpha _\varphi ) < \bigoplus _{c \in C} c(\beta _\varphi )$. This implies that $M \vDash _{\mathcal{P}} \varphi$. As we considered an arbitrary $\varGamma$- satisfying Pareto model M, we have $\varGamma \vDash _{\mathcal{P}} \varphi$.    $\square$

Analogously, one can prove Proposition 8 which implies relations (V).

Proposition 8

Let $\varGamma \subseteq \mathcal{L}^\mathcal{A}$ and $\varphi \in \mathcal{L}^\mathcal{A}$. If $\varGamma \vDash _{\textit{L}EX} \varphi$, then $\varGamma \vDash _{\mathcal{P}(1)} \varphi$.

The relations (II) and (VI) are demonstrated in the following example.

	$\alpha$	$\beta$	$\gamma$
$c_1$	2	1	1
$c_2$	0	2	3

Example 5

Consider the preference structure $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$ with operator $\oplus$ as the standard addition on $\mathbb {Q}^{\ge 0}$. The table on the right gives the values of the evaluation functions $\mathcal{C}= \{c_1,c_2\}$ on alternatives $\mathcal{A}= \{\alpha ,\beta ,\gamma \}$. Let $S = \mathcal{A}$ and $\varGamma = \{\beta < \alpha \}$. The $\varGamma$-satisfying HCLP models are $(\{c_1\})$ and $(\{c_1\},\{c_2\})$. The only $\varGamma$-satisfying Pareto model is $\{\{c_1\}\}$. Furthermore, $(\{c_1\}) \vDash _{\textit{H}CLP} \beta \equiv \gamma$ and $\{\{c_1\}\} \vDash _{\mathcal{P}} \beta \equiv \gamma$. Also, $(\{c_1\},\{c_2\}) \vDash _{\textit{H}CLP} \beta \le \gamma$ and $(\{c_1\},\{c_2\}) \not \vDash _{\textit{H}CLP} \beta \ge \gamma$. Thus, $\varGamma \vDash _{\mathcal{P}} \beta \le \gamma , \beta \ge \gamma$, and $\varGamma \vDash _{\textit{H}CLP} \beta \le \gamma$ and $\varGamma \not \vDash _{\textit{H}CLP} \beta \ge \gamma$. Then Opt($S,<_\varGamma ^{\mathcal{P}}$) $= \{\beta , \gamma \} \not \subseteq \{\beta \} =$ Opt($S,<_\varGamma ^{\textit{H}CLP}$). Note, that the models $(\{c_1\})$ and $(\{c_1\},\{c_2\})$ are in particular LEX models and $\{\{c_1\}\}$ is in $\mathcal{P}(1)$. Thus, Opt($S,<_\varGamma ^{\mathcal{P}(1)}$) $\not \subseteq$ Opt($S,<_\varGamma ^{\textit{L}EX}$) holds.

The relations in (VII) are demonstrated by the following example.

	$\alpha$	$\beta$	$\gamma$	$\delta$
$c_1$	2	0	1	2
$c_2$	1	2	0	3

Example 6

Consider the preference structure $\langle \mathcal{A}, \mathcal{C}, \oplus \rangle$ with operator $\oplus$ as the standard addition on $\mathbb {Q}^{\ge 0}$. The table on the right gives the values of the evaluation functions $\mathcal{C}= \{c_1,c_2\}$ on alternatives $\mathcal{A}= \{\alpha ,\beta ,\gamma , \delta \}$. Let $S = \mathcal{A}$ and $\varGamma = \{\beta \le \alpha , \gamma \le \beta \}$. The only $\varGamma$-satisfying LEX model is () and the only $\varGamma$-satisfying $\mathcal{P}(1)$ model is $\{\}$. The $\varGamma$-satisfying HCLP models are $(\{c_1,c_2\})$ and () and the $\varGamma$-satisfying $\mathcal{P}$ models are $\{\{c_1,c_2\}\}$ and $\{\}$. The empty model entails $\alpha \equiv \beta \equiv \gamma \equiv \delta$ for LEX, HCLP, $\mathcal{P}(1)$ and $\mathcal{P}$. For the HCLP model $H=(\{c_1,c_2\})$, $\gamma<_H \beta<_H \alpha <_H \delta$. Similarly, for the Pareto model $M=\{\{c_1,c_2\}\} \in \mathcal{P}$, $\gamma<_M \beta<_M \alpha <_M \delta$. Thus, Opt($S,<_\varGamma ^{\mathcal{P}(1)}$) $= \{\alpha , \beta ,\gamma , \delta \} \not \subseteq \{\gamma \} =$ Opt($S,<_\varGamma ^{\mathcal{P}}$). Also, Opt($S,<_\varGamma ^{\textit{L}EX}$) $=$ $\{\alpha , \beta ,\gamma , \delta \} \not \subseteq \{\gamma \} =$ Opt($S,<_\varGamma ^{\textit{H}CLP}$).

5 Conclusion

We investigated the Preference Deduction Problem and the Preference Consistency Problem based on Pareto models. Here, we developed characterisations for consistency and deduction (strict and non-strict) which allow one to design algorithms for PCP and PDP. However, PCP and PDP are NP-complete and coNP-complete, respectively. In the special case of singleton models, the characterisations of consistency and deduction lead to polynomial algorithms that solve PCP and PDP in $O(|\varGamma ||\mathcal{C}|)$ for given preferences $\varGamma$ and evaluations $\mathcal{C}$. A comparison shows that Pareto models lead to a less cautious form of inference considering the relations $\ll ^*_\varGamma$, which is often desirable. However, the conjunctive definition of Pareto satisfaction can lead to more sets of preference statements being inconsistent, in comparison with other semantics we considered. In future work, we plan to investigate the cautiousness of inference based on Pareto models under relation $<^*_\varGamma$ experimentally. Here, it is essential to implement good algorithms to solve PDP (and PCP) based on Pareto models in $\mathcal{P}$. Furthermore, we plan to extend our theory to more complex preference languages.