Efficient Inference for Expressive Comparative Preference Languages

1 INTRODUCTION

Recent years have seen a considerable literature develop in the Artificial Intelligence community on formalisms for reasoning with comparative preferences in combinatorial problems, involving statements which compactly express the relative preference of outcomes (complete assignments to a set of variables). For example, consider a CP-net [Boutilier et al., 1999; 2004] statement ϕ of the form u : x > x′ where x and x′ are assignments to a single variable X, and u is an assignment to some set of other variables U. This compactly represents the typically exponentially large set ϕ∗ of all pairs (α, β) of outcomes such that (i) α and β both extend u, (ii) α(X) = x, β(X) = x′ and (iii) α and β agree on all other variables. Each pair (α, β) ∈ ϕ∗ represents a preference for α over β.

CP-nets and related formalisms [Boutilier et al., 2004; Brafman et al., 2006; Wilson, 2004a] allow only very restricted forms of comparative preference statements. We can consider much more general statements ϕ, with associated relation ϕ∗ giving the preferences between alternatives that are directly implied by ϕ. Each pair (α, β) in ϕ∗ represents a preference (e.g., of a single user) for outcome α over outcome β. Many comparative preference statements may be elicited, to form a set Γ. This set Γ thus directly represents preferences Γ∗ = ⋃ϕ∈Γ ϕ∗ . A key problem is the following:

Given that the user has told us Γ is it reasonable to infer that the user prefers outcome α to outcome β?

We take a semantic approach to inference, related to that taken in [Boutilier et al., 2004; Brafman and Dimopoulos, 2004; Wilson, 2004b; 2006]. Let us assume that the user's preference relation 1 ≽ is a weak order, also known as a total pre-order, i.e., a relation on outcomes which is transitive and complete, so that (i) α ≽ β and β ≽ γ implies α ≽ γ, and (ii) for all outcomes α and β, either α ≽ β or β ≽ α. A weak order satisfies a comparative preference statement ϕ if and only if it extends ϕ∗ . We write Γ |= ϕ (and also Γ∗ |= ϕ∗ ) if and only if every weak order satisfying every statement in Γ also satisfies ϕ. It can be shown that this holds if and only if ϕ∗ is a subset of the transitive closure of Γ∗ .

Unfortunately, even for quite restrictive languages, it appears to be extremely hard in general to test if Γ entails, in this sense, a preference of α over β, i.e., if Γ∗ |= {(α, β)}. In particular, for CP-nets such dominance testing has been shown to be PSPACE-complete [Goldsmith et al., 2005]. In addition, this kind of inference is conservative, and tends to lead to weak preferences with a great deal of incomparability. It is very often desirable to be able to fill out the user's direct preferences in a plausible way by some kind of extrapolation, generating a fuller relation. This can be done by basing the inference relation on a smaller set of weak orders.

Note, however, that the aim is not to generate a single utility function (or weak order) compatible with the inputs (cf. the approaches in [Boutilier et al., 2001; Domshlak et al., 2003; McGeachie and Doyle, 2004; Brafman and Domshlak, 2008]). This would need to involve many arbitrary choices, since the output preferences are so much stronger than the inputs, and therefore the utility function would be extremely unlikely to be compatible with the user's unknown preferences.

Our approach involves defining entailment using only weak orders which are of a kind of generalised lexicographic form. It extends and generalises the upper approximation described in [Wilson, 2006], especially, in allowing very much more general comparative preference input statements. In fact, the approach applies to completely arbitrary input preference relations, and the inference algorithm is polynomial for many natural kinds of preference statements, such as comparisons between arbitrary partial tuples (including complete assignments), and with the preferences being ceteris paribus or not. No acyclicity conditions are required regarding the input statements, and consistency (i.e., acyclicity of the preference relation) is not assumed.

