Qualitative Decision under Uncertainty: Back to Expected Utility

1 Introduction and motivation

A decision-making problem under uncertainty is a 4-tuple (S, X, A, ~), where S is a set of states of nature, X a set of consequences, A = X 8 the set of possible acts (in deci­ sion under uncertainty, an act is a function f : S t--+ X) and ~ is a preference relation on A, usually complete and transitive (i.e. is a complete preorder).

A numerical approach is classically advocated (see e.g. [Savage, 1954]) for encoding both the information pertain­ ing to the states of nature and the preferences on X : uncer­ tainty is represented by a probability distribution p and pref­ erence is encoded by a utility function u : X --t [0, 1] 1 · The pair < p, u > will be called a probabilistic utility model, PU-model for short. Acts are then ranked according to their expected utility EUp,u (written here in the finite setting):

Information about preference and uncertainty in decision problems cannot always be quantified in a simple way, but only qualitative evaluations can sometimes be attained. As a

1 Since expected utility is not sensitive to linear transformations of u , the choice of [0, 1] as the range for u is made for convenience.

Regis Sabbadin

INRA-UBIA,

BP 27 - 31326 Castanet-Tolosan Cedex - France sabbadin@toulouse.inra.fr

consequence, the topic of qualitative decision theory is a nat­ ural one to consider [Pearl, 1993; Dubois and Prade, 1995; Brafman and Tennenholtz, 1997; Dubois et al. , 1998b; Doyle and Thomason, 1999; Giang and Shenoy, 2000; Dubois et al., 2000]. Giving up the quantification of utility and uncer­ tainty has led to give up the expected utility (EU) criterion as well: the principle of most theories of qualitative deci­ sion making is to model uncertainty by an ordinal plausi­ bility relation on events and preference by a complete pre­ order~ng on consequences. In [Dubois and Prade, 1995; DubOis eta/., 1998b] two qualitative criteria based on pos­ sibility theory, an optimistic and a pessimistic one, are pro­ posed and axiomatized whose definitions only require a finite ordinal scale L = {OL :::; · · · :::; lL} for evaluating both utility and plausibility:

• f ~OPT,7r , J.L g {::} UoPT,1r,J.L(f) 2: UoPT,1r ,J.L(g) where Vh, UoPT,7r ,J.L(h) = maxsES min(1r(s) , f..L(h(s)))
• f ~PES,1r , J.L g {::} Upes,'Tr ,J.L(f) 2: Upes,'Tr ,J.L(g) where Vh, U PES,1r ,J.L(h) = minsES max(n(1r(s)), f..L(h(s))),

where n : L --t L is the order reversing function of L, 1r : S ___. L is a normalized possibility distribution and f..L : X ___. L is a utility function on X. In the following, < S, X , L, ?T, f..L >will be called a qualitative possibisitic util­ ity model (QPU-model) and we will assumeS, X and L to be finite, as is generally the case in qualitative decision making.

The value Up ES,1r ,J.L (f) is high only iff gives good conse­ quences in every "rather plausible" state. This criterion gen­ eralizes the Wald criterion, which estimates the utility of an act by that of its worst possible consequence. Upes,'Tr,J.L is thus "pessimistic" or "cautious", the pessimism being moder­ ated by taking relative possibilities of states into account. On the other hand, UoPT,7r ,J.L is a mild version of the maximax criterion which is "optimistic", or "adventurous".

Although appealing from a qualitative point of view, pos­ sibilistic utilities suffer from a lack of decisiveness called the "drowning effect": when two acts give an identical and extreme (either good or bad) consequence in some plausi­ ble state, they may be undistinguished by these criteria, al­ though they may give significantly different consequences in the other states. As a consequence the principle of Pareto dominance is not satisfied. That is it may be the case that Vs , f..L(f(s)) 2: f..L(g(s)) and that :Js*,?T(s*) > 0 and f..L(f(s*)) > f..L(g(s*)) but g ~f.

