Given a finite set of generalized lotteries, that is random quantities equipped with a belief function, and a partial preference relation 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.
Introduction
In the classical von Neumann-Morgenstern decision theory under risk [
The assumptions behind the EU theory rely on a complete probabilistic description 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 [
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
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 [
In [
In [
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 [
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 glotteries, 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. 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 [
Bel n [ Ai i=1 ! ≥
X ∅6=I⊆{1,...,n} (−1)|I|+1Bel
! \ Ai . i∈I
A belief function Bel on A is completely singled out by its M¨obius inverse, defined for every A ∈ A as (1) (2) (3) m(A) =
X (−1)|A\B|Bel(B).
Such a function, usually called basic (probability) assignment, is a function m :
A → [
Bel(A) = X m(B).
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) → [
Z
C f dϕ =
n
X f (xi)(ϕ(Ei) − ϕ(Ei+1))
i=1
where Ei = {xi, . . . , xn} for i = 1, . . . , n, and En+1 = ∅ [
In the classical von Neumann-Morgenstern theory [
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. For example, a g-lottery L on XL = {x1, x2, x3} can be expressed as L = {x1} {x2} {x3} {x1, x2} {x1, x3} {x2, x3} {x1, x2, x3}
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}) L = {x1} {x2} {x3} {x1, x2} {x1, x3} {x2, x3} {x1, x2, x3} m1 m2 m3 m12 m13 m23 m123 .
Given a finite set L of g-lotteries, let X = S{XL : L ∈ L}. Then, any g-lottery L on XL with belief function BelL can be rewritten as a g-lottery on X by defining a suitable extension BelL0 of BelL.
Proposition 1. Let L = (℘(XL), BelL) be a g-lottery on XL. Then for any finite X ⊇ XL there exists a unique belief function BelL0 on ℘(X) with the same focal elements of BelL and such that BelL0|℘(XL) = BelL.
Given L1, . . . , Lt ∈ L, all rewritten on X, and a real vector k = (k1, . . . , kt) with ki ≥ 0 (i = 1, . . . , t) and Pt
i=1 ki = 1, the convex combination of L1, . . . , Lt according to k is defined as k(L1, . . . , Lt) =
A Pt i=1 kimLi (A) for every A ∈ ℘(X) \ {∅}.
(4) 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 Consider a set L of g-lotteries with X = S{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 xi∈B⊆Ei ML(xi) = mL(B), (5) where Ei = {xi, . . . , xn} for i = 1, . . . , n. Note that ML(xi) ≥ 0 for every xi ∈ X and Pn
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 [
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: (g-CR) For all h ∈ N and Li, L0i ∈ L with Li - L0i (i = 1, . . . , h), if k(ML1 , . . . , MLh ) = k(ML01 , . . . , ML0h ) with k = (k1, . . . , kh), ki > 0 (i = 1, . . . , h) and Ph 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 [
Theorem 1. Let L be a finite set of g-lotteries, X = S{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 represents (-, ≺).
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 a row vector k of size (1 × s + r) with ki > 0 for at least a pair (Li, L0i) ∈ S and Pis=+1r 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) (8) S0 : yA + zB = 0 y, z ≥ 0 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.
By virtue of a well-known alternative theorem (see, e.g., [
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}) = 13 , 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}) = 14 , P λ({y}) = λ, P λ({o}) = 43 − λ, with λ ∈ 0, 34 .
Concerning the ball drawn from U1 and the one drawn from U2, the following gambles are considered:
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 w2 = u(100), both the following inequalities must hold 13 w1+θw1+ 23 − θ w2 < 31 w2+ θw1 + 23 − θ w1 and 13 w2 + θw2 + 32 − θ w1 < 31 w1 + θw2 + 23 − θ 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: ℘(S1) ∅ {w} {b} {r} {w, b} {w, r} {b, r} S1
P 1 0 31 0 0 13 13 23 1 ℘(S2) ∅ {g} {y} {o} {g, y} {g, o} {y, o} S2
P 2 0 14 0 0 41 41 43 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 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 FF21 224844 229944 223744 22114437 21214545 22114426 11 MMFF21 2218442 229944 223744 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 S : admits no solution. Notice that, taking into account Remark 1, condition (gCR) fails since it holds 3 1 1 4 MF1 + 8 Mδ{0} + 8 Mδ{10} = 3 1 1 4 MF2 + 8 Mδ{10} + 8 Mδ{100} . 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 [
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 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
S≺? :
A0w > 0 Bw ≥ 0
S ? :
A00w > 0 Bw ≥ 0
S∼? :
Aw > 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 B0 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 following 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 [
We stress that each choice made by the decision maker imposes a new constraint 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 produce a step by step completion of the preference relation (-, ≺) on L. Algorithm 1 Extension of a Choquet rational relation function Extensi?on((-, ≺), F , G) ieflsSe≺i?f aSn≺d?? Sis soalvraebsloelvaanbdleSt∼h??eins nfroete tphreenferietnmceubstetbweeFen≺F Gand G eellssee iiff SS≺?? iasnsdolSv∼ab??learaensdolSv∼ableistnhoetnthitecnanitnomtubset bGe≺GF≺ 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, B0 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
programming 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, B0, respectively [
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 + 13 w3 23 w1 + 13 w3 < 13 w1 + 23 w3 w2 < 34 w2 + 14 w3 S 134224ww21++142w943w<2+14 w2342w+3 34<w2384 w1 + 294 w2 + 274 w3 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 23 w1 + 31 w3 < 13 w1 + 23 w3 S≺? : w2 < 34 w2 + 41 w3 2433 ww12 ++ 4311 ww33 << 1434 ww22 ++ 3414 ww33 w1 < w2 < w3
S ? : 3344 ww22 ++ 1414 ww33 << 1243 ww21 ++ 3413 ww33 w1 < w2 < w3 are solvable, thus in this case the decision maker is totally free to choose his preference between L1 and G1.