1 Equivalently we might assume that the user's preference is represented by a utility function which assigns a real value to each outcome, with U(α) ≥ U(β) indicating that the user prefers α to β. The focus on weak orders, as in [Brafman and Dimopoulos, 2004; Wilson, 2006], rather than on total orders, means that the approach also applies to situations where the preferences can imply cycles of outcomes.

Section 2 describes some different forms of comparative preference statements, and an operation on them which is important for our computational approach. Section 3 describes a special kind of weak order on outcomes, those generated by what we call a cp-tree. In the semantics, restricting to this kind of weak order leads to a stronger form of inference, as defined in Section 4. Section 5 describes our computational technique for determining entailment, which is polynomial for a wide range of comparative preference statements. Section 6 sketches the proof of correctness of the technique in Section 5. Section 7 discusses application to a broader range of comparative preference statements.

Terminology. Let V be a set of n variables. For each X ∈ V let X be the set of possible values of X; we assume X has at least two elements. For subset of variables A ⊆ V let A = ∏X∈A X be the set of possible assignments to set of variables A. The assignment to the empty set of variables is written ⊤. An outcome is an element of V , i.e., an assignment to all the variables. If a ∈ A is an assignment to A, and b ∈ B, where A ∩ B = ∅, then we may write ab as the assignment to A∪B which combines a and b. For partial tuples a ∈ A and u ∈ U, we may write a |= u, or say a extends u, if A ⊇ U and a(U) = u, i.e., a projected to U gives u. More generally, we say that a is compatible with u if there exists outcome α ∈ V extending both a and u, i.e., such that α(A) = a and α(U) = u. This is if and only if u and a agree on common variables, i.e., u(A∩U) = a(A∩U). Otherwise, we say that a and u are incompatible.

Let ≽ be some transitive relation on a set Z. We say that z1 and z2 are ≽-equivalent if both z1 ≽ z2 and z2 ≽ z1.

2 COMPARATIVE PREFERENCE STATEMENTS

In this paper we will focus especially on comparative preference statements ϕ of the form p > q ‖ T , where P , Q and T are subsets of V , and p ∈ P is an assignment to P , and q ∈ Q is an assignment to Q. Informally, the statement p > q ‖ T represents the following: p is preferred to q if T is held constant. Formally, the semantics of this statement is given by the relation ϕ∗ which is defined to be the set of pairs (α, β) of outcomes such that α extends p, and β extends q, and α and β agree on T : α(T ) = β(T ).

If p and q do not agree on common variables in T, i.e., if p(P ∩Q∩ T) ̸= q(P ∩Q∩ T), then ϕ is vacuous: ϕ∗ = ∅. Given that p and q do agree on common variables in T, we can assume, without loss of generality, that P ∩ T = ∅ and Q∩T = ∅, since, for example, we can add any variable X in (P ∩T )-Q to Q, extending q by q(X) = p(X), and remove X from T , without changing ϕ∗ .

We are particularly interested in such statements ϕ when P = Q. The statement can then be written as us > us′ ‖ T, where U, S and T are disjoint sets of variables, and u ∈ U, and s and s′ are assignments to S which differ on each variable: s(Z) ̸= s′ (Z) for all Z ∈ S.

Ceteris paribus preferences are represented by statements with T = V - (U ∪ S); a feature vector rule in [McGeachie and Doyle, 2004] can be represented by such a statement. On the other hand, statements with T = ∅ represent a stronger kind of preference, which can be used, for example, for representing lexicographic and similar orders. A CP-theory [Wilson, 2004b; 2004a] statement u : x > x′ [W] is exactly equivalent to statement us > us′ ‖ T when we set S = {X}, x = s, x′ = s′ and T = V - (U ∪ {X} ∪ W). CP-nets [Boutilier et al., 1999; 2004] and TCP-nets [Brafman and Domshlak, 2002; Brafman et al., 2006] can be expressed in terms of CP-theories [Wilson, 2004a]. In particular, CP-net statement u : x > x′ is equivalent to a CP-theory statement when W = ∅ and so T = V - (U ∪ {X}). A preference of outcome α over outcome β can be expressed by a statement us > us′ ‖ ∅ by setting u = α(U) = β(U), where U is the variables on which α and β agree, and s = α(V - U) and s′ = β(V - U). A more general statement p > q ‖ T can also be used to represent statements of the form "α is the best outcome extending tuple u".