Examplel LetS= {s1 ,s2}, L = {0,1,2,3,4,5}. Let f and g be two acts whose utilities in states s1 and s2 are listed below, as well as the possibility degrees of the states. One can check that UoPr,.,.. ,J-<(1) = UoPr,.,..,J-<(g) = 3 and UPES,.,..,J-<(1) = UPES,-rr ,J-<(g) = 3 although j strictly dom­ inates g (J..L(f(si)) J..L(g(s 1 )) and f has a better conse­ quence in s2).

Most of the qualitative approaches [Pearl, 1993; Dubois and Prade, 1995; Brafman and Tennenholtz, 1997; Giang and Shenoy, 2000], fail to satisfy Pareto dominance. But this is not the case within expected utility theory, since this model obeys the following Sure-Thing Principle (STP) that insures that identical consequences do not influence the relative pref­ erence between two acts:

where f Ah denotes the act identical to f on A ~ S and to h on S \ A. When ~ is complete and transitive, the principle of Pareto dominance is a direct consequence of the STP. So, is it possible to benefit from the STP in the possibilistic frame­ work in order to satisfy the Pareto principle ? Unfortunately, it can been shown that this is generally not possible:

This means that possibilistic decision criteria cannot obey the STP, except in a very particular case: when the actual state of the world is known, i.e. when there is no uncertainty at all! So, we cannot stay in the pure QPU framework and escape the drowning effect altogether. The idea is then to cope with the difficulty by proposing refinements of the possibilistic criteria that obey the Sure Thing Principle 2 .

This paper shows (Section 2) that any possibilistic model can be refined by an expected utility. The kind of expected utility that is at work, and the very special probability mea­ sure that underlies it, are studied in Section 3 under the light of related work. It is also shown (Section 4) that although numerical, these expected utility criteria remain qualitative, since they lead to a decision procedure based solely on min, max and reverse operators- these new procedures general­ ize well known leximin and leximax decision procedures .

2 Expected utility refinements of qualitative possibilistic utilities

Recall that a refinement ~~ of a relation ~ is a relation per­ fectly compatible with ~ (it agrees with ~ when ~ provides a strict preference), but can break ties by setting f >-' g for some j, g that are indifferent w.r.t. ~- Formally:

2 The idea of refining QPU first appeared in [Dubois eta!., 2000]: the principle was to break ties thougth an extra criterion (e.g. refin­ ing the pessimistic QPU by the optimitic QPU or by another max­ tnorm aggregation). The use of a max operator kept the approach in an ordinal framework, but forbade the full satisfaction of the STP

Definition 1 (Refinement)

Since we are looking for complete and transitive relations it is natural to think of refinements based on expected utility. Savage [1954] has indeed shown that, as soon as a complete preorder is desired that satisfies the STP and some very nat­ ural axioms, the EU criterion is almost unavoidable. So, the question is: are there any expected utility criteria that refine the possibilistic criteria ?

Let< S, X, L, 1r, J..L > be a QPU model. When considering the optimistic (resp. pessimistic) criterion, we are looking for a probability distribution p and a utility function u such that ~EU,p , u refines ~OPT, -rr , J-< (resp. ~PEs,.,.., J-<). The idea is to build the EU criteria by means of a transformation x: L ---> [0, 1] that maps 1r to a probability distribution:

Definition 2 (Probabilistic transformation of a scale)

Let< S, X, L, 1r, J..L > be a QPU model. A probabilistic trans­ formation of L w.r.t. 1r is a mapping X: L---> [0, 1] such that x(OL) = 0 and p = x o 1r is a probability distribution.

Notice the presence of the condition x(OL) = 0 that ex­ presses the fact that the impossibility of an event (represented by a degree ofOL in possibility theory) is expressed by a null probability. But the most plausible events (possibility degrees of 1L), obviously do not receive a probability degree of 1, since they may be mutually exclusive. Notice also that we are looking for a unique function x for transforming L - both p and u will be built upon this transformation. This is due to the fact that we assume that preference and uncertainty levels are commensurate and belong to the same scale : it is thus natural to transform the degrees regardless whether they model uncertainty or preference.

