Computation and Complexity of Preference Inference Based on Hierarchical Models

1 Introduction

There are increasing opportunities for decision making/support systems to take into account the preferences of individual users, with the user preferences being elicited or observed from the user's behaviour. However, users tend to have limited patience for preference elicitation, so such a system will tend to have a very incomplete picture of the user preferences. Preference Inference involves inferring additional user preferences from elicited or observed preferences, based on assumptions regarding the form of the user's preference relation. More specifically, given a set of input preferences Γ, and a set of preference models M (considered as candidates for the user's preference model), we infer a preference statement ϕ if every model in M that satisfies Γ also satisfies ϕ. Preference Inference can take many forms, depending on the choice ofM, and on the choices of language(s) for the input and inferred statements. For instance, if we just assume that the user model is a total order (or total pre-order), we can set M as the set of total [pre-]orders over a set of alternatives. This leads to a relatively cautious form of inference (based on transitive closure), including, for instance, the dominance relation for CP-nets and some related systems, e.g., [Boutilier et al., 2004; Brafman et al., 2006; Bouveret et al., 2009; Bienvenu et al., 2010].

Often it can be valuable to obtain a much less cautious form of inference, for example, in order to have some help in deciding which options to show to the user next in a recommender system [Bridge and Ricci, 2007; Trabelsi et al., 2011]. This includes assuming that the user's preference relation in a multi-objective context is based on a simple weighted sum of objectives (as in a simple form of a Multi-Attribute Utility Theory model [Figueira et al., 2005]); this kind of preference inference is considered in [Bridge and Ricci, 2007; Marinescu et al., 2013]; or alternatively, assuming different lexicographic forms for the preference models as in [Wilson, 2009; Trabelsi et al., 2011; Wilson, 2014]. Note that all these systems involve reasoning about what holds in a set of preference models. This contrasts with work in preference learning [F¨urnkranz and (eds.), 2010; Dombi et al., 2007; Flach and Matsubara, 2007; Br¨auning and H¨ullermeier, 2012; Booth et al., 2010] that typically learns a single model.

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 (HCLP) model [Wilson and Borning, 1993]. 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.

We consider the case where the input preference statements are of a simple form that one alternative is preferred to another alternative, where we allow the expression of both strict and non-strict preferences (in contrast to most related preference logics, such as [Wilson, 2011; Boutilier et al., 2004; Wilson, 2009; 2014]). This form of preference is natural in many contexts, including for conversational recommender systems [Bridge and Ricci, 2007]. The preference inference problem then consists of determining whether a preference statement can be inferred from a set of input preferences, i.e., if every model (of the assumed form) satisfying the inputs also satisfies the query. We show that this problem is coNPcomplete, even if one restricts the cardinality of the equalimportance 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.

Section 2 defines our simple preference logic based on hierarchical models, along with some associated preference inference problems. Section 3 shows that in general the preference inference problem is coNP-complete. Section 4 considers the case where the importance ordering on criteria is a total order, and gives a polynomial algorithm for consistency. Section 5 concludes.

Proofs are included in a longer version of the paper available online [Wilson et al., 2015].

2 A Preference Logic Based on Hierarchical Models

We consider preference models, based on an importance ordering of criteria, that is basically lexicographic, but involving a combination of criteria which are at the same level in the importance ordering. We call these "HCLP models", because models of a similar kind appear in the HCLP system [Wilson and Borning, 1993] (though we have abstracted away some details from the latter system).

HCLP structures: Define an HCLP structure to be a tuple S = 〈A,⊕, C〉, where A (the set of alternatives) is a finite set; ⊕ is an associative, commutative and monotonic operation (x ⊕ y ≤ z ⊕ y if x ≤ z) on the non-negative rational numbers Q+, with identity element 0; and C (known as the set of (A-)evaluations) is a set of functions from A to Q+. We also assume that operation ⊕ can be computed in linear time (which holds for natural definitions of ⊕, including addition and max). The evaluations in C may be considered as representing criteria or objectives under which the alternatives are evaluated. For c ∈ C and α ∈ A, if c(α) = 0 then α fully satisfies the objective corresponding to c; more generally, the smaller the value of c(α), the better α satisfies the c-objective. With each subset C of C we define ordering ≼⊕C on A by α ≼⊕C β if and only if ⊕c∈C c(α) ≤ ⊕c∈C c(β). Relation ≼⊕C represents how well the alternatives satisfy the multi-set of evaluations C if the latter are considered equally important. ≼⊕C is a total pre-order (a weak order, i.e., a transitive and complete binary relation). If α ≼⊕C β, we might also write

β ≽⊕C α. We write ≡⊕C for the associated equivalence relation on A, given by α ≡⊕C β ⇐⇒ α ≼⊕C β and β ≼⊕C α. We write ≺⊕C for the associated strict weak ordering, defined by α ≺⊕C β ⇐⇒ α ≼⊕C β and β ̸≼⊕C α. Thus, α ≡⊕C β if and only if ⊕c∈C c(α) = ⊕c∈C c(β); and α ≺⊕C β if and only if ⊕c∈C c(α) < ⊕c∈C c(β).

HCLP models: An HCLP model H based on 〈A,⊕, C〉 is defined to be an ordered partition (C1, . . . , Ck) of a (possibly empty) subset σ(H) of C. The sets Ci are called the levels of H, which are thus non-empty, disjoint and have union σ(H). If c ∈ Ci and c′ ∈ Cj, and i < j, then we say that c appears before c′ (and c′ appears after c) in H. Associated with H is an ordering relation ≼⊕H on A given by:

• α ≼⊕H β if and only if either:
• (I) for all i = 1, . . . , k, α ≡⊕Ci β; or
• (II) there exists some i ∈ {1, . . . , k} such that (i) α ≺⊕Ci β and (ii) for all j with 1 ≤ j < i, α ≡⊕Cj β.

Relation ≼⊕H is a kind of lexicographic order on A, where the multi-set Ci of evaluations at the same level are first combined into a single evaluation. ≼⊕H is a weak order on A. We write ≡⊕H for the associated equivalence relation (corresponding with condition (I)), and ≺⊕H for the associated strict weak order (corresponding with condition (II)), so that ≼⊕H is the disjoint union of ≺⊕H and ≡⊕H . If σ(H) = ∅ then then the first condition for α ≼⊕H β holds vacuously (since k = 0), so we have α ≼⊕H β for all α, β ∈ A, and ≺⊕H is the empty relation.

Preference Language Inputs: Let A be a set of alternatives. We define LA≤ to be the set of statements of the form α ≤ β, for α, β ∈ A (the non-strict statements), we write LA< for the set of statements of the form α < β, for α, β ∈ A (the strict statements), and let LA = LA≤ ∪ LA< . If ϕ is the preference statement α ≤ β then ¬ϕ is defined to be the preference statement β < α. If ϕ is the preference statement α < β then ¬ϕ is defined to be the preference statement β ≤ α.

Satisfaction of preference statements: For HCLP model H over HCLP structure 〈A,⊕, C〉, we say that H satisfies α ≤ β (written H |=⊕ α ≤ β) if α ≼⊕H β holds. Similarly, we say that H satisfies α < β (written H |=⊕ α < β) if α ≺⊕H β. For Γ ⊆ LA, we say that H satisfies Γ (written H |=⊕ Γ) if H satisfies ϕ for all ϕ ∈ Γ.

Preference Inference/Deduction relation: We are interested in different restrictions on the set of models, and the corresponding inference relations. Let Mbe a set of HCLP models over HCLP structure 〈A,⊕, C〉. For Γ ⊆ LA, and ϕ ∈ LA, we say that Γ |=⊕M ϕ, if H satisfies ϕ for every H ∈ M satisfying Γ. Thus, if we elicit some preference statements Γ of a user, and we assume that their preference relation is an HCLP model in M (based on the HCLP structure), then Γ |=⊕M ϕ holds if and only if we can deduce that the user's HCLP model H satisfies ϕ.

Consistency: For set of HCLP models M over HCLP structure 〈A, ⊕, C〉, and set of preference statements Γ ⊆ LA, we say that Γ is (M,⊕)-consistent if there exists H ∈ M such that H |=⊕ Γ; otherwise, we say that Γ is (M,⊕)- inconsistent. In the usual way, because of the existence of a negation operator, deduction can be reduced to checking (in)consistency.

Proposition 1 Γ |=⊕M ϕ if and only if Γ ∪ {¬ϕ} is (M, ⊕)- inconsistent.

Let t be some number in {1, 2, . . . , |C|}. We define C(t) to be the set of all HCLP models (C1, . . . , Ck) based on HCLP structure 〈A,⊕, C〉 such that |Ci| ≤ t, for all i = 1, . . . , k. An element of C(1) thus corresponds to a sequence of singleton sets of evaluations; we identify it with a sequence of evaluations (c1, . . . , ck) in C. Thus, Γ |=⊕C(t) ϕ if and only if H |=⊕ ϕ for all H ∈ C(t) such that H |=⊕ Γ. Note that for t = 1, these definitions do not depend on ⊕ (since there is no combination of evaluations involved), so we may drop any mention of ⊕.

Let ≡ be an equivalence relation on C. We define C(≡) to be the set of all HCLP models (C1, . . . , Ck) such that each Ci is an equivalence class with respect to ≡. It is easy to see that the relation |=⊕C(≡) is the same as the relation |=C′ (1) where C ′ is defined as follows. C ′ is in 1-1 correspondence with the set of ≡-equivalence classes of C. If E is the ≡-equivalence class of C corresponding with c′ ∈ C ′ then, for α ∈ A, c′ (α) is defined to be ⊕c∈E c(α).

For |= either being |=⊕C(t) for some t ∈ {1, 2, . . . , |C|}, or being |=⊕C(≡) for some equivalence relation ≡ on C, we consider the following decision problem.

HCLP-DEDUCTION FOR |=: Given C, Γ and ϕ is it the case that Γ |= ϕ?

In Section 4, we will show that this problem is polynomial for |= being |=⊕C(t) when t = 1. Thus it is polynomial also for |=⊕C(≡) , for any equivalence relation ≡. It is coNP-complete for |= being |=⊕C(t) when t > 1, as shown below in Section 3.

Theorem 1 HCLP-DEDUCTION FOR |=⊕C(t) is polynomial when t = 1, and is coNP-complete for any t > 1, even if we restrict the language to non-strict preference statements. HCLP-DEDUCTION FOR |=⊕C(≡) is polynomial for any equivalence relation ≡.

Example

We consider an example with alternatives A = {α, β, γ}, using ⊕ as + (ordinary addition), and with evaluations C = {c1, c2, c3}, defined as follows.

• c1(α) = 0; c1(β) = 2; c1(γ) = 1;
• c2(α) = 2; c2(β) = 0; c2(γ) = 2;

c3(α) = 1; c3(β) = 0; c3(γ) = 0.

Suppose that the user tells us that they consider α to be at least as good as β. We represent this as the non-strict preference α ≤ β. This eliminates some models; for instance, α ≤ β is not satisfied by model H equalling ({c1, c2}, {c3}), since c1(α) ⊕ c2(α) = 2 = c1(β) ⊕ c2(β), and c3(β) < c3(α), which implies that β ≺⊕H α, and thus H |= β < α and H ̸|= α ≤ β.

Now, α ≤ β does not entail any preference between β and γ, as can be seen by considering the two models ({c1}) and ({c1, c2}), each with just a single level, and both satisfying α ≤ β. Model ({c1, c2}) satisfies β < γ, since c1(β) ⊕ c2(β) = 2 < 3 = c1(γ) ⊕ c2(γ), whereas model ({c1}) satisfies γ < β, since c1(γ) < c1(β). However, it can be shown that α ≤ β |=⊕C(3) α ≤ γ, so we infer that α is nonstrictly preferred to γ.

A strict preference for α over β entails additional inferences, for instance, α < β |=⊕C(3) γ < β. If we restrict the set of models to C(1) (thus assuming that the importance ordering on C is a total order) we get slightly stronger inferences still, obtaining in addition: α < β |=C(1) α < γ.

3 Proving coNP-completeness of HCLP-Deduction for |=⊕C(t) for t > 1

Given an arbitrary 3-SAT instance we will show that we can construct a set Γ and a statement α ≤ β such that the 3SAT instance has a satisfying truth assignment if and only if Γ ̸|=⊕C(t) α ≤ β (see Proposition 2). This then implies that determining if Γ ̸|=⊕C(t) α ≤ β holds is NP-hard.

We have that Γ ̸|=⊕C(t) α ≤ β if and only if there exists an HCLP-model H ∈ C(t) such that H |=⊕ Γ and H ̸|=⊕ α ≤ β. For any given H, checking that H |=⊕ Γ and H ̸|=⊕ α ≤ β can be performed in polynomial time. This implies that determining if Γ |=⊕C(t) α ≤ β holds is coNP-complete.

For simplicity, we describe the construction for the t = 2 case. This construction also works for all t ≥ 2 if 1 ⊕ 1 > 1. We indicate below how the construction is modified for the case when t ≥ 3.

Consider an arbitrary 3-SAT instance based on propositional variables p1, . . . , pr, consisting of clauses Λj, for j = 1, . . . , s. For each propositional variable pi we associate two evaluations q+ i and qi , where qi corresponds with literal ¬pi and q+ i corresponds with literal pi.

The idea behind the construction is as follows: we generate a (polynomial size) set Γ ⊆ LA≤ as the disjoint union of sets Γ1, Γ2 and Γ3. Γ1 is chosen so that if H |=⊕ Γ1 then, for each i = 1, . . . , r, σ(H) cannot contain both q+ i and qi , i.e., q+ i and qi do not both appear in H. (Recall H is an ordered partition of σ(H), so that σ(H) is the subset of C that appears in H.) If H |=⊕ Γ2 and H |=⊕ β < α then σ(H) contains either q+ i or qi . Together, this implies that if H |=⊕ Γ and H ̸|=⊕ α ≤ β then for each propositional variable pi, model H involves either q+ i or qi , but not both. Γ3 is used to make the correspondence with the clauses. For instance, if one of the clauses is p2 ∨ ¬p5 ∨ p6 then any HCLP model H ∈ C(t) of Γ ∪ {β < α} will involve either q+ 2 , q5 , or q+ 6 .

Suppose that H satisfies Γ but not α ≤ β. We can generate a satisfying assignment of the 3-SAT instance, by assigning pi to 1 (TRUE) if and only if q+ i appears in H.

We describe the construction more formally below.

Defining A and C: The set of alternatives A is defined to be: {α, β} ∪ {δi, γi, αi, βi : i = 1, . . . , r} ∪ {θj, τj : j = 1, . . . , s}. We define the set of evaluations C to be {c∗} ∪ {ai, q+ i , qi : i = 1, . . . , r}. Both A and C are of polynomial size.

Satisfying β < α: The evaluations on α and β are defined as follows:

• c∗ (α) = 1, and for all c ∈ C - {c∗}, c(α) = 0.
• For all c ∈ C, c(β) = 0.

It immediately follows that: H |=⊕ β < α ⇐⇒ σ(H) ∋ c∗ .

The construction of Γ1: For each i = 1, . . . , r, we define Γi1 = {δi ≤ γi, γi ≤ δi}, and we let Γ1 = ⋃ri=1 Γi1 . We make use of auxiliary evaluation ai. The values of the evaluations on γi and δi are defined as follows:

• ai(γi) = 1, and for all c ∈ C - {ai} we set c(γi) = 0.
• q+ i (δi) = qi (δi) = 1, and for other c ∈ C, c(δi) = 0.

Thus (ai⊕q+ i )(δi) = ai(δi)⊕q+ i (δi) = 0⊕1 = 1. Similarly, (ai ⊕ qi )(δi) = 1, and (ai ⊕ q+ i )(γi) = (ai ⊕ qi )(γi) = 1 ⊕ 0 = 1.

Lemma 1 H |=⊕ Γi1 if and only if either (i) σ(H) does not contain ai or q+ i or qi , i.e., σ(H)∩{ai, q+ i , qi } = ∅; or (ii) {ai, q+ i } is a level of H, and σ(H) ̸∋ qi ; or (iii) {ai, qi } is a level of H, and σ(H) ̸∋ q+ i . In particular, if H |=⊕ Γi1 then σ(H) does not contain both q+ i and qi .

This holds because if ai appears in H before q+ i and qi then we will have that H ̸|=⊕ γi ≤ δi. If q+ i or qi appear in H before ai then we will have H ̸|=⊕ δi ≤ γi. Also, if e.g., {ai, q+ i } is a level of H and qi appears later in H then we will have H ̸|=⊕ δi ≤ γi.

(For the case when t ≥ 3, we need a slightly more complex construction, involving evaluations aki and alternatives δk i and γ k i for k = 1 . . . , t - 1, with similar definitions as given above.)

The construction of Γ2: For each i = 1, . . . , r, define ϕi to be αi ≤ βi. We let Γ2 = {ϕi : i = 1, . . . , r}. The values of the evaluations on αi and βi are defined as follows. We define c∗ (αi) = 1, and for all c ∈ C - {c∗}, c(αi) = 0. Define q+ i (βi) = qi (βi) = 1, and for all c ∈ C - {q+ i , qi }, c(βi) = 0. The following result easily follows.

Lemma 2 If q+ i or qi appears before (or in the same level as) c∗ inH thenH |=⊕ ϕi. If σ(H) ∋ c∗ andH |=⊕ ϕi then σ(H) ∋ q+ i or σ(H) ∋ qi .

The construction of Γ3: For each i = 1, . . . , r, define Q(pi) = q+ i and Q(¬pi) = qi . This defines the function Q over all literals. Let us write the jth clause as l1 ∨ l2 ∨ l3 for literals l1, l2 and l3. Define Qj = {Q(l1),Q(l2),Q(l3)}. For example, if the jth clause were p2 ∨ ¬p5 ∨ p6 then Qj = {q+ 2 , q5 , q+ 6 }. We define ψj to be θj ≤ τj, and Γ3 = {ψj : j = 1, . . . s}. Define c∗ (θj) = 1 and c(θj) = 0 for all c ∈ C -{c∗ }. Define q(τj) = 1 for q ∈ Qj , and for all other c (i.e., c ∈ C -Qj), define c(τi) = 0. This leads to the following properties.

Lemma 3 If some element of Qj appears in H before c∗ then H |=⊕ ψj. If σ(H) ∋ c∗ and H |=⊕ ψj then σ(H) contains some element of Qj .

We set Γ = Γ1 ∪ Γ2 ∪ Γ3. The following result implies that the HCLP deduction problem is coNP-hard (even if we restrict to the case when Γ ∪ {ϕ} ⊆ LA≤ ).

Proposition 2 Using the notation defined above, the 3-SAT instance is satisfiable if and only if Γ ̸|=⊕C(t) α ≤ β.

Proof: First let us assume that Γ ̸|=⊕C(t) α ≤ β. Then by definition, there exists an HCLP model H ∈ C(t) with H |=⊕ Γ and H ̸|=⊕ α ≤ β. Since H ̸|=⊕ α ≤ β ⇐⇒ H |=⊕ β < α, we have H |=⊕ Γ ∪ {β < α}. Because H |=⊕ β < α, σ(H) ∋ c∗ .

Because also H |=⊕ Γi2 , either σ(H) ∋ q+ i or σ(H) ∋ qi , by Lemma 2. Since H |=⊕ Γi1 , the set σ(H) does not contain both q+ i and qi , by Lemma 1.

Let us define a truth function f : P → {0, 1} as follows: f(pi) = 1 ⇐⇒ σ(H) ∋ q+ i . Since σ(H) contains exactly one of q+ i and qi , we have f(pi) = 0 ⇐⇒ σ(H) ∋ qi . We extend f to negative literals in the obvious way: f(¬pi) = 1 - f (pi).

Since H |=⊕ Γ3 ∪ {β < α}, σ(H) contains at least one element of each Qj, by Lemma 3. Thus for each j, f(l) = 1 for at least one literal l in the jth clause, and hence f satisfies clause Λj. We have shown that f satisfies each clause of the 3-SAT instance, proving that the instance is satisfiable.

Conversely, suppose that the 3-SAT instance is satisfiable, so there exists a truth function f satisfying it.

We will construct an HCLP model H ∈ C(t) such that H |=⊕ Γ ∪ {β < α}, and thus H ̸|=⊕ α ≤ β, proving that Γ ̸|=⊕C(t) α ≤ β.

For i = 1, . . . , r, let Si = {ai, q+ i } if f(pi) = 1, and otherwise, let Si = {ai, qi }. We then define H to be the sequence S1, S2, . . . , Sr, {c∗}. Since σ(H) ∋ c∗ , we have that H |=⊕ β < α.

By Lemma 1, for all i = 1, . . . , r, H |=⊕ Γi1 and so H |=⊕ Γ1. By Lemma 2, for all i = 1, . . . , r, H |=⊕ ϕi, so H |=⊕ Γ2.

Consider any j ∈ {1, . . . , s}, and, as above, write the jth clause as l1 ∨ l2 ∨ l3. Truth assignment f satisfies this clause, so there exists k ∈ {1, 2, 3} such that f(lk) = 1, where f is extended to literals in the usual way. Then Q(lk) appears in H before c∗ , so, by Lemma 3, H |=⊕ ψj . Thus H |=⊕ Γ3.

Since Γ = Γ1 ∪ Γ2 ∪ Γ3, we have shown that H |=⊕ Γ ∪ {β < α}, completing the proof. ✷

4 Sequence-of-Evaluations Models

In this section, we consider the case where we restrict to HCLP models which consist of a sequence of singletons; thus each model corresponds to a sequence of evaluations, and generates a lexicographic order based on these.

Let C be a set of evaluations on A. A C(1)-model is a sequence of different elements of C. The operation ⊕ plays no part, so we can harmlessly abbreviate ordering ≼⊕H to just ≼H, for any C(1)-model H, and similarly for ≺H and ≡H.

4.1 Some Basic Definitions and Results

We write ϕ ∈ LA as αϕ < βϕ, if ϕ is strict, or as αϕ ≤ βϕ, if ϕ is non-strict. We consider a set Γ ⊆ LA, and a set C of evaluations on A. For ϕ ∈ Γ, define SuppϕC to be {c ∈ C : c(αϕ) < c(βϕ)}; define OppϕC to be {c ∈ C : c(αϕ) > c(βϕ)}; and define IndϕC to be {c ∈ C : c(αϕ) = c(βϕ)}. We may sometimes abbreviate SuppϕC to Suppϕ, and similarly for OppϕC and IndϕC . Suppϕ are the evaluations that support ϕ; Oppϕ are the evaluations that oppose ϕ. Indϕ are the other evaluations, that are indifferent regarding ϕ. For a model H to satisfy ϕ it is necessary that no evaluation that opposes ϕ appears before all evaluations that support ϕ.

The following defines inconsistency bases, which are concerned with evaluations that cannot appear in any model satisfying the set of preference statements Γ (see Proposition 3 below).

Definition 1 Let Γ ⊆ LA, and let C be a set of Aevaluations. We say that (Γ′ ,C′ ) is an inconsistency base for (Γ, C) if Γ′ ⊆ Γ, and C ′ ⊆ C, and

• (i) for all ϕ ∈ Γ′ , SuppϕC ∪OppϕC ⊆ C ′ (and thus C -C ′ ⊆ IndϕC ); and
• (ii) for all c ∈ C ′ , there exists ϕ ∈ Γ′ such that OppϕC ∋ c.

Thus, for all ϕ ∈ Γ′ , C ′ contains all evaluations that are not indifferent regarding ϕ, and for all c ∈ C ′ there is some element of Γ′ that is opposed by c. The following result motivates the definition:

Proposition 3 Let H be an element of C(1). Suppose that H |= Γ, and let (Γ′ , C′ ) be an inconsistency base for (Γ, C). Then C ′ ∩ σ(H) = ∅. Thus no C(1) model of Γ can involve any element of C ′ . Also, we have for any ϕ ∈ Γ′ , αϕ ≡H βϕ, so H ̸|= αϕ < βϕ.

Thus H does not strictly satisfy any element of Γ′ .

For inconsistency bases (Γ1,C1) and (Γ2,C2) for (Γ, C), define (Γ1,C1)∪(Γ2,C2) to be (Γ1∪Γ2,C1∪C2). It is easy to show that if (Γ1,C1) and (Γ2,C2) are both inconsistency bases for (Γ, C) then (Γ1,C1) ∪ (Γ2,C2) is one also. Define MIB(Γ, C), the Maximal Inconsistency Base for (Γ, C), to be the union of all inconsistency bases for (Γ, C), i.e., ⋃ {(Γ1,C1) ∈ I}, where I is the set of inconsistency bases for (Γ, C). The next result follows.

Proposition 4 MIB(Γ, C) always exists, and is an inconsistency base for (Γ, C), which is maximal in the following sense: if (Γ1,C1) is an inconsistency base for (Γ, C) then Γ1 ⊆ Γ⊥ and C1 ⊆ C ⊥, where MIB(Γ, C) = (Γ⊥, C⊥).

It can also be easily shown that if Γ is C(1)-consistent then Γ⊥ contains no strict elements. Theorem 2 below implies the converse of this result.

4.2 A Polynomial Algorithm for Consistency and Deduction

Throughout this section we consider a set Γ ⊆ LA of input preference statements, and a set C of A-evaluations.

Define OppΓ (c) (abbreviated to Opp(c)) to be the set of elements opposed by c, i.e., ϕ ∈ Γ such that c(αϕ) > c(βϕ), and define SuppΓ (c) (usually abbreviated to Supp(c)) to be the set of elements ϕ of Γ supported by c, (i.e., c(αϕ) < c(βϕ)). Also, for sequence of evaluations (c1, . . . , ck), we define Supp(c1, . . . , ck) to be ⋃ki=1 Supp(ci).

The idea behind the algorithm is as follows: suppose that we have picked a sequence of elements of C, C ′ being the set picked so far. We need to choose next an evaluation c such that, if c opposes some ϕ in Γ, then ϕ is supported by some evaluation in C ′ (or else the generated sequence will not satisfy ϕ).

The Algorithm

H is initialised as the empty list () of evaluations. H ← H+c means that evaluation c is added to the end of H.

Function Cons-check(Γ, C) H ← () for k = 1, . . . , |C| do if ∃ c ∈ C - σ(H) such that Opp(c) ⊆ Supp(H) then choose some such c; H ← H + c else stop end for return H

The algorithm involves often non-unique choices. However, if we wish, the choosing of c can be done based on an ordering c1, . . . , cm of C, where, if there exists more than one c ∈ C - σ(H) such that Opp(c) ⊆ Supp(H), we choose the element ci with smallest index i. The algorithm then becomes deterministic, with a unique result following from the given inputs.

A straight-forward implementation runs in O(|Γ||C|2 ) time; however, a more careful implementation runs in O(|Γ||C|) time.

Properties of the Algorithm

Any ϕ ∈ Γ which is opposed by some evaluation c in H is supported by some earlier evaluation in H. Consider any ϕ in Supp(H). Let cj be the earliest evaluation in H that supports ϕ. None of the earlier evaluations than cj oppose ϕ, and thus H strictly satisfies ϕ. A similar argument shows that H satisfies Γ(≤) , defined to be {αϕ ≤ βϕ : ϕ ∈ Γ}, i.e., Γ where the strict statements are replaced by corresponding non-strict statements.

The algorithm will always generate an HCLP model satisfying Γ if Γ is consistent. It can also be used for computing the Maximal Inconsistency Base. The following result sums up some properties related to the algorithm.

Theorem 2 Let H be a sequence returned by the algorithm with inputs Γ and C, and write MIB(Γ, C) as (Γ⊥, C⊥). Then C ⊥ = C - σ(H) (i.e., the evaluations that don't appear in H), and Γ⊥ = Γ - Supp(H). We have that H |= Γ(≤) . Also, Γ is C(1)-consistent if and only if Supp(H) contains all the strict elements of Γ, which is if and only if Γ⊥ ∩ LA< = ∅. If Γ is C(1)-consistent then H |= Γ.

The algorithm therefore determines C(1)-consistency, and hence C(1)-deduction (because of Proposition 1), in polynomial time, and also generates the Maximal Inconsistency Base. For the case when Γ is not C(1)-consistent, the output H of the algorithm is a model which, in a sense, comes closest to satisfying Γ: it always satisfies Γ(≤) , the non-strict version of Γ, and if any model H′ ∈ C(1) satisfies Γ(≤) and any element ϕ of Γ, then H also satisfies ϕ. These properties suggest the following way of reasoning with inconsistent Γ. Let us define Γ′ to be equal to (Γ - Γ⊥) ∪ Γ(≤) . By Theorem 2, this is equal to Supp(H) ∪ Γ(≤) , where H is a model generated by the algorithm, enabling easy computation of Γ′ . Γ′ is consistent, since it is satisfied by H. We might then (re)define the (non-monotonic) deductions from inconsistent Γ to be the deductions from Γ′ .

4.3 Strong Consistency

In the set of models C(1), we allow models involving any subset of C, the set of evaluations. We could alternatively consider a semantics where we only allow models H that involve all elements of C, i.e., with σ(H) = C.

Let C(1∗ ) be the set of elements H of C(1) with σ(H) = C. Γ is defined to be strongly C(1)-consistent if and only if there exists a model H ∈ C(1∗ ) such that H |= Γ. Let MIB(Γ, C) = (Γ⊥,C⊥). Proposition 3 implies that, if Γ is strongly C(1)-consistent then C ⊥ is empty, and Γ⊥ consists of all the elements of Γ that are indifferent to all of C, i.e., the set of ϕ ∈ Γ such that c(αϕ) = c(βϕ) for all c ∈ C.

We write Γ |=C(1∗ ) ϕ if H |= ϕ holds for every H ∈ C(1∗ ) such that H |= Γ. The next result shows that the nonstrict |=C(1∗ ) inferences are the same as the non-strict |=C(1) inferences, and that (in contrast to the case of |=C(1)), the strict |=C(1∗ ) inferences almost correspond with the non-strict ones. The result also implies that the algorithm in Section 4.2 can be used to efficiently determine the |=C(1∗ ) inferences.

Proposition 5 Let MIB(Γ, C) = (Γ⊥,C⊥). Γ is strongly C(1)-consistent if and only if C ⊥ = ∅. Suppose that Γ is strongly C(1)-consistent. Then,

• (i) Γ |=C(1) α ≤ β ⇐⇒ Γ |=C(1∗ ) α ≤ β;
• (ii) Γ |=C(1∗ ) α ≡ β if and only if α and β agree on all of C, i.e., for all c ∈ C, c(α) = c(β);
• (iii) Γ |=C(1∗ ) α < β if and only if Γ |=C(1) α ≤ β and α and β differ on some element of C, i.e., there exists c ∈ C such that c(α) ̸= c(β).

We obtain a similar (and generalisation of this) result, if we consider only the maximal models in C(1) that satisfy Γ (these all have the same cardinality: |C| - |C ⊥|).

The next result shows that |=C(1) inference is not affected if one removes the evaluations in the MIB.

Proposition 6 Suppose that Γ is C(1)-consistent, let MIB(Γ, C) = (Γ⊥,C⊥), and let C ′ = C - C ⊥. Then Γ is strongly C ′ (1)-consistent, and Γ |=C(1) ϕ if and only if Γ |=C′ (1) ϕ.

4.4 Orderings on evaluations

The preference logic defined here is closely related to a logic based on disjunctive ordering statements. Given set of evaluations C, we consider the set of statements OC of the form C1 < C2, and of C1 ≤ C2, where C1 and C2 are disjoint subsets of C.

We say that H |= C1 < C2 if some evaluation in C1 appears in H before every element of C2, that is, there exists some element of C1 in H (i.e., C1 ∩ σ(H) ̸= ∅) and the earliest element of C1 ∪ C2 to appear in H is in C1.

We say that H |= C1 ≤ C2 if either H |= C1 < C2 or no element of C1 or C2 appears in H: (C1 ∪ C2) ∩ σ(H) = ∅. Then we have that

This shows that the language OC can express anything that can be expressed in LA. It can be shown, conversely, that for any statement τ in OC, one can define αϕ and βϕ, and the values of elements of C on these, such that for all H ∈ C(1), H |= τ if and only if H |= ϕ. For instance, if τ is the statement C1 < C2, we can define c(αϕ) = 1 for all c ∈ C2, and c(αϕ) = 0 for c ∈ C - C2; and define c(βϕ) = 1 for all c ∈ C1, and c(βϕ) = 0 for c ∈ C - C1.

The algorithm adapts in the obvious way to the case where we have Γ consisting of (or including) elements in OC. When viewed in this way, the algorithm can be seen as a simple extension of a topological sort algorithm; the standard case corresponds to when the ordering statements only consist of singleton sets.

5 Discussion and Conclusions

We defined a class of relatively simple preference logics based on hierarchical models. These generate an adventurous form of inference, which can be helpful if there is only relatively sparse input preference information. We showed that the complexity of preference deduction is coNP-complete in general, and polynomial for the case where the criteria are assumed to be totally ordered (the sequence-of-evaluations case, Section 4).

The latter logic has strong connections with the preference inference formalism described in [Wilson, 2014]. To clarify the connection, for each evaluation c ∈ C we can generate a variable Xc, and let V be the set of these variables. For each alternative α ∈ A we generate a complete assignment α∗ on the variables V (i.e., an outcome as defined in [Wilson, 2014]) by α∗ (Xc) = c(α) for each Xc ∈ V . Note that values of α∗ (Xc) are non-negative numbers, and thus have a fixed ordering, with zero being the best value. A preference statement α ≤ β in LA≤ then corresponds with a basic preference formula α∗ ≥ β∗ in [Wilson, 2014]. Each model H ∈ C(1) corresponds to a sequence of evaluations, and thus has an associated sequence of variables; this sequence together with the fixed value orderings, generates a lexicographic model as defined in [Wilson, 2014].

In contrast with the lexicographic inference system in [Wilson, 2014], the logic developed in this paper allows strict (as well as non-strict) preference statements, and allows more than one variable at the same level. However, the lexicographic inference logic from [Wilson, 2014] does not assume a fixed value ordering (which, translated into the current formalism, corresponds to not assuming that the values of the evaluation function are known); it also allows a richer language of preference statements, where a statement can be a compact representation for a (possibly exponentially large) set of basic preference statements of the form α ≤ β. Many of the results of Section 4 immediately extend to richer preference languages (by replacing a preference statement by a corresponding set of basic preference statements). In future work we will determine under what circumstances deduction remains polynomial when extending the language, and when removing the assumption that the evaluation functions are known.

The coNP-hardness result for the general case (and for the |=⊕C(t) systems with t ≥ 2) is notable and perhaps surprising, since these preference logics are relatively simple ones. The result obviously extends to more general systems. The preference inference system described in [Wilson, 2009] is based on much more complex forms of lexicographic models, allowing conditional dependencies, as well as having local orderings on sets of variables (with bounded cardinality). Theorem 1 implies that the (polynomial) deduction system in [Wilson, 2009] is not more general than the system described here (assuming P ̸= NP). It also implies that if one were to extend the system from [Wilson, 2009] to allow a richer form of equivalence, generalising e.g., the |=⊕C(2) system, then the preference inference will no longer be polynomial.

Acknowledgments

This publication has emanated from research conducted with the financial support of Science Foundation Ireland (SFI) under Grant Number SFI/12/RC/2289. Nic Wilson is also supported by the School of EEE&CS, Queen's University Belfast. We are grateful to the reviewers for their helpful comments.