Selection-projections. The computational technique described in this paper is efficient essentially if and only if one can efficiently compute a particular compound operation on the input comparative preference statements: the projection of a selection. Fortunately, this operation is efficient for a broad class of natural comparative preference statements. Let a be an assignment to set of variables A, and let Y be a set of variables disjoint with A. For relation R on the set of outcomes, define the a-selection Ra of R to consist of all pairs (α, β) in R such that both α and β extend a. We define, for Y ⊆ V , the projection R↓Y of R to be the set of all pairs (y, y′ ) ∈ Y × Y such that there exists tuples z and z′ with (yz, y′ z′ ) ∈ R. We write RY a for (Ra)↓Y , the projection to Y of the a-selection of R. We call this compound operation a selection-projection. Let y, y′ ∈ Y be assignments to Y . We have (y, y′ ) ∈ RY a if and only if there exist assignments z, z′ to V - (A ∪ Y ) such that (ayz, ay′ z′ ) ∈ R.

The following property, which is important for the efficiency of our approach, follows easily from the definitions.

Proposition 1 (Decomposition) For i in some index set I, let Ri be some relation on outcomes, and let R = ⋃i∈I Ri. Let a be an assignment to set of variables A, and let Y be a set of variables disjoint with A. Then RY a = ⋃i∈I (Ri)Ya .

For comparative preference statement ϕ and set of comparative preference statements Γ we abbreviate (ϕ∗ )Ya to ϕYa and abbreviate (Γ∗ )Ya to ΓYa . We thus have ΓYa = ⋃ϕ∈Γ ϕYa . We are interested in sets Y whose associated product set Y is not large (so, small sets of variables whose domains are fairly small). Then the relations ΓYa are of manageable size, even though Γ∗ may very well be exponentially large.

Proposition 2 Let P , Q and T be subsets of V , and let p ∈ P be an assignment to P , and q ∈ Q be an assignment to Q. Let ϕ be a comparative preference statement of the form p > q ‖ T , as defined above, where p ∈ P , q ∈ Q and (P ∪Q)∩T = ∅ . Let a be an assignment to a set of variables A, and let Y be a set of variables disjoint from A. ϕYa is empty unless a is compatible with both p and q. If a is compatible with both p and q then ϕYa consists of all pairs (y, y′ ) such that (i) y and y′ agree on Y ∩ T, i.e., y(Y ∩ T) = y′ (Y ∩ T); (ii) y is compatible with p; and (iii) y′ is compatible with q.

Each of these conditions can be checked in time at worst linear in n, the number of variables, and so the relation ϕYa can be computed in time linear in n, given that the size of Y is bounded by a constant. Proposition 2 therefore shows that computing selection-projection can be achieved efficiently for statements of the form p > q ‖ T , and hence, by Proposition 1, for sets Γ of such statements.

For compatible p and q a variation of the above definition of ϕ∗ will often be natural, which insists in addition that, for (α, β) ∈ ϕ∗ , α does not extend q, and β does not extend p (cf. [McGeachie and Doyle, 2004]). It can be shown that ϕYa can be computed efficiently in this case also.

3 cp-TREES AND THEIRWEAKORDERS