Moreover, 1r and J..L originally represent all the information available to the user, both in terms of uncertainty of the actual state of the world and preference over possible consequences. So, no undesirable arbitrary information should be introduced in the refined decision model and p and u must be as close as possible to the original information: we are looking for "unbiased" transformations of L. Formally:

Definition 3 (Unbiased transformation of a scale)

Let < S, X, L, 1r, J..L > be a QPU model and X a probabilistic transformation of L. X is unbiased iff Va.,o/ E L,a.:::; a.'¢::> x(a.):::; x(a.')

As a consequence, using an unbiased x ensures that 1r and p = x o 1r (resp. J..L and u = x o J..L) are ordinally equivalent: - Vs, s' E S,p(s) ~ p(s') ¢::> n(s) ~ n(s'), - Vx, y EX, u(x) ~ u(y) ¢::> J..L(x) ~ J..L(y).

2.1 Expected utility refinements of optimistic QPU

Let us first provide a tractable sufficient condition for a prob­ abilistic transformation to generate an expected utility that refines ~OPT,.,..,J-<:

Proposition 2 Let< S, X, L, 1r, J..L > be a QPU model and X be a probabilistic transformation of L w.r.t. 1r. Also let H be the condition :

Then ~EU,xo-rr,xoJ-< refines ~OPT,-rr,J-< whenever X satisfies H.

H is a sufficient condition to generate an EU-refinement of the optimistic QPU (it is also a necessary one when every degree in L is attained by both 1r and tJ.). Importantly, there always exists a probabilistic transformation of L satisfying H. Let ni = l{s E S, 1r(s) = ai}l and N =IS I +1.

Proposition 3

The function X : L = { ao < ... < ak} ---+ [0, 1] such that x(ao) = 0 and x(ai) = N 2 L,, i = 1, k satisfies H Vv > 0. x o 1r is a probability distribution iffv = C2.::i=l,k N,JL. )- 1 .

In the sequel, x* will denote the function x*(ai) = N2L. obtained with v = (2:i=1,k N~·-· )- 1 .

Example 2 Let us take the QPU model of Example 1, where N = 2, L = {0, 1,2,3,4,5}. x*(L) is the series (0 v v v v v ) h ( 1 + { ) -1 s . , N'6' NB·.N·' N2· N w erev = N NB . o. EU(f) = x*(5) · x*(3) + x*(4) · x*(2) = ~ + ~. EU(g) = x*(5) · x*(3) + x*(2) · x*(1) = lis+~. f is thus preferred to g.

x* is in fact sufficient to generate every unbiased EU­ refinement of ~OPT,-rr ·~-' ' since all such refinements are equiv­ alent.

Definition 4 Two relations ~ and ~~ are said to be equiva­ lent ~ = ~ 1 ) iff V j, g E A,f ~ g <=> f ~~ g.

Proposition 4 Let< S, X, L, 1r, fJ. > be a QPU model, x1, X2 two unbiased probabilistic transformations of L w.r.t. 1r. ~EU,x1 o-rr,x 1 ol-' and ~EU,x2 o-rr,x2 ol-' both refine ~OPT,-rr , J-L ==::} >- = >- _£U,x,o-rr ,x,ol-' - _£U,x2 o-rr ,x2 oJ-L

Notice that Proposition 4 does not mean that the numbers attached to the states by P1 = X1 o 1r and P2 = X2 o 1r, nor the ones attached to the consequences by u1 = X1 o fJ. and u2 = x2 o fJ. are the same - it only means that the two models are ordinally equivalent, that they make the same decisions and order the events and the consequences in the same way. It also implies that the refinements that does not belong to this class (they may exist, e.g. those which introduce a total order in S or in X) cannot be unbiased : they must either introduce a strict preference between equivalent consequences or order equi-plausible states.

So, we get the following result for optimistic QPU models:

Theorem 1 For any QPUmodel < S,X,L,7r,f.l. >:

• There exists an unbiased probabilistic transformation x* of L w.r.t. 1r such that ~EU,x·o-rr,x·o/1- refines ~OPT,-rr,w
• If X and X 1 are two unbiased transformations of L s. t. both ~EU,xo-rr,xol-' and ~EU,x'o-rr ,x'oi-L refine ~OPT,-rr,t-L· then ~EU,xo-rr , xoi-L = ~EU,x'o-rr,x'ow

We have hence obtained what we were looking for: for any QPU model we are able to propose an EU model that re­ fines ~OPT,-rr ,w As a refinement, it is perfectly compatible with but more decisive than the optimistic utility. Moreover, it does not use other information than the original one - it is unbiased. Since based on expected utility, it obviously satis­ fies the Sure Thing Principle as well as Pareto Dominance.

2.2 EU refinements of pessimistic QPU

When considering the pessimistic qualitative model, the same kind of result can be obtained, noticing that ~PES,-rr,/1- and ~OPT, -rr ,J-L are dual relations:

Proposition 5 Let < S, X, L, 1r, fJ. > be a QPU model. Then: Vf,g E A,f ~PES,-rr,J-L g <=> g ~OPT,-rr,noJ-L f.

Proposition 6 Let< S, X, L, 1r, fJ. >be a QPU model and x be a probabilistic transformation of L w.r.t. 1r. Let p = X o 1r, u =X o f.l., U 1 = X(lL)- X on o f.l.· It holds that: ~EU,p,u refines ~OPT, -rr , t-L iff ~EU,p,u' refines ~PES,-rr,w

Consequently, it is always possible to build a probabilistic transformation x* using Theorem 1, a probability p = x* 0 7r and a utility function U 1 = X*(1L) -X* on o fJ. that define an unbiased EU-refinement of ~PES,-rr,w This provides the following pessimistic counterpart of Theorem 1:

Theorem 2 For any QPU model< S, X, L, 1r, J.L >:

• There exist at least one unbiased transformation x* of L w.r.t. 1r, a probability distribution p = x* o 1r and a utility function U 1 = x*(1L) - x* 0 n 0 fJ. such that ~EU,p,u' refines ~PES,-rr,w
• Let X and X 1 be two unbiased probabilistic trans­ formations of L. If both ~EU,xo-rr,x(1L)-xonoJ-L and ~EU,x'o-rr,x'(1L)-x'onot-L refine ~PES,-rr,J-L· then they are equivalent.

At this point in the paper we have proved an important re­ sult for bridging qualitative possibilistic decision theory and expected utility theory: we have shown than any optimistic or pessimistic QPU model can be refined by a EU model. Thus, we may conclude that (i) possibilistic decision criteria are compatible with the classical expected utility criterion and (ii) choosing a EU model is advantageous, since it leads to a EU-refinement of the original rule (thus overcomes the lack of decisiveness of the possibilisitic criteria), it satisfies the STP and the principle of Pareto. But this does not mean that qualitativeness and ordinality are given up. In Section 4, we will show that, although probabilistic and based on additive manipulations of numbers, these criteria remain ordinal. This is very natural: since we start with an ordinal model and do not accept any bias, we produce another (probabilistic but) ordinal model, in which the numbers only encode orders of magnitude - this is the topic of the next Section.

3 EU refinements and big-stepped probabilities : related work

Both EU refinements of Section 2 are based on the same transformation of the possibility 1r into a probability distri­ bution p = x o 1r 3 . The corresponding measure P is actually a "big-stepped probability" that is, it satisfies:

3 But the optimisitc utility u = x o J.L is not equal to the pes­ simisitic utility u' = x( h) - x on o J.L : u puts the emphasis on the best consequences, while the pessimistic u' provides a high utility when low consequences are avoided. It is actually hopeless to look for a common refinement of ?::.oPT,-rr,J.L and ?::.PES,-rr,J.L since it may happen that f >-oPT,-rr ,,.. g and g >- p ES,-rr ,,.. f altogether.

