Nahla Ben Amor
email: nahla.benamor@gmx.fr

Hélène Fargier
email: fargier@irit.fr

Wided Guezguez
email: widedguezguez@gmail.com

Possibilistic sequential decision making

Keywords:

. This paper focuses on sequential decision making in possibilistic decision trees. It proposes a theoretical study on the complexity of the problem of finding an optimal strategy depending on the monotonicity property of the optimization criteria -when the criterion is transitive, this property indeed allows a polytime solving of the problem by Dynamic Programming. We show that most possibilistic decision criteria, but possibilistic Choquet integrals, satisfy monotonicity and that the corresponding optimization problems can be solved in polynomial time by Dynamic Programming. Concerning the possibilistic likely dominance criteria which is quasi-transitive but not fully transitive, we propose an extended version of Dynamic Programming which remains polynomial in the size of the decision tree. We also show that for the particular case of possibilistic Choquet integrals, the problem of finding an optimal strategy is NP-hard. It can be solved by a Branch and Bound algorithm. Experiments show that even not necessarily optimal, the strategies built by Dynamic Programming are generally very good.

Introduction

For several decades, there has been a growing interest in Operation Research and more recently in Artificial Intelligence towards the foundations and computational methods of decision making under uncertainty. This is especially relevant for applications to sequential decision making under uncertainty, where a suitable strategy is to be found, that associates a decision to each state of the world. Several representation formalisms can be used for sequential decision problems, such as decision trees, influence diagrams or Markov decision processes. A decision tree is an explicit representation of a sequential decision problem, while influence diagrams or Markov decision processes are compact representations. In this paper, we focus on the former framework: even in this simple, explicit, case, the set of potential strategies is combinatorial (i.e., its size increases exponentially with the size of the tree); the determination of an optimal strategy for a given representation and a given decision criterion is then an algorithmic issue in itself.

A popular criterion to compare decisions under risk is the expected utility (EU) model axiomatized by Von Neumann and Morgenstern [START_REF] Neumann | Theory of Games and Economic Behavior[END_REF]. This model relies on a probabilistic representation of uncertainty: an elementary decision (i.e. a one-step decision problem) is modeled by a probabilistic lottery over the possible outcomes. The preferences of the decision maker are supposed to be captured by a utility function assigning a numerical value to each outcome. The evaluation of a lottery is then performed through the computation of its expected utility (the greater, the better). In sequential decision making, each possible strategy is viewed as a compound lottery. It can be reduced to an equivalent simple lottery, and thus compared to remaining ones according to its expected utility.

Operational Research then proposes an efficient tool for the optimization of expected utility in probabilistic decision trees: Dynamic Programming. Although the high combinatorial nature of the set of possible strategies, the selection of an optimal strategy can be performed in time polynomial with the size of the decision tree: the EU model indeed satisfies a property of monotonicity that guarantees the completeness of Dynamic Programming.

When the information about uncertainty cannot be quantified in a probabilistic way the topic of possibilistic decision theory is often a natural one to consider [START_REF] Dubois | Qualitative decision theory with preference relations and comparative uncertainty: An axiomatic approach[END_REF][START_REF] Dubois | Making decision in a qualitative setting: from decision under uncertainty to case-based decision[END_REF][START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF]. Giving up the probabilistic quantification of uncertainty yielded to give up the EU criterion as well. The development of possibilistic decision theory has lead to the proposition and often of the characterization of a series of possibilistic counterparts of the EU criterion. Rebille [START_REF] Rebille | Decision making over necessity measures through the Choquet integral criterion[END_REF], for instance, advocates the use of possibilistic Choquet integrals, which relies on a numerical interpretation of both possibility and utility degrees. On the contrary, Dubois and Prade [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF] have studied the case of a qualitative interpretation and propose two criteria based on possibility theory, an optimistic and a pessimistic one (denoted U opt and U pes ), whose definitions only require a finite ordinal, non-compensatory, scale for evaluating both utility and plausibility.

The axiomatization of U opt and U pes has given rise to the development of sophisticated qualitative models for sequential decision making, e.g. possibilistic Markov Decision Processes [START_REF] Sabbadin | A possibilistic model for qualitative sequential decision problems under uncertainty in partially observable environments[END_REF][START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF], possibilistic ordinal Decision Trees [START_REF] Garcia | Possibilistic influence diagrams[END_REF] and even possibilistic ordinal Influence Diagrams [START_REF] Guezguez | Qualitative possibilistic influence diagrams based on qualitative possibilistic utilities[END_REF]. One of the most interesting properties of this qualitative model is indeed that it obeys a weak form of the monotonicity property. As a consequence, Dynamic Programming may be used and an optimal strategy with respect to U opt or U pes can be built in polytime, just like in the case of expected utility.

On the contrary, general Choquet integrals are incompatible with Dynamic Programming. Worst, the problem of determining an optimal strategy with respect to Choquet integrals is NP-hard in the general case [START_REF] Jeantet | Rank-dependent probability weighting in sequential decision problems under uncertainty[END_REF]. We will show in the present paper that the problem of determining a strategy optimal with respect to a possibilistic Choquet integrals is NP-hard as well.

More generally, this paper gives a deep study of complexity of strategy optimization problem w.r.t. possibilistic decision criteria and proposes a resolution algorithm (Dynamic Programming or Branch and Bound) for each criterion according to its complexity class ( P or NP).

This paper 1 is organized as follows: Section 2 presents a refresher on possibilistic decision making under uncertainty and a short survey on most common possibilistic decision criteria. Section 3 then presents our results about the complexity of sequential decision making in possibilistic decision trees. Finally, Section 4 is devoted to the proposition of a Branch and Bound algorithm for the optimization of Choquet-based possibilistic decision trees in the general case. For the sake of readability, the proofs have been gathered in Appendix A.

Possibilistic decision theory

Basics of possibility theory

Possibility theory, issued from Fuzzy Sets theory, was introduced by Zadeh [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF] and further developed by Dubois and Prade [START_REF] Dubois | Possibility Theory, an Approach to Computerized Processing of Uncertainty[END_REF]. This subsection gives some basic elements of this theory, for more details see [START_REF] Dubois | Possibility Theory, an Approach to Computerized Processing of Uncertainty[END_REF].

The basic building block in possibility theory is the notion of possibility distribution [5]. Let X 1 , . . . , X n be a set of state variables whose value are ill-known such that D 1 , . . . , D n are their respective domains. Ω = D 1 × • • • × D n denotes the universe of discourse, which is the cartesian product of all variable domains in X 1 , . . . , X n . Vectors ω ∈ Ω are often called realizations or simply "states" (of the world). The agent's knowledge about the value of the x i 's can be encoded by a possibility distribution π : Ω → [0, 1]; π(ω) = 1 means that realization ω is totally possible and π(ω) = 0 means that ω is an impossible state. It is generally assumed that there exist at least one state ω which is totally possible -π is said then to be normalized.

Extreme cases of knowledge are presented by:

• complete knowledge, i.e. ∃ω 0 s.t. π(ω 0 ) = 1 and ∀ω = ω 0 , π(ω) = 0,

• total ignorance, i.e. ∀ω ∈ Ω, π(ω) = 1 (all values in Ω are possible).

From π , one can compute the possibility Π(A) and the necessity N( A) of an event A ⊆ Ω:

Π(A) = sup ω∈A π(ω), (1)
N( A) = 1 -Π( Ā) = 1 -sup ω /
∈A π(ω).

(

) 2
Measure Π(A) evaluates to which extend A is consistent with the knowledge represented by π while N( A) corresponds to the extent to which ¬A is impossible and thus evaluates at which level A is certainly implied by the knowledge. The particularity of the possibilistic scale is that it can be interpreted twofold: when the possibilistic scale is interpreted in an ordinal manner, i.e. when the possibility degree reflects only an ordering between the possible values, the minimum operator is used to combine different distributions. In a numerical interpretation, possibility distributions are combined using the product operator. In possibility theory, the possibilistic conditioning may be considered as a special case of informations fusion. It consists in revising the initial knowledge, represented by a possibility distribution π , and to change it into another possibility distribution π ′ = π(.|ψ) with ψ = ∅ and Π(ψ) > 0. The two interpretations of the possibilistic scale induce two definitions of the operation of conditioning:

• min-based conditioning, which is relative to the ordinal setting:

π(ω|ψ) =    1 if π(ω) = Π(ψ) and ω ∈ ψ, π(ω) if π(ω) < Π(ψ) and ω ∈ ψ, 0 otherwise, (3)
• product-based conditioning, which is relative to the numerical setting:

π(ω|ψ) = π (ω) Π (ψ) if ω ∈ ψ, 0 otherwise.
(4)

Possibilistic lotteries

Following [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF]'s possibilistic approach of decision making under uncertainty, a decision can be seen as a possibility distribution over a finite set of outcomes. In a single stage decision making problem, a utility function maps each outcome to a utility value in a totally ordered set U = {u 1 , . . . , u n } (we assume without loss of generality that u 1 • • • u n ). This function models the attractiveness of each outcome for the decision maker. An act can then be represented by a possibility distribution on U , also called a (simple) possibilistic lottery, and denoted by λ 1 /u 1 , . . . , λ n /u n : λ i = π(u i ) is the possibility that the decision leads to an outcome of utility u i ; this possibility degree are also be denoted L[u i ], e.g. in the algorithms.

For the sake of simplicity, we shall forget about the utility degrees that receive a possibility degree equal to 0 in a lottery.

In the following, L denotes the set of simple lotteries (i.e. the set of possibility distributions over U ).

A possibilistic compound lottery L = λ 1 /L 1 , . . . , λ k /L k is a possibility distribution over a subset of L. The possibility π i, j of getting a utility degree u j ∈ U from one of its sub-lotteries L i depends on the possibility λ i of getting L i and on the conditional possibility λ i j = π(u j |L i ) of getting u j from L i , i.e. π i, j = min(λ j , λ i j ) in the ordinal setting and π i, j = λ j * λ i j in the numerical one. Hence, the possibility of getting u j from a compound lottery λ 1 /L 1 , . . . , λ k /L k is the max, over all the L i 's, of the π i, j 's (and this for the two interpretation of the possibility scale). Thus, [START_REF] Dubois | Making decision in a qualitative setting: from decision under uncertainty to case-based decision[END_REF][START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF] have proposed to reduce a compound lottery λ 1 /L 1 , . . . , λ k /L k (where L i are simple lotteries) into the following equivalent simple lottery:

Reduction λ 1 /L 1 , . . . , λ k /L k = max j=1..k ⊗ λ j , λ j 1 /u 1 , . . . , max j=1..k ⊗ λ j , λ j n /u n ( 5
)
where ⊗ = min for the ordinal setting and ⊗ = * for the numerical one.

Example 1.

Let L 1 = 1/u 1 , 0.7/u 2 and L 2 = 1/u 1 , 0.6/u 2 be two simple lotteries, the possibilistic compound lottery 1/L 1 , 0.8/L 2 and its reduction are represented by Fig. 1.

Obviously, the reduction of a simple lottery is the simple lottery itself. Since min and max are polynomial operations, the reduction of a compound lottery is polynomial in the size of the compound lottery. 2 We review in the following the different criteria that have been proposed to evaluate and/or compare (simple) possibilistic lotteries; thanks to the notion of reduction, they also apply to compound possibilistic lotteries: to evaluate/compare compound lotteries, simply reduce each one to an equivalent simple one; then use one of the criteria proposed for the evaluation/the comparison of simple lotteries. Formally, any comparison criterion O , i.e. any preference order O defined on simple lotteries, can be extended to compound lotteries as follows:

L O L ′ ⇐⇒ Reduction(L) O Reduction L ′ . ( 6
)
Note that a lottery L is indifferent to a lottery L ′ w.r.t. a decision criterion O (denoted by L ∼ O L ′ ) iff their reduced forms are also indifferent.

Qualitative possibilistic utilities (U pes , U opt , PU)

Under the assumption that the utility scale and the possibility scale are commensurate and purely ordinal, Dubois and Prade [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF] have proposed the following qualitative pessimistic (denoted by U pes ) and optimistic (denoted by U opt ) utility degrees for evaluating any simple lottery L = λ 1 /u 1 , . . . , λ n /u n (possibly issued from the reduction of a compound lottery):

U pes (L) = min i=1..n max(u i , 1 -λ i ), (7)
U opt (L) = max i=1..n min(u i , λ i ). ( 8
)
U pes generalizes the Wald criterion and estimates to what extend it is certain (i.e. necessary according to measure N) that L reaches a good utility. Its optimistic counterpart, U opt , estimates to what extend it is possible that L reaches a good utility. Because decision makers are rather cautious than adventurous, the former is generally preferred to the latter. The preference order induced by U opt and U pes is obviously complete transitive.

Claiming that the lotteries that realize in the best prize or in the worst prize play an important role in decision making, Giang and Shenoy [START_REF] Giang | A comparison of axiomatic approaches to qualitative decision making using possibility theory[END_REF] have proposed a bipolar model in which the utility of an outcome is a pair u = u, u where max(u, u) = 1: the utility is binary in this sense that u is interpreted as the possibility of getting the ideal, good reward (denoted ⊤) and u is interpreted as the possibility of getting the anti ideal, bad reward (denoted ⊥).

The normalization constraint max(u, u) = 1, implies that the set

U = { u, u ∈ [0, 1] 2 , max(u, u) = 1} is totally ordered
by the relation pu defined by:

u, u pu v, v ⇐⇒              u = v = 1 and u v or u v and u = v = 1 or u = v = 1 and v < 1. (9)
From this relation we can derive that if u u ′ and u u ′ , then u, u pu v, v . Each u i = u i , u i in the utility scale is thus understood as a small lottery u i /⊤, u i /⊥ . Hence, a lottery λ 1 /u 1 , . . . , λ n /u n can be viewed as a compound lottery, and its PU utility is computed by reduction:

