Reasoning about soft constraints and conditional preferences: complexity results and approximation techniques

1 Introduction and Motivation

Representing and reasoning about preferences is an area of increasing interest in theoretical and applied AI. In many real life problems, we have both hard and soft constraints, as well as qualitative conditional preferences. For example, in a product configuration problem, the producer may have hard and soft constraints, while the user has a set of con­ ditional preferences. Until now, there has been no single formalism which allows all these different kinds of informa­ tion to be specified efficiently and reasoned with effectively. For example, soft constraint solvers [Bistarelli eta!., 1997; Schiex eta!. , 1995] are most suited for reasoning about the hard and soft constraints, while CP-nets [Boutilier et a!., 1999] are most suited for representing qualitative conditional preference statements. In this paper, we exploit a connec­ tion between these two approaches, and define a framework based on both CP-nets and soft constraints which can effi­ ciently handle both constraints and preferences.

*This research was partially funded by AFOSR, grant F496200l-l-0076 (Intelligent Information Systems Institute, Cornell Uni­ versity) and F49620-0l-l-0361 (MURI grant on Cooperative Con­ trol of Distributed Autonomous Vehicles in Adversarial Environ­ ments), DARPA, F30602-00-2-0530 (Controlling Computational Cost: Structure, Phase Transitions and Randomization) and F3060200-2-0558 (Configuring Wireless Transmission and Decentralized Data Processing for Generic Sensor Networks), the Italian MIUR projects NAPOLI and COVER, the ASI (Italian Space Agency) project ARISCOM and Science Foundation Ireland.

Soft constraints [Bistarelli eta!., 1997; Schiex eta!., 1995] are one of the main methods for dealing with preferences in constraint optimization. Each assignment to the variables of a constraint is annotated with a level of its desirability, and the desirability of a complete assignment is computed by a com­ bination operator applied to the "local" preference values. Whilst soft constraints are very expressive, and have a power­ ful computational machinery, they are not good at modeling and solving the sort of conditional preference statements that occur in the real world. Moreover, soft constraints are based on quantitative measures of preference, which tends to make preference elicitation more difficult.

Qualitative user preferences have been widely studied in decision-theoretic AI [Doyle and Thomason, 1999]. Of par­ ticular interest are CP-nets [Boutilier et a/., 1999]. These model statements of qualitative and conditional preference such as "I prefer a red dress to a yellow dress", or "If the car is convertible, I prefer a soft top to a hard top". These are interpreted under the ceteris paribus (that is, "all else being equal") assumption. Preference elicitation in such a framework is intuitive, independent of the problem con­ straints, and suitable for naive users. However, the Achilles heel of CP-nets and other sophisticated qualitative prefer­ ence models [Lang, 2002] is the complexity of reasoning with them [Domshlak and Brafman, 2002; Boutilier eta/., 2002].

Motivated by a product configuration application [Sabin and Weigel, 1998], we have developed a framework to reason simultaneously about qualitative conditional preference state­ ments and hard and soft constraints. In product configuration, the producer has hard (e.g., component compatibility) and soft (e.g., supply time) constraints, while the customer has preferences over the product features. We first investigate the complexity of reasoning about qualitative preference state­ ments, addressing in particular preferential consistency. To tackle the complexity of preference reasoning, we then intro­ duce two approximation schemes based on soft constraints.

To the best of our knowledge, this work provides the first connection between the CP-nets and soft constraints machin­ ery. In addition, for product configuration problems or any problem with both hard and soft quantitative constraints as well as qualitative conditional preferences, this framework lets us treat the three kinds of information in a unifying en­ vironment. Finally, we compare the two approximations in terms of both expressivity and complexity.

2 Formalisms for Describing Preferences

2.1 Soft constraints

There are many formalisms for describing soft constraints. We use the c-semi-ring formalism [Bistarelli et al., 1997], which is equivalent to the valued-CSP formalism when total orders are used [Bistarelli et a!., 1996], as this generalizes many of the others. In brief, a soft constraint associates each instantiation of its variables with a value from a partially or­ dered set. We also supply operations for combining ( x) and comparing(+) values. A semi-ring is a tuple (A,+, x, 0, 1) such that: A is a set and 0, 1 E A; + is commutative, asso­ ciative and 0 is its unit element; x is associative, distributes over+, 1 is its unit element and 0 is its absorbing element. A c-semi-ring is a semi-ring (A,+, x, 0, 1) in which + is idempotent, 1 is its absorbing element and x is commutative.

