In a large number of problems such as product con guration, automated recommendation and combinatorial auctions, decisions stem from agents subjective preferences and requirements in the presence of uncertainty. In this paper, we introduce a framework based on the belief function theory to deal with problems in group decision settings where the preferences of the agents may be uncertain, imprecise, incomplete, con icting and possibly distorted. A case study is conducted on product recommendation to illustrate the applicability and validity of the proposed framework.
In many real world applications such as product con guration, product design and automated recommendations, decision-making stems from the interplay of agents' preferences and requirements given a set of alternatives. The main task of such applications is to nd the most preferred feasible outcomes. While imperfection pervades our real life, when expressing preferences, agents are assumed to (i) act with full external information so they can certainly and precisely gure out which alternatives are better than which; (ii) act with full internal information so they are decisive about their preferences whatever the proposed set of alternatives in such a way they are able to rank the alternatives from the best to the worst, so that their beliefs are often ignored or confounded with their nal preferences. Far from being primitive, agents' preferences should depend on their beliefs about the properties and the outcomes of the alternatives especially in those situations in which an agent may only have partial and somehow uncertain information about alternatives he is required to provide his preferences over, i.e., ill-de ned alternatives. From another side, the increasing use of multi-agent applications demands for the combination and handling of possibly con icting or distorted preferences supplied by multiple agents. Once preferences are xed, decisions can be inferred given the constraints that determine which alternatives are feasible. In this context, we propose an evidential approach for group decision where agents requirements are modeled as hard constraints that should be imperatively met and their possibly imperfect (uncertain, imprecise, incomplete, indecisive, and con icting) preferences are modeled as belief-based soft constraints using the belief function theory. Soft constraints [1], equipped with a powerful solving machinery, provide an interesting way to model and reason with quantitative preference relations and constraints. However, the notion of preference had still not been properly addressed within soft constraints framework in the sense that preferences are basically used to relax over-constrained problems, to discriminate between di erent solutions or to reduce search e ort. Thus, a preference structure is not clearly de ned where some speci c induced relations are implicitly stated such as the indi erence relation or ignored such as the incomparability relation. The belief function theory [3, 10, 11] o ers a sound mathematical basis that faithfully recognizes all situations ranging from complete knowledge to complete ignorance. Moreover, by considering its Transferable Belief Model (TBM) interpretation [11], we introduce a two-level preference perspective: (i) the evidence base in which imperfect preferences are quanti ed, combined and revised; (ii) the nal preferences derived from the evidence base. In addition, the TBM allows to combine the possibly con icting preferences supplied by multiple agents. Our purpose in this paper is to bring into sharper focus the interesting interplay between beliefs, preferences and constraints when reasoning under uncertainty. We propose then a speci c Branch and Bound algorithm for solving such kind of problems. The remainder of this paper is organized as follows: Section 2 reviews related work. Some preliminaries are discussed in Section 3. We present the evidential approach and its basic components in Section 4. In Section 5, reasoning with preferences and constraints to construct solutions are discussed and a speci c branch and bound algorithm is introduced. Conclusions and further researches are drawn in Section 6. 2
While intertwined preferences and constraints is thoroughly studied in the AI literature, beliefs and preferences are rarely considered despite the multitude of approaches to preferences except some studies of the logic of preference [6, 7] investigating preference dynamics under belief change. To the best of our knowledge, in the constraint satisfaction eld, we are the rst proposing such connection between the belief function theory and soft constraints framework. Nevertheless, a variety of proposals has been introduced to extend soft constraints framework to deal with imperfect preferences. In our model, imperfect (i.e., uncertain, imprecise, incomplete, contradictory and so on) information affects the agent's evidence base and then propagated into his preferences. The work in [4] that considers incomplete soft constraint problems where some of the preferences may be allowed to be missing as long as it is feasible to nd an optimal solution, otherwise, the agent will be required to add some preferences. In this work, incompleteness is interpreted as temporary inability or unwillingness to provide preferences over some alternatives. In our approach, we consider incompleteness as a decisive undesirability to compare some alternatives with regard to the available evidence, thus, we do not require the agent to supply further information. Another proposal considers preference intervals [5] to model imprecision in preference intensity. In our work, we assume that the preference intensities are, precisely stated. However, we permit ties in the preference list to model users' indi erence about the tied alternatives. Other work that addresses uncertainty in soft constraints using the possibility theory is shown in [9] where some alternatives may be ill-de ned, i.e., one cannot decide their values. In our work, we, thoroughly, address uncertainty at two levels. First, we consider the case where the alternatives may be ill-de ned so the agent cannot express his preferences in the form of "yes/no" but he could reply "I somewhat prefer this alternative", i.e., preference intensity, or he may simply say "I do not know" to express his ignorance. Second, we consider the case where the preference relation itself may be ill-de ned, i.e., an agent's true preferences may be distorted because the agent is not decisive (hesitant) about his preferences like in matching problems or he is not willing to provide his true preferences due to privacy reasons in the case of multi-agent settings with competing agents. Thus, in our proposal, the truth intensity of the preference is evaluated to measure to what extent the provided preferences by some agent meet his true preferences. This issue is too important, especially, for critical domains such as medical or business applications. Not taking into account such issues may result in costly biased decisions and unsatis ed users as happened with Walmart UX in 2009. Further, by means of our two-level preference perspective, we have been able to, faithfully, capture the di erent preferential positions of an agent, i.e., strict preference, indi erence and incomparability. Furthermore, our evidential approach permits to cope, systematically and consistently, with all of these decision-making ingredients in a unifying frame. 3 3.1
Soft Constraints The problem of nding an optimal satisfying assignment of values to a nite set of variables, each with a nite domain, given a nite set of constraints and with respect to a nite set of agent's preferences is often referred to as constrained optimization problem. In this paper, we are interested in the two generic soft constraints frameworks, namely Semiring-based CSP (SCSP) and Valued CSP (VCSP) [1] that cover many speci c others.
In general, in a SCSP, a soft constraint or a preference relation is de ned by associating a degree from a partially ordered set with each involved alternative indicating to which extent an alternative is preferred. Moreover two operations with certain properties for comparing (+) and for combining ( ) preference degrees in order to select the best solution. Formally, a c-semiring is a tuple < A; +; ; 0; 1 > such that: A is a set, and 0; 1 2 A; + is commutative, associative, idempotent, 0 is its unit element, and 1 is its absorbing element; is commutative, associative, distributes over +, 1 is its unit element and 0 is its absorbing element. Consider the relation S over A such that a S b i a+b = b. Then: S is a partial order; + and are monotone on S ; 0 is its minimum and 1 its maximum; < A; S > is a lattice and, for all a; b 2 A; a + b = lub(a; b). Moreover, if is idempotent, then < A; S > is a distributive lattice and is its glb. Given a c-semiring S =< A; +; ; 0; 1 >, a nite set D, and an ordered set of variables V , a constraint is a pair < def; con > where con V and def : Djconj ! A.
In a VCSP, each soft constraint, i.e., the whole set of alternatives, is associated with a degree from a totally ordered set indicating to which extent the satisfaction of a given constraint is preferred. Besides one operation with certain properties for combining (~) di erent constraints. Formally, a valuation structure is de ned by (E; ~; ; >; ?) where E is a set of valuations; is a total ordering over E; >and ? are maximum and minimum elements of E given by ; ~ is a commutative, associative binary operation on E, ? is its unit element and > is its absorbing element, ~ is monotone on .
In our approach, we have adopted both approaches at di erent levels. We opt for the SCSP approach to model the preference intensities of alternatives and for the VCSP approach to model the truth intensities of the preferences using the belief function theory. 3.2
Belief Function Theory The belief function theory was rst initiated by [3] and then extended by [10]. Several interpretations have been introduced such as the well known TBM established by [11].
Basic Concepts Let be a frame of discernment representing a nite set of elementary alternatives. A basic belief assignment (bba) m is the mapping from elements of the power set 2 to [0; 1] such that:
X m( ) = 1
22
and
m(?) = 0:
(
X B;C
;B\C=
m12( ) = m1 \ m2( ) =
m1(B)m2(C); 8
:
(
BetP (A) = 1 1 m(?)
X jA \ j:m( ) j j ; 8A 2 : 4
An evidential constrained optimization problem } is de ned by the tuple (X,D,BPref,Cons), involving a nite set of variables X, their associated nite domains D and a nite set of belief-based preferences B-Pref. A belief-based preference b-pref is a belief soft constraint de ned by the tuple (S,A,B,R), where, S X is the scope of the preference delimiting the set of Example 1. (revised from [4]) A travel agency is planning Alice and Bob's honeymoon. The candidate destinations are the Maldive islands and the Caribbean, and they can decide to go by ship or by plane. For the accommodations, the couple can choose between a standard room, a suite, or a bungalow. We have X = fT r; Des; Accg where the subscripts Tr, Des, Acc stand respectively for Transport, Destination and Accommodation, with D(T r) = fp; shg (p stands for plane and sh for ship), D(Des) = fm; cg (m stands for Maldives, c for Caribbean), and D(Acc) = fr; su; bg (r stands for room, su for suite and b for bungalow). Alice and Bob have independent and distinct opinions about this decision situations given the evidence held by each of them so they have di erent preferences. However, they have a common budget constraint as they cannot afford more than $5000 for this trip. Table 1 summarizes the information supplied by the agency about the di erent costs. Beliefs Modeling Given the scope of the preference S and the related set of alternatives A, the agent's beliefs B over A are modeled in terms of a partial order D induced by the bba m on 2A to [0,1]:
D = f( 1; 2)jm(
In Example 1, The evidence bases of Alice and Bob are shown in Table 2.
By means of our two-level preference perspective, we have been able to capture all the states of the agent towards his preferences. For us, beliefs as prior preferences count as reasons for nal preferences forming and then a base for their justi cation.
{ Full certainty: take Example 1, for the preference b-pref1 in Table 2, if Alice came to learn from a best friend that the service on the ship they are planning to board on is of poor quality, she will certainly prefer traveling by plane. This is will be translated by a certain and precise belief:(p:1.0 ; sh:0.0). { Partial ignorance: for the preference b-pref1, Alice has an uncertain but precise belief about the betterness of the alternatives. For the preference bpref2, Bob has an uncertain and imprecise belief as he tied some alternatives together. { Total ignorance: for the preference b-pref1, Bob is totally ignorant about both transport alternatives. { Null support: the agent has no evidence to believe that an alternative can be somehow good or bad such as for the preference b-pref2, Alice evidence does not allow her to decide her preference for the alternative (c,p). Preference Truth Intensity In some cases, the provided preferences by some source may not re ect true ones for various reasons. An agent may be unable or unwilling to de nitely decide their preferences because of uncertainty or privacy issues. Hence, the reliability of the source providing preferences and then the truth intensities of the provided preferences should be evaluated. In spite of its importance for decision-making, the intertwining of preferences and reliability is rather unexplored in AI literature. When we can quantify the extent to which provided preferences re ect true ones, we can weaken the preference relation by discounting its corresponding evidence base using the discounting rule described in section 3.2. Given 2 [0; 1], the truth intensity of some b-pref, indicating the reliability of its source, two extreme scenarios can be met: { If = 1, the provided preferences match the true ones therefore discounting does not a ect the preference relation so that b-pref =b-pref. { If = 0, the provided preferences are totally distorted therefore discounting induces to the total ignorance case where all the provided information is discarded.
Take Example 1, the travel agency asks both of Alice and Bob to quantify their decisiveness about their provided preferences. Alice was well informed about the alternatives in question so she was more decisive than Bob who was a little bit hesitant (see Table 3). Finally, it is necessary to take this metaknowledge about preferences into account especially for those decision-making problems relying on agents' preferences such as product and service bundling, multi-item auctions, policy making and so on. Instead of distrusting, or relying on preferences no matter how distorted they are, one may want to assess their truth intensities in order to decide whether to rely on those preferences. In some critical applications, decisions should depend only on undistorted preferences. In other applications, we may tolerate distortion to some degree. Combination of Agents' Preferences After revising the provided prior preferences given the truth intensities, we can combine them using the CRC described in Section 3.2. The combined preferences of Alice and Bob are shown in Table 4. Final Preferences Deriving As the agents' prior preferences are combined, the nal preference relations are derived as a partial preorder B induced by the BetP measures over A, the set of alternatives:
B= f(a1; a2)j(BetP (a1)
BetP (a2) ^ (min(BetP (a1); BetP (a2)) > 0)g (
The derived nal preference relations from evidence bases in Example 1 are shown in Table 5. Con icting Preferences In practice, there are often several preference relations that have to be considered, each emphasizing a di erent facet of the problem being addressed. In our approach, a variable may be involved in more than one preference relation which may give rise to some con ict. A preference set B-Pref is consistent (con ict free) if and only if it has no preference b-pref i and b-pref j such that a1 iB a2 and a2 jB a1 for any alternatives a1 and a2. As the preference relation is no longer a yes-or-no issue, the notion of consistency also becomes a matter of degree. In our approach, we assume that the more two preference relations are far from each other, the more they are in con ict. Thus, we propose to de ne the con ict between two belief-based preference relations Ri and Rj using a normalized L1 metric between their respective BetP distributions as follows:
8 P(a2D(S)) jBetPiSi#S(a) BetPjSi#S(a)j
Conf (i; j) = < jD(S)j
:0
if S 6= ?;
if S = ?:
(
Returning Example 1 : To compute the con ict degree between b-pref1 and
bpref2, we have S = S1 \ S2 = fT rg, D(S) = D(T r), jD(S)j = 2, BetP1S1#S (p) =
0:8 and BetP2S2#S (p) = max(0:296; 0:0) = 0:296, BetP1S1#S (sh) = 0:2 and
BetP2S2#S (sh) = max(0:6; 0:104) = 0:6, hence Conf(
P ref ) = 1
max(conf (i; j))
(
X j=1;i6=j
(
Constraints Modeling Constraints represent limitations that winnow the set of alternatives we can opt for in a given situation.
In our approach, we separately deal with constraints and preferences differently from the common soft constraints formalism where hard and soft constraints are coupled together and handled using the same representation. We argue that for many real world applications, such as product con guration and design, automated customized recommendations, a decoupled setting is the most appealing and allows saving computation time for early discovered unfeasible outcomes. This issue is carefully discussed in [2].
In Example 1, Alice and Bob have one budget constraint C1(Pi=1::2 pi $5000), where p1 and p2 are respectively the transport and the accommodation costs. Once nal preferences and constraints are given, decisions are determinative. 5
Let S be a set of variables, we will use the notation !S to denote an outcome resulting from assigning a value to each variable in S from its equivalent domain. We will say that an outcome is complete i it is de ned on X, otherwise it is said to be partial. Consider a b-prefi de ned on the set of variables Si, (i; !Si ) = BetPi(!Si ) will denote the satisfaction degree of b-prefi by some outcome !Si 2 Ai. b-prefi is said to be satis ed by !Si , noted !Si j= b-prefi, i (i; !Si ) > 0.
Solving an evidential constrained optimization problem consists in nding a complete outcome !X , if it exists, that satis es all the constraints in Cons and is optimal with respect to the preferences in B-Pref. 5.1
Operations on Preferences Projection and Combination consider two sets of variables S = fx1; ::; xlg and Si = fxi1; ::; ximg such that Si S X. Let ! = (v1; ::; vl) be any S is deoutcome over S, the projection of !S from S to Si denoted by ! #Si ned as the outcome !Si = (vi1; ::; vim) with vik = vj if xik = xj . For exfDes;Accg= (m). Consequently, given ample, if !fDes;Accg = (m; su), then ! #fDesg a b-pref i de ned on Si and some outcome !S such that Si S X, then (i; !S ) = (i; ! #SSi ) will be the local satisfaction degree of b-pref i by !S . Hence, The global degree of joint satisfaction of the set of n belief-based preferences B-Pref de ned on the set of variables X by a given complete outcome !X is obtained by combining the local satisfaction degrees as follows: (B
P ref; !X ) =
i (i; !X ) =
i (i; ! #SXi ); 8i = 1::n
(
can be used that re ect various attitudes { Min-Combination: using the egalitarian min operator is a pessimistic approach leading to the so-called "drowning e ect", i.e., the worst local degree of satisfaction drowns all the others regardless how much the rest of the preferences are satis ed. For instance, consider two complete outcomes !X and !X0 with only two belief-based preferences, and such that !X satis es these b-pref (s) with degrees 0.5 and 1.0 while !X0 satis es them with degrees 0.5 and 0.5. Although !X is obviously strictly preferable to !X0 , the global satisfaction degree of the two outcomes is identical since min (0.5,1.0) = min (0.5,0.5). { Max-Combination: it represents an optimistic approach, but this egalitarian operator su ers from the same weakness as the Min-Combination and barely discriminates between outcomes with the same global satisfaction degree. { Product-Combination: using an utilitarian operator avoids falling in the "drowning e ect" weakness. However, it does not discriminate between outcomes fully falsifying at least one preference. { Average-Combination: it represents an utilitarian exible approach that offers more discriminating ordering than the former combinations tolerating some preferences to be falsi ed.
The suitability of each of these combination approaches depends on the application nature, where in some critical applications we need a pessimistic and strict approach that does not tolerate the falsi cation of any preference. However, in other domains, an optimistic and exible approaches are more useful.
Extension and Estimation consider two sets of variables S = fx1; ::; xlg and Si = fxi1; ::; ximg such that S Si X. Let !S = (v1; ::; vl) be any outcome over S, the extension of !S from S to Si denoted by ! "SSi is de ned as the set of outcomes Si = f(vi1; ::; vim) DS Si g. For example,if !fDesg = (m), then ! "ffDDeess;gT rg=
fDes;T rg = f(m; p); (m; sh)g. Thus, given a b-pref i de ned on Si and some outcome !S such that S Si X, then the estimated satisfaction degree of b-pref i by !S will be e(i; !S ) = M axf (i; !Si )j!Si 2 Si g. Given an evidential constrained optimization problem } (X,D,B-Pref,Cons), every feasible complete outcome with respect to Cons that jointly satis es B-Pref to a global satisfaction degree greater than 0 (whatever the used approach), is considered as a solution.
!X 2 S(P ) , !X j= Cons ^ (B
P ref; !X ) > 0 The global satisfaction degree induces a total preorder over the set of feasible outcomes, so that the best outcome will be the one that, maximally, satis es B-Pref: !X = argmax (B !X 2S(P )
P ref; !X )
(
PDBB Algorithm Commonly, when solving such constrained optimization problems, Variable-Directed Branch and Bound (VDBB) algorithm is the most widely used using two bounds: an upper bound B and a lower bound b. It incrementally builds, by assigning a variable with a value selected from its domain, outcomes prospected to be solutions, where it early on aborts every partial outcome that cannot be extended to construct a better solution than the one found so far using the bounds B and b.
At each level, instead of assigning one variable with a value from its domain, we propose to assign multiple variables with values from the preference relation covering those variables, hence, the Preference-Directed BB (PDBB). This idea has been rst introduced in [8] for the Constraint-Directed Backtracking and proved to be less costly in terms of search e ort.
Initially, the PDBB selects a minimal set of m preferences, from the set of n preferences, that covers all the model variables X, denoted B-Pref c B P ref . In Example 1, the selected preferences will be b-pref2 and b-pref3. An upper bound B that contains the global satisfaction degree of the best solution found so far and is initialized to the tolerated worst global satisfaction degree in order to discard each solution giving a satisfaction degree B. After that, at each level, a preference relation Ri related to a b-pref i 2 B-Pref c is explored by trying each alternative from its related alternatives set Ai. The current partial solution is then extended to that alternative so that variables in Si implied by the preference, not previously covered, get assigned. If the constructed partial outcome satis es all the constraints involving the assigned variables, an exact satisfaction degree of all preferences covering those variables is computed, joined with an estimation of the satisfaction degree of the rest of preferences, resulted in a lower bound b which is initialized to 1. Let the current partial outcome !S de ned on the set of variables S and let B-Prefa the set of preferences activated by the assignment and B-Prefa be the rest of B-Pref, the lower bound is computed as follows: b = (B prefa; !S ) e(B prefa; !S ) (13)
Backtracking occurs and the sub-tree below the current node is pruned if
(
In addition, by applying the heuristic "alternative giving best satisfaction degree (max-BetP) is selected rst", we ensure that best solution is early constructed and thus the search space is reduced (see Algorithm 1).
We illustrate, in Fig. 1, the PDBB execution to solve the problem described in Example 1. In this execution we adopted the product combination seen in Section 5.1.
Algorithm 1: PDBB Algorithm input : (X; Rc; Cons; S; !S; B; b) /* Rc = fRij Sm
(i=1) Si = Xg is minimal; S = ?;!S = ?; B = 0; b = 1 */ output: (!X ; B)
In Fig. 1, the outcomes having a red (X) are discarded because they violates the constraints, however, the outcomes with green (X) are aborted because they cannot lead to a better solution.
For Example 1, the best a ordable trip package for Alice and Bob is f Destination: Caribbean; Transport: Ship; Accommodation: suiteg. 6
In this paper, we have introduced an evidential approach for constrained optimization problems whereby agents, often dealing with only partial and somehow uncertain external and internal information, seek for decisions that satisfy their preferences based on their beliefs subject to certain constraints by extending the soft constraints framework to the belief function theory.
For solving such kind of problems, we have provided a speci c branch and bound algorithm which is initially proven to be less costly than the classical branch and bound algorithm. However, a detailed study of its computational properties and potential re nements should be conducted by introducing heuristics for the order of checking the preferences. More sophisticated methods from the constraint satisfaction machinery could be easily extended to our approach.
Further research targets exploiting the expressiveness o ered by the evidential approach in order to enlarge the scope of the issues that can be tackled such as prioritized preferences. Preference dynamics can also be studied using the belief revision process. We can address the bipolar preferences exploiting the negative and positive belief notions. We also intend to introduce the weak preference relation using thresholds. Finally, we plan to explore how our model can be employed in decision support applications like recommender systems, con guration problems and combinatorial auctions.