=Paper=
{{Paper
|id=Vol-2157/paper6
|storemode=property
|title=Evidential Group Decision Making Model with Belief-Based Preferences
|pdfUrl=https://ceur-ws.org/Vol-2157/paper6.pdf
|volume=Vol-2157
|authors=Aouatef Rouahi,Kais Ben Salah,Khaled Ghedira
|dblpUrl=https://dblp.org/rec/conf/cade/RouahiSG18
}}
==Evidential Group Decision Making Model with Belief-Based Preferences==
https://ceur-ws.org/Vol-2157/paper6.pdf
Evidential Group Decision Making Model with
Belief-Based Preferences
Aouatef Rouahi1[0000−0001−8293−9991] , Kais Ben Salah2[0000−0003−4309−9226] ,
and Khaled Ghedira3[0000−0001−5719−1598]
1
ISG of Tunis, Tunis University, Tunisia rouahi.aouatef@hotmail.fr
2
FCIT, University of Jeddah, SA kaisuria@yahoo.fr
3
Central University, Tunisia khaled.ghedira@isg.rnu.tn
Abstract. In a large number of problems such as product configuration,
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,
conflicting and possibly distorted. A case study is conducted on prod-
uct recommendation to illustrate the applicability and validity of the
proposed framework.
Keywords: Preference · Constraints · Uncertainty · Group decision ·
Belief Function Theory · Soft constraints.
1 Introduction
In many real world applications such as product configuration, 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 find the most preferred feasible outcomes. While imper-
fection pervades our real life, when expressing preferences, agents are assumed
to (i) act with full external information so they can certainly and precisely figure
out which alternatives are better than which; (ii) act with full internal informa-
tion 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
final preferences. Far from being primitive, agents’ preferences should depend
on their beliefs about the properties and the outcomes of the alternatives espe-
cially in those situations in which an agent may only have partial and somehow
uncertain information about alternatives he is required to provide his prefer-
ences over, i.e., ill-defined alternatives. From another side, the increasing use of
multi-agent applications demands for the combination and handling of possibly
conflicting or distorted preferences supplied by multiple agents. Once preferences
are fixed, decisions can be inferred given the constraints that determine which
alternatives are feasible. In this context, we propose an evidential approach for
2 A. Rouahi et al.
group decision where agents requirements are modeled as hard constraints that
should be imperatively met and their possibly imperfect (uncertain, imprecise,
incomplete, indecisive, and conflicting) 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 rea-
son with quantitative preference relations and constraints. However, the notion
of preference had still not been properly addressed within soft constraints frame-
work in the sense that preferences are basically used to relax over-constrained
problems, to discriminate between different solutions or to reduce search effort.
Thus, a preference structure is not clearly defined where some specific induced
relations are implicitly stated such as the indifference relation or ignored such as
the incomparability relation. The belief function theory [3, 10, 11] offers a sound
mathematical basis that faithfully recognizes all situations ranging from com-
plete knowledge to complete ignorance. Moreover, by considering its Transferable
Belief Model (TBM) interpretation [11], we introduce a two-level preference per-
spective: (i) the evidence base in which imperfect preferences are quantified,
combined and revised; (ii) the final preferences derived from the evidence base.
In addition, the TBM allows to combine the possibly conflicting 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 specific Branch and Bound algo-
rithm 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 Sec-
tion 4. In Section 5, reasoning with preferences and constraints to construct
solutions are discussed and a specific branch and bound algorithm is introduced.
Conclusions and further researches are drawn in Section 6.
2 Related Work
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 field, we are the first proposing such
connection between the belief function theory and soft constraints framework.
Nevertheless, a variety of proposals has been introduced to extend soft con-
straints framework to deal with imperfect preferences. In our model, imperfect
(i.e., uncertain, imprecise, incomplete, contradictory and so on) information af-
fects 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 find an
optimal solution, otherwise, the agent will be required to add some preferences.
In this work, incompleteness is interpreted as temporary inability or unwilling-
ness to provide preferences over some alternatives. In our approach, we consider
Evidential Group Decision Making Model with Belief-Based Preferences 3
incompleteness as a decisive undesirability to compare some alternatives with
regard to the available evidence, thus, we do not require the agent to supply fur-
ther 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’ indifference 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-defined, 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-defined 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-defined, i.e., an agent’s true preferences may be distorted because
the agent is not decisive (hesitant) about his preferences like in matching prob-
lems 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 applica-
tions. Not taking into account such issues may result in costly biased decisions
and unsatisfied 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 different preferential positions of an agent, i.e., strict preference, indifference
and incomparability. Furthermore, our evidential approach permits to cope, sys-
tematically and consistently, with all of these decision-making ingredients in a
unifying frame.
3 Preliminaries
3.1 Soft Constraints
The problem of finding an optimal satisfying assignment of values to a finite set
of variables, each with a finite domain, given a finite set of constraints and with
respect to a finite 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 specific others.
In general, in a SCSP, a soft constraint or a preference relation is defined 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 ∈ A; + is commutative, asso-
ciative, 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
4 A. Rouahi et al.
absorbing element. Consider the relation ≤S over A such that a ≤S b iff 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 ∈ 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 finite set D, and an or-
dered set of variables V , a constraint is a pair < def, con > where con ⊆ V and
def : D|con| −→ A.
In a VCSP, each soft constraint, i.e., the whole set of alternatives, is asso-
ciated 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 (~) different constraints. Formally, a valuation struc-
ture is defined 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 different 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 first initiated by [3] and then extended by [10].
Several interpretations have been introduced such as the well known TBM es-
tablished by [11].
Basic Concepts Let Θ be a frame of discernment representing a finite 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 and m(∅) = 0. (1)
θ∈2Θ
The basic belief mass (bbm) m(θ), assigned to some subset θ of Θ, is a positive
finite amount of support that is derived from the available pieces of evidence and
exactly given to the set θ and not to any specific subset of θ by lack of evidence.
Discounting The discounting procedure allows taking into account the reliabil-
ity of the source providing the bba m. It consists in weighting the beliefs yielded
by each source using a discounting coefficient, so that, the smaller the reliability,
the stronger the discounting. Let m be a bbm given by the source S on Θ and
let α ∈ [0, 1] be the confidence degree allocated to the source S. If the source
is not fully reliable, the provided bba is discounted into a new weaker and less
informative one denoted mα , where every lost mass is reassigned to Θ as total
Evidential Group Decision Making Model with Belief-Based Preferences 5
ignorance: (
mα (θ) = α.m(θ), ∀θ ⊂ Θ
(2)
mα (Θ) = (1 − α) + α.m(Θ).
Evidence combination The evidence of two independent bbas m1 and m2
induced from two distinct sources and defined on the same frame of discernment
Θ could be combined to form a single bba m12 on Θ via the TBM Conjunctive
Rule of Combination (CRC):
X
m12 (θ) = m1 ∩ m2 (θ) = m1 (B)m2 (C); ∀θ ⊆ Θ. (3)
B,C⊆Θ,B∩C=θ
Decision Making Given a set of alternatives Θ and a given bba m, we want
to establish an ordering over Θ based on m. Many decision-making criteria have
been developed in the literature. In our approach, we opt for decision-making
based on maximum of pignistic probability (BetP ) that offers a compromise
between pessimistic and optimistic strategies, where higher probability degree
indicates more preferred alternative. Hence, The bba m is reformed to a subjec-
tive probability measure BetP as follows:
1 X |A ∩ θ|.m(θ)
BetP (A) = ; ∀A ∈ Θ. (4)
1 − m(∅) |θ|
θ⊆Θ
4 Evidential Constrained Optimization
An evidential constrained optimization problem ℘ is defined by the tuple (X,D,B-
Pref,Cons), involving a finite set of variables X, their associated finite domains
D and a finite set of belief-based preferences B-Pref. A belief-based preference
b-pref is a belief soft constraint defined 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 hon-
eymoon. 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 = {T r, Des, Acc} where the subscripts Tr, Des, Acc stand respectively for
Transport, Destination and Accommodation, with D(T r) = {p, sh} (p stands
for plane and sh for ship), D(Des) = {m, c} (m stands for Maldives, c for
Caribbean), and D(Acc) = {r, su, b} (r stands for room, su for suite and b for
bungalow). Alice and Bob have independent and distinct opinions about this de-
cision situations given the evidence held by each of them so they have different
preferences. However, they have a common budget constraint as they cannot af-
ford more than $5000 for this trip. Table 1 summarizes the information supplied
by the agency about the different costs.
6 A. Rouahi et al.
Table 1. Choices costs for Example 1.
Destination
Maldives Caribbean
Plane $2112,00 $1030,00
Transport
Ship $1346,00 $760,00
room $2280,00 $3450,00
Accommodation suite $3825,00 $4120,00
bungalow $4285,00 $4685,00
Table 2. The evidence bases for Example 1.
b-pref1 b-pref2 b-pref3
S {T r} {Des, T r} {Des, Acc}
A {p, sh} {(m, p), (m, sh), (c, p), (c, sh)} {(m, r), (m, su), (m, b),
(c, r), (c, su), (c, b)}
B(Alice) p:0.8 (c,sh):0.6 (c,su),(c,b),(m,su):0.7
sh:0.2 (m,p),(m,sh):0.4 (c,r),(m,b):0.3
B(Bob) (p,sh):1.0 (m,p),(c,sh):0.6 (m,r),(c,su):0.5
(m,p),(m,sh),(c,p),(c,sh):0.4 (c,r),(c,b),(m,su):0.3
(m,b):0.2
4.1 Evidence Base
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 = {(θ1 , θ2 )|m(θ1 ) ≥ m(θ2 )}. (5)
The instance θ1 Dθ2 stands for ”the betterness of θ1 is at least as supported as the
betterness of θ2 ”, giving the evidence held by the agent. D is reflexive, transitive
and antisymmetric as its associated strict component B(”is strictly supported
to”) is irreflexive, transitive and asymmetric, its indifference component ≡(”is
as supported as”) is reflexive, symmetric and composed of (θ, θ) pairs only, and
its associated incomparability relation ./ (”is incomparable to”) is irreflexive,
not transitive and symmetric.
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 cap-
ture all the states of the agent towards his preferences. For us, beliefs as prior
preferences count as reasons for final preferences forming and then a base for
their justification.
– 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).
Evidential Group Decision Making Model with Belief-Based Preferences 7
– Partial ignorance: for the preference b-pref1 , Alice has an uncertain but
precise belief about the betterness of the alternatives. For the preference b-
pref2 , 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 reflect true ones for various reasons. An agent may be unable or
unwilling to definitely 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 reflect true ones, we can weaken the preference relation by
discounting its corresponding evidence base using the discounting rule described
in section 3.2. Given α ∈ [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 affect 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 quan-
tify 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 meta-
Table 3. The discounted evidence bases for Example 1.
b-pref1 b-pref2 b-pref3
B(Alice) p:0.8 (c,sh):0.6 (c,su),(c,b),(m,su):0.7
α = 1.0 sh:0.2 (m,p),(m,sh):0.4 (c,r),(m,b):0.3
B(Bob) (p,sh):1.0 (m,p),(c,sh):0.48 (m,r),(c,su):0.4
α = 0.8 (m,p),(m,sh),(c,p),(c,sh):0.52 (c,r),(c,b),(m,su):0.24
(m,b):0.16
(m,r),(m,su),(m,b),(c,r),
(c,su),(c,b):0.2
knowledge about preferences into account especially for those decision-making
8 A. Rouahi et al.
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 pref-
erences given the truth intensities, we can combine them using the CRC de-
scribed in Section 3.2. The combined preferences of Alice and Bob are shown in
Table 4.
Table 4. The combined prior preferences for Example 1.
b-pref1 b-pref2 b-pref3
B(Alice, BoB) p:0.8 (c,sh):0.6 (c,su):0.28
sh:0.2 (m,p),(m,sh):0.208 (c,b),(m,su):0.168
(m,p):0.192 (c,su),(c,b),(m,su):0.14
(c,r):0.072
(c,r),(m,b):0.06
(m,b):0.048
∅4 :0.232
4.2 Final Preferences
Final Preferences Deriving As the agents’ prior preferences are combined,
the final preference relations are derived as a partial preorder B induced by
the BetP measures over A, the set of alternatives:
B = {(a1 , a2 )|(BetP (a1 ) ≥ BetP (a2 ) ∧ (min(BetP (a1 ), BetP (a2 )) > 0)} (6)
The relation B is reflexive and transitive. Given the ordering B and two
alternatives a1 , a2 ∈ A, we distinguish between three relations over a1 and a2 :
– a1 is strictly preferred to a2 , denoted by a1 B a2 , when a1 B a2 holds
but a2 B a1 does not. The agent’s evidence provides more support 5 for a1
over a2 . B is irreflexive, transitive and asymmetric.
– a1 is indifferent to a2 denoted by a1 ≈B a2 , when both a1 B a2 and
a2 B a1 hold. The agent’s evidence does not support a1 more strongly
than a2 and does not support a2 more strongly than a1 . ≈B is reflexive,
transitive and symmetric.
4
The preferences will be re-normalized when deriving the final preferences using the
pignistic probabilities (see Section 3.2).
5
The term support denotes a non-null degree of belief; otherwise, we cannot refer to
a zero degree of belief as a support.
Evidential Group Decision Making Model with Belief-Based Preferences 9
– a1 is incomparable to a2 , denoted by a1 ∼B a2 , when neither a1 B a2 nor
a2 B a1 holds. The agent has no evidence (about a1 or a2 or both) for
comparing a1 and a2 . ∼B is irreflexive, not transitive and symmetric.
The derived final preference relations from evidence bases in Example 1 are
shown in Table 5.
Table 5. The derived final preference for Example 1.
b-pref1 b-pref2 b-pref3
R(Alice, BoB) p:0.8 (c,sh):0.6 (c,su):0.43
sh:0.2 (m,p):0.296 (c,b):0.17
(m,sh):0.104 (m,su):0.17
(c,p):0.0 (c,r):0.13
(m,b):0.1
(m,r):0.0
B instances p B sh (c,sh)∼B (c,p) (c,b)≈B (m,su)
Conflicting Preferences In practice, there are often several preference re-
lations that have to be considered, each emphasizing a different 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 conflict. A preference
set B-Pref is consistent (conflict free) if and only if it has no preference b-pref i
and b-pref j such that a1 B B
i a2 and a2 j 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 conflict.
Thus, we propose to define the conflict between two belief-based preference re-
lations Ri and Rj using a normalized L1 metric between their respective BetP
distributions as follows:
P
(a∈D(S)) |BetPiSi ↓S (a)−BetPjSi ↓S (a)|
|D(S)| if S 6= ∅,
Conf (i, j) = (7)
0 if S = ∅.
Where: S = Si ∩ Sj ; D(S)6 ={×k Dk |xk ∈ S} ; |D(S)|: Cardinality of D(S) and
BetPiSi ↓S (a) = maxai ∈Ai :a↓S =a BetP (ai )
i
– If Conf (i, j) = 0 the preference relations Ri and Rj are totally concordant
– If 0 < Conf (i, j) < 1 the preference relations Ri and Rj are partially con-
flicting
– If Conf (i, j) = 1 the preference relations Ri and Rj are totally conflicting
6
We use D(.) to denote the domain of a variable and the domain of a set of variables
as well.
10 A. Rouahi et al.
Returning Example 1 : To compute the conflict degree between b-pref1 and b-
pref2 , we have S = S1 ∩ S2 = {T r}, D(S) = D(T r), |D(S)| = 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(1,2)= (|0.8−0.296|+|0.2−0.6|)
2 =
0.452. The same process is used to get Conf(1,3)=0 and Conf(2,3)=0.148.
Consistency(B − P ref ) = 1 − max(conf (i, j)) (8)
In Example 1, Consistency(B-Pref )= 1 − 0.452 = 0.548, so B-Pref is partially
consistent. In our approach, as soon as two preference relations are totally con-
flicting, the preference set is totally inconsistent. Assessing conflict between two
preference relations may serve as an early detection of the problem inconsistency,
which brings cost and time savings. Furthermore, we can quantify to what extent
a given preference relation b-prefi , in a preference set B-Pref with n preferences,
is in conflict with the other (n-1) preferences by:
n
1 X
Conf (i, B − P ref ) = Conf (i, j) (9)
n−1
j=1,i6=j
Returning Example 1 : Conf(1,B-Pref )=0.226; Conf(2,B-Pref )=0.3; Conf(3,B-
Pref )=0.074.
4.3 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 dif-
ferently from the common soft constraints formalism where hard and soft con-
straints are coupled together and handled using the same representation. We
argue that for many real world applications, such as product configuration 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]. P
In Example 1, Alice and Bob have one budget constraint C1( i=1..2 pi ≤
$5000), where p1 and p2 are respectively the transport and the accommodation
costs. Once final preferences and constraints are given, decisions are determina-
tive.
5 Reasoning with Preferences and Constraints
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 iff it is defined on X, otherwise it is said
to be partial. Consider a b-prefi defined on the set of variables Si , δ(i, ωSi ) =
BetPi (ωSi ) will denote the satisfaction degree of b-prefi by some outcome ωSi ∈
Ai . b-prefi is said to be satisfied by ωSi , noted ωSi |= b-prefi , iff δ(i, ωSi ) > 0.
Evidential Group Decision Making Model with Belief-Based Preferences 11
Solving an evidential constrained optimization problem consists in finding a
∗
complete outcome ωX , if it exists, that satisfies 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 = {x1 , .., xl }
and Si = {xi1 , .., xim } such that Si ⊆ S ⊆ X. Let ω = (v1 , .., vl ) be any
outcome over S, the projection of ωS from S to Si denoted by ω ↓SSi is de-
fined as the outcome ωSi = (vi1 , .., vim ) with vik = vj if xik = xj . For ex-
{Des,Acc}
ample, if ω{Des,Acc} = (m, su), then ω ↓{Des} = (m). Consequently, given
a b-pref i defined 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 prefer-
ences B-Pref defined 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, ω ↓X
Si ), ∀i = 1..n (10)
Different combination operators ⊗ can be used that reflect various attitudes
towards preferences satisfaction:
– Min-Combination: using the egalitarian min operator is a pessimistic ap-
proach leading to the so-called ”drowning effect”, i.e., the worst local degree
of satisfaction drowns all the others regardless how much the rest of the
preferences are satisfied. For instance, consider two complete outcomes ωX
0
and ωX with only two belief-based preferences, and such that ωX satisfies
0
these b-pref (s) with degrees 0.5 and 1.0 while ωX satisfies them with degrees
0
0.5 and 0.5. Although ωX is obviously strictly preferable to ωX , 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 suffers 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 effect” weakness. However, it does not discriminate between out-
comes fully falsifying at least one preference.
– Average-Combination: it represents an utilitarian flexible approach that of-
fers more discriminating ordering than the former combinations tolerating
some preferences to be falsified.
The suitability of each of these combination approaches depends on the applica-
tion nature, where in some critical applications we need a pessimistic and strict
approach that does not tolerate the falsification of any preference. However, in
other domains, an optimistic and flexible approaches are more useful.
12 A. Rouahi et al.
Extension and Estimation consider two sets of variables S = {x1 , .., xl } and
Si = {xi1 , .., xim } 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 defined as the set
of outcomes ΩSi = {(vi1 , .., vim ) × DS−Si }. For example,if ω{Des} = (m), then
{Des,T r}
ω ↑{Des} = Ω{Des,T r} = {(m, p), (m, sh)}. Thus, given a b-pref i defined 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 ax{δ(i, ωSi )|ωSi ∈ ΩSi }.
5.2 Constructing solutions
Given an evidential constrained optimization problem ℘ (X,D,B-Pref,Cons), ev-
ery feasible complete outcome with respect to Cons that jointly satisfies B-Pref
to a global satisfaction degree greater than 0 (whatever the used approach), is
considered as a solution.
ωX ∈ S(P ) ⇔ ωX |= Cons ∧ δ(B − P ref, ωX ) > 0 (11)
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, satisfies
B-Pref:
∗
ωX = argmax δ(B − P ref, ωX ) (12)
ωX ∈S(P )
5.3 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 solu-
tions, 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 first introduced in [8] for the Constraint-Directed Backtracking and
proved to be less costly in terms of search effort.
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 ∈ 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
Evidential Group Decision Making Model with Belief-Based Preferences 13
the preference, not previously covered, get assigned. If the constructed partial
outcome satisfies 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
defined 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
(1) the partial outcome violates at least one constraint; (2) it satisfies all the
constraints but it cannot lead to a better solution b ≤ B. If all the problem’s
variables are assigned, a new solution is found with a satisfaction degree strictly
higher than B, so the solution is printed and the upper bound B is updated.
The algorithm terminates when no better solution can be found.
In addition, by applying the heuristic ”alternative giving best satisfaction
degree (max-BetP) is selected first”, we ensure that best solution is early con-
structed 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.
Fig. 1. PDBB trace for the problem in Example 1.
14 A. Rouahi et al.
Algorithm 1: PDBB Algorithm
input : (X, RSc , Cons, S, ωS , B, b)
/* Rc = {Ri | m (i=1) Si = X} is minimal; S = ∅;ωS = ∅; B = 0; b = 1 */
∗
output: (ωX , B)
while Rc is not empty do
select and remove a relation Ri ∈ Rc ;
S ← S ∪ Si ;
while Ai is not empty do
select and remove best a ∈ Ai ;
ωS ← ωS ∪ a;
if ωS |= Cons then
Compute a lower bound b for ωS ;
/* b = δ(B − prefa , ωS ) ⊗ δ e (B − prefa , ωS ) such that B-Prefa
is the set of preferences activated by the current
assignment and B-Prefa is the rest of B-Pref that are
not yet implied. */
if b > B then
if S = X then
B ← b;
∗
ωX ← ωS ;
∗
Print (ωX , B);
if B = 1 then
return ”Finished”;
else
PDBB(X, Rc , Cons, S, ωS , B, b);
else
PDBB(X, Rc , Cons, S, ωS − a, B, b);
else
PDBB(X, Rc , Cons, S, ωS − a, B, 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 affordable trip package for Alice and Bob is { Des-
tination: Caribbean; Transport: Ship; Accommodation: suite}.
6 Conclusion and Further Work
In this paper, we have introduced an evidential approach for constrained opti-
mization 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.
Evidential Group Decision Making Model with Belief-Based Preferences 15
For solving such kind of problems, we have provided a specific 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 refinements should be conducted by introducing heuris-
tics 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 offered by the eviden-
tial 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,
configuration problems and combinatorial auctions.
References
1. S. Bistarelli, U. Montanari, and F. Rossi (1995). Constraint Solving over Semirings.
In Proc. IJCAI95. Morgan Kaufman.
2. C. Boutilier, R. I. Brafman, C. Domshlak, H. Hoos, and D. Poole (2004).
Preference-based constrained optimization with CP-nets. Computational Intelli-
gence, 20(2):137–157.
3. A. P. Dempster (1967). Upper and lower probabilities induced by a multivalued
mapping. The Annals of Mathematical Statistics, 38(2): 325-339.
4. M. Gelain, M. S. Pini, F. Rossi and K. B. Venable (2007). Dealing with Incomplete
Preferences in Soft Constraint Problems. In Proceedings of CP 2007: 286-300.
5. M. Gelain, M. S. Pini, F. Rossi, K. B. Venable and N. Wilson (2010). Interval-
valued soft constraint problems. Ann. Math. Artif. Intell. 58(3-4): 261-298.
6. J. Lang and L. Van der Torre (2010). Preference change triggered by belief change:
A principled approach. G. Bonanno, B. Löwe, W. van der Hoek (Eds.), Logic
and the Foundations of Game and Decision Theory (LOFT 8), Lecture Notes in
Computer Science. 6006: 86-111, Springer.
7. F. Liu (2008). Changing for the better: Preference dynamics and agent diversity.
Ph.D. dissertation, University of Amsterdam.
8. W. Pang and S. Goodwin (1997). Constraint directed backtracking. Advanced Top-
ics in AI. 1342: 47-56. Springer Verlag.
9. M. S. Pini and F. Rossi (2005). Uncertainty in Soft Constraint Problems. In Pro-
ceedings of CP 2005,3709: 865.
10. G. Shafer (1976). A Mathematical Theory of Evidence. Princeton University Press,
Princeton, NJ.
11. P. Smets and R. Kennes (1994). The Transferable Belief Model. Artifical Intelli-
gence, 66: 191–234.