PU λ 1 /u 1 , . . . , λ n /u n = Reduction λ 1 / u 1 /⊤, u 1 /⊥ , . . . , λ n / u n /⊤, u n /⊥ = max j=1..n min(λ j , u j ) /⊤, max j=1..n min(λ j , u j ) /⊥ . ( 10
)
We thus get, for any lottery L a binary utility PU(L) = u, u in U . Lotteries can then be compared according to Eq. ( 9):

L PU L ′ ⇐⇒ Reduction(L) pu Reduction L ′ . ( 11
)
In [START_REF] Giang | Two axiomatic approaches to decision making using possibility theory[END_REF] Giang and Shenoy show that the order induced by PU is transitive and that it collapses with the one induced by U opt (resp. U pes ) whenever for any lottery, the possibility u (resp. u) of getting the worst (resp. the best) utility is equal to 1. One shall thus say that PU captures U opt and U pes as particular cases.

Possibilistic likely dominance (LΠ , LN)

When the scales evaluating the utility and the possibility of the outcomes are not commensurate, [START_REF] Dubois | Qualitative decision theory with preference relations and comparative uncertainty: An axiomatic approach[END_REF][START_REF] Fargier | Qualitative models for decision under uncertainty without the commensurability assumption[END_REF] propose to prefer, among two possibilistic decisions, the one that is more likely to overtake the other. Such a rule does not assign a utility degree to the decisions, but draws a pairwise comparison. Although designed on a Savage-like framework rather than on lotteries, it can be translated on lotteries. This rule states that given two lotteries

L 1 = λ 1 1 /u 1 1 , . . . , λ 1 n /u 1 n and L 2 = λ 2 1 /u 2 1 , . . . , λ 2 n /u 2
n , L 1 is as least as good as L 2 as soon as the likelihood (here, the necessity or the possibility) of the event "The utility of L 1 is as least as good as the utility of L 2 " is greater or equal to the likelihood of the event "The utility of L 2 is as least as good as the utility of L 1 ". Formally:

L 1 LN L 2 iff N(L 1 L 2 ) N(L 2 L 1 ), (12)
L 1 LΠ L 2 iff Π(L 1 L 2 ) Π(L 2 L 1 ) (13) where Π(L 1 L 2 ) = max u 1 i ,u 2 j s.t. u 1 i u 2 j (⊗(λ 1 i , λ 2 j )) and N(L 1 L 2 ) = 1 - max u 1 i ,u 2 j s.t. u 1 i <u 2 j ⊗ λ 1 i , λ 2 j ,
such that ⊗ = min for ordinal setting and ⊗ = * for numerical setting.

The preference order induced on the lotteries is not transitive, but only quasi-transitive [START_REF] Dubois | Qualitative decision theory with preference relations and comparative uncertainty: An axiomatic approach[END_REF]: obviously

L 1 ≻ LN L 2 and L 2 ≻ LN L 3 imply that L 1 ≻ LN L 3 (resp. L 1 ≻ LΠ L 2 and L 2 ≻ LΠ L 3 imply that L 1 ≻ LΠ L 3 ) but it may happen that L 1 ∼ LN L 2 , L 2 ∼ LN L 3 (resp. L 1 ∼ LΠ L 2 , L 2 ∼ LΠ L 3 ) and L 1 ≻ LN L 3 (resp. L 1 ≻ LΠ L 3 ).
Note that contrary to U pes , U opt and PU, which are purely ordinal, possibilistic likely dominance can be defined in the ordinal setting or the numerical setting of possibility theory.

Order of Magnitude Expected Utility (OMEU)

Order of Magnitude Expected Utility theory relies on a qualitative representation of beliefs, initially proposed by Spohn [START_REF] Spohn | A general non-probabilistic theory of inductive reasoning[END_REF], via Ordinal Conditional Functions, and later popularized under the term kappa-rankings. Formally, κ : 2 Ω → Z + ∪ {+∞} is a kappa-ranking if and only if it obeys to the following axioms:

(S1) min ω∈Ω κ {ω} = 0, (S2) κ(A) = min ω∈A κ({ω}) if A = ∅ and A ⊆ Ω, +∞ otherwise.
Note that an event A is more likely than an event B if and only if κ(A) < κ(B): kappa-rankings have been termed as disbelief functions. They receive an interpretation in terms of order of magnitude of "small" probabilities. Say "κ( A) = i" is equivalent to say that P (A) is of the same order of ε i , for a given fixed infinitesimal ε. As pointed out by [START_REF] Dubois | Epistemic entrenchment and possibilistic logic[END_REF], there exists a close link between kappa-rankings and possibility measures, insofar as any kappa-ranking can be represented by a possibility measure, and vice versa. Order of magnitude utilities have been defined in the same way [START_REF] Pearl | From conditional oughts to qualitative decision theory[END_REF][START_REF] Wilson | An order of magnitude calculus[END_REF]. Namely, an order of magnitude function µ : X → Z + ∪ {+∞} can be defined to rank outcomes x ∈ X in terms of degrees of "dissatisfaction". Once again, µ(x) < µ(x ′ ) if and only if x is more desirable than x ′ , µ(x) = 0 for the most desirable consequences, and µ(x) = +∞ for the least desirable consequences: µ(x) = i is equivalent to say that the utility of x is of the same order of ε i , for a given fixed infinitesimal ε.

An Order of Magnitude Expected Utility (OMEU) model can then be defined (see [START_REF] Pearl | From conditional oughts to qualitative decision theory[END_REF][START_REF] Wilson | An order of magnitude calculus[END_REF] among others). Considering that an order of magnitude lottery L = κ 1 /µ 1 , . . . , κ n /µ n represents some probabilistic lottery, it is possible to compute the order of magnitude of the expected utility of this probabilistic lottery: it is equal to min i=1..n {κ i + µ i }. Hence the definition of the OMEU value of a kappa lottery L = κ 1 /µ 1 , . . . , κ n /µ n :

OMEU(L) = min i=1,n {κ i + µ i }. ( 14
)
The preference relation OMEU is thus defined as:

L OMEU L ′ iff OMEU(L) OMEU L ′ . ( 15
)
The preference order induced on the lotteries is transitive [START_REF] Giang | A qualitative linear utility theory for spohn's theory of epistemic beliefs[END_REF].

Possibilistic Choquet integrals (Ch N , Ch Π )

In presence of heterogeneous information, i.e. when the knowledge about the state of the world is possibilistic while the utility degrees are numerical and compensatory, Choquet integrals [START_REF] Choquet | Théorie des capacités[END_REF] appear as a right way to extend expected utility to non-Bayesian models [START_REF] Choquet | Théorie des capacités[END_REF]. Like the EU model, this model is a numerical, compensatory, way of aggregating uncertain utilities. But it does not necessarily resort on a Bayesian modeling of uncertain knowledge. Indeed, this approach allows the use of any monotonic set function µ, also called a capacity or fuzzy measure. Such measures capture Probability measures, Necessity and Possibility measures and Belief functions, etc. as particular cases.

Ch µ (L) = u 1 + i=2,n (u i -u i-1 ) * µ(L u i ). ( 16
)
If µ is a probability measure then Ch µ (L) is simply the expected utility of L.

Choquet integrals have been proposed by Schmeidler [START_REF] Schmeidler | Subjective probability and expected utility without additivity[END_REF] for decision making under probabilistic ambiguity (the capacity is a lower probability) and by Quiggin [START_REF] Quiggin | A theory of anticipated utility[END_REF] and Yaari [START_REF] Yaari | The dual theory of choice under risk[END_REF] as a model of "rank dependent utility" (in these works, the capacity is a transformation of the original probability measure). In the present paper, we are interested in studying the possibilistic framework for decision making: for cautious (resp. adventurous) decision makers, the capacity µ is the necessity measure N (resp. the possibility measure Π ):

Ch N (L) = u 1 + i=2,n (u i -u i-1 ) * N(L u i ), ( 17
)
Ch Π (L) = u 1 + i=2,n (u i -u i-1 ) * Π(L u i ). ( 18
)
Example 2. Let L 1 and L 2 be two possibilistic lotteries such that L 1 = 0.1/2, 0.4/4, 1/5 and L 2 = 1/3, 0.7/5, 0.2/10 . Thus:

Ch N (L 1 ) = 2 + (4 -2) * (1 -0.1) + (5 -4) * (1 -0.4) = 4.4, Ch Π (L 2 ) = 3 + (5 -3) * 0.7 + (10 -5) * 0.2 = 5.4.
The following proposition emphasizes the pessimistic character of Ch N : increasing the possibility of a possibly, good consequence that is not better than its best possible one cannot increase (and may decrease) its evaluation.

Proposition 1. Given a lottery L = λ 1 /u 1 , . . . , λ n /u n where utilities are ranked in an increasing order. Let u i be a utility in L s.t. u i max u j ∈L,λ j >0 u j . Let L ′ be a lottery constructed from L by just increasing the possibility of u i , i.e. λ ′ i > λ i . Thus Ch N (L ′ ) Ch N (L).

Example 3. Let L 1 and L 2 be two possibilistic lotteries such that L = 0.2/10, 0.5/20, 1/30 and L ′ = 0.2/10, 1/20, 1/30 . We can check that:

Ch N (L) = 23 > Ch N (L ′ ) = 18.
This result can be extended to the composition of lotteries: compounding a lottery with another lottery that is not strictly better than the original one cannot increase its Choquet value. Proposition 2. Let L 1 = λ 1 1 /u 1 , . . . , λ 1 n /u n and L 2 = λ 2 1 /u 1 , . . . , λ 2 n /u n be two lotteries such that max

u i ∈L 2 ,λ 2 i >0 u i max u i ∈L 1 ,λ 1 i >0 u i .
Then:

Ch N Reduction( 1/L 1 , 1/L 2 ) Ch N (L 1 ).
So, the compound lottery 1/L 1 , 1/L 2 cannot be better (with respect to the pessimistic Choquet integral) than L 1 , except when it allows to reach a utility degree not reached by L 1 . Simply increasing the possibility of the good utilities reached by L 1 is not a way to increase its Ch N utility.

On the complexity of decision making in possibilistic decision trees

Possibilistic decision trees

Decision trees [START_REF] Raifaa | Decision Analysis: Introductory Lectures on Choices under Uncertainty[END_REF] are graphical representations of sequential decision problems under the assumption of full observability. This framework proposes an explicit modeling of sequential decision problems, by representing each possible scenario by a path from the root to the leaves of the tree. Formally, the graphical component of a decision tree T is composed of a set of nodes N and a set of edges E such that the set N contains three kinds of nodes:

• D = {D 0 , . . . , D m } is the set of decision nodes (represented by rectangles). The labeling of the nodes is supposed to be in accordance with the temporal order, i.e. if D i is a descendant of D j , then i > j. The root node of the tree is necessarily a decision node, denoted by D 0 .

• LN = {LN 1 , . . . , LN k } is the set of leaves, also called utility leaves: ∀LN i ∈ LN , u(LN i ) is the utility of being eventually in node LN i . For the sake of simplicity we assume that only leave nodes lead to utilities.

Fig. 2. Example of a possibilistic decision tree with

C = {C 1 , C 2 , C 3 , C 4 , C 5 , C 6 }, D = {D 0 , D 1 , D 2 } and LN = U = {0, 1, 2, 3, 4, 5}.
• C = {C 1 , . . . , C n } is the set of chance nodes represented by circles.

For any X i ∈ N , Succ( X i ) ⊆ N denotes the set of its children. Moreover, for any

D i ∈ D, Succ(D i ) ⊆ C: Succ(D i ) is the set of actions that can be decided when D i is observed. For any C i ∈ C, Succ(C i ) ⊆ LN ∪ D: Succ(C i ) is indeed the set
of outcomes of the action C i -either a leaf node is observed, or a decision node is reached (and then a new action should be executed).

In the following |D| (resp. |C|, |LN |) denotes the total number of decision nodes (resp. chance nodes, leaves) in the tree. The size |T | of a decision tree is equal to its number of edges (|E|) and nodes (|N |). In classical, probabilistic, decision trees [START_REF] Raifaa | Decision Analysis: Introductory Lectures on Choices under Uncertainty[END_REF] the uncertainty pertaining to the possible outcomes of each C i ∈ C, is represented by a conditional probability distribution p i on Succ(C i ), such that ∀N ∈ Succ(C i ), p i (N) = P (N|path(C i )) where path(C i ) denotes all the value assignments to chance and decision nodes on the path from the root to C i .

In the present work, we obviously use a possibilistic labeling (see Fig. 2). The difference with probabilistic decision trees is that the chance nodes are not probabilistic but possibilistic lotteries. More precisely, for any C i ∈ C, the uncertainty pertaining to the more or less possible outcomes of each C i is represented by a conditional possibility distribution π i on

Succ(C i ), such that ∀N ∈ Succ(C i ), π i (N) = Π(N|path(C i )).
Solving a decision tree amounts at building a strategy that selects an action (i.e. a chance node) for each reachable decision node. Formally, we define a strategy as a function δ from D to C ∪ {⊥}. δ(D i ) is the action to be executed when a decision node D i is observed. δ(D i ) = ⊥ means that no action has been selected for D i (because either D i cannot be reached or the strategy is partially defined). Admissible strategies must be:

-sound:

∀D i ∈ D, δ(D i ) ∈ Succ(D i ) ∪ {⊥}, -complete: (i) δ(D 0 ) = ⊥ and (ii) ∀D i s.t. δ(D i ) = ⊥, ∀N ∈ Succ(δ(D i )), either δ(N) = ⊥ or N ∈ LN .
Let be the set of sound and complete strategies that can be built from the decision tree. Any strategy in can be viewed as a connected subtree of the decision tree whose arcs are of the form (D i , δ(D i )), i.e. there being exactly one decision arc left at each decision node.

