State Space Search for Risk-Averse Agents

1 Introduction

Various problems investigated in Artificial Intelligence can be formalized as shortest path problems in an implicit state space graph (e.g. path-planning for mobile robots, VLSI layout, internet searching). Starting from a given state, we want to determine an optimal sequence of admissible actions allowing transitions from state to state until a goal state is reached. Here, optimality refers to the minimization of one or several cost functions attached to transitions, representing distances, times, energy consumptions...For such problems, constructive search algorithms like A∗ and A∗ε [Hart et al., 1968; Pearl, 1984] for single objective problems or MOA∗ for multiobjective problems [Stewart and White III, 1991] have been proposed, performing the implicit enumeration of feasible solutions.

An important source of complexity in path-planning problems is the uncertainty attached to some elements of the problem. In some situations, the consequences of actions are not certain and the transitions are only known in probabilities. In some other, the knowledge of the current state is imperfect (partial observability). Finally, the costs of transitions might itself be uncertain. Although many studies concentrate on the two first sources of uncertainty (see the important litterature on MDPs and POMDPS, e.g. Puterman, 1994; Kaebling et al., 1999), some others focus on the uncertainty attached to

Louis-Xavier Storme

LIP6 - University of Paris 6 4 Place Jussieu 75252 Paris Cedex 05, France

louis-xavier.storme@lip6.fr

transition-costs. For example, when costs are time dependent and representable by random variables, the SDA∗ algorithm has been introduced to determine the preferred paths according to the stochastic dominance partial order [Wellman et al., 1995]. An extension of this algorithm specifically designed to cope with both uncertainty and multiple criteria has been proposed by Wurman and Wellman [1996].

We consider here another variation of the search problem under uncertainty, that concerns the search of "robust" solution-paths, as introduced by Kouvelis and Yu [1997]. Under total uncertainty, it corresponds to situations where costs of paths might depend on different possible scenarios (states of the world), or different viewpoints (discordant sources of information). Roughly speaking, the aim is to determine paths with "reasonnable" cost in all scenarios. Under risk (i.e. when probabilities are known) this problem generalizes to the search of "low-cost/low-risk" paths. Let us consider a simple example:

Example 1 Consider the network pictured on Figure 1 where the initial state is 1 and the goal node is 6. Assume that only two scenarios with known probabilities p1 and p2 are relevant concerning the traffic, yielding two different sets of costs on the network. Hence, to each path P i is associated a vector (xi1 , xi2 ), one cost per scenario: P 1 = 〈1, 3, 5, 6〉 with x1 = (5, 18), P 2 = 〈1, 3, 6〉 with x2 = (8, 15), P 3 = 〈1, 3, 4, 6〉 with x3 = (16, 15), P 4 = 〈1, 2, 5, 6〉 with x4 = (13, 10), P 5 = 〈1, 2, 6〉 with x5 = (16, 7), P 6 = 〈1, 2, 4, 6〉 with x6 = (20, 2). Using cost-distributions X i = (xi1 , xi2 ; p1, p2), i = 1, . . . , 6, we want to determine solutions paths associated with low-risk cost-distributions.

(2,10)

3

(1,0)

5

(3,4)

(6,5)

(8,1)

(3,1)

(8,6)

(2,8)

1

6

2

(1,0)

4

(11,1)

This simple problem might prove very hard to solve on larger instances due to the coexistence of two difficulties: the combinatorial nature of the solution space and the existence of several conflicting scenarios on costs. It is important to note that the vector-valued path problem introduced above cannot be reduced to a standard shortest path problem by linear scalarization of cost-vectors without loosing significant information. Assume for example that the arcs of the graph plotted on the left part of Figure 1 are valued accoding to their expected cost, so that each path P i receives a weight w(xi , p) = p1xi1 + p2xi2 . Then algorithm A∗ used with such scalars weights might output P 1 or P 6 , depending on the relative value of p1 and p2, but neither path P 4 nor P 2 , P 5 . This can easily be shown using the right part of Figure 1 where the images of solution-paths are plotted in the valuation space; we can indeed see that P 2 , P 4 and P 5 do not belong to the boundary of the convex hull (grey triangle) of the images of paths, thus being excluded from the set of potential winners, as long as a linear criterion is used. This is not satisfactory because P 4 presents a well-balanced profile and might be preferred to P 1 or P 6 by a risk-averse agent. Similarly he might prefers P 2 to P 1 or P 5 to P 6 , depending on probabilities.