Let us consider the relation :::; over A such that a :::; b iff a + b = b. Then :::; is a partial order, + and x are mono­ tone on :::;, 0 is its minimum and 1 its maximum, (A,:::;) is a complete lattice and, for all a, b E A, a+ b = lub(a, b). Moreover, if x is idempotent: + distributes over x; (A, :::;) is a complete distributive lattice and x its glb. Informally, the relation :::; compares semi-ring values and constraints. When a :::; b, we say that b is better than a. Given a semi-ring S = (A,+, x, 0, 1), a finite set D (variable domains) and an ordered set of variables V, a constraint is a pair ( def , con) where con ~ V and def : nlconl -+ A. A constraint spec­ ifies a set of variables, and assigns to each tuple of values of these variables an element of the semi-ring.

A soft constraint satisfaction problem (SCSP) is given by a set of soft constraints. For exam­ ple, a classical CSP is an SCSP with the c-semi­ ring ScsP = ({false,true},V,I\,jalse,true), a fuzzy CSP [Schiex, 1992] is an SCSP with the c­ semi-ring SFcSP ([0, l],max,min,O, 1), and probabilistic and weighted CSPs are SCSPs with the c-semi-rings Sprob ([O,l],max,x,O,l) and Sweight = (n, min,+, 0, +oo), respectively. A solu­ tion to an SCSP is a complete assignment to its variables. The preference value associated with a solution is obtained by multiplying the preference values of the projections of the solution to each constraint. One solution is better than another if its preference value is higher in the partial order. Finding an optimal solution for an SCSP is an NP-complete problem. On the other hand, given two solutions, checking whether one is preferable is easy: we compute the semi-ring values of the two solutions and compare the resulting values.

2.2 CP-nets

Soft constraints are the main tool for representing and rea­ soning about preferences in constraint satisfaction problems. However, they require the choice of a semi-ring value for each variable assignment in each constraint. They are therefore a quantitative method for expressing preferences. In many ap­ plications, it is more natural for users to express preferences via generic qualitative (usually partial) preference relations over variable assignments. For example, it is often more in­ tuitive for the user to say "I prefer red wine to white wine", rather than "Red wine has preference 0. 7 and white wine has preference 0.4". Of course, the former statement provides less information, but it does not require careful selection of preference values to maintain consistency. Moreover, soft constraints do not naturally represent conditional preferences, as in "If they serve meat, then I prefer red wine to white wine". It is easy to see that both qualitative statements and conditions are essential ingredients in many applications.

CP-nets [Boutilier et al., 1999] are a graphical model for compactly representing conditional and qualitative prefer­ ence relations. They exploit conditional preferential indepen­ dence by structuring a user's preferences under the ceteris paribus assumption. Informally, CP-nets are sets of condi­ tional ceteris paribus (CP) preference statements. For in­ stance, the statement "/prefer red wine to white wine if meat is served." asserts that, given two meals that differ only in the kind of wine served and both containing meat, the meal with a red wine is preferable to the meal with a white wine. Many philosophers (see [Hansson, 2001] for an overview) and AI researchers [Doyle and Wellman, 1994], have argued that most of our preferences are of this type.

CP-nets bear some similarity to Bayesian networks, as both utilize directed acyclic graphs where each node stands for a domain variable, and assume a set of fea­ tures F = {X1 , ... , Xn} with finite, discrete domains V(Xl), ... , V(Xn) (these play the same role as variables in soft constraints). During preference elicitation, for each fea­ ture Xi, the user is asked to specify a set of parent features Pa(Xi) that can affect her preferences over the values of Xi . This information is used to create the graph of the CP-net in which each node Xi has Pa(Xi) as its immediate prede­ cessors. Given this structural information, the user is asked to explicitly specify her preference over the values of Xi for each complete assignment on Pa(Xi), and this preference is assumed to take the form of total [Boutilier et al., 1999] or partial [Boutilier et al., 2002] order over V(X). These conditional preferences over the values of Xi are annotated with the node Xi in the CP-net. For example, consider a CP­ net with the graph given in Figure 1, and with the preference statements as follows: a >- a, b >- b, (a 1\ b) v (a 1\ b) : c >- c, (a 1\ b) V (a 1\ b) : c >- c, c: d >- d, c: d >-d. Here, statement a >- a represents the unconditional preference of the user for A = a over A = a, while statement c : d >- d represents that the user prefers D = d to D = d, given that C = c.