The size |δ| of δ is the sum of its number of nodes and edges. It is obviously lower than the size of the decision tree (but for trivial trees that are already sound and complete strategies to start with).

Strategies can be evaluated and compared thanks to the notion of lottery reduction. Recall indeed that leaf nodes in LN are labeled with utility degrees. Then a chance node can be seen as a simple lottery (for the rightmost chance nodes) or as a compound lottery (for the inner chance nodes). Each strategy is a compound lottery and can be reduced to an equivalent simple one. Formally, the composition of lotteries will be applied from the leafs of the strategy to its root, according to the following recursive definition for any N i in N :

L(N i , δ) =    L(δ(N i ), δ) if N i ∈ D, Reduction( π i (X j )/L(X j , δ) X j ∈Succ(N i ) ) if N i ∈ C, 1/u(N i ) if N i ∈ LN . (19)
Eq. ( 19) is simply the adaptation to strategies of lottery reduction (Eq. ( 5)). We can then compute Reduction(δ) = L(D 0 , δ): Reduction(δ)(u i ) is simply the possibility of getting utility u i when δ is applied from D 0 . Since operators max and * (resp. max and min) are polytime Eq. ( 19) defines a polytime computation of the reduced lottery. Proposition 3. For any strategy δ in , the simple possibilistic lottery Reduction(δ) can be computed in polytime.

We are now in position to compare strategies, and thus to define the notion of optimality. Let O be one of the decision criteria defined above (i.e. depending on the application, O is either LΠ , or LN , or the order induced by U pes , or by U opt , etc.). A strategy δ ∈ , is said to be optimal w.r.t. O iff:

∀δ ′ ∈ , Reduction(δ) O Reduction δ ′ . ( 20
)
Note that this definition does not require the full transitivity of O and is meaningful as soon as O is complete and its the strict part, i.e. ≻ O , is transitive. This means that it is applicable to the preference relations that rely on the comparison of utility degrees (qualitative utilities, binary utility, Choquet integrals) but also to LN and LΠ .

Dynamic Programming in possibilistic decision trees

Finding optimal strategies via an exhaustive enumeration of δ is a highly computational task. For instance, in a decision tree with n decision nodes and a branching factor equal to 2, the number of potential strategies is in O (2

√ n ).
For standard probabilistic decision trees, where the goal is to maximize expected utility, an optimal strategy can be computed in polytime (with respect to the size of the tree) thanks to an algorithm of Dynamic Programming which builds the best strategy backwards, optimizing the decisions from the leaves of the tree to its root. Note that this algorithm does not generate all the best strategies but returns only one among them.

Regarding qualitative decision trees, Garcia and Sabbadin [START_REF] Garcia | Possibilistic influence diagrams[END_REF] have shown that such a method can also be used to get a strategy maximizing U pes and U opt . The reason is that, like EU, U pes and U opt satisfy the key properties of transitivity and weak monotonicity.

Formally a preference order O is said to be weakly monotonic iff whatever L, L ′ and L ′′ , whatever (α, β) such that max(α, β) = 1:

L O L ′ ⇒ α/L, β/L ′′ O α/L ′ , β/L ′′ . (21)
For the sake of simplicity, we write here the property for a binary composition of lotteries. By associativity of possibilistic composition, it obviously applies to a composition of more than two lotteries.

This property states that the combination of L (resp. L ′ ) with L ′′ , does not change the initial order induced by O between L and L ′ -this allows Dynamic Programming to decide in favor of L or L ′ before considering the compound decision. The principle of backwards reasoning procedure is depicted in a recursive manner by Algorithm 1 for a preference order O over possibilistic lotteries.

In this algorithm L[u i ] is the possibility degree to have the utility u i in the lottery L, Succ(N).first is the first node in the set of successors of N, i.e. Succ(N) and ⊗ (Line 1) is the min operator for the ordinal setting and the product operator for the numerical setting.

The principle of this algorithm is as follows: When each chance node is reached, an optimal sub-strategy is built for each of its children -these sub-strategies are combined w.r.t. their possibility degrees, and the resulting compound strategy is reduced: we get an equivalent simple lottery, representing the current optimal sub-strategy. When a decision node X is reached, a decision Y * leading to a sub-strategy optimal w.r.t. O is selected among all the possible decisions Y ∈ Succ( X), by comparing the simple lotteries equivalent to each sub-strategy.

Algorithm 1, Line 2 performs the comparison of two simple lotteries according to the criterion O to optimize (e.g. We will see in the following that, beyond U pes and U opt criteria, several other criteria satisfy the monotonicity property and that their optimization can be managed in polytime by Dynamic Programming. The possibilistic Choquet integrals, on the contrary, do not satisfy weak monotonicity; we show in the next section that they lead to NP-complete decision problems.

Ch N (L Y ) and Ch N (L Y * ))
Algorithm 1: ProgDyn(N: node, δ: strategy).

Data: O is the criterion to optimize. Result: A lottery L begin // Initialization for i ∈ {1, . . . , n} do L[u i ] ← 0 // Leaves if N ∈ LN then L[u(N)] ← 1 // Chance nodes if N ∈ C then // Reduce the compound lottery foreach Y ∈ Succ(N) do L Y ← ProgDyn(Y , δ); for i ∈ {1, . . . , n} do (Line 1) L[u i ] ← max(L[u i ], (⊗(π N (Y ), L Y [u i ]))); // Decision nodes if N ∈ D then // Choose the best decision Y * ← Succ(N).first; foreach Y ∈ Succ(N) do L Y ← ProgDyn(Y , δ); (Line 2) if L Y ≻ O L Y * then Y * ← Y δ(N) ← Y * ; L ← L Y * ;
return L;

On the complexity of possibilistic decision trees

Formally, for any of the optimization criteria proposed above, the corresponding decision problem can be defined as follows:

Definition 1 (DT-OPT-O ). (Strategy optimization w.r.t. an optimization criterion O in possibilistic decision trees.)

INSTANCE: A possibilistic decision tree T , a constant lottery θ . QUESTION: Does there exist a strategy δ ∈ such that Reduction(δ) O θ ?

For instance DT-OPT-Ch N corresponds to the optimization of the necessity-based Choquet integrals. DT-OPT-U pes and DT-OPT-U opt correspond to the optimization of the possibilistic qualitative utilities U pes and U opt , respectively.

Possibilistic Qualitative Utilities (U pes , U opt , PU)

Possibilistic qualitative utilities U pes and U opt satisfy the weak monotonicity principle. Although not referring to a classical, real-valued utility scale, but to a 2 dimensional scale, this is also true in the case of PU. Proposition 5. U pes , U opt and PU satisfy the weak monotonicity property for both ⊗ = min and ⊗ = * . This proposition is not explicitly proved in the literature although it is a common knowledge in qualitative possibilistic decision theory (see [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF][START_REF] Giang | A comparison of axiomatic approaches to qualitative decision making using possibility theory[END_REF]); it is also known that Dynamic Programming applies to the optimization of U pes , U opt and PU in qualitative possibilistic Markov decision processes and thus to decision trees (see [START_REF] Garcia | Possibilistic influence diagrams[END_REF][START_REF] Perny | Algebraic Markov decision processes[END_REF][START_REF] Sabbadin | Towards qualitative approaches to multi-stage decision making[END_REF]). We prove it in the general case -i.e. for both the qualitative case (⊗ = min) and the quantitative case (⊗ = * ).

Dynamic Programming applies to the optimization of U pes , U opt and PU: the polynomiality of these criteria is a direct consequence of Propositions 4 and 5.

Corollary 1. DT-OPT-U pes , DT-OPT-U opt and DT-OPT-PU belong to P for both ⊗ = min and ⊗ = * .

Possibilistic Likely Dominance (LΠ , LN)

a) Comparing lotteries by LΠ Although LΠ is not a fully transitive criterion (it is only quasi-transitive). It is easy to show that: Proposition 6. LΠ satisfies the weak monotonicity principle.

Because this criterion is not fully transitive but only quasi-transitive, classical Dynamic Programming shouldn't be applied. Nevertheless, it can be extended so as to keep, for each decision node, a judicious subset of all the best (but possibly indifferent) strategies for the current subtree [START_REF] Kikuti | Partially ordered preferences in decision trees: Computing strategies with imprecision in probabilities[END_REF][START_REF] Huntley | Normal form backward induction for decision trees with coherent lower previsions[END_REF] -see Algorithm 2. The recursive procedure thus returns a set S of simple lotteries and their associated strategies: dominated strategies are removed by a call to a pruning function -see Algorithm 3, thanks to the monotonicity principle.

At each chance node, a pointwise composition of the lotteries returned by the recursive calls is performed: this leads to a set of reduced lotteries that is pruned so as to keep, again, judicious non-dominated decisions. The difficulty with this type of procedure it that the size of the set of lotteries handled by the algorithm may grow exponentially. We show in the following that it is possible to keep it within polynomial bounds when the criterion to optimize is LΠ . Indeed, when O = LΠ , the comparison of two lotteries only depends on the relative position of their cores. Formally, for any lottery L,

let L =α = {u i , L[u i ] = α}; the core of L corresponds to L =1 . It is easy to show that L LΠ L ′ iff max(L =1 ) min(L ′ =1
). This allows us to replace any simple lottery L built during the computation by a simple lottery where any utility degree different from max(L =1 ) and min(L =1 ) receives a possibility degree of 0. We call this lottery called the core lottery of L and denote it by L core ; namely:

L core = 1/ min(L =1 ), 1/ max(L =1 ) .
Π(L L ′ ) = 1 and Π(L ′ L) = 0.9: L LΠ L ′ ; and that Π(L core L ′ core ) = 1 and Π(L ′ core L core ) = 0: L core LΠ L ′ core .
It can now be shown that:

Proposition 7. ∀L, L ′ ∈ L, L LΠ L ′ ⇐⇒ L core LΠ L ′ and L ′ LΠ L ⇐⇒ L ′ LΠ L core .
A first consequence of this proposition is that replacing any simple lottery by its core lottery during the computation does not change the set of optimal strategies of the problem. A second consequence is that if L core = L ′ core , then for any L ′′ , L LΠ L ′′ ⇐⇒ L ′ LΠ L ′′ and L ′′ LΠ L ⇐⇒ L ′′ LΠ L ′ which means that lotteries sharing the same core form an equivalence class. We shall then remove from S the pairs (L core , δ) such that there exist in the set another pair (L ′ core , δ ′ ): since leading to the same core lottery, δ and δ ′ are equivalent w.r.t. LΠ .

Then we can remark that the number of simple core lotteries is bounded by n 2 , n being the number of different utility values labeling the leaves. As a consequence, the set S of lotteries handled by Extended Dynamic Programming (Algorithm 2) when optimizing LΠ contains at most n 2 elements. The different loops on S in this function are then also polynomially bounded: O (n 4 ) is a trivial upper bound for the pruning function (assuming that the comparison of simple lotteries can be done in linear time and the pointwise composition of the sets is bounded by O (m.n 4 ), m being the number of children of the chance node). The Extended Dynamic Programming procedure is thus polynomial in the size of the decision tree when O = LΠ . b) Comparing lotteries by LN When O = LN, the principle is similar to O = LΠ but a little more tricky. The idea is to replace any simple lottery L by a lottery which keeps track of the bounds of the core (as it is the case with LΠ criterion) but also of the bound of the next cut of L, since only these two levels play a role in the LN comparison. We call this lottery the 2nd core lottery of L and denote it L 2nd . Formally, let

L =α = {u i , L[u i ] = α} and α 2nd (L) = max u i ,L[u i ]<1 L[u i ], then: L 2nd = 1/ min(L =1 ), 1/ max(L =1 ) if max(L =1 ) = min(L =1 ), 1/ max(L =1 ), α 2nd (L)/ min(L =α 2nd ), α 2nd (L)/ max(L =α 2nd ) otherwise.
The second point corresponds to the case where L (and thus L 2nd ) is unimodal with mode max(L =1 ) = min(L =1 ). In other terms, a 2nd core lottery is:

• either of the form 1/m, 1/M where m = min(L =1 ) < M = max(L =1 ),
• or of the form α/m, 1/u, α/M where u = max(L =1 ), α = α 2nd (L), m = min(L =α ) < M = max(L =α ).

Example 5. Let L = 1/10, 0.5/20, 0.9/30, 1/40, 1/50 and L ′ = 0.2/10, 0.9/20, 0.9/30, 1/40 be two simple lotteries, then:

L =1 = {10, 40, 50}, L core = L 2nd = 1/10, 1/50 , L ′ =1 = {40}, L ′ core = 1/
40 and L ′ 2nd = 0.9/20, 0.9/30, 1/40 .

When two lotteries L and L ′ are to be compared w.r.t. LN, the decision is made at possibility degree 1 (i.e. the core level) as soon as one of them (say L) is not unimodal (and thus L 2nd is of the form 1/m, 1/M ). Indeed,

(i) If L ′ 2nd is of the form 1/m ′ , 1/M ′ then L ≻ LN L ′ when m M ′ , L ′ ≻ LN L when m ′ M and L ∼ LN L ′ otherwise. (ii) If L ′ 2nd is of the form α ′ /m ′ , 1/u ′ , α ′ /M ′ then L ≻ LN L ′ when m u ′ , L ′ ≻ LN L when u ′ M and L ∼ LN L ′ otherwise.
Let us now study the case where L and L ′ are unimodal, then L 2nd (resp. L ′ 2nd ) can be written as α/m, 1/u, α/M (resp. α ′ /m ′ , 1/u ′ , α ′ /M ′ ).

(i) If u = u ′ , then only the modes are used to make the decision: either u > u ′ , and then L ≻ LN L ′ ; or u ′ > u and then L ′ ≻ LN L.