Example 1 shows the limitations of linear aggregation functions in decision-making under risk on non-convex domains. To overcome the difficulty, we need to resort to more sophisticated decision criteria to compare cost distributions in term of risk, as those introduced in decision theory. These decision criteria escape linearity either by introducing a transformation of costs as in the Expected Utility Model (EU [von Neumann and Morgenstern, 1947]) or by introducing a probability-transformation as in Yaari's model [Yaari, 1987], or even both as in the Rank-Dependent Utility model (RDU [Quiggin, 1993]). Alternatively, partial comparison models including an idea of risk might be used when the agent's utility function is not known (e.g. Second-order Stochastic Dominance, SSD). The aim of this paper is to incorporate such models in search algorithms to determine low-risk solution paths in implicit graphs.

The paper is organized as follows: in Section 2, we introduce preliminary formal material as well as decision criteria modelling risk-sensitive decision behaviours. In Section 3, we propose a general optimization procedure to find the best paths with respect to such criteria. In Section 4, we propose a multiobjective search algorithm for the determination of SSD-optimal paths. Finally, numerical experiments of algorithms are given in Section 5.

2 Problem Formulation

2.1 Notations and Definitions

We consider a state space graph G = (N,A) where N is a finite set of nodes (possible states), and A is a set of arcs representing feasible transitions between nodes. Formally, we have A = {(n, n′), n ∈ N, n′ ∈ S(n)} where S(n) ⊆ N is the set of all successors of node n (nodes that can be reached from n by a feasible elementary transition). Then s ∈ N denotes the source of the graph (the initial state), Γ ⊆ N the subset of goal nodes, P(s, Γ) the set of all paths from s to a goal node γ ∈ Γ, and P(n, n′ ) the set of all paths linking n to n′ . We call solution-path a path from s to a goal node γ ∈ Γ. Throughout the paper, we assume that there exists at least one solution-path.

Following a classical scheme in robust optimization [Kouvelis and Yu, 1997], we consider a finite set S = {s1, . . . , sm} of possible scenarios, each having possibly a different impact on the transition-costs, and a scenariodependent valuation v : A × S → N giving, for any arc a ∈ A and any scenario s ∈ S the cost v(a, s) of the transition represented by a. Costs over a path are supposed to be additive, which allows valuation v to be extended from arcs to paths by setting, for any path P and any scenario s, v(P, s) = ∑a∈P v(a, s). In the sequel, we assume that the cost of every solution path is (upper) bounded by a positive constant M .

A cost-vector x = (x1, . . . , xm) ∈ Rm+ is associated to each path P in the graph in such a way that component xi = v(P, si). Let pi denote the probability of scenario si, with pi ≥ 0 for i = 1, . . . ,m and ∑mi=1 pi = 1, then a path P with cost-vector x is represented by the distribution (x1, . . . , xm; p1, . . . , pm). Let L be the set of probabilistic distributions having a finite support in [0,M]. The cost of each path is a random variable X characterized by law PX ∈ L, defined for any B ⊆ [0,M], by PX(B) = P({s ∈ S : X(s) ∈ B}). For any random variable X, the expected value of X is given by E(X) = ∑mi=1 pixi, the cumulative function FX is given by FX(z) = P({s ∈ S : X(s) ≤ z}) for all z ∈ [0,M] and the associated decumulative function is denoted GX(z) = 1 - FX(z).

2.2 Decision Criteria for Risk-Averse Agents

In the field of decision making under risk, the concept of riskaversion has been widely investigated, first in the framework of EU theory and then in more general frameworks. Roughly speaking, risk-aversion amounts to preferring a solution with a guaranteed cost to any other risky solution with the same expected cost. This was formalized by Pratt and Arrow [Pratt, 1964; Arrow, 1965] that define weak risk-aversion for a weak preference relation ≿ on L as follows:

Definition 1 An agent is said to be weakly risk-averse if, for any distribution X in L, he considers that E(X) is as least as good as X, i.e. E(X) ≿ X.

In EU theory, risk-aversion means that the agent's utility function u on payoffs is increasing and concave, the coefficient of risk-aversion of any agent being measured by -u′′ (x)/u′ (x) [Arrow, 1965]. In our context, the counterpart of EU is given by the expected weight function:

where w : [0,M] → R is a strictly increasing function such that w(xi) represents the subjective weight (disutility) attached to cost xi by the agent. Criterion EW(X) is to be minimized since it represents the disutility of any cost distribution X. In the EW model, risk aversion means choosing an increasing and convex w in Equation (1), so as to get EW(E(X)) ≤ EW(X) for all X ∈ L.

Despite its intuitive appeal, EU theory does not explain all rational decision making behaviors (e.g. the violation of Savage's sure thing principle [Ellsberg, 1961]). This has led researchers to sophisticate the definition of expected utility. Among the most popular generalizations of EU, let us mention the rank dependent utility introduced by Quiggin [1993], which can be reformulated in our context as follows:

where (.) represents a permutation on {1, . . . ,m} such that x(1) ≤ . . . ≤ x(m), ϕ is a non-decreasing probability transformation function, proper to any agent, such that ϕ(0) = 0 and ϕ(1) = 1, and w is a weight function assigning subjective disutility to real costs. This criterion can be interpreted as follows: the weight of a path with cost-distribution X is at least w(x(1)) with probability 1. Then the weight might increase from w(x(1) ) to w(x(2)) with probability mass ϕ(GX (x(1))); the same applies from w(x(2)) to w(x(3)) with probabilitymass ϕ(GX(x(2))), and so on... When w(z) = z for all z, RDW is known as Yaari's model [Yaari, 1987].

Weak risk-aversion can be obtained in Yaari's model by choosing a probability transformation such that ϕ(p) ≥ p for all p ∈ [0, 1]. This holds also for RDW provided function w is convex [Quiggin, 1993]. On the other hand, when ϕ is the identity function, then RDW boils down to EW. Indeed, considering probabilities q(1) = 1 and q(i+1) = GX(x(i)) = ∑mk=i+1 p(k) for all i = 1, ...,m- 1, RDW criterion can be rewritten as follows:

From this last equation, observing that q(i) - q(i+1) = p(i), we can see that RDW reduces to EW when ϕ(z) = z for all z. Hence, RDW generalizes both EW and Yaari's model. For the sake of generality, we consider RDW in the sequel and investigate the following problem:

RDW Search Problem. We want to determine a RDWoptimal distribution in the set of all cost distributions of paths in P(s, Γ).

This problem is NP-hard. Indeed, choosing w(x) = x, ϕ(0) = 0 and ϕ(x) = 1 for all x ∈ (0,M], we get RDW(X) = x(m) = maxi xi. Hence RDW minimization in a vector valued graph reduces to the min-max shortest path problem, proved NP-hard by Murthy and Her [1992].

3 Search with RDW

As many other non-linear criteria, RDW breaks the Bellman principle and one cannot directly resort to dynamic programming to compute optimal paths. To overcome this difficulty, we propose an exact algorithm which proceeds in three steps: 1) linear scalarization: the cost of every arc is defined as the expected value of its cost distribution; 2) ranking: enumeration of paths by increasing order of expected costs; 3) stopping condition: stops enumeration when we can prove that a RDW-optimal distribution has been found. Step 2 can be performed by kA∗ , an extension of A∗ proposed by Galand and Perny [2006] to enumerate the solution-paths of an implicit graph by increasing order of costs. Before expliciting step 3, we need to establish the following result:

Proposition 1 For all non-decreasing probability transformations ϕ on [0, 1] such that ϕ(q) ≥ q for all q ∈ [0, 1], for all non-decreasing and convex weight functions w on [0,M], for all X ∈ L we have: RDW(X) ≥ w (E(X))