Definition 5 A probability measure P is said to be big stepped iff: 'Vs E S , P({s}) > P({s' s.t. P({s'}) < P({s})})

In other terms, for any s, p(s) > Ls' s.t. p(s')<p (s) p(s'). Such measures are often encountered in the AI literature. First, they have much in common with [Spohn, 1990]'s "'­ functions: these disbelief degrees can indeed be interpreted as the order of magnitude of a E probability [Pearl, 1993; Giang and Shenoy, 1999], which is obviously a big stepped probability. Moreover, big stepped probabilities also form a special class of lexicographic probabilities in the sense of [Blume et a!., 1991; Lehmann, 1998] - we add the re­ striction that here all the states within a single cluster are equiprobable. Indeed each cluster corresponds to a class of equipossible states and since we are looking for unbiased transformations, equipossibility leads to equiprobability. Fi­ nally, Definition 5 generalizes the notion of big-stepped prob­ ability of[Snow, 1999; Benferhat eta!., 1999]- which is recovered when each cluster is a singleton. Big stepped prob­ abilities have also been proposed by [Dubois eta!., 1998a] as a way to refine any possibility/necessity measure 4 .

This reasoning on the order of magnitude also applies to utility: in a discrete setting, big-stepped utilities can be de­ fined in the same way:

Definition 6 A utility measure u is said to be big stepped iff: 'Vx , x' EX, u(x) > u(x') ===} u(x ) > ([Sf- 1) · u(x')

The utility functions x* 0 J.L and x*(1L) - x* 0 n 0 J.L are big stepped utilities. It is also the case of the E utilities that underly K--utility functions [Pearl, 1993; Wilson, 1995; Bonet and Geffner, 1996; Giang and Shenoy, 2000]. These works have advocated an approach to decision under uncer­ tainty based on K--functions, but without taking the STP into account (decision is made on the order of magnitude only, with a criterion comparable to optimistic utility). The present work makes a step further: in order to satisfy Pareto optimal­ ity, we go back to the underlying E utilities and probabilities, using double exponents for epsilons instead of simple ones -we remain "big stepped" on the join scale. The other con­ tribution of our approach is that it can be followed to encode pessimistic utilities as well.

[La Valle and Fishburn, 1992; Hammond, 1998; Lehmann, 1998] have studied decision models of lexicographic prob­ abilities or lexicographic utilities, but in these models, the lexicographic characteristic is used only on one of the two dimensions (either the likelihood level, or the utility level). We operate on both dimensions simultaneously using a join transformation.

4 QPU refinements are qualitative

Although probabilistic and based on additive manipulations of utilities, our EU criteria remain ordinal, as paradoxical as it may seem at first sight. To establish this claim, this Section relates the previous EU criteria to the ordinal comparison of vectors. When S is finite, the comparison of acts can indeed be seen as a comparison of vectors of pairs of elements of L:

4 The "probabilistic likelihood relation" p = x o1r is a refinement of both the necessity (N) and possibility (II) relations based on 1r. Reciprocally, it is easy to show that, for any big stepped probability P, there exists a 1r such that P refines both II and N .

Definition 7 The representative vector of any act f E A is the vector l = ((1r1 , J.Ll) , .. . , (1ri, J.Li ), ... (7rN, J.LN )) where 1ri stands for 1r(si) and J.Ldor J.L(f(si)).

Comparing acts thus amounts to comparing elements of (L 2 )N. For instance, 'coPT,rr ,p, is a restriction to the case M = 2 ofthe general 'c.Maxmin relation on (LM)N .

where wi,j is the /h element of the ith vector ofw E (LM)N If i1 and iJ are representative of some acts, M = 2 and it is obvious that f 'c.oPT,rr ,p, g <=> l 'eM axmin §. In this Section we will propose a refinement of 'eM axmin, based only on the ordinal comparison of degrees and we will show the equiv­ alence between this purely syntactical decision rule and the above EU models.

4.1 Case of total ignorance

Let us first consider the degenerate case of total ignorance, where 'Vs E S, 1r(s) = 1£. In this case, the comparison of acts comes down to the comparison of utility degrees: l = ((1£, J.LI) , ... , (1L, J.LN )) becomes l = (J.Ll , .. . , J.LN ). So, f 'c.OPT,rr, p, g iff l 'c.Max g and f 'c.PES,rr ,p, g iff l 'c.Min §. In decision making, the comparison of vectors by the max and min operators is well known, as it is known that it suffers from a lack of decisive power. That is why refinements of 'c. min and 'cmax have been proposed [Moulin, 1988]:

Definition 9 (Leximax, Leximin) Let il, iJ E LN. Then

• i1 bmax iJ <=> ('Vj, U(j) = V(j) or 3i, 'Vj < i, U(j) V(j ) and U(i) > V(i) )
• i1 'c.lmin iJ <=> ('Vj, U(j) = V(j) or 3i, 'Vj > i, U(j) = V(j ) and U(i) > V(i))

where,for any wE LN, W(k) is the k-th biggest element ofw (i.e. W(l ) ~ .. . ~ W(N)) .

In practice, the leximin (resp. leximax) comparison con­ sists in ordering both vectors in increasing (resp. decreasing) order and then lexicographically comparing them.

Example 3 Let i1 = (3, 2, 4) and iJ = (2, 2, 4) : i1 >-lmax iJ since u(l ) = V(l ) = 4 and U(2) = 3 > V(2) = 2; i1 >-lmin iJ since U(J) = V(J ) = 2 and uc2) = 3 > v(2) = 2.

It is obvious that bmax refines 'cmax and 'c.lmin refines 'c.min· Moreover, both relations escape the drowning effect and are very efficient: the only pairs of ties are vectors that are identical up to a permutation of their elements.

4.2 General Case

Since the leximax and leximin comparisons are good candi­ dates in a particular case, we have imagined an extension of these;,rocedures to the case of2 dimensions ( (LM) N instead of L ). The only thing that we need is to use any complete preorder ~ on vectors of LM instead of the classical relation ~ on L. It is then possible to order the sub-vectors of any w according to~ and to apply any of the previous procedures:

Definition 10 (Leximax(~), Leximin(~)) Let~ be a com­ plete pre order on £M, ~ the associated equivalence relation and C> is the strict part of~. Let il, iJ E (LM)N. Then

• i1 bmax(~) iJ ¢:> (Vj, U(~,j) ~ V(~ ,j) or 3i s.t. Vj < i, U(~,j) S:' V(~,j) and U(~,i) C> V(~,i)) .
• i1 t:tmin(~) iJ ¢:> (Vj, U(~,j) S:' V(~,j) or 3i s.t. 't/j > i, U(~ ,j) S:' V(~,j) and U(~ , i) C> V(~ , i))·

where, for any w E (LM)N, W(~,i) is the ith biggest sub­ vector of w according to ~.

The leximax procedure can in particular be applied to the preorder ~ =bmin- In practice, this comparison consists in first ordering the elements of each sub-vector in increasing order w.r.t t:, then in ordering the sub-vectors in decreasing order (w.r.t. t:tmin). It is then enough to lexicographically compare the two new vectors of vectors.

Proposition 7 (t:tmax(~lmin) order)

i) t:tmax(~lmin) is a complete preorder;

ii) t:tmax(tlmin) refines t:maxmin:

iii) If N = 1, then t:tmax(tlmin) =t:tmin; iv) If M = 1, then t:tmax(tlmin)=t:tmax·

