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