Proof. Since x(i+1) ≥ x(i) for i = 1, . . . ,m- 1 and w is non-decreasing, we have: w(x(i+1)) - w(x(i)) ≥ 0 for all i = 1, . . . ,m- 1. Hence, from Equation (2), ϕ(q) ≥ q for all q ∈ [0, 1] implies that: RDW(X)

Now, let {P 1 , . . . , P r } denotes the set of elementary solution-paths in P(s, Γ), with cost distributions X 1 , . . . , X r , indexed in such a way that E(X 1 ) ≤ E(X 2 ) ≤ . . . ≤ E(X r ). Each distribution X j yields cost xji = v(P j , si) with probability pi for i = 1, . . . ,m. The sequence of paths (P j )j=1,...,r can be generated by implementing the ranking algorithm of step 2 on the initial graph G = (N,A), using a scalar valuation v′ : A → R+ defined by v′ (a) = ∑mi=1 piv(a, si). Indeed, the value of any path P j in this graph is v′ (P j ) = E(X j ) by linearity of expectation.

Now, assume that, during the enumeration, we reach (at step k) a path P k such that: w(E(X k )) ≥ RDW(X β(k) ) where β(k) is the index of a RDW-optimal path in {P 1 , . . . , P k }, then enumeration can be stopped thanks to:

Proposition 2 If w(E(X k )) ≥ RDW(X β(k)) for some k ∈ {1, . . . , r}, where β(k) is the index of a RDW-minimal path in {P 1, . . . , P k }, then P β(k) is a RDW-minimal solutionpath in P(s, Γ).

Proof. We know that P β(k) is RDW-minimal among the k-first detected paths. We only have to show that no other solution-path can have a lower weight according to RDW. For all j ∈ {k + 1, . . . , r} we have: RDW(X j ) ≥ w(E(X j )) thanks to Proposition 1. Moreover E(X j ) ≥ E(X k ) which implies w(E(X j )) ≥ w(E(X k )) ≥ RDW(X β(k) ). Hence RDW(X j ) ≥ RDW(X β(k) ) which shows that P β(k) is RDW-minimal over P(s, Γ). ✷

Propositions 1 and 2 show that the ranked enumeration of solution-paths performed at step 2 can be interrupted without loosing the RDW-optimal solution. This establishes the admissibility of our 3-steps algorithm. Numerical tests performed on different instances and presented in Section 5 indicate that the stopping condition is activated early in the enumeration, which shows the practical efficiency of the proposed algorithm.

4 Dominance-based Search

Functions RDW and EW provide sharp evaluation criteria but require a precise knowledge of the agent's attitude towards risk (at least to assess the disutility function). In this section we consider less demanding models yet allowing well-founded discrimination between some distributions.

4.1 Dominance Relations

A primary dominance concept to compare cost distributions in L is the following:

Definition 2 For all X, Y ∈ L, Functional Dominance is defined by: X FD Y ⇔ [∀s ∈ S, X(s) ≤ Y (s)]

For relation FD and any other dominance relation ⪰ defined in the sequel, the set of ⪰-optimal distributions in L ⊆ L is defined by: {X ∈ L : ∀Y ∈ L, Y ⪰ X ⇒ X ⪰ Y }.

When the probabilities of scenarios are known, functional dominance can be refined by first order stochastic dominance defined as follows:

Definition 3 For all X, Y ∈ L, the First order Stochastic Dominance relation is defined by:

Actually, the usual definition of FSD involves cumulative distributions FX applied to payoffs instead of decumulative functions GX applied to costs. In Definition 3, X FSD Y means that X assigns no more probability than Y to events of type: "the cost of the path will go beyond z". Hence it is natural to consider that X is at least as good as Y when X FSD Y .

Relation FSD is clearly related to the EW model since X FSD Y if and only if EW(X) ≤ EW(Y ) for all increasing weight function w [Quiggin, 1993]. This gives a nice interpretation to Definition 3 within EU theory, with a useful consequence: if the agent is a EW-minimizer (with any increasing weight function w), then his preferred solutions necessarily belong to the set of FSD-optimal solutions. Now, an even richer dominance relation can be considered:

Definition 4 For all X, Y ∈ L, the Second order Stochastic Dominance relation is defined as follows:

Stochastic Dominance is acknowledged as a standard way of characterizing risk-averse behaviors independently of any utility model. For example, Rotschild and Stiglitz [1970] and Machina and Pratt [1997] provide axiomatic characterizations of SSD in terms of risk using "mean preserving spreads". As a consequence, an agent is said to be strongly risk-averse if he prefers X to Y whenever X SSD Y . Moreover, SSD has a natural interpretation within EU theory: X SSD Y if and only if EW(X) ≤ EW(Y ) for all increasing and convex weight function w [Quiggin, 1993]. As a nice consequence, we know that whenever an agent is a risk-averse EW-minimizer, then his preferred solutions necessarily belong to the set of SSD-optimal solutions. The same applies to RDW provided φ(q) ≥ q for all q ∈ [0, 1] and function w is convex (this directly follows from a result of Quiggin [1993]). This shows that, even outside EU theory, SSD appears as a natural preference relation for risk-averse agents. It can be used as a first efficient filtering of risky paths.

Interestingly enough, relations FSD and SSD dominance relations can equivalently be defined by:

where ˇGX and ˇG2X are inverse functions defined by:

Since S is finite in our context, X is a discrete distribution; thereforeGX and ˇGX are step functions. Moreover G2X and ˇG2X are piecewise linear functions. Function ˇG2X (z) is known as the Lorenz function. It is commonly used for inequality ordering of positive random variables [Muliere and Scarsini, 1989]. As an illustration, consider Example 1 with p1 = 0.4 and p2 = 0.6. We have: ˇG2X1(p) = 18p for all p ∈ [0, 0.6), ˇG2X1 (p) = 7.8 + 5p for all p ∈ [0.6, 1], whereas ˇG2X5 (p) = 16p for all p ∈ [0, 0.4), ˇG2X5 (p) = 3.6+7p for all p ∈ [0.4, 1]; hence ˇG2X5 (p) ≤ ˇG2X1(p) for all p and therefore X 5 SSD X 1 . This confirms the intuition that path P 5 with cost (16, 7) is less risky than path P 1 with cost (5, 18)

The dominance relations introduced in this subsection being transitive, the sets of FD-optimal elements, FSD-optimal elements and SSD-optimal elements are not empty. Moreover, these sets are nested thanks to the following implications: X FD Y ⇒ X FSD Y and X FSD Y ⇒ X SSD Y , for all distributions X, Y ∈ L. In Example 1 we have L = {X 1,X 2 ,X 3,X 4 ,X 5,X 6} and p1 = 0.4 and p2 = 0.6. Hence the set of FD-optimal elements is {X 1,X 2,X 4 ,X 5,X 6}, the set of FSD-optimal elements is the same and the set of SSD-optimal elements is {X 4,X 5,X 6}. The next section is devoted to the following:

SSD Search Problem. We want to determine all SSD-optimal distributions in the set of cost distributions of paths in P(s, Γ) and for each of them, at least one solution-path.

4.2 ProblemComplexity

To assess complexity of the search, we first make explicit a link between SSD and Generalized Lorenz Dominance, as defined by Marshall and Olkin [1979]. Generalized Lorenz dominance, denoted GLD in the sequel, is based on the definition of Lorenz vector L(x) = (L1(x), . . . , Lm(x)) for any vector x = (x1, . . . , xm) where Lk(x) is the sum of the k greatest components of x. Then, relation GLD is defined as follows: x GLD y if L(x) Pareto dominates L(y), i.e. Lk(x) ≤ Lk(y) for k = 1, . . . ,m. Now, if pi = 1/m for i = 1, . . . ,m then SSD defined by Equation (5) on distributions reduces to Lorenz dominance on the corresponding cost vectors since Lk(x) = m ˇG2X (k/m). Hence, in the particular case of equally probable scenarios, the SSD search problem reduces to the search of Lorenz non-dominated paths, a NPhard problem as shown by Perny and Spanjaard [2003]. This shows that the SSD search problem is also NP-hard.

4.3 The SSDA∗ Algorithm