In this section we define a special kind of weak order, one generated by what we call a cp-tree. They are generalisations of the pre-ordered search trees of [Wilson, 2006]. cp-trees represent a rather natural and simple model of a user's preferences. In such a model, the user orders outcomes as follows: they first choose a small set of variables Y and an ordering ⩾ on the assignments to Y . Outcomes are primarily ordered by considering their projections to Y , comparing them using ⩾. If the outcomes do not differ on Y then a disjoint set of variables Y ′ is considered next, along with an ordering ⩾′ on Y ′ , and so on. cp-trees therefore represent a form of lexicographic order, but where the importance ordering on variables can depend on more important variables, as can the value orderings.

A cp-tree is a rooted directed tree, which we picture being drawn with the root at the top, and children below parents. Associated with each node r in the tree is a set of variables Yr, which is instantiated with a different assignment in each of the node's children (if it has any), and also a weak order ⩾r of the values of Yr.

More formally, define a cp-node r (usually abbreviated to just "node") to be a tuple 〈Ar, ar, Yr, ⩾r〉, where Ar ⊆ V is a set of variables, ar ∈ Ar is an assignment to those variables, Yr ⊆ V -Ar is a non-empty set of other variables; ⩾r is a weak order on the set Yr of values of Yr which is not equal to the trivial full relation on Y ; so there exists some y, y′ ∈ Y with y ̸⩾r y′ .

A cp-tree is defined to be a directed tree, where edges are directed away from a root node, root, so that all nodes apart from the root node have a unique parent node. The ancestors of a node r are the nodes on the path from root to the parent node of r. Each node is identified with a unique cp-node r. Let r → r′ be an edge in the cp-tree from a node r to one of its children r′ . Associated with this edge is an assignment y to variables Yr. This is different from the assignment y′ associated with any other edges from node r. Ar′ = Ar ∪Yr′ , and ar′ is ar extended with the assignment Yr = y. We also have Aroot = ∅. Therefore Ar is the union of sets Yr′′ over all ancestors r′′ of r; and ar consists of all assignments made on the path from the root to r. The root node has aroot = ⊤, the assignment to the empty set of variables.

We also assume that the weak orders ⩾r satisfy the following condition, (to ensure that the associated ordering on outcomes is transitive): if there exists a child of node r associated with instantiation Yr = y, then y is not ⩾r-equivalent to any other value of Y , so that y ⩾r y′ ⩾r y only if y′ = y. In particular, ⩾r totally orders the assignments (of Yr) associated with the children of r. The only difference between a cp-tree and a pre-ordered search tree as defined in [Wilson, 2006] is that, in the latter, Yr is just a single variable, rather than a non-empty set of variables.

The weak order ≽σ associated with a cp-tree σ

For outcome α, define the path to α to be the path from the root which includes all nodes r such that α extends ar. To generate this, for each node r, starting from the root, we choose the child associated with the instantiation Yr = α(Yr) (there is at most one such child); the path finishes when there exists no such child.

Node r is said to decide outcomes α and β if it is the deepest node (i.e., furthest from the root) which is both on the path to α and on the path to β. Hence α and β both extend the tuple ar (but they may differ on variable Yr). We compare α and β by using ⩾r, where r is the unique node which decides α and β.

Definition 1 Let σ be a cp-tree. The associated relation ≽σ on outcomes is defined as follows: For outcomes α, β ∈ V outcomes, we define α ≽σ β to hold if and only if α(Yr) ⩾r β(Yr), where r is the node which decides α and β.

We therefore have that α and β are ≽σ-equivalent if and only if α(Yr) and β(Yr) are ⩾r-equivalent; also: α ≻σ β holds if and only if α(Yr) >r β(Yr). This ordering is similar to a lexicographic ordering in that two outcomes are compared on the first variable on which they differ. The definition implies immediately that ≽σ is complete; it is easily shown to be transitive, and is hence a weak order.

We say that cp-tree σ satisfies relation R if and only if ≽σ satisfies R i.e., ≽σ extends R, that is, (α, β) ∈ R ⇒ α ≽σ β. Similarly, for comparative preference statement ϕ and set of comparative statements Γ, we say that σ satisfies ϕ (respectively, Γ) if and only if σ satisfies ϕ∗ (respectively, Γ∗ ).