So, t:tmax(ttmin) is the refinement of t:maxmin we desire. Let us now compare representative vectors of acts using this relation (letting M = 2)- we get a refinement of t:oPT,.,..,p,:

Proposition 8 The relation bmax(tlmin) defined by f t:tmax(tlmin) g ¢=> f t:tmax(tlmin) §refines t:oPT,.,..,p,­

Example 4 The representative vectors off and g in Example I are: f = ((5, 3), (2, 4)), § = ((5, 3), (2, 1)). (5, 3) ~lmin (5, 3), ( 4, 2) >-tmin (2, 1)), SO J >-tmax(tlmin) §.

The same kind of reasoning can be followed to re­ fine t:PEs,.,.. ,w The pessimistic utility of act f is minsES max(n(1r(s)), J-L(J(s))). We need to refine a mini­ max procedure, and this can be done using bmin(tlmax)· Since operator max does not apply to (1r(s), J-L(J(s))) but to ( n( 1r( s) ), J-LU( s)) ), we use the 1r-reverse vectors of acts:

Definition 11 The 1r-reverse vector of an act f E A is n(J) = ((n(1r(s1)) , J-LU(si)) , ... (n(1r(sN )),J-L(J(sN))).

Proposition 9 The relation t:tmin(tlmax,n) defined by f t:tmin(tlmax,n) g {::> n(J) t:tmin(~lmax) n(g)

refines t:PES,.,.. ,w

So, the lexi-refinement of t:PEs,.,..,p, applies the lex­ imin(leximax) comparison to the 1r-reverse vectors, while the refinement of t:oPT,.,..,p, applies the leximax(leximin) com­ parison directly to the representative vectors. Both proce­ dures are purely ordinal: the degrees in L are only compared using min, max and reverse operators - only their relative orders matter. Our final result is that these refinements are equivalent to the EU-refinements identified in Section 2.

Theorem 3 Let< S, X , L, 1r, J-l > be a QPU model and x a probabilistic transformation of L w.r.t. 1r, p = x o 1r, u =

X o J-L, u' = X (1 L) - X o n o J-l.' i) t:EU,p,u refines t:oPT,.,.. ,p,¢=>t:EU,p,u=t:tmax(tlmin)· ii) t:EU,p,u' refines t:PES,.,.. ,p, ¢=>t:EU,p,u' =t:tmin(tlmax,n)·