(ii) If u = u ′ , decision is made at level max(α, α ′ ); when α > α ′ , then either u > M (and then L ′ ≻ LN L); or u < m (and then L ≻ LN L ′ ); or M > u > m (and then L ∼ LN L ′ ). Similar results hold for α ′ > α. u ′ = u and α ′ = α, it is easy to show that the two lotteries are indifferent w.r.t. LN.

We can now show that:

Proposition 8. LN satisfies the weak monotonicity principle.

Since when comparing L and L ′ , only the information contained in L ′ 2nd and L 2nd matters we can also show that:

Proposition 9. ∀L, L ′ ∈ L, L LN L ′ ⇐⇒ L 2nd LN L ′ and L ′ LN L ⇐⇒ L ′ LN L 2nd .
This means that we can replace any simple lottery by its 2nd core lottery during the computation without changing the set of optimal strategies of the problem. A second consequence of that proposition is that if

L 2nd = L ′ 2nd then for any L ′′ , L LN L ′′ ⇐⇒ L ′ LN L ′′ and L ′′ LN L ⇐⇒ L ′′ LN L ′ .
Lotteries sharing the same 2nd core form an equivalence class. We shall then remove from S the pairs (L 2nd , δ) such that there exist in the set another pair (L ′ 2nd , δ ′ ) where L 2nd = L ′ 2nd : since leading to the same 2nd core lottery, δ and δ ′ are equivalent w.r.t. LN. The set S will thus contain pairs (L i , δ i ) where each L i is indifferent to others, while no pair of lotteries in S share the same 2nd core lottery. Now, it is possible to prove that:

Proposition 10. Let L and L ′ be two indifferent 2nd core lotteries of the form L = 1/u, α/m, α/M and L

′ = 1/u ′ , α ′ /m ′ , α ′ /M ′ such that α < α ′ . Then: L ∼ LN L ′ iff u = u ′ and m < u < M.
This means that in a set S of indifferent 2nd core lotteries, all the unimodal 2nd core lotteries share the same mode and for all of them, but maybe the one with the lowest α 2nd , and m < u < M. This latter is very significant, since one can forget about all the unimodal 2nd core lotteries in the set S for which α 2nd is not the lowest one. It can indeed be shown that:

Proposition 11. Let L and L ′ be two indifferent 2nd core lotteries of the form L = 1/u, α/m, α/M and L ′ = 1/u, α ′ /m ′ , α ′ /M ′ where α < α ′ . Let L 1 = γ /L, β/L ′′ and L 2 = γ /L ′ , β/L ′′ such that L ′′ is a lottery and max(γ , β) = 1. Then for any lottery L b , it holds that:

(i) L 2 ≻ LN L b ⇒ L 1 ≻ LN L b ; (ii) L b ≻ LN L 2 ⇒ L b ≻ LN L 1 .
Actually, replacing L ′ by L in a strategy may break ties (for instance, it may happen that γ /L ′ , β/L ′′ ∼ LN L b and γ /L, β/L ′′ ≻ LN L b ), but this can never change the strict preference. An important consequence of Proposition 11 is that, if the strategy corresponding to a lottery L ′ belongs to the set of optimal lotteries, so does the strategy associated to L.

Thus, before returning the set S of lotteries computed by the recursive procedure, the pruning function Prune O (see Algorithm 3) can prune not only the dominated lotteries (and the associated strategies) but also all the unimodal core lotteries except the one with the lowest α 2nd . As a consequence, the sets of lotteries handled by Extended Dynamic Programming when optimizing LN contains at most 2.n 2 elements (n 2 multimodal core lotteries and n 2 unimodal 2nd core lotteries sharing the same α 2nd ), all being indifferent to each other. The Extended Dynamic Programming procedure is thus polynomial in the size of the decision tree when O = LN.

In summary, for both LΠ and LN, it is possible to ensure the polynomiality of the size of the set of strategies handled by Extended Dynamic Programming. Hence the result: Proposition 12. DT-OPT-LN and DT-OPT-LΠ belong to P .

Order of Magnitude Expected Utility

In kappa decision trees, for any C i ∈ C the uncertainty pertaining to the more or less possible outcomes N of C i is represented by a kappa degree κ i :

∀N ∈ Succ(C i ), κ i (N) = Magnitude P N|path(C i ) .
then ∀u i , L[u i ] ← 0; L[u(N)] ← 1; S ← {(L, δ 0 )}; if N ∈ C // Chance nodes then // Reduce the compound lotteries foreach Y j ∈ Succ(N) do S j ← ExtProgDyn(Y j ) S ← S 1 ; for j ∈ {2, . . . , |Succ(N)|} do Res ← ∅; foreach (L, δ) ∈ S, (L ′ , δ ′ ) ∈ S j do // Create a strategy δ ′′ and a lottery L ′′ δ ′′ ← δ ∪ δ ′ ; ∀u i , L ′′ [u i ] ← 0; for i ∈ {1, . . . , n} do L ′′ [u i ] ← max(L[u i ], (⊗(π N (Y j ), L ′ [u i ]))); if O = LΠ then L ′′ ← L ′′ core if O = LN then L ′′ ← L ′′ 2nd Res ← Res ∪ {(L ′′ , δ ′′ )}; S ← Prune O (Res); if N ∈ D //
(L ′ , δ ′ ) ∈ S, δ ′ = δ do if (L ′ ≻ O L) or (L is identical to L ′ ) then Remove (L, δ) from Res; if O = LN then if (L = 1/u, α/m, α/M ) and (∃L ′ = 1/u, α ′ /m ′ , α ′ /M ′ ∈ S), with α ′ < α then Remove (L, δ) from Res;
return Res;

Such that the normalization condition that the degree κ = 0 is given to at least one N in Succ(C i ). According to the interpretation of kappa-ranking in terms of order of magnitude of probabilities, the product of infinitesimal conditional probabilities along the paths lead to a sum of the kappa levels. Hence the following principle of reduction of the kappa lotteries:

Reduction κ 1 /L 1 , . . . , κ k /L k = min j=1..k κ j 1 + κ j /u 1 , . . . , min j=1..k κ j m + κ j /u m . ( 22
)
It follows from the definition of the order of magnitude expected utility (i.e. OMEU(L = κ 1 /µ 1 , . . . , κ n /µ n ) = min i=1..n {κ i + µ i }) that this criterion is transitive and also satisfies the weak monotonicity principle: Proposition 13. OMEU is complete, transitive and satisfies the weak monotonicity property.

As a consequence Dynamic Programming is sound and complete for the optimization of Order of Magnitude Expected Utility: Corollary 2. DT-OPT-OMEU belongs to P .

Possibilistic Choquet integrals (Ch N , Ch Π )

Contrary to qualitative utilities, binary possibilistic utility and likely dominance, the situation is much lesser comfortable for Choquet integrals (either Ch N or Ch Π ). The point is that the possibilistic Choquet integrals (as many other Choquet integrals) do not satisfy the monotonicity principle neither in the ordinal setting nor in the numerical one. This is illustrated by the following counterexamples.

Counterexample 1 (Ch N does not satisfy the monotonicity principle). Let L = 0.2/0, 0.5/0.51, 1/1 , L ′ = 0.1/0, 0.6/0.5, 1/1 , L ′′ = 0.01/0, 1/1 , L 1 = α/L, β/L ′′ and L 2 = α/L ′ , β/L ′′ , with α = 0.55 and β = 1.

• For ⊗ = min, we have: Reduction(L 1 ) = 0.2/0, 0.5/0.51, 1/1 and Reduction(L 2 ) = 0.1/0, 0.55/0.5, 1/1 .

Computing Ch N (L) = 0.653 and Ch N (L ′ ) = 0.650 we get L Ch N L ′ .

But Ch N (Reduction(L 1 )) = 0.653 < Ch N (Reduction(L 2 )) = 0.675, i.e. α/L, β/L ′′ ≺ Ch N α/L ′ , β/L ′′ , which contradicts the monotonicity property.

• For ⊗ = * , we have: Reduction(L 1 ) = 0.11/0, 0.275/0.51, 1/1 and Reduction(L 2 ) = 0.055/0, 0.33/0. Counterexample 2 (Ch Π does not satisfy the monotonicity principle). Let L = 1/0, 0.5/0.51, 0.2/1 , L ′ = 1/0, 0.6/0.5, 0.1/1 and L ′′ = 1/0, 0.49/0.51 . L 1 = α/L, β/L ′′ and L 2 = α/L ′ , β/L ′′ , with α = 1 and β = 0.55.

• For ⊗ = min, we have: Reduction(L 1 ) = 1/0, 0.5/0.51, 0.2/1 and Reduction(L 2 ) = 1/0, 0.6/0.5, 0.49/0.51, 0.1/1 . Computing Ch Π (L) = 0.353 and Ch Π (L ′ ) = 0.350 we get L ≻ Ch Π L ′ .

But Ch Π (Reduction(L 1 )) = 0.3530 ≺ Ch Π (Reduction(L 2 )) = 0.3539, i.e. α/L, β/L ′′ ≺ Ch Π α/L ′ , β/L ′′ , which contradicts the monotonicity property.

• For ⊗ = * , we have: Reduction(L 1 ) = 1/0, 0.5/0.51, 0.2/1 and Reduction(L 2 ) = 1/0, 0.6/0.5, 0.26/0.51, 0.1/1 . Computing Ch Π (L) = 0.353 and Ch Π (L ′ ) = 0.350 we get L ≻ Ch Π L ′ .

But Ch Π (Reduction(L 1 )) = 0.3530 < Ch Π (Reduction(L 2 )) = 0.3516, i.e. α/L, β/L ′′ ≺ Ch Π α/L ′ , β/L ′′ , which contradicts the monotonicity property.

As a consequence, Dynamic Programming cannot guarantee an optimal policy. Making a step further, we show that it is impossible to solve the problem in polytime, unless P = NP: Proposition 14. DT-OPT-Ch N and DT-OPT-Ch Π are NP-complete.

The proofs of NP-hardness of these criteria (detailed in Appendix A) follow the principle used by [START_REF] Jeantet | Computing rank dependent utility in graphical models for sequential decision problems[END_REF] for proving the difficulty of the problem in the RDU case. For DT-OPT-Ch Π , the transformation we used is a simplification of the one proposed in [START_REF] Jeantet | Computing rank dependent utility in graphical models for sequential decision problems[END_REF]. For DT-OPT-Ch N , the underlying idea is different and is mainly based on the fact that compounding a lottery with another lottery that is not strictly better than the original one cannot increase its Choquet value (see Section 2.6).

In summary, optimizing possibilistic Choquet integrals is untractable in the general case. We can nevertheless look restrictions that make the question polynomial. It is for instance the case when the decision tree is "binary", i.e. when the leaves involve two levels of utility.

Proposition 15. DT-OPT-Ch N (resp. DT-OPT-Ch Π ) is polynomial on decision trees involving two levels of utility.

A Branch and Bound approach for optimizing the Choquet-based possibilistic criteria

As we have seen in the previous section, possibilistic Choquet integrals define NP-hard problems and the polynomial algorithm of Dynamic Programming may lead to sub-optimal decision policies. As an alternative, we have chosen to proceed by implicit enumeration via a Branch and Bound algorithm, following [START_REF] Jeantet | Rank-dependent probability weighting in sequential decision problems under uncertainty[END_REF] for the case of another (non-possibilistic) Choquet integrals, namely the one encoding the Rank Dependent Utility criterion. The Branch and Bound procedure (see Algorithm 4) takes as argument a partial strategy δ and an upper bound of the Choquet value Ch µ of the best extension of the partial strategy (µ is either the necessity or the possibility measure, depending on the criterion that is to be optimized). It returns the Choquet value of the best strategy found so far, δ opt . As initial value for δ we retain the empty strategy (δ(D i ) = ⊥, ∀D i ). For δ opt , we can choose the strategy provided by the Dynamic Programming algorithm: indeed, even not necessarily providing an optimal strategy, this algorithm generally provides a good one. At each step, the current partial strategy, δ, is developed by the choice of an action for some unassigned decision node. When several decision nodes are candidate, the one with the minimal rank (i.e. the former one according to the temporal order) is developed first. The recursive procedure backtracks when either the current strategy is complete (then δ opt and Ch opt µ may be updated) or proves to be worst than the current δ opt in any case. // Is δ a complete strategy?

if D pend = ∅ then if Ch δ µ > Ch opt µ then δ opt ← δ; Ch opt µ ← Ch δ µ ; else D next ← arg min Di ∈D pend i; foreach C i ∈ Succ(D next ) do δ(D next ) ← C i ; Eval ← Ch µ (Lottery µ (D 0 , δ)); if Eval > Ch opt µ then Ch opt µ ← BranchAndBound(δ, Ch δ µ )
return Ch opt µ ;

Computation of an upper bound for the current partial solution

In order to get an upper bound of the Choquet value of the best completion of δ, we call a function Lottery µ (µ = N or Π ) that computes a lottery that is better than all the complete strategies that extend δ when applied from a node given in argument and use the Choquet value of this lottery as an upper bound of the Choquet value of the best strategy compatible with δ. Whenever Ch µ (Lottery µ (δ)) Ch opt µ the algorithm will backtrack, yielding the choice of another action for the last decision nodes considered. Moreover when δ is complete, Lottery µ (δ) returns L(D 0 , δ); the upper bound is equal to the Choquet value when computed for a complete strategy.

Lottery µ (δ) actually builds a lottery that overcomes with respect of µ all the possible extensions of δ. Formally: Definition 2. A lottery L ∈ L is said to overcome a lottery L ′ ∈ L w.r.t. N (or "to possibility overcome L ′ ") iff: ∀u i , N(L u i ) N(L ′ u i ).

A lottery L ∈ L is said to overcome a lottery L ′ ∈ L w.r.t. Π ("to necessarily overcome L ′ ") iff: ∀u i , Π (L u i ) Π(L ′ u i ).