Example. I am planning a holiday, and I have to decide where, when, and for how long I want to go, represented by variables X1 (Paris or London), X2 (Spring or Summer) and X3 (one week or two weeks), respectively. Let V be the set of variables {X1,X2,X3} with domains Xi = {xi, x′i }, for i = 1, 2, 3, where x1 represents Paris, x2 represents Spring, x3 represents going for one week, etc. Define a cp-tree σ with two nodes, root = 〈∅, ⊤, {X1}, [x1 > x′1 ]〉 and its only child node r = 〈{X1}, x1, {X3}, [x3 > x′3 ]〉. Let ϕ1 be the comparative preference statement x1x2 > x′1 ‖ {X3}, which represents that I'd rather go to Paris in the Springtime than London any time. The associated set of pairs of outcomes ϕ∗1 consists of (x1x2x3, x′1x2, x3), (x1x2x′3 , x′1x2, x′3 ), (x1x2x3, x′1x′2 , x3), and (x1x2x′3 , x′1x′2 , x′3 ).

Each of these is in ≽σ, which implies that ≽σ extends ϕ∗1 , and so cp-tree σ satisfies ϕ1. Similarly, σ satisfies ϕ2 and ϕ3, where ϕ2 = x′2x3 > x2x′3 ‖ {X1}, and ϕ3 = x′1x′3 > x′1x3 ‖ ∅. Node r decides outcomes x1x2x′3 and x1x2x3, and we have x1x2x3 >r x1x2x′3 , and so x1x2x3 ≻σ x1x2x′3 , i.e., x1x2x′3 ̸≽σ x1x2x3. This implies that σ fails to satisfy the statement ψ equalling x1x2x′3 > x1x2x3, since ≽σ does not extend ψ∗ = {(x1x2x′3 , x1x2x3)}.

A cp-tree ordering is a special kind of weak order in which there is a most important set Y ′ of variables, and outcomes are compared first on these. Only if the outcomes agree on Y ′ are further variables considered. If someone had the same preferences as cp-tree σ in the Example, then they would regard that X1 (destination) is the (uniquely) most important variable, with x1 (Paris) being better than x′1 (London). Given x1, X3 (length of stay) is the next most important variable, with x3 being better than x′3 . cp-tree orderings thus represent quite a simple way of ordering outcomes, but one which seems fairly psychologically plausible (people often focus first on a small set of variables).

4 DEDUCTION BASEDON cp-TREES

We fix a family Y of small subsets of V . For example, Y might be defined to be all singleton subsets of V (i.e., sets with cardinality of one), or, alternatively, all subsets of cardinality at most two, and so on.

Definition 2 (Y-cp-tree) Let Y be a set of non-empty subsets of V such that if Y ∈ Y and non-empty Y ′ is a subset of Y then Y ′ ∈ Y. A Y-cp-tree is defined to be a cp-tree σ such that for any node r of σ, we have Yr ∈ Y.

Y-entailment |=Y. We can nowconsider deduction of comparative preferences based on Y-cp-trees. Let R be a relation on outcomes, and let ψ be a comparative preference statement. R |=Y ψ holds if and only if every Y-cp-tree satisfying R also satisfies ψ∗ . Let Γ be a set of comparative preference statements. Γ |=Y ψ holds if and only if Γ∗ |=Y ψ∗ . In the example, using Y = {{X1}, {X2}, {X3}}, we have {ϕ1, ϕ2, ϕ3} ̸|=Y ψ because there exists a Y-cp-tree satisfying {ϕ1, ϕ2, ϕ3} but not ψ.

