=Paper=
{{Paper
|id=Vol-1231/long9
|storemode=property
|title=Extendibility of Choquet rational preferences on generalized lotteries
|pdfUrl=https://ceur-ws.org/Vol-1231/long9.pdf
|volume=Vol-1231
|dblpUrl=https://dblp.org/rec/conf/ictcs/ColettiPV14
}}
==Extendibility of Choquet rational preferences on generalized lotteries==
https://ceur-ws.org/Vol-1231/long9.pdf
Extendibility of Choquet rational preferences on
generalized lotteries
Giulianella Coletti1 , Davide Petturiti2 , and Barbara Vantaggi2
1
Dip. Matematica e Informatica, Università di Perugia, Italy
coletti@dmi.unipg.it
2
Dip. S.B.A.I., Università di Roma “La Sapienza”, Italy
{davide.petturiti,barbara.vantaggi}@sbai.uniroma1.it
Abstract. Given a finite set of generalized lotteries, that is random
quantities equipped with a belief function, and a partial preference rela-
tion on them, a necessary and sufficient condition (Choquet rationality)
has been provided for its representation as a Choquet expected utility of
a strictly increasing utility function. Here we prove that this condition
assures the extension of the preference relation and it actually guides the
decision maker in this process.
Keywords: Generalized lottery, preference relation, belief function, prob-
ability envelope, Choquet expected utility, Choquet rationality
1 Introduction
In the classical von Neumann-Morgenstern decision theory under risk [23, 18],
the decision maker faces “one-shot” decisions [17] by specifying a preference
relation on lotteries, i.e., random quantities endowed with a probability distri-
bution. If the preference relation satisfies suitable axioms then the preference is
representable by an expected utility (EU) and the decision maker behaves like an
EU maximizer.
The assumptions behind the EU theory rely on a complete probabilistic de-
scription of the decisions, which is rarely met in practice. Indeed, in situations of
incomplete and revisable information, uncertainty cannot be handled through a
probability but it is unavoidable to refer to non-additive uncertainty measures,
for which the EU model is no more appropriate.
Here, we refer to Dempster-Shafer belief functions [7, 19] as uncertainty mea-
sures and to Choquet expected utility (CEU) as decision model (see for instance
[20, 21, 15, 1]). We recall that in some probabilistic inferential problems belief
functions can be obtained as lower envelopes of a family of probabilities, pos-
sibly arising as coherent extensions of a probability assessed on a set of events
different from those of interest (see for instance [7, 5, 10, 14, 6]).
Another issue typical of real problems is the partial observability of the world
which leads the decision maker to act under partial knowledge. Both in the
classical expected utility and in the Choquet expected utility frameworks it can
be difficult to construct the utility function u and even to test if the preferences
121
G.Coletti et al. Extendibility of Choquet rational preferences on generalized lotteries
agree with an EU (or a CEU). In fact, to find the utility u the classical methods
ask for comparisons between “lotteries” and “certainty equivalent” or, in any
case, comparisons among particular large classes of lotteries (for a discussion in
the EU framework see [13]). For that, the decision maker is often forced to make
comparisons which have little or nothing to do with the given problem, having
to choose between risky prospects and certainty.
In [4], referring to the EU model, a different approach (based on a “rationality
principle”) is proposed: it does not need all these non-natural comparisons but,
instead, it can work by considering only the (few) lotteries and comparisons
of interest. Moreover, when new information is introduced, the same principle
assures that the preference relation can be extended maintaining rationality,
and, even more, the principle suggests how to extend it.
In [2] and in an extended version [3], we proposed a similar approach for the
CEU model by generalizing the usual definition of lottery. In detail, a generalized
lottery L (or g-lottery for short) is a random quantity with a finite support XL
endowed with a Dempster-Shafer belief function BelL [7, 19, 22] (or, equivalently,
a basic assignment mL ) defined on the power set ℘(XL ).
Assuming that the elements of the set X = {x1 , . . . , xn } resulting by the
union of the supports of the considered g-lotteries is totally ordered as x1 <
. . . < xn (which is quite natural, thinking at elements of X as money payoffs),
then for every g-lottery L the Choquet integral of any strictly increasing utility
function u : X → R, not only is a weighted average (as observed in [12]), but
the weights have a clear meaning. In fact, this allows to map every g-lottery L
to a “standard” lottery whose probability distribution is constructed (following
a pessimistic approach) through the aggregated basic assignment ML .
The “Choquet rationality principle” (namely, condition (g-CR)) requires
that it is not possible to obtain two g-lotteries L and L0 with ML = ML0 , by
combining in the same way the aggregated basic assignments of two groups of g-
lotteries, if every g-lottery of the first group is not preferred to the corresponding
one of the second group, and at least a preference is strict.
Condition (g-CR) turns out to be necessary and sufficient for the existence
of a strictly increasing u : X → R whose CEU represents our preferences on
a finite set L of g-lotteries, under a natural assumption of agreement of the
preference relation with the order of X.
In this paper we show that condition (g-CR) assures also the extendibility
of a preference relation and actually “guides” the decision maker in this process.
An algorithm for the extension of a preference relation to a new pair of g-lotteries
is also provided. Such algorithm relies on the solution of at most three linear
programming problems and can be used “interactively” by the decision maker
in a step by step enlargement of his preferences.
The paper is structured as follows. In Section 2 some preliminary notions
are given, while Section 3 copes with preferences on g-lotteries and introduces
the condition (g-CR). Finally, Subsection 3.1 presents a motivating example,
and Subsection 3.2 deals with the extendibility of a Choquet rational preference
relation providing an algorithm for this task.
122
G.Coletti et al. Extendibility of Choquet rational preferences on generalized lotteries
2 Numerical model of reference
Let X be a finite set of states of nature and denote by ℘(X) the power set of X.
We recall that a belief function Bel [7, 19, 22] on an algebra of events A ⊆ ℘(X) is
a function such that Bel(∅) = 0, Bel(X) = 1 and satisfying the n-monotonicity
property for every n ≥ 2, i.e., for every A1 , . . . , An ∈ A,
n
! !
[ X \
|I|+1
Bel Ai ≥ (−1) Bel Ai . (1)
i=1 ∅6=I⊆{1,...,n} i∈I
A belief function Bel on A is completely singled out by its Möbius inverse,
defined for every A ∈ A as
X
m(A) = (−1)|A\B| Bel(B).
B⊆A
Such a function, usually called basicP(probability) assignment, is a function m :
A → [0, 1] satisfying m(∅) = 0 and A∈A m(A) = 1, and is such that for every
A∈A X
Bel(A) = m(B). (2)
B⊆A
A set A in A is a focal element for m (and so also for the corresponding Bel)
whenever m(A) > 0.
Given a set X = {x1 , . . . , xn } and a normalized capacity ϕ : ℘(X) → [0, 1]
(i.e., a function monotone with respect to the inclusion, and satisfying ϕ(∅) = 0
and ϕ(X) = 1), the Choquet integral of a function f : X → R, with f (x1 ) ≤
. . . ≤ f (xn ) is defined as
Z n
X
C f dϕ = f (xi )(ϕ(Ei ) − ϕ(Ei+1 )) (3)
i=1
where Ei = {xi , . . . , xn } for i = 1, . . . , n, and En+1 = ∅ [8].
In the classical von Neumann-Morgenstern theory [23] a lottery L consists of
a probability distribution on a finite support XL , which is an arbitrary finite set
of prizes or consequences.
In this paper we adopt a generalized notion of lottery L, by assuming that a
belief function BelL is assigned on the power set ℘(XL ) of XL .
Definition 1. A generalized lottery, or g-lottery for short, on a finite set
XL is a pair L = (℘(XL ), BelL ) where BelL is a belief function on ℘(XL ).
Let us notice that, a g-lottery L = (℘(XL ), BelL ) could be equivalently
defined as L = (℘(XL ), mL ), where mL is the basic assignment associated to
BelL . We stress that this definition of g-lottery generalizes the classical one in
which mL (A) = 0 for every A ∈ ℘(XL ) with card A > 1.
123
G.Coletti et al. Extendibility of Choquet rational preferences on generalized lotteries
For example, a g-lottery L on XL = {x1 , x2 , x3 } can be expressed as
{x1 } {x2 } {x3 } {x1 , x2 } {x1 , x3 } {x2 , x3 } {x1 , x2 , x3 }
L=
b1 b2 b3 b12 b13 b23 b123
where the belief function BelL on ℘(XL ) is such that bI = BelL ({xi : i ∈ I})
for every I ⊆ {1, 2, 3}. Notice that as one always has BelL (∅) = mL (∅) = 0,
the empty set is not reported in the tabular expression of L. An equivalent
representation of previous g-lottery is obtained through the basic assignment
mL associated to BelL (where mI = mL ({xi : i ∈ I}) for every I ⊆ {1, 2, 3})
{x1 } {x2 } {x3 } {x1 , x2 } {x1 , x3 } {x2 , x3 } {x1 , x2 , x3 }
L= .
m1 m2 m3 m12 m13 m23 m123
S
Given a finite set L of g-lotteries, let X = {XL : L ∈ L}. Then, any
g-lottery L on XL with belief function BelL can be rewritten as a g-lottery on
0
X by defining a suitable extension BelL of BelL .
Proposition 1. Let L = (℘(XL ), BelL ) be a g-lottery on XL . Then for any
0
finite X ⊇ XL there exists a unique belief function BelL on ℘(X) with the same
0
focal elements of BelL and such that BelL|℘(XL ) = BelL .
Given L1 , . . . , Lt ∈ L, all rewritten
Pt on X, and a real vector k = (k1 , . . . , kt )
with ki ≥ 0 (i = 1, . . . , t) and i=1 ki = 1, the convex combination of L1 , . . . , Lt
according to k is defined as
A
k(L1 , . . . , Lt ) = Pt for every A ∈ ℘(X) \ {∅}. (4)
i=1 ki mLi (A)
Since the convex combination of belief functions (basic assignments) on ℘(X) is
a belief function (basic assignment) on ℘(X), k(L1 , . . . , Lt ) is a g-lottery on X.
For every A ∈ ℘(X)\{∅}, there exists a degenerate g-lottery δA on X such that
mδA (A) = 1, and, moreover, every g-lottery L with focal elements A1 , . . . , Ak
can be expressed as k(δA1 , . . . , δAk ) with k = (mL (A1 ), . . . , mL (Ak )).
3 Preferences over a set of generalized lotteries
S
Consider a set L of g-lotteries with X = {XL : L ∈ L} and assume X is
totally ordered by the relation ≤, which is a quite natural condition thinking
at elements of X as money payoffs. Denote with < the total strict order on X
induced by ≤.
In what follows the set X is always assumed to be finite, i.e., X = {x1 , . . . , xn }
with x1 < . . . < xn . Under previous assumption, we can define the aggregated
basic assignment of a g-lottery L, for every xi ∈ X, as
X
ML (xi ) = mL (B), (5)
xi ∈B⊆Ei
124
G.Coletti et al. Extendibility of Choquet rational preferences on generalized lotteries
wherePE i = {xi , . . . , xn } for i = 1, . . . , n. Note that ML (xi ) ≥ 0 for every xi ∈ X
n
and i=1 ML (xi ) = 1, thus ML determines a probability distribution on X.
Let - be a preference/indifference relation on L . For every L, L0 ∈ L the
assertion that “L is indifferent to L0 ”, denoted by L ∼ L0 , summarizes the two
assertions L - L0 and L0 - L. Observe that not all the pairs of g-lotteries are
necessarily compared. An additional strict preference relation can be elicited by
assertions such as “L is strictly preferred to L0 ”, denoted by L ≺ L0 . Let ≺• be
the asymmetric relation formally deduced from -, namely ≺• =- \ ∼. If the pair
of relations (-, ≺) represents the opinion of the decision maker, then it is natural
to have ≺⊂≺• : in fact, it is possible that, at an initial stage of judgement, the
decision maker has not decided yet if L ≺ L0 or L ∼ L0 and he expresses his
opinion only by L - L0 . Obviously if - is complete then ≺=≺• and so for every
L, L0 ∈ L either L ≺ L0 or L0 ≺ L or L ∼ L0 .
Remark 1. Since the set X is totally ordered by ≤, it is natural to require that
the partial preference relation (-, ≺) agrees with ≤ on degenerate g-lotteries
δ{x} , for x ∈ X, that correspond to decisions under certainty. For this, L must
contain the set of degenerate g-lotteries on singletons L0 = {δ{x} : x ∈ X}
and it must be x ≤ x0 if and only if δ{x} - δ{x0 } , for x, x0 ∈ X. Actually, the
decision maker is not asked to provide such a set of preferences, but in this case
the initial partial preference (-, ≺) on L must be extended in order to reach this
technical condition and, of course, the decision maker is asked to accept such an
extension.
We call the pair (-, ≺) strengthened preference relation if ≺ is not empty,
moreover, we say that a function U : L → R represents (or agrees with) (-, ≺)
if, for every L, L0 ∈ L
L - L0 ⇒ U (L) ≤ U (L0 ) and L ≺ L0 ⇒ U (L) < U (L0 ). (6)
In analogy with [4], given (-, ≺) on L, our aim is to find a necessary and
sufficient condition for the existence of a utility function u : X → R such that
the Choquet expected utility of g-lotteries in L, defined for every L ∈ L as
Z
CEU(L) = C u dBelL , (7)
represents (-, ≺). In particular, since X is totally ordered by ≤ and CEU(δ{x} ) =
u(x) for every x ∈ X, we search for a strictly increasing u.
The next axiom requires that it is not possible to obtain two g-lotteries
having the same aggregated basic assignment, by combining in the same way
the aggregated basic assignments of two groups of g-lotteries, if each g-lottery
in the first group is not preferred to the corresponding one in the second group,
and at least a preference is strict.
Definition 2. A strengthened preference relation (-, ≺) on a set L of g-lotteries
is said to be Choquet rational if it satisfies the following condition:
125
G.Coletti et al. Extendibility of Choquet rational preferences on generalized lotteries
(g-CR) For all h ∈ N and Li , L0i ∈ L with Li - L0i (i = 1, . . . , h), if
k(ML1 , . . . , MLh ) = k(ML01 , . . . , ML0h )
Ph
with k = (k1 , . . . , kh ), ki > 0 (i = 1, . . . , h) and i=1 ki = 1, then it can
be Li ≺ L0i for no i = 1, . . . , h. In particular, if - is complete, it must be
Li ∼ L0i for every i = 1, . . . , h.
Note that the convex combination referred to in condition (g-CR) is the
usual one involving probability distributions on X. Moreover, it is easily proven
that if k(L1 , . . . , Lh ) = k(L01 , . . . , L0h ), then it also holds k(ML1 , . . . , MLh ) =
k(ML01 , . . . , ML0h ) but the converse is generally not true.
The following theorem, proved in [2], shows that (g-CR) is a necessary and
sufficient condition for the existence of a strictly increasing utility function u
whose Choquet expected value on g-lotteries represents (-, ≺).
S
Theorem 1. Let L be a finite set of g-lotteries, X = {XL : L ∈ L} with X
totally ordered by ≤, and (-, ≺) a strengthened preference relation on L. Assume
L0 ⊆ L and for every x, x0 ∈ X, x ≤ x0 if and only if δ{x} - δ{x0 } . The following
statements are equivalent:
(i) (-, ≺) is Choquet rational (i.e., it satisfies (g-CR));
(ii) there exists a strictly increasing function u : X → R (unique up to a positive
linear transformation), whose Choquet expected utility (CEU) on L repre-
sents (-, ≺).
The proof of previous result provides an operative procedure to compute
a strictly increasing utility function u on X in case (g-CR) is satisfied. For
this, introduce the collections S = {(Lj , L0j ) : Lj ≺ L0j , Lj , L0j ∈ L} and R =
{(Gh , G0h ) : Gh - G0h , Gh , G0h ∈ L} with s = card S and r = card R. Then
condition (g-CR) is equivalent to the non-existence of aProw vector k of size
s+r
(1 × s + r) with ki > 0 for at least a pair (Li , L0i ) ∈ S and i=1 ki = 1 such that
k(ML1 , . . . , MLs , MG1 , . . . , MGr ) = k(ML01 , . . . , ML0s , MG01 , . . . , MG0r ).
In turn, setting k = (y, z), previous condition is equivalent to the non-solvability
of the following linear system (in which || · ||1 denotes the L1 -norm)
yA + zB = 0
0 y, z ≥ 0
S : (8)
y 6= 0
||y||1 + ||z||1 = 1
where A = (aj ) and B = (bh ) are, respectively, (s × n) and (r × n) real matrices
with rows aj = ML0j −MLj for j = 1, . . . , s, and bh = MG0h −MGh for h = 1, . . . , r,
and y and z are, respectively, (1 × s) and (1 × r) unknown row vectors.
126
G.Coletti et al. Extendibility of Choquet rational preferences on generalized lotteries
By virtue of a well-known alternative theorem (see, e.g., [11]), in [2] the
non-solvability of S 0 has been proven to be equivalent to the solvability of the
following system
Aw > 0
S: (9)
Bw ≥ 0
where w is a (n × 1) unknown column vector. In detail, setting u(xi ) = wi ,
i = 1, . . . , n, the solution w induces a utility function u on X which, taking into
account Remark 1, is strictly increasing and whose CEU represents (-, ≺).
3.1 A paradigmatic example
To motivate the topic dealt with in this paper we introduced the following ex-
ample, which is inspired to the well-known Ellsberg’s paradox [9].
Example 1. Consider the following hypothetical experiment. Let us take two
urns, say U1 and U2 , from which we are asked to draw a ball each. U1 contains
1
3 of white (w) balls and the remaining balls are black (b) and red (r), but in
a ratio entirely unknown to us, analogously, U2 contains 41 of green (g) balls
and the remaining balls are yellow (y) and orange (o), but in a ratio entirely
unknown to us.
In light of the given information, the composition of U1 singles out a class
of probability measures P1 = {P θ } on the power set ℘(S1 ) of S1 = {w, b, r} s.t.
P θ ({w}) = 31 , P θ ({b}) = θ, P θ ({r}) = 23 − θ, with θ ∈ 0, 23 . Analogously, for
the composition of U2 we have the class P2 = {P λ } on ℘(S2 ) with S2 = {g, y, o}
s.t. P λ ({g}) = 41 , P λ ({y}) = λ, P λ ({o}) = 34 − λ, with λ ∈ 0, 43 .
Concerning the ball drawn from U1 and the one drawn from U2 , the following
gambles are considered:
w b r g y o
L1 100e 0e 0e G1 100e 10e 10e
L2 0e 0e 100e G2 10e 10e 100e
L3 0e 100e 100e G3 10e 100e 100e
L4 100e 100e 0e G4 100e 100e 10e
If we express the strict preferences L2 ≺ L1 , L4 ≺ L3 , then for no value of θ
there exists a function u : {0, 100} → R s.t. its expected value on the Li ’s w.r.t.
P θ represents our preferences on the Li ’s. Indeed, putting w1 = u(0) and 1w2 =
1 2
u(100), both the
following inequalities must
hold 3 w1 +θw 1 + 3 − θ w2 < 3 w2 +
θw1 + 23 − θ w1 and 31 w2 + θw2 + 23 − θ w1 < 31 w1 + θw2 + 32 − θ w2 , from
which, summing memberwise, we get w1 + w2 < w1 + w2 , i.e., a contradiction.
The same can be proven if we express the strict preferences G2 ≺ G1 , G4 ≺ G3 .
Now take P 1 = min P1 and P 2 = min P2 , where the minimum is intended
pointwise on the elements of ℘(S1 ) and ℘(S2 ), obtaining:
℘(S 1 ) ∅ {w} {b} {r} {w, b} {w, r} {b, r} S1
P 1 0 31 0 0 1
3
1
3
2
3 1
127
G.Coletti et al. Extendibility of Choquet rational preferences on generalized lotteries
℘(S2 ) ∅ {g} {y} {o} {g, y} {g, o} {y, o} S2
P 2 0 14 0 0 1
4
1
4
3
4 1
It is easily verified that both P 1 and P 2 are belief functions.
The gambles Li ’s and Gi ’s allow to transport the belief functions P 1 and P 2
to the whole set of prizes {0, 10, 100}, obtaining the following g-lotteries with
the corresponding aggregated basic assignments
{0} {10} {100} {0, 10} {0, 100} {10, 100} {0, 10, 100} 0 10 100
2 1 2 1
L1 3 0 3 3 1 3 1 ML1 23 0 13
1 1
L2 3 0 0 3 1 0 1 ML2 1 0 0
1 2 1 2
L3 3 0 3 3 1 3 1 ML3 13 0 23
1 1
L4 0 0 3 0 1 3 1 ML4 23 0 13
3 1 3 1
G1 0 4 4 4 4 1 1 MG1 0 34 14
1 1
G2 0 4 0 4 0 1 1 MG 2 0 1 0
G3 0 1
4
3
4
1
4
3
4 1 1 MG3 0 13 34
G4 0 0 1
4 0 1
4 1 1 MG4 0 34 14
It is easily proven that for every strictly increasing u : {0, 10, 100} → R the
strict preferences L2 ≺ L1 , L4 ≺ L3 , G2 ≺ G1 , G4 ≺ G3 are represented by their
Choquet expected utility. Indeed, putting w1 = u(0), w2 = u(10), w3 = u(100),
the following system
w1 < 32 w1 + 13 w3
32 w1 + 13 w3 < 31 w1 + 23 w3
S : w2 < 34 w2 + 14 w3
3
w2 + 14 w3 < 41 w2 + 34 w3
4
w1 < w2 < w3
is such that any choice of values satisfying w1 < w2 < w3 is a solution.
Now, suppose to toss a fair coin and to choose among L1 and G1 depending
on the face shown by the coin. In analogy, suppose to choose among L2 and G1
with a totally similar experiment. Let us denote with F1 and F2 the results of
the two experiments. This implies that F1 and F2 can be defined as the convex
combinations F1 = 21 L1 + 12 G1 and F2 = 21 L2 + 12 G1 , obtaining the g-lotteries
with the corresponding aggregated basic assignments
{0} {10} {100} {0, 10} {0, 100} {10, 100} {0, 10, 100} 0 10 100
8 9 7 17 15 16 8 9 7
F1 24 24 24 24 24 24 1 MF1 24 24 24
4 9 3 13 15 12 12 9 3
F2 24 24 24 24 24 24 1 MF2 24 24 24
If we add to previous preferences the further strict preference F1 ≺ F2 then
there is no strictly increasing u : {0, 10, 100} → R whose Choquet expected
utility represents our preferences. Indeed, in this case, the extended system
w1 < 23 w1 + 31 w3
23 w1 + 13 w3 < 31 w1 + 32 w3
w < 34 w2 + 41 w3
S : 32
4 w2 + 14 w3 < 41 w2 + 43 w3
8 9 7 12 9 3
24
w1 + 24 w2 + 24 w3 < 24 w1 + 24 w2 + 24 w3
w1 < w2 < w3
128
G.Coletti et al. Extendibility of Choquet rational preferences on generalized lotteries
admits no solution. Notice that, taking into account Remark 1, condition (g-
CR) fails since it holds
3 1 1 3 1 1
MF1 + Mδ{0} + Mδ{10} = MF2 + Mδ{10} + Mδ{100} .
4 8 8 4 8 8
3.2 Extension of Choquet rational preferences
In previous section it has been shown that condition (g-CR) is equivalent to the
existence of a strictly increasing utility function u on X, whose CEU represents
(-, ≺), moreover, such a u can be explicitly determined by solving the linear
system S defined in (9). It is straightforward that once a utility u has been
fixed, a complete preference relation on L (or any finite superset L0 of g-lotteries
on the same finite set X) extending (-, ≺) is induced by the corresponding CEU
functional.
Nevertheless, system S has generally infinite solutions which can give rise to
possibly very different complete preference relations, thus any choice of a utility
function causes a loss of information, moreover, it is not clear why one should
choose a utility function in place of another.
This is why it is preferable to face the extension in a qualitative setting
by considering the entire class of utility functions whose CEU represents the
preference (-, ≺) and suggesting to the decision maker those pairs of g-lotteries
where all the utility functions unanimously agree. In this view, the following
Theorem 2 proves the extendibility of a Choquet rational relation and shows
how condition (g-CR) guides the decision maker in assessing his preferences.
Theorem 2. Let X be a finite set totally ordered by ≤, L and L0 finite sets of
g-lotteries on X, with L ⊆ L0 , and (-, ≺) a strengthened preference relation on
L. Assume L0 ⊆ L and for every x, x0 ∈ X, x ≤ x0 if and only if δ{x} - δ{x0 } .
Then if (-, ≺) satisfies condition (g-CR) there exists a family {-γ : γ ∈ Γ }
of complete relations on L0 satisfying (g-CR) which extend (-, ≺). Moreover,
denoting with ≺γ and ∼γ , respectively, the strict and symmetric parts of -γ , for
γ ∈ Γ , condition (g-CR) singles out the relations
\ \
≺? = {≺γ : γ ∈ Γ } and ∼? = {∼γ : γ ∈ Γ }.
Proof. Suppose X = {x1 , . . . , xn } with x1 < . . . < xn . By the proof of Theorem 1
(see [2]), (-, ≺) satisfies condition (g-CR) if and only if system S defined in (9)
admits a (n × 1) column vector w as solution. In turn, setting u(xi ) = wi , for
i = 1, . . . , n, we get a strictly increasing utility function u on X whose Choquet
expected value represents (-, ≺) on L. Defining for every L, L0 ∈ L0
L -γ L0 ⇔ CEU(L) ≤ CEU(L0 ),
we get a relation -γ on L0 which is complete and satisfies (g-CR) by virtue of
Theorem 1. This implies that the family {-γ : γ ∈ Γ } is not empty and all its
members are obtained varying the solution w of system S. The correspondence
129
G.Coletti et al. Extendibility of Choquet rational preferences on generalized lotteries
between the set of solutions and the family of relations {-γ : γ ∈ Γ } is onto but
not one-to-one, as every positive linear transformation of a solution w gives rise
to the same relation -γ .
The relations ≺? and ∼? express, respectively, the pairs of g-lotteries in L0
on which all the strict ≺γ and symmetric ∼γ parts, for γ ∈ Γ , agree. It trivially
holds that ≺? and ∼? extend the relations ≺ and ∼ obtained from (-, ≺),
moreover, in order to determine ≺? and ∼? , for every F, G ∈ L0 such that it
does not hold F ≺ G or G ≺ F or F ∼ G it is sufficient to test the solvability of
the three linear systems
0 00
? Aw>0 ? A w>0 ? Aw > 0
S≺ : S : S∼ :
Bw ≥ 0 Bw ≥ 0 B0w ≥ 0
where w is an unknown (n × 1) column vector, A and B are, respectively, (s × n)
and (r×n) real matrices defined as in (8), A0 is a ((s+1)×n) real matrix obtained
adding to A the (s + 1)-th row a(s+1) = MG − MF , A00 is a ((s + 1) × n) real
matrix obtained adding to A the (s + 1)-th row a(s+1) = MF − MG , and B 0 is a
((r+2)×n) real matrix obtained adding to B the (r+1)-th row b(r+1) = MG −MF
and the (r + 2)-th row b(r+2) = MF − MG .
? ? ?
Depending on the solvability of systems S ≺ , S , S ∼ we can have the fol-
lowing situations:
? ? ?
(a) F ≺? G if and only if S ≺ is solvable and S , S ∼ are not, as this happens
if and only if CEU(F ) < ?CEU(G) for every u? given?
by a solution of S;
(b) G ≺? F if and only if S is solvable and S ≺ , S ∼ are not, as this happens
if and only if CEU(G) < ?CEU(F ) for every u? given?
by a solution of S;
(c) F ∼? G if and only if S ∼ is solvable and S ≺ , S are not, as this happens
if and only if CEU(F ) = CEU(G) for every u given by a solution of S.
In all the remaining cases, the Choquet expected utilities determined by solutions
of S do not unanimously agree in ordering the pair F and G.
Relations ≺? and ∼? determined in the proof of previous theorem express
“forced” preferences that the decision maker has to accept in order to maintain
Choquet rationality. On the other hand, pairs of g-lotteries not ruled by ≺?
and ∼? are subject to a choice by the decision maker. In the latter situation, a
subjective elicitation is required or, in case of a software agent [17], a suitable
automatic choice criterion can be adopted.
We stress that each choice made by the decision maker imposes a new con-
straint in system S, thus the set of utility functions whose CEU represents the
current strengthened preference (-, ≺) is possibly reduced.
Previous discussion suggests the following Algorithm 1 which is thought to
guide the decision maker in enlarging a Choquet rational preference relation
(-, ≺) to a (possibly new) pair of g-lotteries F and G: the extended preference
is still denoted as (-, ≺). In particular, Algorithm 1 returns to the decision
maker what he must do or he cannot do in order to maintain (g-CR).
Notice that possibly F, G ∈ L, thus previous algorithm can be used to pro-
duce a step by step completion of the preference relation (-, ≺) on L.
130
G.Coletti et al. Extendibility of Choquet rational preferences on generalized lotteries
Algorithm 1 Extension of a Choquet rational relation
function Extension((-, ≺), F , G)
? ?
if S ≺ and S are solvable then free preference between F and G
? ?
else if S ≺ is solvable and S ∼ is not then it must be F ≺ G
? ∼?
else if S is solvable and S is not then it must be G ≺ F
? ?
else if S ≺ and S ∼ are solvable then it cannot be G ≺ F
? ?
else if S and S ∼ are solvable then it cannot be F ≺ G
else it must be F ∼ G
end function
Algorithm 1 requires as input a Choquet rational preference relation (-, ≺)
on a set of g-lotteries L, and two (possibly new) g-lotteries F and G, all rewritten
on X = {x1 , . . . , xn } with x1 < . . . < xn . The g-lotteries in L ∪ {F, G} can be
simply regarded as basic assignments on ℘(X), i.e., as real (1×q) row vectors with
q = 2n − 1. The formation of matrices A, A0 , A00 , B, B 0 requires the computation
of the aggregated basic assignment ML for every L ∈ L ∪ {F, G}, which can be
done in polynomial time with respect to q.
The extension is faced through the solution of at most three linear program-
ming problems, whose solution has time complexity which is a polynomial in
n = log2 (q + 1) and the digital size of the coefficients in matrices A0 , B or A00 , B
or A, B 0 , respectively [16].
The following example shows an application of Algorithm 1.
Example 2. Consider the situation described in Example 1. It has already been
observed that adding the further strict preference F1 ≺ F2 implies that the global
preference relation has no more a Choquet expected utility representation. We
use Algorithm 1 to guide the decision maker in judging his preference between
F1 and F2 in order to preserve Choquet rationality. It is easily seen that only
system
w1 < 32 w1 + 31 w3
2 1 1 2
3 w1 + 3 w3 < 3 w1 + 3 w3
3 1
? w < 4 w2 + 4 w3
S : 3 2 1 1 3
4 w2 + 4 w3 < 4 w2 + 4 w3
12 9
w + w + w < 24 3 8 9
w1 + 24 7
w2 + 24 w3
24 1 24 2 24 3
w1 < w2 < w3
? ?
is solvable while S ≺ and S ∼ are not. In turn, this implies that F2 ≺? F1 and
so the decision maker is forced to strictly prefer F1 to F2 to respect condition
(g-CR).
On the other hand, considering the g-lotteries L1 and G1 , both systems
w1 < 32 w1 + 31 w3
w1 < 23 w1 + 13 w3
2 1 1 2
3 w1 + 3 w3 < 3 w1 + 3 w3
23 w1 + 13 w3 < 13 w1 + 23 w3
3 1
? w < 4 w2 + 4 w3 ? w2 < 34 w2 + 14 w3
S≺ : 3 2 1 1 3 S
:
4 w2 + 4 w3 < 4 w2 + 4 w3
34 w2 + 14 w3 < 14 w2 + 34 w3
2 1 3 1
3 w1 + 3 w3 < 4 w2 + 4 w3
34 w2 + 14 w3 < 23 w1 + 13 w3
w1 < w2 < w3 w1 < w2 < w3
131
G.Coletti et al. Extendibility of Choquet rational preferences on generalized lotteries
are solvable, thus in this case the decision maker is totally free to choose his
preference between L1 and G1 .
References
1. Chateauneuf, A., Cohen, M.: Choquet expected utility model: a new approach to
individual behavior under uncertainty and social choice welfare. Fuzzy Meas. and
Int.: Th. and App., pp. 289–314, Heidelberg: Physica (2000).
2. Coletti, G., Petturiti, D., Vantaggi, B.: Choquet expected utility representation of
preferences on generalized lotteries. IPMU 2014, Part II, CCIS 443, A. Laurent et
al. (Eds.), pp. 444–453 (2014).
3. Coletti, G., Petturiti, D., Vantaggi, B.: Rationality principles for preferences on
belief functions. Submitted to Kybernetika.
4. Coletti, G., Regoli, G.: How can an expert system help in choosing the optimal
decision?. Th. and Dec., 33(3), 253–264 (1992).
5. Coletti, G., Scozzafava, R.: Toward a General Theory of Conditional Beliefs. Int.
J. of Int. Sys., 21, 229–259 (2006).
6. Coletti, G., Scozzafava, R., Vantaggi, B.: Inferential processes leading to possibility
and necessity. Inf. Sci., 245, 132–145 (2013).
7. Dempster, A.P.: Upper and Lower Probabilities Induced by a Multivalued Mapping.
Ann. of Math. Stat., 38(2), 325–339 (1967).
8. Denneberg, D.: Non-additive Measure and Integral. Theory and Decision Library:
Series B, Vol. 27, Kluwer Academic, Dordrecht, Boston (1994).
9. Ellsberg, D.: Risk, Ambiguity and the Savage Axioms. Quart. Jour. of Econ., 75,
643–669 (1961).
10. Fagin, R., Halpern, J.Y.: Uncertainty, belief and probability. Comput. Int., 7(3),
160–173 (1991).
11. Gale, D.: The Theory of Linear Economic Models. McGraw Hill (1960).
12. Gilboa, I., Schmeidler, D.: Additive representations of non-additive measures and
the Choquet integral. Ann. of Op. Res., 52, 43–65 (1994).
13. Mc Cord, M., de Neufville, R.: Lottery Equivalents: Reduction of the Certainty
Effect Problem in Utility Assessment. Man. Sci., 23(1), 56–60 (1986).
14. Miranda, E., de Cooman, G., Couso, I.: Lower previsions induced by multi-valued
mappings. J. of Stat. Plan. and Inf., 133, 173–197 (2005).
15. Quiggin, J.: A Theory of Anticipated Utility. J. of Ec. Beh. and Org., 3, 323–343
(1982).
16. Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and
Complexity. Dover, New York (1998).
17. Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach. Second edition.
Prentice Hall, Upper Saddle River (2003).
18. Savage, L.: The foundations of statistics. Wiley, New York (1954).
19. Shafer, G.: A Mathematical Theory of Evidence. Princeton University Press (1976).
20. Schmeidler, D.: Subjective probability and expected utility without additivity.
Econometrica, 57(3), 571–587 (1989).
21. Schmeidler, D.: Integral representation without additivity. Proc. of the Am. Math.
Soc., 97(2), 255–261, 1986.
22. Smets, P.: Decision making in the TBM: the necessity of the pignistic transforma-
tion. Int. J. Approx. Reas., 38(2), 133–147 (2005).
23. von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior.
Princeton University Press (1944).
132