Ch N (Lottery N (δ)) (resp. Ch Π (Lottery Π (δ))) is an upper bound of the Choquet value of the best strategy compatible with δ.

Indeed:

Proposition 16. If L ′ necessarily (resp. possibly) overcomes L ′′ , then Ch N (L ′ ) Ch N (L ′′ ) (resp. Ch Π (L ′ ) Ch Π (L ′′ )).
Let us build an upper bound of the possibility-based Choquet integral. The computation relies on a Lottery Π (see Algorithm 5 bellow) that computes a lottery that overcomes all the possible extensions of the current strategy. This function inputs a partial strategy and proceeds backwards, assigning a simple lottery 1/u(L i ) to each terminal node LN i . At each chance node C i , it performs the composition of the lotteries in Succ(C i ) according to Eq. [START_REF] Neumann | Theory of Games and Economic Behavior[END_REF]. At each decision node D i it builds a lottery that overcomes all those in Succ(D i ) w.r.t. Π ; this lottery is simply the upper envelop of all the lotteries in Succ(D i ), i.e.

∀i, L

X = L upp Succ(D i ) (u i ) = max L∈Succ(D i ) L[u i ]. It follows directly that L X [u i ] L[u i ] for any L ∈ Succ(D i ), i.e. L X
overcomes each of the lotteries in Succ(D i ). Hence, the Choquet value of Lottery Π (X, δ) is an upper bound of the Choquet value of the best complete strategy rooted in X and extending δ, which proves the correctness of our algorithm for µ = Π .

Let us now build an upper bound for the necessity-based Choquet integral. The computation relies on a function Lottery N (see Algorithm 6) which, as Lottery Π , inputs a partial strategy and proceeds backwards, assigning a simple lottery 1/u(N L i ) to each terminal node LN i . At each chance node C i , it performs the composition of the lotteries in Succ(C i ) according to Eq. [START_REF] Neumann | Theory of Games and Economic Behavior[END_REF]. At each decision node D i it builds a lottery that overcomes all those in Succ(D i ) w.r.t. N. But the case of the necessity-based Choquet integrals is more tricky than the case of the possibility-based integrals. Let us use the following notations and definitions: Algorithm 5: Lottery Π : Computation of a lottery that overcomes w.r.t. Π all the completions of δ when applied from X .

Data: A node X , a (possibly partial) strategy δ Result: A lottery L X // L X [u i ] is the possibility degree to have the utility

u i in L X begin foreach i ∈ {1, . . . , n} do L X [u i ] ← 0; // Initialization of L X if X ∈ LN then L X [u(X)] ← 1 if X ∈ C then foreach Y ∈ Succ( X) do L Y ← Lottery Π (Y , δ); foreach i ∈ {1, . . . , n} do L X [u i ] ← max(L X [u i ], ⊗(π X (Y ), L Y [u i ]));
// ⊗ = min in the ordinal setting; ⊗ = * in the numerical setting

if X ∈ D then if δ(X) = ⊥ then foreach Y ∈ Succ( X) do L Y ← Lottery Π (Y , δ); foreach i ∈ {1, . . . , n} do L X [u i ] ← max(L X [u i ], L Y [u i ]); else L X ← Lottery Π (δ(X), δ); return L X ; • Given a simple lottery L ∈ L, G c L is the possibilistic decumulative function of L: ∀u ∈ U , G c L (u) = N(L u). • Given a set G = {G c L 1 , . . . , G c L k } of decumulative functions, the upper decumulative envelop of G is the decumulative function G c G defined by: ∀u ∈ U , G c G (u) = max G c L i ∈G G c L i (u).
• Given a decumulative function G c on U , Rev(G c ) is the lottery defined by: We have:

Rev G c (u i ) = 1 if i = n, 1 -G c (u i+1 ) if i ∈ {1, . . . , n -1}.
Rev(G c G ) overcomes any lottery L i ∈ {L 1 , . . . , L k }.
Hence, the Choquet value Ch N of Lottery N (D 0 , δ) is an upper bound of the Choquet value of the best complete strategy compatible with δ, which proves the correctness of our algorithm for µ = N.

Experimental results

The algorithms presented in the previous section have been implemented over Java and the computational experiments were carried out on a processor Intel Xeon X5650, 2.66 GHz, 16 GB of RAM. We have compared the performances of the Branch and Bound approach with those of the sole Dynamic Programming procedure. The tests were performed on complete binary decision trees with different height. We have considered four sets of problems, the number of decisions to be made in sequence (denoted seq) varies from 2 to 5, with an alternation of decision and chance nodes: At each decision level i (i.e. odd levels from 1 to seq * 2), the tree contains 2 i-1 decision nodes followed by 2 i chance nodes. Thus, the number of chance nodes in the tree is equal to |C| = |D| *

u i in L X begin foreach i ∈ {1, . . . , n} do L X [u i ] ← 0 if X ∈ LN then L X [u(X)] ← 1 if X ∈ C then foreach Y ∈ Succ( X) do L Y ← Lottery N (Y , δ); for i ∈ {1, . . . , n} do L X [u i ] ← max(L X [u i ], ⊗(π X (Y ), L Y [u i ])) // ⊗ = min in the ordinal setting; ⊗ = * in the numerical setting if X ∈ D then if δ(X) = ⊥ then L X ← Lottery N (δ(X), δ); else if |Succ(X)| = 1 then L X ← Lottery N (δ(Succ(X)), δ); else foreach Y ∈ Succ( X) ∩ N δ do L Y ← Lottery N (Y , δ); foreach i ∈ {1, . . . , n} do G c Y [u i ] ← 1 -max u j <ui L Y [u j ]; // Compute the upper envelop of G c foreach i ∈ {1, . . . , n} do G c [u i ] ← max Y ∈Succ(X)∩Nδ G c Y [u i ]; // Compute Rev(G c ) L X [u n ] ← 1; foreach i ∈ {n -1, . . . , 1} do L X [u i ] ← 1 -G c [u i+1 ]; return L X ;
3. Structure of the randomly generated decision trees for seq = 2.

The values of the utilities have been randomly fired in the set U = {0, 1, . . . , 20} following equiprobable distribution. Conditional possibilities relative to chance nodes are also chosen randomly in [0, 1] and normalized. Each of the four samples of problems contains 300 randomly generated problems. Quality of solutions provided by Dynamic Programming Since the application of Dynamic Programming can lead to sub-optimal strategies, we propose to estimate their quality by comparing them to exact values generated by Branch and Bound. More precisely, we compute for different trees the number of cases for which the value provided by Dynamic Programming is not the optimal one, and for the problems on which it fails, we report the closeness value equal to

V DP V BB
where V DP is the possibilistic Choquet integrals relative to the optimal strategy provided by Dynamic Programming and V BB by Branch and Bound -the results are summarized in Tables 1 and2.

For the necessity-based qualitative Choquet integrals the percentage of full success of the DP approximation is decreasing with the number of decision to be made. Notice that this approximation is very good even when it does not predict the optimal value, with a closeness value greater than 94% in any case. For the possibility-based qualitative Choquet integrals, the closeness value is also very good (greater than 96% in any case) and the percentage of full success of the DP approximation is increasing with the number of decision to be made (this is due to the fact that the higher the number of leaves, the higher the possibility of getting a Ch Π value maximal in the utility scale -to utility degree 20 in our case; for trees with 2047 nodes indeed, all the problems have a Ch Π equal to 20).

The results are similar when the conditioning is numerical (product-based) rather than qualitative (min-based). Tables 3 and4 provide different average execution CPU time for Dynamic Programming and for the complete Branch and Bound procedure.

Obviously, the execution CPU time for Ch N and also for Ch Π in qualitative and numerical setting increases according to the size of the tree, and is better for Dynamic Programming than for the complete than Branch and Bound algorithm. Unsurprisingly, the increasing is linear in the first case and clearly exponential for the latter one. But the times remains affordable in average even for very big trees (341 nodes). For reasonable trees (85 decision nodes) the average CPU time is less than 4 s and the maximal CPU time is about one minute. The results are thus good enough to allow the handling of real-size problems.

Conclusion

In this paper, we have shown that strategy optimization in possibilistic decision trees is tractable for most of the criteria, extending the results about the qualitative utility criteria U pes and U opt to other possibilistic criteria. We have in particular shown that even not fully transitive, the possibilistic likely dominance criteria (LN, L Π ) can be handled in polytime: the number of strategies retained in the set-Extended algorithm of Dynamic Programming can be kept polynomial throughout the process. We have also shown that the problem is intractable for the possibilistic Choquet-based criteria. Finally, we have extended this work to OMEU, defining a new model for sequential decision trees, extending the notion of reduction to kappa lotteries and showing that this model obeys the weak monotonicity principle. These results are summarized in Table 5.

It should be noticed that the optimization of the possibilistic Choquet integrals is "only" in NP: the computation of the Choquet value of a possibilistic strategy is polynomial, whereas this computation can be more costly for other capacity measures; for instance computing the Choquet value of a strategy on the basis of its multi prior expected utility is itself an NP-hard problem -and the corresponding optimization problem is probably beyond NP. Concerning possibilistic Choquet integrals, we have then proposed a Branch and Bound approach that extends the use of Dynamic Programming. Our first experiments suggest that this approach is computationally sustainable. So, it appears that the use of possibilistic decision criteria does not lead to an increase in complexity, except for Choquet integrals. This is an interesting result that allows the extension of our work to possibilistic influence diagrams. Further work includes the development of a direct evaluation algorithm for possibilistic influence diagrams where possibilistic Choquet integrals are used as a decision criteria inspired by the variable elimination approach [START_REF] Jeantet | Computing rank dependent utility in graphical models for sequential decision problems[END_REF].

In the same manner Ch N (L ′ ) can be decomposed into three terms, i.e.

Ch N (L ′ ) = V ′ 1 + V ′ 2 + V ′
3 where:

V ′ 1 = u 1 + (u 2 -u 1 )(1 -λ 1 ) + • • • + (u i -u i-1 ) 1 -max(λ 1 , . . . , λ i-1 ) = V 1 , V ′ 2 = (u i+1 -u i ) 1 -max λ 1 , . . . , λ ′ i + (u i+2 -u i+1 ) 1 -max λ 1 , . . . , λ ′ i , λ i+1 + • • • + (u k -u k-1 ) 1 -max λ 1 , . . . , λ ′ i , λ i+1 , . . . , λ k-1 , V ′ 3 = (u k+1 -u k ) 1 -max(λ 1 , . . . , λ k ) + • • • + (u n -u m-1 ) 1 -max(λ 1 , . . . , λ n ) = V 3 = 0.
As a consequence, it holds that:

Ch N (L) -Ch N (L ′ ) = V 2 -V ′ 2 . Since λ ′ i > λ i , thus 1 -max(λ 1 , . . . , λ ′ i ) 1 -max(λ 1 , . . . , λ i ) and ∀ j, i < j < k, 1 -max(λ 1 , . . . , λ ′ i , . . . , λ j ) 1 - max(λ 1 , . . . , λ i , . . . , λ j ). Thus V ′ 2 V 2 and Ch N (L ′ ) Ch N (L). ✷ Proof of Proposition 2. Let L = Reduction( 1/L 1 , 1/L 2 ).
Since ∀λ, (λ * 1) = λ and min(1, λ) = λ, Eq. ( 5) gives the same L for both ⊗ = * and ⊗ = min, i.e. ∀ j ∈ {1..m}, λ j = max(λ 1 j , λ 2 j ).

Since max u i ∈L 2 ,λ 2 i >0 u i max u i ∈L 1 ,λ 1 i >0 u i , we can get L from L 1 in n steps by replacing at each step j ∈ {1..m}, λ 1 j by max(λ 1 j , λ 2 j ). According to Proposition 1, this is done without increasing the value of the Choquet integral of L. Formally, let L 0 = L 1 , then for j = 1..n, L j = λ j 1 /u 1 , . . . , λ j n /u n such that for any k = j, λ

j k = λ j-1 k and λ j j = max(λ j-1 j , λ j-1 2 ). By construction, L n = L. Thanks to Proposition 1, ∀ j ∈ {1..m}, Ch N (L j ) Ch N (L j-1 ). Then Ch N (L n ) Ch N (L 0 ), i.e. Ch N (L) Ch N (L 1 ). ✷
Proof of Proposition 3. Let δ ∈ such that δ = {(D 0 , δ(D 0 )), . . . , (D i , δ(D i )), . . . , (D n , δ(D n ))} be a complete and sound strategy. We first compute the compound lottery corresponding to δ, merging each decision node D i in δ with the chance node in δ(D i ), say C δ i . We get a compound lottery L = {C δ 0 , . . . , C δ i , . . . , C δ l }; the merging is performed linearly in the number of decision nodes in the strategy.

Then we can suppose without loss of generality that the nodes are numbered in such a way that i < j implies that C δ i does not belong to the subtree rooted by C δ j (we label the nodes from the root to the leaves). Then, for i = m to 1, we replace each compound lottery C δ i = π i (X i1 )/X i1 , . . . , π i (X ik i )/X ik i by its reduction.

Since we proceed from the leaves to the root, the X i1 (i = 1..m) are simple lotteries. Since the min, * and max operators can be performed in linear time and size, the reduction of this 2 level compound lottery is linear in the size of the compound lottery. The size of the resulting compound lottery is bounded by the sum of the size of the elementary lotteries before reduction, and thus linear. In any case, it is bounded by the number of levels in the scale, which is itself bounded by the number of edges and leaves in the tree (for the case where all the possibility degrees and all the utility degrees are different). Hence a complexity of the reduction is bounded by O (|E + LN|), where E is the number of edges and LN is the number of leave nodes in the strategy. Thank to the backward recursion, each node in the strategy is visited only once. Thus a global complexity is bounded by

O (C * (E + LN))
, where E is the number of edges, LN the number of leave nodes and C the number of chance nodes in the strategy. ✷