An especially important case is when ψ∗ is just equal to a singleton set {(α, β)} for some outcomes α and β. Such an inference from Γ is an inferred preference for α over β. For input relation R on outcomes we define the inferred preference relation RY to consist of all pairs (α, β) such that R |=Y {(α, β)}. It is clear that RY contains R. It is also transitive, since it is the intersection of a set of transitive relations (the set of ≽σ over all σ satisfying R). It hence contains the transitive closure of R. Therefore, for the special cases of CP-theories and CP-nets, RY contains the standard preference relation: it is an upper approximation [Wilson, 2006]. In particular, we associate preference relation Γ∗Y with set Γ of comparative preference statements (in some language). If we let Y be the set of singleton subsets of V , and consider only comparative preference statements of the form ux > ux′ ‖ T where x and x′ are different values of a variable X (see Section 2) then Γ∗Y is the same as the preference relation ⊵Γ defined in [Wilson, 2006].

We will consider somewhat more general preference statements ψ, of the following form: all outcomes extending p are preferred to all outcomes extending p′ , where p and p′ are given assignments to set of variables P ⊆ V . We can write this, using the notation developed in Section 2, as a statement us > us′ ‖ ∅.

5 COMPUTATIONOF Y-ENTAILMENT

This section describes an algorithm for Y-entailment, which is polynomial for a wide range of comparative preference relations; in particular, statements of the form p > q ‖ T as described in Section 2, or any other comparative statements for which computing selection-projections is polynomial.

The approach very substantially generalises that in [Wilson, 2006]. A completely arbitrary input relation R is allowed (which simplifies some of the results). We also allow a much richer language of output queries ψ, and a richer class of models, by allowing elements of Y to be non-singleton sets; these two things complicate some proofs; however, the proof follows the same structure as that in [Wilson, 2006].

Throughout this section, we consider a fixed family Y of sets of variables, which parameterises the inference relation, and a fixed input relation R on outcomes. We also consider a fixed comparative preference statement ψ of the form us > us′ ‖ ∅, as defined in Section 4. U and S are disjoint sets of variables, and u ∈ U, and s and s′ are assignments to S which differ on each variable in S.

Definition 3 (Pickable and Decisive) Given set Y ⊆ V and assignment a to some subset A of V - Y , we define ⊐Ya to be the transitive closure of RY a . Suppose that u is compatible with a ∈ A. Set of variables Y is said to be ψ-pickable given a if Y ∩ A = ∅ and either

• (i) Y ⊆ U and u(Y ) is not ⊐Ya -equivalent to any other assignment in Y ; or
• (ii) Y ̸⊆ U and there exists y, y′ ∈ Y with y ̸⊐Ya y′ and y is compatible with us, and y′ is compatible with us′ .

In case (ii) we say that Y is ψ-decisive given a.

Algorithm for determining Y-entailment

The following algorithm assumes a given input relation R on outcomes and comparative preference statement ψ of the form us > us′ ‖ ∅. It determines if R Y-entails ψ or not, i.e., if R |=Y ψ∗ , where family of subsets Y is as defined in Section 4, parameterises the deduction relation.

procedure Does R Y-entail ψ?

• if there exists a set in Y which is ψ-decisive given aj then return false and stop;
• if there exists a set in Y which is ψ-pickable given aj then let Yj be any such set;

else return true and stop;

next j; return true.

The theorem states the correctness of the algorithm. Section 6 shows how this is proved.

Theorem 1 Let R be a relation on outcomes, and let ψ be a comparative preference statement of the form us > us′ ‖ ∅. The above procedure is correct, i.e., it returns true if R |=Y ψ∗ and it returns false if R ̸|=Y ψ∗ .

Application to Deduction for Comparative Preference Statements

The algorithm applies to arbitrary input relations R. Relation R will very often be exponentially large, and so will need to represented compactly, in particular as a set Γ of comparative preference statements (in some language), where Γ represents relation R = Γ∗ on outcomes. We infer ψ of the form us > us′ ‖ ∅ from Γ if and only if Γ∗ |=Y ψ∗ . Applying the approach described above requires us to compute selection-projections of the form ΓYa , which we can compute as ⋃ϕ∈Γ ϕYa using Proposition 1.

