else maxs(**s, t**) = t; on the contrary, mins(**s, t**) = s if sk+1 ≺ tk+1 else mins(**s, t**) = t.

It is easy to show that SSLO is a c-semi-ring and that the ordering induced by maxs on A is lexicographic ordering [Fargier *et al.*, 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 - 1, 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 P a(X) =
{U1 **. . . U**h} 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 sequence, each element corresponds to a soft constraint. The element corresponding to the constraint on P a(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 statement of the form u : x1 ≻ x2 ≻ **. . . x**i = x ≻ x|D(X)|).

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 wi. For example, in constraint weighted w3, p1 = (1, 1, 1, 1) and p2 = (1, 1, 0, 1). Given the pair of outcomes o1 = **abcd** and o2 = a
¯bcd, 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.

![0_image_0.png](0_image_0.png)

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 structure. 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 Nmin+
cand NSLO
cstand for the corresponding min+ and SLO based SC-nets respectively. From the results in the previous section, we can see that pairs of outcomes ordered by N remain ordered the same way by both Nmin+
cand NSLO
c. 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 Nmin+
c, while being strictly ordered by NSLO
c. Therefore, the (total) preference relation induced by Nmin+
cis a less brutal linearization of the partial preference relation induced by N, compared to that induced by NSLO
c. Mapping incomparability onto equality might seem more reasonable than mapping 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 usefulness 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 system 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 preferences, as allowed in soft constraints, to better approximate CP nets. Finally, we intend to use machine learning techniques to learn conditional preferences from comparisons of complete assignments.

## References

[Bistarelli *et al.*, 1996] S. Bistarelli, H. Fargier, U. Montanari, F. Ros si, T. Schiex, and G. Verfaillie. Semiring-based CSPs and valued CSPs: Basic properties and comparison. In *OverConstrained Systems*. 1996.

[Bistarelli *et al.*, 1997] S. Bistarelli, U. Montanari, and F. Rossi.

Semiring-based Constraint Solving and Optimization. *Journal* of the ACM, 44(2):201–236, 1997.

[Boutilier *et al.*, 1999] C. Boutilier, R. Brafman, H. Hoos, and D. Poole. Reasoning with Conditional Ceteris Paribus Preference Statements. In *Proc. of UAI-99*, 1999.

[Boutilier *et al.*, 2001] C. Boutilier, F. Bacchus, and R. I. Brafman.

UCP-Networks: A Directed Graphical Representation of Conditional Utilities. In *Proc. of UAI-01*, 2001.

[Boutilier *et al.*, 2002] C. Boutilier, R. Brafman, C. Domshlak, H. Hoos, and D. Poole. CP-nets: A Tool for Representing and Reasoning about Conditional *Ceteris Paribus* Preference Statements. *submitted for publication*, 2002.

[Domshlak and Brafman, 2002] C. Domshlak and R. Brafman. CPnets - Reasoning and Consistency Testing. In *Proc. of KR-02*,
pages 121–132, 2002.

[Doyle and Thomason, 1999] J. Doyle and R. H. Thomason. Background to Qualitative Decision Theory. *AI Magazine*, 20(2):55–
68, 1999.

[Doyle and Wellman, 1994] J. Doyle and M. Wellman. Representing Preferences as Ceteris Paribus Comparatives. In Proc. AAAI
Spring Symposium on Decision-Making Planning, pages 69–75, 1994.

[Fargier *et al.*, 1993] H. Fargier, J. Lang, and T. Schiex. Selecting preferred solutions in fuzzy constraint satisfaction problems. In Proc. 1st European Congress on Fuzzy and Intelligent Technologies (EUFIT), 1993.

[Hansson, 2001] S. O. Hansson. Preference Logic. In D. M. Gabbay and F. Guenthner, editors, *Handbook of Philosophical Logic*,
volume 4, pages 319–394. Kluwer, 2001.

[Lang, 2002] J. Lang. From Preference Representation to Combinatorial Vote. In *Proc. of KR-02*, 2002.

[McGeachie and Doyle, 2002] M. McGeachie and J. Doyle. Efficient utility functions for ceteris paribus preferences. In Proc.

AAAI 2002, pages 279–284, 2002.