So, the probabilistic refinements of possibilistic utili­ ties are equivalent to purely comparative procedures: effi­ cient QPU refinements are probabilistic but remain qualita­ tive. Reciprocally, we can prove that the bmax(tlmin) and t:tmin(tlmax ,n) preference relations over vectors of vectors always admit a representation by a sum (on N) of products (on M), provided that L is discrete - but this is beyond the scope of this paper, that focuses on decision under uncertainty (where M=2).

5 Conclusion

The topic of Qualitative Decision Theory has received much attention in the past few years and several approaches, includ­ ing QPU, have been proposed. This latter model forms a con­ venient framework for a qualitative expression of problems of decision under uncertainty. However, it suffers from a lack of decisiveness. We have proposed EU-based refinements of QPU which proved to be perfectly compatible with the original qualitative expression of knowledge and preferences: the only difference is that lexicographic (leximax(leximin) or leximin(leximax)) comparisons are used instead of maxmin or minmax. The axiomatization of these decision procedures is out of the scope of this paper. It actually con­ sists in the 5 basic Savagean axioms, together with "mild" versions of the pessimism or optimism axioms of possibilis­ tic utilities (see [Fargier and Sabbadin, 2003]).

K:-utility functions have also received much attention in AI but they too suffer from a lack of decisive power. Indeed, due to the min operator in U"'(J) = minsEs{K:(s) + JJ-(J(s))}, they cannot satisfy Savage's STP. We claim that t:~<,p, can be EU-refined, in the same way as we did for QPU, and that the EU-refinement can be expressed syntactically by replac­ ing the min operator by a leximin one. The proof of this conjecture, which would follow the same line as the one pre­ sented here, is left for future research.

The other extension of our work is to refine monotonic utilities [Dubois et a!., I998c] a family of decision crite­ ria that generalizes QPU and are based on the Sugeno in­ tegral. Monotonic Utilities admit a maxmin expression maxsEs(min(a(Fs), J-L(J(s)))), where a : 2 8 -+ L is a monotonic measure and F8 = {s' E S s.t. J-LU(s')) 2:: J.L(J(s))}. Again, we conjecture that replacing min and max with their lexicographical versions allows an efficient refine­ ment and lead to Choquet-EU criteria [Gilboa, 1987].

Appendix

Most of the proofs are omitted for sake of brevity and can be found m [Fargier and Sabbadin, 2003] or at the following address http://www­ bia.inra.fr/T/sabbadiniWEB/FargierSabbadin03Rap.html. We provide here the skecthes of the most interesting ones.