Example continued. We can write ψ as us > us′ , where U = {X1,X2}, and u = x1x2, and s = x′3 and s′ = x3. We wish to determine if we can infer ψ, representing a preference for Paris-Spring-TwoWeeks over Paris-SpringOneWeek. {X1} is ψ-pickable because {X1} is a subset of U (case (i)), and u(X1), i.e., x1, is not equivalent to x′1 (since none of the three statements in Γ give a preference of x′1 over x1). {X3} is then ψ-decisive given x1 since:- X3 is not in U so we're in case (ii); ΓX3 x1 does not contain the pair (x′3 , x3), since none of the statements in Γ give a preference for x′3 over x3 in a context compatible with x1. (ϕ3 gives a preference for x′3 over x3 but only when x′1 holds, which is incompatible with x1, and so (ϕ3)X3 x1 is empty.) So the algorithm returns false. This implies (see Section 6) that there exists a cp-tree (e.g., σ defined in Section 3) which satisfies Γ but does not satisfy ψ. Hence Γ does not Y-entail ψ.

On the other hand, consider the statement ψ′ = x1x2x′3 > x′1x2x3. None of the variables are ψ′ -pickable. For example, X1 is not ψ′ -pickable because (ϕ1)X1 ⊤ contains (x1, x′1 ). Hence the algorithm returns true, and so Γ Y-entails ψ′ .

Complexity. Let L be the set of comparative preferences which can be written in the form p > q ‖ T (see Section 2). This includes all CP-net statements and CP-theory statements, along with more complex comparisons between tuples. Assume that Γ ⊆ L. Computing ΓYa can then be performed efficiently, using Propositions 1 and 2. Assume that the domain sizes are bounded above by a constant, and that the elements of Y have cardinality at most k, and so |Y| is less than nk . The algorithm is then O(mnk+1 ), where m = |Γ|, (using the fact that, for a statement p > q ‖ T in Γ, checking the compatibility of a with p and q can be performed incrementally).

6 PROVINGTHE THEOREM