Consider Example 1 and assume that the two scenarios have equal probabilities, we can see that the preferred subpath from node 1 to node 5 is P = 〈1, 3, 5〉 with cost xP = (3, 10) which is preferred to path P ′ = 〈1, 2, 5〉 with cost xP ′ = (11, 2) since (3, 10; 0.5, 0.5) SSD (11, 2; 0.5, 0.5). Indeed, we are in the case of Subsection 4.2 (equally probable scenarios) with L(xP ) = (10, 13) and L(xP ′ ) = (11, 13) and obviously (10, 13) Pareto dominates (11, 13). Now, appending path P ′′ = 〈5, 6〉 with xP ′′ = (2, 8) to P and P ′ respectively yields path P 1 = P ∪ P ′′ with cost x1 = (5, 18) and path P 4 = P ′ ∪P ′′ with x4 = (13, 10). Hence L(x4 ) Pareto dominates L(x1 ), therefore (13, 10; 0.5, 0.5) SSD (5, 18; 0.5, 0.5) which constitutes a preference reversal and illustrates a violation of Bellman principle, thus invalidating a direct dynamic programming approach (optimal path P 4 would be lost during the search if P ′ is pruned at node 5 due to P).

However, the problem can be overcome knowing that: i) SSD-optimal paths are also FD-optimal; ii) FD-optimality satisfies the Bellman principle; iii) the set of scenarios being finite, FD-optimality on cost distributions is nothing else but Pareto-optimality on cost-vectors. SSD-optimal distributions might indeed be obtained in two stages: 1) generate FD-optimal solution-paths using Multiobjective A∗ (MOA∗, Stewart and White III, 1991; Mandow and de la Cruz, 2005); 2) eliminate SSD-dominated solutions within the output set. However, FD-optimal solutions being often numerous, it is more efficient to focus directly on SSD-optimal solutions during the search. For this reason we introduce now a refinement of MOA∗ called SSDA∗ for the direct determination of SSDoptimal solutions.

As in MOA∗ , SSDA∗ expands vector-valued labels (attached to subpaths) rather than nodes. Note that, unlike the scalar case, there possibly exists several Pareto nondominated paths with distinct cost-vectors to reach a given node; hence several labels can be associate to a same node n. At each step of the search, the set of generated labels is divided into two disjoint sets: a set OPEN of not yet expanded labels and a set CLOSED of already expanded labels. Whenever the label selected for expansion is attached to a solution path, it is stored in a set SOL. Initially, OPEN contains only the label attached to the empty subpath on node s, while CLOSED and SOL are empty. We describe below the essential features of the SSDA∗ algorithm.

Output: it determines the set of SSD-optimal solution-paths, i.e. solution-paths the distribution of which is SSD-optimal. If several paths have the same G2 distribution, only one path among them is stored using standard bookkeeping techniques.

Heuristics: like in MOA∗ , a set H(n) of heuristic costvectors is used at any node n since n may be on the path of more than one non-dominated solution. This set estimates the set H ∗ (n) of non-dominated costs of paths from n to Γ.

Priority: to direct the search we use a set-valued labelevaluation function F defined in such a way that, F(ℓ), at any label ℓ, estimates the set F ∗ (ℓ) of non-dominated costs of solution paths extending the subpath associated with ℓ. This set F(ℓ) is computed from all possible combinations {g(ℓ) + h : h ∈ H(n)}, where g(ℓ) denotes the value of the subpath associated with ℓ and n the node to which ℓ is attached. At each step of the search, SSDA∗ expands a label ℓ in OPEN such that F(ℓ) contains at least one SSD-optimal cost-vector in ⋃ℓ∈OPEN F(ℓ). Such a label can be chosen, for instance, so as to minimize EW with a convex w function. At goal nodes, this priority rule guarantees to expand only labels attached to SSD-optimal paths.

Pruning: the pruning of labels cannot be done directly with the SSD relation, as shown in the beginning of this subsection. The following pruning rules are used:

RULE 1: at node n, a label ℓ ∈ OPEN is pruned if there exists another label ℓ′ at the same node n such that g(ℓ′ ) FD g(ℓ). This rule is essentially the same as in MOA∗ and is justified by the fact that FD-optimality does satisfy the Bellman principle and FD dominance implies SSD dominance. Indeed, labels pruned like this necessarily lead to a FD-dominated paths and therefore cannot lead to SSD-optimal solution paths.