Proof of Proposition 4. The principle of the Backward induction method at work in Dynamic Programming (Algorithm 1) is to eliminate sub-strategies that are not better than the optimal sub-strategies. The weak monotonicity principle expressed by Eq. ( 21) guarantees that the elimination of sub-strategies that are not strictly better than their concurrents is sound and complete for the decision trees of size 2. Notice that L ≻ O L ′ does not imply that L ′ does not belong to an optimal strategy3 ; but it implies that if L ′ belongs to an optimal strategy, so does L. When a unique strategy among the optimal ones is searched for, the algorithm can forget about L ′ .

• If the three lotteries are unimodal but the mode of L 1 and L 2 is not equal to the one of L b , then the decision is made at possibility level 1, where L 1 and L 2 are identical. Hence the property.

• If L b , L 1 and L 2 are unimodal and share the same mode, u. L 1 can be written as 1/u, a 1 /m 1 , a 1 /M 1 , with m 1 < M 1 and a 1 < 1, L 2 can be written as 1/u, a 2 /m 2 , a 2 /M 2 , with m 2 < M 2 and a 2 < Since α < α ′ , a 1 < a 2 . Moreover, LN satisfies the principle of weak monotonicity, thus Proof of Proposition 11(ii). The proof is similar to the previous one. Thanks to Proposition 9 we can assume without loss of generality that L 1 , L 2 and L b are 2nd core lotteries. Consider the case where they are unimodal and share the same mode, u (if not, refer to the previous proof). Then: L 1 can be written as 1/u, a 1 /m 1 , a 1 /M 1 , with m 1 < M 1 and a 1 < 1, L 2 can be written as 1/u, a 2 /m 2 , a 2 /M 2 , with m 2 < M 2 and a 2 < 1, L b can be written as 1/u, b/m b , b/M b , with m b < M b and b < 1. Following the previous proof, we have u Proof of Proposition 13. Let L, L ′ and L ′′ be 3 kappa lotteries. We can suppose without loss of generality that they are in reduced form, i.e. that:

L ∼ LN L ′ implies L 1 ∼ LN L 2 . Thanks to Proposition 10, L 1 ∼ LN L 2 and a 1 < a 2 imply m 2 < u < M 2 . By hypothesis, L 2 ≻ LN L b . We have m 2 < u < M 2 , suppose that a 2 b, this implies Π(L 2 > L b ) = a 2 and Π(L b > L 2 ) = a 2 . Thus a 2 b contradicts the hypothesis. Hence b > a 2 . Since b > a 2 , Π(L 2 > L b ) > Π (L b > L 2 ) iff Π(L 2 > L b ) = b and Π(L b > L 2 ) < b. Which means that at level b, u > M b (if u < M b , Π(L b > L 2 ) = b and u = M b is not possible).
/ ∈ {M 1 , m 1 , M 2 , m 2 , M b , m b } and also L 1 ∼ LN L 2 and a 1 < a 2 imply m 2 < u < M 2 . By hypothesis, L b ≻ LN L 2 . But a 2 b and m 2 < u < M 2 imply that Π(L 2 > L b ) = a 2 and Π(L b > L 2 ) = a 2 . Thus a 2 b contradicts the hypothesis. Hence b > a 2 . Since b > a 2 , Π(L 2 < L b ) > Π (L b < L 2 ) iff Π(L 2 < L b ) = b and Π(L b < L 2 ) < b. Which means that at level b, u < m b (if u > m b , Π(L b < L 2 ) = b and u = m b is impossible).
L = κ 1 /µ 1 , . . . , κ n /µ m , L ′ = κ ′ 1 /µ 1 , . . . , κ ′ n /µ m and L ′′ = κ ′′ 1 /µ 1 , . . . , κ ′′ n /µ m . Let L 1 = Reduction( α/L, β/L ′′ ) and L 2 = Reduction( α/L ′ , β/L ′′ ).
According to Eq. ( 22) the kappa-ranking of utility degree u 1 k from L 1 is

κ 1 k = min (α + κ k ), β + κ ′′ k .
Thus:

OMEU(L 1 ) = min i=1..m min (κ i + α), κ ′′ i + β + u i .
Similarly:

OMEU(L 2 ) = min i=1..m min κ ′ i + α , κ ′′ i + β + u i .
Suppose that OMEU(L) OMEU(L ′ ), i.e. min i=1..m

{κ i + u i } min i=1..m κ ′ i + u i ⇒ min i=1..m {κ i + u i } + α min i=1..m κ ′ i + u i + α ⇒ min i=1..m {κ i + u i + α} min i=1..m κ ′ i + u i + α .
As a consequence, we get: min min i=1..m

κ ′′ i + u i + β , min i=1..m {κ i + u i + α} min min i=1..m κ ′′ i + u i + β , min i=1..m κ ′ i + u i + α .
By associativity of the min operator, we get:

min i=1..m min κ ′′ i + u i + β , {κ i + u i + α} min i=1..m min κ ′′ i + u i + β , κ ′ i + u i + α . Hence: min i=1..m min[(κ i + α), (κ ′′ i + β)] + u i min i=1..m min[(κ ′ i + α), (κ ′′ i + β)] + u i .
That is to say that OMEU(L 1 ) OMEU(L 2 ). ✷ Proof of Proposition 14. We first show that DT-OPT-Ch N and DT-OPT-Ch Π belong to the NP class. Next, we prove that 3CNF can be polynomially reduced to our problem, following the principle used by [START_REF] Jeantet | Computing rank dependent utility in graphical models for sequential decision problems[END_REF] for proving the difficulty of the problem in the RDU case. For DT-OPT-Ch Π , the transformation we used is a simplification of the one proposed in [START_REF] Jeantet | Computing rank dependent utility in graphical models for sequential decision problems[END_REF]. For DT-OPT-Ch N , the underlying idea is different and is mainly based on the fact that compounding a lottery with another lottery that is not strictly better than the original one cannot increase its Choquet value (see Section 2.6).

Membership to NP

The membership of DT-OPT-Ch N (resp DT-OPT-Ch Π ) to NP is straightforward, using the following procedure:

1. Call to the NP oracle • Guess a strategy δ from T 2. Polytime checking

• Compute L = Reduce(δ), using Eq. ( 5)

3. Compute Ch µ (µ is N or Π ) • max ← 0 • Ch µ ← u 1 • If µ = N, then ∀i = 1, m -1 -if max < λ L j , then max ← λ L j -Ch µ ← Ch µ + (u i+1 -u i ) * (1 -max) • If µ = Π , then ∀i = m, 2 -If max < λ L j , then max ← λ L j -Ch µ ← Ch µ + (u i -u i-1 ) * max • Check that Ch µ θ
Since the reduction operation is linear in the size of the compound lottery and the computation of the necessity-based Choquet value (resp. the possibility-based Choquet value) is linear in the number of utility levels in the utility scale, the full procedure is polynomial. Hence DT-OPT-Ch N (resp. DT-OPT-Ch Π ) belongs to NP.

NP-hardness of DT-OPT-C h N

The hardness of DT-OPT-Ch N is obtained by a reduction from the 3-SAT problem. Each instance of the 3-SAT problem is a CNF-formula consisting of m clauses, denoted by Cl = {Cl 1 , . . . , Cl m }, on a set of n propositional variables X = {X 1 , . . . , X n } such that ∀X i ∈ X , x i and ¬x i are called literals. The set of all literals is denoted by L and l i denotes any literal in L.

Each clause Cl i is composed of 3 literals. Given a 3CNF, the question is whether there is a value-assignment of its literals which satisfies its clauses or not. The principle of the transformation from any 3CNF into a possibilistic decision tree can be summarized as follows:

• For each literal l i ∈ L we define a utility u l i and a possibility degree λ l i . We also define a utility degree u ⊤ such that ∀l i ∈ L, u ⊤ > u l i . • For each X i ∈ X we associate a decision node D X i with two children relative to the two choices x i and ¬x i , i.e.

C x i = 1/u ⊤ , λ x i /u x i and C ¬x i = 1/u ⊤ , λ ¬x i /u ¬x i .
• For each Cl i ∈ Cl, we associate a decision node D Cl i with three children relative to its three literals. In fact, for each literal l i ∈ Cl i , we associate a chance node C Cl i l i = 1/u ⊤ , λ l i /u l i meaning that the satisfaction of Cl i is ensured by the choice of l i . When selecting a chance node for D Cl i , a strategy specifies how it intends to satisfy Cl i .

More formally, given a CNF Cl = {Cl 1 , . . . , Cl m } on X = {x 1 , . . . , x n }, the necessity-based transformation into a possibilistic tree ΠT can be ensured by the following procedure. A strategy δ can select the literals in a consistent manner (in this case, if L is chosen for x i , ¬l is never chosen for a D Cl i ) or in a contradictory manner (i.e. δ selects L in some decision and ¬l for some others). By construction, there is a bijection between the non-contradictory strategies, if any, and the models of the formula.

. Fix ǫ ∈ [0, 1] such that ǫ n < 0.5 2. ∀x i ∈ X • u x i ← 2(n -i) + 1 • λ x i ← ǫ i+1 • u ¬x i ← 2(n -i) + 2 • λ ¬x i ← ǫ i 3. Let u ⊤ ← 2n + 1
The simple lottery equivalent to some strategy δ is the following: π(⊤) = 1, π(u l ) = λ l if literal L is chosen for some decision node, π(u l ) = 0 otherwise. The set of simple lotteries equivalent to contradictory strategies is included in:

L NC = {L: L[u ⊤ ] = 1, ∀l ∈ L, L[u l ] ∈ {0, λ l } and min(L[u l ], L[u ¬l ] = 0}. The set of simple lotteries equivalent to contradictory strategies is included in: L C = {L: L[u ⊤ ] = 1, ∀l ∈ L, L[u l ] ∈ {0, λ l }, ∃l ∈ L s.t. min(L[u l ], L[u ¬l ]) = 0}.
The principle of the proof is to set the values of the λ l 's and the u l 's in such a way that the Choquet value of the worst of the non-contradictory lotteries is greater than the Choquet value of the best contradictory lottery. To this extend, we choose an ǫ ∈ [0, 1] such that ǫ n < 0.5. Then we set:

λ x i = ǫ i+1 , u x i = 2(n -i) + 1, λ ¬x i = ǫ i , u ¬x i = 2(n -i) + 2 and u ⊤ = 2n + 1.
It holds that:

-The worst non-contradictory lottery in L NC (i.e. the one having the lowest Ch N value), denoted by L ↓ NC , is such as all the positive literals are possible and the possibility of any negative literal is equal to 0, i.e. 4 L

↓ NC = λ x n /u x n , . . . , λ x 1 /u x 1 , 1/u ⊤ .
This holds since according to the proposed encoding, utilities of positive literal are always lower than their negative version (u

x i = 2(n -i) + 1 < u ¬x i = 2(n -i) + 2).
-The best contradictory lottery in L C (i.e. the one having the greatest Ch N value), denoted by L ↑ C is such as all negative literals are possible and the possibility of any positive literal is equal to 0 except for x 1 (i.e. the one having the greatest utility value within all positive literals), i.e. 5

L ↑

C = λ ¬x n /u ¬x n , . . . , λ x 1 /u x 1 , λ ¬x 1 /u ¬x 1 , 1/u ⊤ .
This holds since (i) according to the proposed codification, utilities of negative literal are always greater than their positive version (u

x i = 2(n -i) + 1 < u ¬x i = 2(n -i) + 2)
, moreover the presence of x 1 and ¬x 1 causes the contradiction (we choose x 1 since u x 1 is the greatest utility value within all positive literals) and (ii) the less the number of utilities in the lottery receiving a non-negative possibility degree, the greater the Choquet value (Proposition 2).

Considering L ↓ NC , the utilities that receive a positive possibility degrees are, by increasing order: u x n < u x n-1 < • • • < u x 1 < u ⊤ (∀i = 1..n, ¬x i , receive a possibility degree equal to 0). Hence: 4 For the sake of simplicity we omitted terms where possibility degrees are equal to 0.

Ch N (L

↓ NC = u x n + (u x n-1 -u x n )(1 -λ x n )
+ (u x n-2 -u x n-1 ) 1 -max(λ x n , λ x n-1 )

+ • • • + (u x 1 -u x 2 ) 1 -max(λ x n , . . . , λ x 2 )
+ (u ⊤ -u x 1 ) 1 -max(λ x n , . . . , λ x 2 , λ x 1 )

= 1 + 2(1 -λ x n ) + 2(1 -λ x n-1 ) + • • • + 2(1 -λ x 1 ) = 2n + 1 -2(λ x n + • • • + λ x 1 ).
Considering L ↑ C , the utilities that receive a positive degree of possibility are, by increasing order:

u ¬x n < u ¬x n-1 < • • • < u ¬x 2 < u x 1 < u ¬x 1 < u ⊤ (
all the x i , i > 1, receives a possibility degree equal to 0). Hence:

Ch N L ↑ C = u ¬x n + (u ¬x n-1 -u ¬x n )(1 -λ ¬x n ) + (u ¬x n-2 -u ¬x n-
+ • • • + 2(1 -λ ¬x 3 ) + (1 -λ ¬x 2 )
+ (1λ x 1 )

+ (1 -λ ¬x 1 ) = 2 + 2(1 -λ ¬x n ) + 2(1 -λ ¬x n-1 ) + • • • + (1 -λ ¬x 2 )
+ (1λ ¬x 2 ) (since by definition λ x 1 = λ ¬x 2 )

+ (1 -λ ¬x 1 ) = 2(1 -λ ¬x n ) + 2(1 -λ ¬x n-1 ) + • • • + 2(1 -λ ¬x 2 )
+ (1λ ¬x 1 )

= 2 + 2(n -1) -2(λ ¬x n + • • • + λ ¬x 2 ) + 1 -λ ¬x 1 = 2n + 1 -2(λ ¬x n + • • • + λ ¬x 2 ) -λ ¬x 1 .

Table 6

Quantification of the decision tree in Fig. 4. = λ ¬x 1 -2λ x n (since by definition λ ¬x i = λ x i-1 ).

x
Recall that by construction λ ¬x 1 = ǫ and λ x n = ǫ n+1 :

Ch N (L ↓ NC ) -Ch N (L ↑ C
) is equal to ǫ -2ǫ n+1 . Since we have chosen ǫ in [0, 1] is such a way that ǫ n < 0.5, we get This shows that the Choquet value of any non-contradictory strategy, if such a strategy exists, is greater than the Choquet value of the best contradictory strategy. Moreover, the CNF is consistent iff there exists a non-contradictory strategy. This means that the CNF is consistent iff there exists a strategy with a Choquet value Ch N greater than Ch N (L

↑ C ) = 2n + 1 - 2(λ ¬x n + • • • + λ ¬x 2 ) -λ ¬x 1 .
To illustrate the necessity-based transformation, we will consider the 3CNF (x 1 ∨ x 2 ∨ x 3 ) ∧ (¬x 1 ∨ ¬x 2 ∨ ¬x 3 ) corresponding to the decision tree of Fig. 4. Table 6 represents necessary values for the quantification of this decision tree by following steps of transformation for ǫ = 0.

NP-hardness of DT-OPT-C h Π

The hardness of DT-OPT-Ch Π is proved by the reduction from a 3-SAT problem. More precisely, given a CNF Cl = {Cl 1 , . . . , Cl m } on X = {X 1 , . . . , X n } the possibility-based transformation into a possibilistic decision tree ΠT can be ensured by the following procedure.

1. Fix ǫ such that 0 < ǫ < 1 2. Create a decision node D 0 as the root of ΠT 3. Create a chance node H 4. Add H as a child of D 0 5. ∀x i ∈ X

• Create a decision node D X i with two children C x i and C ¬x i s.t.:

• C x i is initialized with the lottery 1/0 • C ¬x i is initialized with the lottery 1/0 6. ∀Cl i ∈ Cl, ∀ literal l j ∈ Cl i : Add to C l j the lottery ǫ i / i-1 k=0 10 k Consider a 3CNF with m clauses Cl = {Cl 1 , . . . , Cl m } on the set X = {X 1 , . . . , X n } of propositional variables. The set of all literals is denoted by L and l i denotes any literal in L. In the following, we will use a constant 0 < ǫ < 1. Obviously, ∀i ∈ {1..m}, ǫ i < 1, and i < j implies ǫ i > ǫ j .

A decision tree is built with a root node D 0 having as unique child a chance node (denoted by H ) that branches on n decision nodes D X i , i = 1 . . . n (with a possibility degree equal to 1 for each child). Each D X i must make a decision on the value of X i (i.e. x i or ¬x i ), that is why it has two children, C x i and C ¬x i , which are chance nodes. Consider any literal l i ∈ L and its corresponding chance node C l i , for the purpose of normalization of its possibility distribution, we systematically add to C l i a leave labeled with utility 0 with a possibility degree equal to 1. In addition, for any Cl i ∈ Cl satisfied by l i , a leave node is added as a child of C l i , with a possibility degree equal to ǫ i and a utility degree equal to i-1 k=0 10 k . In other words, the associated utility to Cl 1 (resp. Cl 2 , Cl 3 , . . . , Cl m ) is 1 (resp. 11, 111, . . . , 1..1 m terms )). One can check that: -There is a bijection between the interpretation of the CNF and the admissible strategies.

-Ch Π value of a strategy δ is equal to i=1,m,δ satisfies Cl i 10 i-1 * ǫ i .

The greater the number of clauses satisfied by a strategy, the greater its Ch Π value. Hence the CNF is consistent iff there exists a strategy with a Choquet value (greater or) equal to i=1..m 10 i-1 * ǫ i , i.e. which satisfies all clauses. Fig. 5 gives an example of this transformation for the 3CNF ((x 1 ∨ x 2 ∨ x 3 ) ∧ (¬x 1 ∨ ¬x 2 ∨ ¬x 3 )) where Cl 1 = (x 1 ∨ x 2 ∨ x 3 )

and Cl 2 = (¬x 1 ∨ ¬x 2 ∨ ¬x 3 ). With ǫ = 0.2 we obtain u(Cl 1 ) = 1, u(Cl 2 ) = 11, π(Cl 1 ) = 0.2 and π(Cl 2 ) = 0.04. We have i=1,2 10 i-1 * 0. First of all, let us remark that the composition of several lotteries built on U only leads by reduction to a simple lottery built on U only.

Let L = λ 1 /u 1 , λ 2 /u 2 , L ′ = λ ′ 1 /u 1 , λ ′ 2 /u 2 and L ′′ = λ ′′ 1 /u 1 , λ ′′ 2 /u 2 be three simple lotteries built on U .

Let L 1 = Reduction( α/L, β/L ′′ ) and L 2 = Reduction( α/L ′ , β/L ′′ ).

Fig. 1 .

 1 Fig. 1. A possibilistic compound lottery (a) and its reduction (b) (same reduction with ⊗ = min and ⊗ = * ).

Example 4 .

 4 Let L = 0.7/10, 0.5/20, 1/30, 1/40 and L ′ = 0.2/10, 1/20, 0.9/30 be two simple lotteries. L core = 1/30, 1/40 and L ′ core = 1/20 . It holds, in both numerical and ordinal settings, that

Algorithm 2 :

 2 ExtProgDyn(N: node). Result: A set S of pairs (L, δ L ) Data: O is the criterion to optimize ( O = LΠ or O = LN). Constant: The empty strategy δ 0 begin if N ∈ LN // Leaves

Algorithm 3 :

 3 Decision nodes then // Build the set of possible decisions S ← ∅; foreach Y ∈ Succ(N) do S ← S ∪ ExtProgDyn(Y ) foreach (L, δ) ∈ S do δ(N) ← L S ← Prune O (S); return S; Prune O (S: a set S of pairs (L: strategy, δ L : lottery)). Data: O is the criterion to optimize ( O = LΠ or O = LN) Result: A pruned set Res of pairs (L ′ , δ ′ L ) begin Res ← S; foreach (L, δ) ∈ S do foreach

Algorithm 4 :

 4 BB(δ: a (partial) strategy, Ch µ : its Choquet value) with µ = N or µ = Π . Result: Ch opt µ i.e. the value of δ opt , the best strategy found so far begin if δ = ∅ then D pend ← {D 0 } else D pend ← {D i ∈ D s.t. δ(D i ) = ⊥ and ∃D j , δ(D j ) = ⊥ and D i ∈ Succ(δ(D j ))};

Lemma 1 .Proposition 17 .

 117 Now it is easy to show the following lemma: The possibilistic decumulative function associated to a lottery Rev(G c ) is equal to G c .As a consequence of Lemma 1, we have: Given a set {L 1 , . . . , L k } ⊆ L of simple lotteries over U and G = {G c L 1 , . . . , G c L k } the set of their decumulative functions.

Algorithm 6 :

 6 Fig. 3.)

1 ,

 1 L b can be written as 1/u, b/m b , b/M b , with m b < M b and b < 1. Notice that u / ∈ {M 1 , m 1 , M 2 , m 2 , M b , m b } (the possibility degree of u is equal to 1 while the possibility degrees of M 1 , m 1 , M 2 , m 2 , M b and m b are equal to a 1 , a 2 or b which are all strictly less than 1).

a 1 <

 1 b (Since a 1 < a 2 and a 2 < b): the comparison of L 1 and L b is made at level b. From u > M b we conclude Π(L 1 > L b ) = b and Π(L b > L 1 ) < b, i.e. L 1 ≻ LN L b . Hence when L b , L 1 and L 2 are unimodal and share the same mode, L 2 ≻ LN L b implies L 1 ≻ LN L b . ✷

a 1 <

 1 b (Since a 1 < a 2 and a 2 < b): the comparison of L 1 and L b is made at level b. From u < m b we conclude that Π(L 1 < L b ) = b and Π(L b < L 1 ) < b, i.e. L 1 ≻ LN L 1 . Hence, when L 1 , L 2 and L b are unimodal and share the same mode, L b ≻ LN L 2 implies L b ≻ LN L 1 . ✷

1

 1

  Ch N (L ↓ NC ) -Ch N (L ↑ C ) > 0, i.e. Ch N (L ↓ NC ) > Ch N (L ↑ C ).

8 .↑ C ) = 2 * 3 + 1 -( 2 * 1 Cl 1 ), (D Cl 2 = d ¬x 3 Cl 2 )

 823121132 The best contradictory lottery L ↑ C = 0.343/2, 0.49/4, 0, 49/5, 0.7/6, 1/7 s.t. Ch N (L (0.343 + 0.49)) -0.7 = 4.643. If we consider the strategyσ = {(D 0 = d 0 ), (D Cl 1 = d x , (D x 1 = d x 1 ), (D x 2 = d x 2 ), (D x 3 = d ¬x 3 )), the compound lottery corresponding to σ is L = 0.343/2, 0.343/3, 0.49/5, 1/7 withCh N (L) = 6.011 > Ch N (L ↑ C ) = 4.643 which means that the 3CNF is satisfiable by the instance x 1 ∧ x 2 ∧ ¬x 3 .

Fig. 4 .

 4 Fig. 4. NP-hardness of DT-OPT-ChN : transformation of the 3CNF ((x 1 ∨ x 2 ∨ x 3 ) ∧ (¬x 1 ∨ ¬x 2 ∨ ¬x 3 )) s.t. Cl 1 = (x 1 ∨ x 2 ∨ x 3 ) and Cl 2 = (¬x 1 ∨ ¬x 2 ∨ ¬x 3 ) with ǫ = 0.8.-The reduction is performed in O (n + m).

  2 i = 0.64. If we consider the strategy σ = {(D 0 = d 0 ), (D x 1 = d x 1 ), (D x 2 = d x 2 ), (D x 3 = d ¬x 3), the compound lottery corresponding to σ is L = 1/0, 0.2/1, 0.04/11 with Ch Π (L) = 0.64 which means that the 3CNF is satisfiable by the instance x 1 ∧ x 2 ∧ ¬x 3 . ✷ Proof of Proposition 15. Let U = {u 1 , u 2 } be the set of considered utilities.

  This procedure crosses each edge in the tree only once. When the comparison of simple lotteries by O (Algorithm 1, Line 2) and the reduction operation on a 2-level lottery (Algorithm 1, Line 1) can be performed in polytime, its complexity is polynomial w.r.t. the size of the tree.

	Proposition 4. If O is transitive and satisfies the weak monotonicity property, then Algorithm 1 computes a strategy optimal w.r.t.
	criterion O in time polynomial with respect to the size of the decision tree (assuming that the reduction operation and the comparison
	of lotteries can be performed in polytime).

  5, 1/1 . Computing Ch N (L) = 0.653 and Ch N (L ′ ) = 0.650 we get L Ch N L ′ . But Ch N (Reduction(L 1 )) = 0.809 < Ch N (Reduction(L 2 )) = 0.45, i.e. α/L, β/L ′′ ≺ Ch N α/L ′ , β/L ′′ , which contradicts the monotonicity property.

Table 1

 1 Percentage of problems for which the DP value is correct.

			Length seq of the sequence
			2	3	4	5
	Ch N	Qualitative	91%	76%	51%	34%
		Numerical	96%	86%	62%	41%
	Ch Π	Qualitative	95%	86%	92%	99%
		Numerical	95%	88%	93%	98%

Table 2

 2 Average closeness value V DP V BBfor problems in which V DP = V BB .

			Length seq of the sequence
			2	3	4	5
	Ch N	Qualitative	95.0%	95.6%	94.7%	94.7%
		Numerical	94%	97%	97%	98%
	Ch Π	Qualitative	96.4%	97.8%	98.5%	99.1%
		Numerical	97%	98%	98%	99%

Table 3

 3 Execution CPU time for Ch N (in seconds).

			Length seq of the sequence
			2	3	4	5
	Qualitative setting	ProgDyn	0.013	0.014	0.083	0.30
		BB	0.05	0.1	3.77	55 214
	Numerical setting	ProgDyn	0.02	0.02	0.06	0.275
		BB	0.05	0.07	3.5	42 362

Table 4

 4 Execution CPU time for Ch Π (in seconds).

			Length seq of the sequence
			2	3	4	5
	Qualitative setting	ProgDyn	0.01	0.04	0.07	0.15
		BB	0.023	0.103	1.943	4817.753
	Numerical setting	ProgDyn	0.01	0.026	0.033	0.235
		BB	1	1.07	1.426	395.13

Table 5

 5 Results about the complexity of DT-OPT-O .

	U pes	U opt	PU	LΠ	LN	OMEU	Ch N	Ch Π
	P	P	P	P	P	P	NP-complete	NP-complete

  4. Create a decision node D 0 as the root of ΠT 5. Create a chance node H as the unique child of D 0 6. ∀X i ∈ X Create a decision node D X i with two children C x i and C ¬x i s.t.:•C x i is the simple lottery 1/u ⊤ , λ x i /u x i • C ¬x i is the simple lottery 1/u ⊤ , λ ¬x i /u ¬x i • Add D X i tothe children of H , with a possibility degree equal to 1 7. ∀Cl i ∈ Cl • Create a decision node D Cl i • ∀l i ∈ Cl i -Create a chance node C Cl i l i corresponding to the simple lottery 1/u ⊤ , λ l i /u l i -Add C Cl i l i to the children of D Cl i • Add D Cl i to the children of H , with a possibility degree equal to 1 This transformation is performed in O (m + n) since the resulted decision tree contains m + n + 1 decision nodes, 3m + 2n + 1 chance nodes and (3m + 2n) × 2 leaves.

  1 ) 1 -max(λ ¬x n , λ ¬x n-1 )+ • • • + (u ¬x 2 -u ¬x 3 ) 1 -max(λ ¬x n , . . . , λ ¬x 3 ) + (u x 1 -u ¬x 2 ) 1 -max(λ ¬x n , . . . , λ ¬x 2 ) + (u ¬x 1 -u x 1 ) 1 -max(λ ¬x n , . . . , λ ¬x 2 , λ x 1 ) + (u ⊤ -u ¬x 1 ) 1 -max(λ ¬x n , . . . , λ ¬x 2 , λ x 1 , λ ¬x 1 )

	= 2

+ 2(1λ ¬x n ) + 2(1λ ¬x n-1 )

  = 2n + 1 -2(λ x n , . . . , λ x 1 ) = -2n -1 + 2(λ ¬x n , . . . , λ ¬x 2 ) + λ ¬x 1 = 2(λ ¬x n , . . . , λ ¬x 2 ) + λ ¬x 1 -2(λ x n , . . . , λ x 1 )

		1	¬x 1	x 2	¬x 2	x 3	¬x 3
	u	5	6	3	4	1	2
	λ	0.49	0.7	0.343	0.49	0.24	0.343
	It follows that:
	Ch N L	↓ NC -Ch N L	↑

C

This paper is an extended version of a preliminary work about the complexity of possibilistic decision trees presented in[START_REF] Fargier | On the complexity of decision making in possibilistic decision trees[END_REF].

The size of a simple lottery is the number of its outcomes; the size of a compound lottery is the sum of the sizes of its sub-lotteries plus the number of its sub-lotteries.

That is why we called the property "weak monotonicity" -strong monotonicity is expressed by: L O L ′ iff α/L, β/L ′′ O α/L ′ , β/L ′′ . Strong monotonicity thus adds to weak monotonicity that if L ≻ O L ′ then L ′ does not belong to an optimal strategy.

Acknowledgements

The authors would like to thank the anonymous reviewers for their helpful and constructive comments that greatly contributed to improving.

Appendix A

Proof of Proposition 1. Let u k be the best possible utility in L, i.e. u k = max u j ∈L,λ j >0 u j , λ k 1 (i.e. is not necessarily equal to 1), but ∃ j, 1 j k s.t. λ j = 1 and thus ∀ j, k j n, 1 -max(λ 1 , . . . , λ j ) = 0.

L and L ′ are written as follows: L = λ 1 /u 1 , . . . , λ i-1 /u i-1 , λ i /u i , λ i+1 /u i+1 , . . . , λ k-1 /u k-1 , λ k /u k , λ k+1 /u k+1 , . . . , λ n /u n ,

The sequel on the proof is by recursion on the depth of the decision tree. The property obviously holds for decision trees of depth 1:

• If the first node is a chance node, no decision is to be made and there is only one strategy, the empty one;

• If the first node is a decision one, the transitivity of O guarantees that the max value obtained at Line 2 (Algorithm 1) is not strictly lower (according to ≻ O ) than the others.

Suppose that the property holds for decision trees of depth n. Consider a tree of depth n + 1:

• If the first node is a chance node, the monotonicity principle ensures that the union of the sub-strategies given by the recursive calls is not dominated according to ≻ O ; • If the first node (say N) is a decision node, the procedure is called recursively on each of its children Y i . Let (Y i ) be the set of possible strategies for the sub-decision trees rooted in Y i ; the recursive call on each Y i returns a strategy

-Weak monotonicity of PU Consider any three lotteries L, L ′ and L ′′ . We can suppose without loss of generality that they are in a reduced form, i.e.:

According to the reduction operation, we get:

Suppose that L PU L ′ . We have to prove that L 1 PU L 2 . Recall that max(α, β) = 1 and that L PU L ′ arises in 3 cases (i.e. (i) u = v = 1 and u v, (ii) u v and u = v = 1, (iii) u = 1, v < 1 and v = 1) which corresponds to 6 different cases. We show that L 1 PU L 2 can be deduced in each of these cases:

• Case 1: u = v = 1 and u v, α = 1. Then:

Hence L 1 PU L 2 .

• Case 2:

Then

• Case 3: u = v = 1 and u v, α = 1. This case is similar to case 1 (exchanging the roles of positive and negative utilities).

• Case 4: u = v = 1 and u v, β = 1. This case is similar to case 2 (exchanging the roles of positive and negative utilities).

• Case 5:

That is to say u 1 = 1 u 2 and u 1 u 2 = 1, i.e. L 1 = 1/⊤, u 1 /⊥ and L 2 = u 2 /⊤, 1/⊥ . Thus using Eq. ( 9),

Since ⊗ is decreasing, max(⊗(α, u), w) max(α, w) (i.e. u 1 u 2 ) and max(α, w) max(⊗(α, v), w)) (i.e. u 1 u 2 ). Thus using Eq. ( 9),