The main aim of this section is to sketch how to prove Theorem 1, which states the correctness of the algorithm for Yentailment in Section 5. (A longer version of the paper including proofs can be downloaded from the author's website.) We are addressing the problem of whether relation R Y-entails ψ, where comparative preference statement ψ is of the form us > us′ ‖ ∅. By definition, this fails to hold if and only if there exists a Y-cp-tree which satisfies R but not ψ. Proposition 3 shows that such cp-trees map to particular sequences of sets in Y, which we call decisive sequences. Y-entailment of ψ from R can therefore be determined by checking for the existence of a decisive sequence. A decisive sequence is a sequence of pickable Y ∈ Y ending with a decisive Y . The pickable Y correspond to nodes in a cptree satisfying R, and a decisive Y corresponds to a node in cp-tree which satisfies R but not ψ. Determining if a Y is pickable or decisive can be done using a selection-projection of R, so is efficient if and only if this selection-projection can be done efficiently.

A monotonicity property, expressed by Proposition 4, states, roughly speaking, that a set Y which is pickable remains pickable if other sets are chosen first. This means that the search for decisive sequences can be performed in a backtrack-free manner, leading to the simple and efficient algorithm below whose correctness is stated by the theorem. The algorithm iteratively checks to see if there exists a decisive set Y , and if so, it returns "false", meaning R does not Y-entail ψ, since a decisive sequence has been constructed. If not, it checks if there is a pickable set Y . If there is no such set Y then it returns "true", as there is then no decisive sequence.

We wish to determine if relation R Y-entails ψ, where comparative preference statement ψ is of the form us > us′ ‖ ∅. We map cp-trees, which satisfy R but not ψ, to a sequence of sets Y ∈ Y, which we call a decisive sequence, generated from the cp-nodes on the path from the root to a node which falsifies ψ (i.e., the node's ordering is incompatible with ψ).

A (Y-)decisive sequence (w.r.t. ψ) is defined to be a sequence Y1, . . . , Yk of disjoint sets in Y satisfying the following conditions:

• for j = 1, . . . , k - 1, Yj ⊆ U, and Yk ̸⊆ U;
• for j = 1, . . . , k, Yj is ψ-pickable given aj where aj is u restricted to Y1 ∪ · · · ∪Yj-1; in particular, Yk is decisive given ak.

The following result shows that entailment is equivalent to the absence of a decisive sequence. A cp-tree which is in the form of a chain is generated from a decisive sequence, where a set Y in the sequence generates a node r with Yr = Y . Conversely, the decisive sequence is generated from a particular path in the cp-tree.

Proposition 3 There exists a Y-decisive sequence w.r.t. ψ if and only if it is not the case that R |=Y ψ, i.e., if and only if there exists (α, β) ∈ ψ∗ and a Y-cp-tree σ satisfying R with β ≻σ α.

Theorem 1 follows easily using Proposition 3 and the following monotonicity result.

Proposition 4 Let ψ be a comparative preference statement of the form us > us′ ‖ ∅, where u ∈ U. Suppose that A ⊆ B ⊆ U, and that a ∈ A and b ∈ B and that u extends b which extends a. Let Y ⊆ V be such that A∩Y = ∅ and that Y ̸⊆ B.

If Y ∈ Y is ψ-pickable given a then Y -B is ψ-pickable given b. If Y ∈ Y is ψ-decisive given a then Y - B is ψdecisive given b.

7 SUMMARYANDDISCUSSION

We have defined a form of inference for comparative preferences, which we call Y-entailment, where Y is a set of small non-empty sets of variables which parameterises the inference. For example, Y might the the set of singleton subsets; or alternatively, the set of all non-empty subsets with at most two elements. We have given a sound and complete algorithm for determining if set of comparative preference statements Γ Y-entails ψ where ψ is a comparative preference statement of a special form; in particular, ψ can represent a preference for an outcome α over an outcome β. As described in [Wilson, 2006], we can use Y-entailment in a constrained optimisation algorithm. Being able to deduce a more general comparative preference statement ψ, can be used to allow pruning at a partial node in the search tree.

The algorithm for Y-entailment is efficient for a broad range of input comparative preference statements, including those in CP-nets, CP-theories, but also allowing comparisons between partial tuples. In particular, it allows as inputs expressing a preference for one outcome over another, which is important for many applications.

In fact, the approach will be fairly efficient for many more kinds of inputs. In terms of complexity, the key issue is the efficiency of the selection-projection operation, i.e., how hard it is to test, for ϕ ∈ Γ, if a pair (y, y′ ) is in ϕYa (for a ∈ A and Y ∈ Y, with Y ∩ A = ∅). If this is polynomial then the algorithm is polynomial (since the decomposibility property expressed by Proposition 1, means that the complexity increases only linearly with the number of input comparative preference statements |Γ|). More generally, the problem of determining if a pair (y, y′ ) is in ϕYa is in NP as long as it is polynomial to test if a given pair of outcomes satisfies ϕ.

Consider a statement ϕ of the form F > G ‖ T , where F and G are propositional formulae (cf. [McGeachie and Doyle, 2004; Lang, 2004]). Determining if a pair (y, y′ ) is in ϕYa is "only" NP-complete. Moreover, if comparative preference statement ϕ is elicited from a user, then one would expect that usually F and G will only involve a small number of propositional variables, in which case, we'll need to solve just a small instance of a NP-complete problem, and so may well be fairly easy.

Acknowledgements

This material is based upon works supported by the Science Foundation Ireland under Grant No. 00/PI.1/C075, Grant No. 08/PI/I1912 and the SFI SRC project ITOBO.