Several types of queries can be asked about CP-nets. First, given a CP-net N, one might be interested in finding an op­ timal assignment to the features of N. For acyclic CP-nets, such a query is answerable in linear time [Boutilier et al., 1999]. Second, given a CP-net N and a pair of complete assignments a and (3, one might be interested in determin­ ing whether a >- (3, i.e. a is preferred to (3. Unfortunately, this query is NP-hard even for acyclic CP-nets [Domshlak and Brafman, 2002] though some tractable special cases do exist.

3 Consistency and Satisfiability

Given a set of preference statements !1 extracted from a user, we might be interested in testing consistency of the induced preference relation. In general, there is no single notion of preferential consistency [Hansson, 2001]. In [Boutilier eta!., 1999], a CP-net N was considered consistent iff the partial or­ dering>- induced by N is asymmetric, i.e. there exist at least one total ordering of the outcomes consistent with >-. How­ ever, in many situations, we can ignore cycles in the prefer­ ence relation, as long as these do not prevent a rational choice, i.e. there exist an outcome that is not dominated by any other outcome. In what follows, we refer to this as satisfiability 1 · It is easy to see that satisfiability is strictly weaker than asym­ metry, and that asymmetry implies satisfiability. We will con­ sider two cases: When the set !1 of preference statements in­ duces a CP-net and, more generally, when preferences can take any fonn (and may not induce a CP-net).

When !1 defines an acyclic CP-net, the partial order in­ duced by !1 is asymmetric [Boutilier et a!., 1999]. How­ ever, for cyclic CP-nets, asymmetry is not guaranteed. In the more general case, we are given a set !1 of conditional preference statements without any guarantee that they define a CP-net. Let the dependence graph of !1 be defined sim­ ilarly to the graphs of CP-nets: the nodes stand for prob­ lem features, and a directed arc goes from X; to Xi iff !1 contains a statement expressing preference on the values of Xi conditioned on the value of X;. For example, the set 0 = {a : b >- b, a 1\ c : b >- b} does not induce a CP­ net (the two conditionals are not mutually exclusive), and the preference relation induced by n is not asymmetric, despite the fact that the dependence graph of n is acyclic.

Note that while asymmetry implies satisfiability, the re­ verse does not hold in general. For example, the set !1 above is not asymmetric, but it is satisfiable (the assignment acb is undominated). Given such a satisfiable set of statements, we can prompt the user with one of the undominated assignments without further refinement of its preference relation. Theo­ rem 1 shows that, in general, determining satisfiability of a set of statements is NP-complete. On the other hand, even for CP-nets, determining asymmetry is not known to be in NP [Domshlak and Brafman, 2002].

Theorem 1 SATISFIABILITY of a set of conditional prefer­ ence statements !1 is NP-comp/ete.

Proof: Membership in NP is straightforward, as an assign­ ment is a polynomial-size witness that can be checked for non-dominance in time linear in the size of!1. To show hard­ ness, we reduce 3-SAT to our problem: Given a 3-cnfformula F, for each clause (x V y V z) E F we construct the condi­ tional preference statement: x 1\ y : z >- z. This set of conditional preferences is satisfiable iff the original original formula F is satisfiable. D

1 In preference logic [Hansson, 200 I] , these notions of 'consis­ tency as satisfi ability" and 'consistency as asymmetry" correspond to the notions of eligibility and restrictable eligibility, respectively. However, we will use the former terms as they seem more intuitive.

While testing satisfiability is hard in general, Theorem 2 presents a wide class of statement sets that can be tested for satisfiability in polynomial time.

Theorem 2 A set of conditional preference statements !1, whose dependency graph is acyclic and has bounded node in-degree can be tested for satisfiability in polynomial time.

Proof: The proof is constructive, and the algorithm is as follows: First, for each feature X E V, we construct a ta­ ble Tx with an entry for each assignment 1r E V(Pa(X)), where each entry Tx[1r] contains all the values of X that are not dominated given !1 and 7f . Subsequently, we remove all the empty entries. For example, let A, B and C be a set of boolean problem features, and let n = { c >- c, a : b >- b, a 1\ c : b >- b}. The corresponding table will be as follows:

I

I

Observe that the entry TB[a 1\ c] has been removed, since, given a 1\ c, b and b are dominated according to the statements a 1\ c : b > b and a : b > b, respectively. Since the in-degree of each node X in the dependence graph of !1 is bounded by a constant k (i.e. jPa(X) I ~ k), these tables take space and can be constructed in time O(n2k). Given such tables for all the features in V, we traverse the dependence graph of !1 in a topological order of its nodes, and for each node X being processed we remove all the entries in Tx that are not "sup­ ported" by (already processed) Pa(X) : An entry Tx[1r] is not supported by Pa(X) ifthere exists a feature Y E Pa(X) such that the value provided by 1r to Y appears in no entry of Ty . For instance, in our example, the rows corresponding to a 1\ c and a 1\ c will be removed, since c does not appear in the (already processed) table of C. Now, if the processing of a feature X results in Tx = 0, then !1 is not satisfiable. Oth­ erwise, any assignment to V consistent with the processed tables will be non-dominated with respect ton. 0

Note that, for sets of preference statements with cyclic de­ pendence graphs, SATISFIABILITY remains hard even if the in-degree of each node is bounded by k 2:: 6, since 3-SAT re­ mains hard even if each variable participates in at most three clauses of the formula the proof of Theorem 1). However, when at most one condition is allowed in each preference statement, and the features are boolean, then SATISFIABIL­ ITY can be reduced to 2-SAT, and thus tested in polynomial time. Further study of additional tractable cases is clearly of both theoretical and practical interest.

4 Approximating CP-nets with Soft Constraints

In addition to testing consistency and determining preferen­ tially optimal outcomes, we can be interested in the preferen­ tial comparison of two outcomes. Unfortunately, determining dominance between a pair of outcomes with respect to a set of qualitative preferential statements under the ceteris paribus assumption is PSPACE-complete in general [Lang, 2002], and is NP-hard even for acyclic CP-nets [Domshlak and Brafman, 2002]. However, given a set 0 of preference statements, in­ stead of using a preference relation >- induced by 0, one can use an approximation » of>-, achieving tractability while sacrificing precision to some degree. Clearly, different ap­ proximations » of >- are not equally good, as they can be characterized by the precision with respect to >-, time com­ plexity of generating», and time complexity of comparing outcomes with respect to » . In addition, it is vital that » faithfully extends >- (i.e. a >- f3 should entail a » /3). We call this information preserving. Another desirable property of approximations is that of preserving the ceteris paribus property (we call this the cp-condition for short).

For acyclic CP-nets, two approximations that are informa­ tion preserving have been introduced, both comparing out­ comes in time linear in the number of features. The first is based on the relative position of the features in the CP­ net graph [Boutilier et al., 2002]. This approximation does not require any preprocessing of the CP-net. However, it is problematic when there are hard constraints. The sec­ ond, based on UCP-nets [Boutilier et al. , 2001], can be used as a quantitative approximation of acyclic CP-nets. UCP­ nets resemble weighted CSPs, and thus they can be used in constraint optimization using the soft constraints machin­ ery. However, generating UCP-nets is exponential in the size of CP-net node's Markov family 2 , and thus in the CP-net node out-degree. An additional related work is described in [McGeachie and Doyle, 2002], where a numerical value func­ tion is constructed using graph-theoretic techniques by exam­ ining the graph of the preference relation induced by a set of preference statements. Note that this framework is also com­ putationally hard, except for some special cases.

Here we study approximating CP-nets via soft constraints (SCSPs). This allows us to use the rich machinery under­ lying SCSPs to answer comparison queries in linear time. Moreover, this provides us a uniform framework to combine user preferences with both hard and soft constraints. Given an acyclic CP-net, we construct a corresponding SCSP in two steps. First, we build a constraint graph, which we call SC-net. Second, we compute the preferences and weights for the constraints in the SC-net, and this computation de­ pends on the actual semi-ring framework being used. Here we present and discuss two alternative semi-ring frameworks, based on min+ and SLO (Soft constraint Lexicographic Or­ dering) semi-rings, respectively. In both cases, our compu­ tation of preferences and weights ensures information pre­ serving and satisfies the cp-condition. We illustrate the con­ struction of the SCSP using the example in Figure 2, which continues our running example from Figure 1.

Given a CP-net N, the corresponding SC-net Ne has two types of nodes: First, each feature X E N is represented in Ne by a node Vx that stands for a SCSP variable with V(Vx) = V(X) . Second, for each feature X E N, such that IPa(X)I ~ 2, we have a node VPa(X) E Ne, with V(VPa(X)) = II YEPa(X) V(Y) . Edges in Ne correspond to hard and soft constraints, where the latter are annotated with weights. Each node Vx corresponding to an "independent feature" X E N has an incoming (source-less) soft constraint edge (e.g., see VA and VB) . For each node Vx corresponding to a "single-parent" feature X E N with Pa(X) = {Y}, we have a soft constraint edge between X andY (e.g., see Vv) . Finally, for each node Vx such that IPa(X)I ~ 2, we have (i) hard constraint edges between VPa(X) and each Y E Pa(X) to ensure consistency (e.g., the edges between VA,B and both VA and VB), and (ii) a soft constraint edge between VPa(X) and Vx (e.g. , the edge between VA,B and Vc).

2 Marlwv family of a node X contains X , its parents and children, and the parents of its children.

To assign preferences to variable assignments in each soft constraint, each soft constraint c (between VPa(X) and Vx) is associated with two items: We , a real number which can be interpreted as a weight (will be defined in the next section), and P e = {Pt, ... ,PID(Vx)l}, a set ofreals which can be in­ terepreted as "quantitative levels of preference". We will see in the next section how to generate the preference for each assignment to the variables of c, depending on the chosen semiring. In any case, each preference will be obtained by combining (via multiplication over naturals) the weight of the constraint We and one of the elements of P e .

4.1 Weighted soft constraints

The weighted SCSP is based on the min+ sem1-nng SwcsP = (R+, min,+, +oo, 0). We assign preferences using real positive numbers (or penalties) and prefer assign­ ments with smaller total penalty (i .e. the sum of all local penalties). In a soft constraint c on VPa(X) and Vx, there are IV(Vx )I penalties. Without loss of generality, we as­ sume they range between 0 and IV(Vx )I - 1, that is, p1 = 0, ... ,PD(Vx )I = IV(Vx) I - 1. In our example, since all vari­ ables are binary, there are only two penalties i:e., p1 = 0 and p2 = 1, in all the constraints.

To ensure the cp-condition, similar to [Boutilier et al., 2001], we need to ensure that each variable dominates its chil­ dren. We therefore set the minimum penalty on a variable to be greater than the sum of the maximum penalties of the chil­ dren. In Figure 3 we show the pseudocode for the algorithm to compute the weights. In this code, w(Vx) represents the weight of the soft constraint c between VPa(X) and Vx .

Considering our example, let { D, C, B, A} be the reverse topological ordering obtained in line 2. Therefore, the first soft constraint to be processed is the one between V c and V D . Since D has no children inN, in line 5 we assign w(Vv) to

1. Next, we process the soft constraint between VA,B and Vc : Vn is the only child of Vc, hence w(Vc) = w(Vn) x V(Vn) = 1 x 2 = 2. Subsequently, since Vc is the only child of both VA and VB, we assign w(VA) = w(VB) = w(Vc) x IV(Vc)l = 2 x 2 = 4. _

Now, consider two outcomes o1 = abed and 02 = abed. The total penalty of o1 is (w(VA) x pi)+ (w(VB) x pi)+ (w(Vc) x pi)+ (w(Vn) x pi) = 0, since P1 = 0, while the total penalty of 02 is ( w(VA) x pi) + ( w(VB) x P2) + (w(Vc) xp2 ) + (w(Vn) xpl) = (4 x 1) + (2 x 1) = 6 since P2 = 1. Therefore, we can conclude that o1 is better than 02 since min(O, 6) = 0.

We now prove that our algorithm for weight computation ensures the cp-condition on the resulting set of soft con­ straints, and this also implies preserving the ordering infor­ mation with respect to the original CP-net.

Theorem 3 The SC-net based weighted SCSP Nc, generated from an acyclic CP-net N, is an information preserving ap­ proximation of N, i.e. for each pair of outcomes a, j3 we have a >- /3 =} a >min+ /3.

Proof: Due to the CP-net semantics, it is enough to show that, for each variable X E N, each assignment u on Pa(X), and each pair of values X1, X2 E V(X), if CP-net specifies that u : x1 >- x2, then we have x1 uy >min+ x2uy, for all assignments y on Y = V - {{X} U Pa(X)} . By definition, X1 uy >min+ X2UY iff E.es p'((xtuY)J.l < L:.esP'((x2uY) I.l· where S is the set of soft constraints of Nc and notation (x1uy)l.stands for the projection on the outcome on constraint s. The con­ straints on which x1uy differs from x2uy are: constraint c on VPa(X) and Vx, and all the constraints t; E T on VPa(B;) and VB; such that X E Pa(B;) (in what follows, we denote the children of X by B = {VB 1 , · · · , VB,.}) . Thus, we can rewrite the above inequality as p'((xtuy) 1 e) + E,; ET p'((xtuY)I,;) < p'((x2uy)lcl + E,;ET p'((x2uy)1, ,) By con­ struction of Nc we have p'(,..e(xtuy) 1 e) = we x p(xtu) < p'({x2UY)JJ = We X p(x2u) and thus X1 uy >min+ X2UY iff Wep(X2 U) - WeP(Xt u) > L:t ·ET p' ({Xt uy)lt ·) - L:t ·ET p' ({x2uy)lt·) In particular, this will hold if we(min ·.· :ev(x) l;(xu) -p(x'u)i) ·> Et;ET Wt; (max ·.·· ,z,blp{x' zb) - p(xzb) I) where z is the assign­ ment to all parents of Bother than X. Observe, that the maxi­ mum in the right term is obtained whenp(x'zb) = IV(B)I-1 andp(xzb) = 0. On the other hand, minx,x'E'D(x)IP(x'u)­ p(xu)l = 1. In other words: We> Lt;ETwt;(IV(B;)I- 1)

must hold. But this is ensured by the algorithm, setting (in line7)wc = Lt;ETwt;(IV(B;)I. D

Theorem 4 (Complexity) Given an acyclic CP-net N with the node in-degree bounded by a constant, the construction of the corresponding SC-net based weighted SCSP Nc is poly­ nomial in the size of N .

Proof: If the CP-net has n nodes then the number of vertices V of the derived SC-net is at most 2n. In fact, in the SC-net a node representing a feature appears at most once and there is at most one node representing its parents. If the number of edges of the CP-net is e, then the number of edges E in the SC-net (including hard and soft edges) is at most e + n, since each edge in the CP-net corresponds to at most one constraint, and each feature in the CP-net generates at most one new soft constraints. Topological sort can be performed in O(V +E), that is, 0(2n + e + n) = O(e + n). Then, for each node, that is, O(V) times, at most V children must be checked to compute the new weight value, leading to a number of checks which is O(V 2 ) = O(n 2 ). Each check involves checking a number of assignments which is exponential in the number of parents of a node. Since we assume that the number of parents of a node is limited by a constant, this exponential is still a constant. Thus the total time complexity is O(V 2 ) (or O(n 2 ) if we consider the size of the CP-net). D

Let us compare in more details the original preference re­ lation induced by the CP-net and this induced by its min+ semi-ring based SC-net. The comparison is summarized in the following table, where "' denotes incomparability. Notice that Theorem 3 shows that ordering information is preserved by the approximation.

I

I

II

I

Since the min+ approximation is a total ordering, it is a lin­ earization of the original partial ordering. In compensation, however, preferential comparison is now linear time.

4.2 SLO soft constraints

We also consider a different semi-ring to approximate CP­ nets via soft constraints. The SLO c-semi-ring is defined as follows: SsLo = (A, max8 , min8 ,MAX,O), where A is the set of sequences of n integers from 0 to MAX, MAX is the se­ quence of n elements all equal to MAX, and 0 is the sequence of n elements all equal to 0. The additive operator, max8 and the multiplicative operator, mins are defined as follows: given s = s1 · · · Sn and t = t 1 · · · tn, s; = t;, i = 1 :::; k and Sk+1 -:f. tk+1, then max8 (s, t) = s if Sk+l >- tk+l else max8 (s, t) = t; on the contrary, min8 (s , t) = s if Sk+l -< tk+l else min.(s, t) = t.

It is easy to show that SsLo is a c-semi-ring and that the ordering induced by max8 on A is lexicographic ordering [Fargier eta/., 1993 ]. To model a CP-net as a soft constraint problem based on SsLo, we set MAX equal to the cardinality of the largest domain - I, and n equal to the number of soft constraints of the SC net. All the weights of the edges are set to 1. Considering the binary soft constraint on Pa(X) =

{U1 ... Uh} and X, a tuple of assignments (u1, ... , uh, x) will be assigned, as preference, the sequence of n integers: (MAX, MAX, ... , MAX - i + 1, ... , MAX). In this se­ quence, each element corresponds to a soft constraint. The element corresponding to the constraint on Pa(X) and X is MAX - i + 1, where i is the distance from the top of the total order of the value x (i.e. we have a preference state­ ment of the form u : x1 >- x2 >- ... x; = x >- xiD(X)I). In the example shown in Figure 2, all the preferences will be lists of four integers (0 and 1 ), where position i corresponds to constraint with weight w;. For example, in constraint weighted w3, P1 = (1, 1, 1, 1) and P2 = (1, 1, 0, 1). Given the pair of outcomes o1 = abed and 02 = abed, the global preference associated with o1 is (1, 1, 1, 1), since it does not violate any constraint, while the preference associated with o2 is mins{(1, 1, 1, 1), (1, 0, 1, 1), (1, 1, 0, 1), (1, 1, 1, 1)} = (1, 0, 1, 1). We can conclude that o1 is better than o2 .

Similar to the comparison performed for min+ semi-ring, the following table compares the preference relation induced by the SLO semiring and that induced by the CP-net.

Note that the SLO model both preserves information and ensures the cp-condition. The proof of this is straightforward and is omitted due to lack of space. The SLO model, like the weighted model, is very useful to answer dominance queries as it inherits the linear complexity from its semi-ring struc­ ture. In addition, the sequences of integers show directly the "goodness" of an assignment, i.e. where it actually satisfies the preference and where it violates it.

4.3 Comparing the two approximations

Given an acyclic CP-net N, let Nr:in+ and N~LO stand for the corresponding min+ and SLO based SC-nets respec­ tively. From the results in the previous section, we can see that pairs of outcomes ordered by N remain ordered the same way by both Nr:in+ and N~LO. On the other hand, pairs of outcomes incomparable in N are distributed among the three possibilities (equal or ordered in one the two ways) in Nr:in+, while being strictly ordered by N~Lo. Therefore, the (total) preference relation induced by N'{;'in+ is a less bru­ tal linearization of the partial preference relation induced by N, compared to that induced by N~Lo. Mapping incompa­ rability onto equality might seem more reasonable than map­ ping it onto an arbitrary strict ordering, since the choice is still left to the user. We might conclude that the min+ model is to be preferred to the SLO model, as far as approximation is concerned. However, maximizing the minimum reward, as in any fuzzy framework [Schiex, 1992], has proved its useful­ ness in problem representation. The user may therefore need to balance the linearization of the order and the suitability of the representation provided.

5 Future Work

We plan to use our approach in a preference elicitation sys­ tem in which we guarantee the consistency of the user preferences, and guide the user to a consistent scenario. Morover, we also plan to exploit the use of partially ordered prefer­ ences, as allowed in soft constraints, to better approximate CP nets. Finally, we intend to use machine learning tech­ niques to learn conditional preferences from comparisons of complete assignments.