So, in any case, L PU L ′ implies that L 1 PU L 2 .

-Weak monotonicity of U pes and U opt Consider any three lotteries L, L ′ , L ′′ and let L 1 = Reduction( α/L, β/L ′′ ) and L 2 = Reduction( α/L ′ , β/L ′′ ). We can, without loss of generality, suppose that L, L ′ and L ′′ are constant lotteries (thanks to certainty equivalence axiom, see [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF]),

i.e. L = 1/u , L ′ = 1/u ′ and L ′′ = 1/u ′′ : in L (resp. L ′ , resp. L ′′ ), any utility degree different fro u (resp. u ′ , resp. u ′′ ) receives a possibility degree equal to 0. Then, for both interpretations of ⊗:

-

Let a = max(u ′′ , 1 -β), then: U pes (L 1 ) = min(max(u, 1 -α), a) and

-

In what follows we develop a formal proof for Proposition 6 which is a direct consequence of the basic axiom defined by Dubois et al. [START_REF] Dubois | Qualitative decision theory: from Savage's axioms to nonmonotonic reasoning[END_REF]. Consider any three lotteries L, L ′ and L ′′ . We can suppose without loss of generality that they are in a reduced form, i.e.:

When α = 1, we have

When β = 1, we have

) the set of utility degrees receiving a possibility equal to 1 in L (resp. L ′ , L 1 , L 2 ). These sets are not empty since the distributions are normalized. It holds that

• If α < 1 and β = 1: let u i be any of the degrees that receive a possibility degree equal to 1 in

Thus L LΠ L ′ implies that L 1 LΠ L 2 in both cases. ✷ Proof of Proposition 7. We give the proof for ∀L,

When L and L ′ are unimodal and share the same mode, L 2nd is of the form γ /m, 1/u, γ /M and

Let us first assume that α = 1, then two cases can be distinguished:

-Case 2: min(L ′ =1 ) max(L =1 ). Then the two lotteries are unimodal and share the same mode, say u (if this was not the case, we had Π(L ′ ≻ L) = 1 and Π(L

and L 2nd 2 contains u (and only u).

(value u at level π = 1 and bounds of the core of L ′′ at level π = β), and thus

• If γ β γ ′ , L 2nd

1 contains u at level π = 1, a value equal or greater than M at level γ and the core of L 2nd 2 contains u.

2 contains u at level π = 1, a value equal or lower than m ′ at level γ ′ and the core of L 2nd 1 contains u.

When α < 1 (and thus β = 1) the core of L 1 and L 2 is the one of L ′′ and two cases can be distinguished:

-Case 1: L ′′ is not unimodal, the comparison is made at level π = 1 and thus L 1 ∼ LN L 2 ; -Case 2: L ′′ is unimodal, L ′′ 2nd is of the of the form γ ′′ /m ′′ , 1/u ′′ , γ ′′ /M ′′ ; because L and L ′ are also unimodal, so are L 1 and L 2 -because α < 1, their mode is u ′′ . Thus:

• If α γ ′′ and u = u ′′ , then the second level on L 1 (resp. L 2 ) contains the core of L 1 (resp. L 2 ), i.e. contains u. Thus

and γ ′′ max(min(α, γ ′ ), min(α, γ ′ ) then the second level on L 1 (resp. L 2 ) is the one of possibility degree π = γ ′′ and contains the second level of L ′′ :

• If u = u ′′ and max(min(α, γ ), min(α, γ ′ )) γ ′′ then the second level on L 1 (resp. L 2 ) is the one of possibility degree π = min(α, γ ) (resp. π = min(α, γ ′ )) and contains the second level of L (resp. L ′ ): L 2nd 1 is of the form min(α, γ )/v, 1/u, min(α, γ )/V with v m and V M, and

and min(α, γ ) > γ ′′ > min(α, γ ′ ) then (i) γ > γ ′ and then L LN L ′ implies M > u and (ii) the second level on L 1 is the one of possibility degree π = min(α, γ ) contains the second level of L:

and min(α, γ ′ ) > γ ′′ > min(α, γ ) then (i) γ ′ > γ and then L LN L ′ implies u > m ′ and (ii) the second level on L 2 is the one of possibility degree π = min(α, γ ′ ) and contains the second level of

Proof of Proposition 9. We give the proof for ∀L,

is similar.)

This inequality is satisfied in three cases only:

Since L 2nd precisely contains max(L =1 ) and min(L =1 ) (at level 1) and max(L

Reciprocally, if L 2nd L ′ , then it is easy to check that one of the three previous cases is fulfilled and thus

(Similar results hold for α ′ > α.)

• If u = u ′ , then only the modes are used to make the decision: either u > u ′ , and then

• If u = u ′ , decision is made at level max(α, α ′ ); when α > α ′ , then either u > M (and then L ′ ≻ LN L); or u < m (and

So, u = u ′ is a necessary condition for the indifference of the two lotteries. Moreover, M = u (resp. m = u) is not possible since the possibility of u is equal to 1 for both L and L ′ and the possibility of M (resp. m) is strictly lower than 1. Thus two cases are possible:

• Case 1: M = m, then the two possible cases are:

-If u > M = m, then Π(L ′ > L) = α (at level α, L ′ can take value u and L value m) and Π(L > L ′ ) < α (one have go below α to find a value for L strictly greater than u); Π(L > L ′ ) cannot be equal to Π(L ′ > L ′ ), i.e. L and L ′ cannot be indifferent.

-If u < M = m, then Π(L > L ′ ) = α (at level α, L ′ can take value u and L value m) and Π(L ′ > L) < α (one have go below α to find a value for L strictly lower than u); i.e. L and L ′ cannot be indifferent.

• Case 2: M = m, then by construction M > m, i.e. three cases are possible:

-If u > M, then Π(L ′ > L) = α (at level α, L ′ can take value u and L value M) and Π(L > L ′ ) < α (one have go below α to find a value for L strictly greater than u). So L ∼ LN L ′ is not satisfied. -If u < m, then Π(L > L ′ ) = α (at level α, L ′ can take value u and L value m) and Π(L ′ > L) < α (one have go below α to find a value strictly lower than u).

Reciprocally, it is easy to check that M > u > m and α > α ′ imply Π(L > L ′ ) = α and Π(L ′ > L) = α. ✷ Proof of Proposition 11(i). We have L 1 = γ /L, β/L ′′ and L 2 = γ /L ′ , β/L ′′ where L = 1/u, α/m, α/M and L ′ = 1/u, α ′ /m ′ , α ′ /M ′ are two indifferent 2nd core lotteries (i.e. L ∼ LN L ′ ), α < α ′ and max(γ , β) = 1.

Thanks to 9 we can assume without loss of generality that L 1 , L 2 and L b are 2nd core lotteries (if it is not the case, simply replace them by their 2nd core lotteries). Since the cores of L and L ′ are equal, the cores of L 1 and L 2 are also equal. So L 1 is unimodal iff L 2 is unimodal (and both share the same mode).

Let us first show that the monotonicity property holds for Ch N in binary decision trees.

Suppose that Ch N (L) Ch N (L ′ ); By definition we have:

))/u 2 . Thus:

and

.

For both ⊗ = min and ⊗ = * , λ ′

Thus Ch N (L 1 ) Ch N (L 2 ).

Thus:

For both ⊗ = min and ⊗ = * , λ ′

: the monotonicity property is satisfied for binary decision trees of two levels. Since L 1 and L 2 are themselves binary, it is satisfied in any binary decision tree.

Let us now show that the monotonicity property holds for Ch Π in binary decision trees. Thus, suppose that Ch Π (L) Ch Π (L ′ );

• If α = 1: L 1 = max(λ 1 , ⊗(β, λ ′′ 1 ))/u 1 , max(λ 2 , ⊗(β, λ ′′ 2 ))/u 2 and L 2 = max(λ ′ 1 , ⊗(β, λ ′′ 1 ))/u 1 , max(λ ′ 2 , ⊗(β, λ ′′ 2 ))/u 2 . Thus:

Ch Π (L 1 ) = u 1 + (u 2 -u 1 ) * max λ 2 , ⊗(β, λ ′′ 2 ) and Ch Π (L 2 ) = u 1 + (u 2 -u 1 ) * max λ ′ 2 , ⊗(β, λ ′′ 2 ) .

From λ 2 > λ ′ 2 it can be easily derived that Ch Π (L 1 ) Ch Π (L 2 ).

• If α < 1, β = 1: L 1 = max(⊗(α, λ 1 ), λ ′′ 1 )/u 1 , max(⊗(α, λ 2 ), λ ′′ 2 )/u 2 and L 2 = max(αλ ′ 1 , λ ′′ 1 )/u 1 , max(αλ ′ 2 , λ ′′ 2 )/u 2 .

Thus:

Ch Π (L 1 ) = u 1 + (u 2 -u 1 ) * max ⊗(α, λ 2 ), λ ′′ Rev(G c ) (u 1 ) = 1 = G c (u 1 ). Note that ∀i = 2, n, Rev(G c )(u i ) Rev(G c )(u i-1 ).