Proof of Proposition 1 {= is trivial to show.

=>For any x, y E X, A ~ S, let us denote xAy the act such that xAy(8) = x if 8 E A, xAy(8) = y otherwise. Let xO and xl be two consequences such that J.L(xO) =OLand J.L(xl) =h.

Suppose there exist 81, 82, 81 =1- 82, 1r(81) ::=: 1r(82) > OL Then, we have xl{82}xO >-oPT,rr ,p. xOSxl and xl{81, 82}xO ~OPT,rr,p. x1{8l}x0, which violates the STP. So, if

'?::oPT,-rr,JL satisfies the STP then there exists at most one s* such that 1r(s*) > 0£. Since 1r is normalized, s* exists and 1r(s*) = 1£. In the pessimistic case, just notice that xl >-PES,-rr,JL x0{s2}xl whereas xO{s1, s2}xl '?::PES,-rr,JL xO{s!}xl. D

Skectch of the proof of Proposition 4. Let us denote L~" = {a; E L,:lx E X,J.L(x) = ai}-letusrankL~" = (ao <···<a;< · · · < ak) and L., = {,6; E L, :ls E S, 1r(s) = ,6i} -let us rank L., = (,6o < · · · < ,{3; < · · · < ,6k' ). It can be assumed (without loss of generality) that L., ~ L~" = L.

Consider any a; E Land ,l3j = min{,i3; E L.,, ,{3; 2: a;}. There exists a pair ( s, x) where 1r( s) = ,6i, J.L( x) = a;. Let us also denote xO (resp. xl) a consequence of utility OL (resp. lL).

The proof of Proposition 4 is based on the observation that act f: j(s) = x, f(s') = xO is always strictly preferred by '?::oPT,.,,JL to act g : g(s') = xl when 1r(s') < a; and g(s') = a;-1 when1r(s') 2: a;.

From this, it can be shown that (i) the sub products, in the expres­ sion of the expected utility, are ranked in the same way by any x and that (ii) the act with the biggest j-product is surely strictly preferred to the other act (whatever the values of the remaining terms).

Lemma 1 Let X1 and X2 two unbiased transformation of L re­ fining '?::oPT,tr,JL· It holds that: Va, a' E L~", \:1,{3, ,6' E L.,: Xl(a) . X1(,6) > Xl(a') . xi(,B') ~ X2(a) . X2(,6) > X2 (a') . X2 (,13')

Lemma 2 J >- EU,xo-rr,xoJL g <=?

:lj/Vi < j,x(1ruf(i)) · X(J.Luf(;)) = X(7ru·(i)) · X(J.Lua(;)) and X(1ruf(j)) · X(J.Luf(j)) > X(1ruauJ) · X(J.Lu·UJ) ·

Lemmas I and 2 together are enough to prove the equivalence of '?::Eu,x 1 o-rr,x 1 o~" and '?::Eu,x2 o-rr,x 2 o~"' whatever X1 and x2: Indeed, f >-Eu,XJo-rr,x 1 o~" g <=?(from Lemma 2) :lj/Vi < j,X1(1ruf(i)) · Xl(J.Luf(i)) = Xl(7ruo(i)) · Xl(J.Lua(i)) and

Xl(7r17 f(j)) · Xl(J.Luf(j)) > Xl(7ru9(j)) · X1(J.Lu9(j))· But, from Lemma I, the comparison of products are the same if we change Xl into X2, so we get: :lj/Vi < j,x2(7r 17 f(i}) · X2(J.Luf(i} ) = X2(7ruY(i})·X2(J.LuY(i)) andx2(7r 17 f(j))·X2(J.L 17 f(j)) > X2(7ruo(j))· X2(J.Lu·(j)), which implies (Lemma 2) that>- EU,x2o-rr,x2ow

The same reasoning, simply swapping Xl and x2 implies >-Eu,x2 o-rr,x2 o~"=:> >-EU,X!o-rr,x 1 o~", from which we get the equiva­ lence of'?::Eu,x 1 o-rr ,x 1 o~" and '?::Eu,x2o-rr,x2oJL· 0