RULE 2: a label ℓ ∈ OPEN is pruned if for all f ∈ F(ℓ) there exists ℓ′ ∈ SOL such that g(ℓ′) SSD f. This rule allows an early elimination of uninteresting labels while keeping admissibility of the algorithm provided heuristic H is admissible, i.e. ∀n ∈ N, ∀h∗ ∈ H ∗ (n), ∃h ∈ H(n) s.t. h FD h∗ . Indeed, if H is admissible, then for all f ∗ ∈ F ∗ (ℓ) there exists f ∈ F(ℓ) such that f = g(ℓ) + h FD g(ℓ) + h∗ = f ∗ , which implies that f SSD f ∗ and therefore g(ℓ′ ) SSD f ∗ by transitivity of SSD.

Note that deciding whether X SSD Y can be performed in constant time. Indeed, since functions ˇG2X (p) and ˇG2Y (p) are piecewise linear as indicated in Section 2, their comparison amounts to test for Pareto dominance on the union set of break points of both functions, the cardinality of which is upper bounded by 2m.

Termination: the process is kept running until the set OPEN becomes empty, i.e. there is no remaining subpath able to reach a new SSD-optimal solution path. By construction, SSDA∗ develops a subgraph of the one developped by MOA∗ and the termination derives from the termination of MOA∗ .

5 Numerical Tests

Various tests have been performed to evaluate the performance of algorithms on randomly generated graphs of different sizes. The number of nodes in these graphs varies from 1000 to 6000 and the number of arcs from 105 (for 1000 nodes) to 5.106(for 6000 nodes). Cost vectors are integers randomly drawn within interval [0, 100]. Algorithms were implemented in C++. The computational experiments were carried out with a Pentium IV CPU 3.2GHz PC.

Table 1 presents the average performance of algorithms for different classes of instances, characterized by #nodes (the number of nodes in the graph), and m (the number of scenarios). In each class, we give the average performance computed over 20 different instances. For every class, we give #SSD the average number of SSD-optimal distributions and tSSD the average time (in seconds) to solve the SSD search problem with SSDA∗ . Results given in Table 1 show that the average number of SSD-optimal distributions increases slowly with the size of the graph; moreover SSDA∗ computation times show a good efficiency (less than 15 seconds in worst cases). The two rightmost columns of Table 1 concern the performance in determining RDW-optimal paths with w(z) = z 2 and ϕ(p) = p 1 2 . We give #Gen, the average number of paths generated before reaching the stopping condition of Proposition 2, and tRDW the average time of the search in seconds. Values obtained for #Gen show that path enumeration is stopped after a very reasonable number of iterations and computation times are about one second in worst cases. The gain in efficiency when compared to SSDA∗ is due to the preliminary scalarization of the graph valuation which avoids numerous Pareto-dominance tests during the exploration, but also to the fact that we only seek one RDW-optimal path among NSSD paths. We have performed other experiments which are not reported here to save space: when ϕ(p) = p (EW model) or w(z) = z (Yaari's model), the performance is even slightly better. Moreover, when convexity of w and concavity of ϕ are increased to enhance riskaversion, e.g. with w(z) = z 10 and ϕ(p) = p 1 10 , the performance is not significantly degraded.

6 Conclusion

We have provided efficient exact algorithms to determine low-risk/low-cost solution paths. Algorithm SSDA∗ proposed in Section 4 provides a subset of paths convenient for a risk-averse agent, without requiring the definition of a disutility function. Moreover, when a disutility criterion is known, more or less risky paths can be efficiently determined with the algorithm proposed in Section 3. In the future, it should be worth investigating optimization based on risk-sensitive models in other dynamic decision making problems, e.g. decision trees or Markov Decision Processes. In that direction, the main problem to deal with is the existence of dynamic inconsistencies induced by such nonlinear models. To face this difficulty, adapting the approaches proposed here to bypass the violation of Bellman principle might be of interest.