Combining Preference Elicitation and Search in Multiobjective State-Space Graphs

1 Introduction

In many practical search problems considered in Artificial Intelligence (e.g path planning, game search, preference-based configuration), the evaluation and comparison of solutions involve several aspects or points of view (e.g. in path planning, time, distance, energy consumption, risk). For this reason, standard search algorithms are worth generalizing to be implementable in the context of multiobjective optimization. This statement has motivated various contributions stemming from the initial A∗ search algorithm [Hart et al., 1968] and aiming at proposing extensions to cope with multiple conflicting criteria. Let us mention, among others, MOA∗ the multiobjective extensions of A∗ finding all Pareto optimal cost vectors [Stewart and White III, 1991; Mandow and de la Cruz, 2005] in a vector-valued state space graph, U∗ a variation of MOA∗ used to find a path maximizing a multiattribute utility function [Dasgupta et al., 1995], and a preference-based specialization of MOA∗ [Perny and Spanjaard, 2003]. The same trend can be observed for AND/OR search [Dasgupta et al., 1996a; Marinescu, 2010], game search [Dasgupta et al., 1996b] and constraint optimization [Marinescu et al., 2013].

In preference-based search, the preference model is often assumed to be known and the effort is put on algorithmic issues. Thus, the elicitation problem must be solved in a prior stage. The standard elicitation procedures proposed in multiattribute utility theory aim at providing a complete elicitation [Fishburn, 1967; Krantz et al., 1971; Keeney and Raiffa, 1976]; the preference model is precisely constructed on the entire multiattribute space. This approach is however difficult to implement on combinatorial domains, except perhaps for very simple and decomposable utility models. The development of recommender systems and the need of fast and efficient preference elicitation procedures for large databases have led researchers to propose less ambitious elicitation procedures: one seeks to obtain only a part of the preference model, sufficient to make a decision on the given instance. This suggests resorting to more incremental elicitation processes. Preference queries are selected one at a time, to be as informative as possible, so as to progressively reduce the set of admissible utility functions until a robust decision can be made. In this line, let us mention the ISMAUT method [White III et al., 1984] for the elicitation of multiattribute utility functions, and more recently, strategies developed within the artificial intelligence community for preference query selection using the minimax-regret criterion, see e.g., [Boutilier, 2002; Wang and Boutilier, 2003; Boutilier et al., 2006; Lu and Boutilier, 2011; 2013].

Incremental elicitation procedures are also involved in the context of voting with partial preference profiles. When individual preferences are incomplete, one can study possible and necessary winners (e.g., [Konczak and Lang, 2005; Xia and Conitzer, 2011; Lang et al., 2012; Ding and Lin, 2013]). In this setting, incremental elicitation methods are used to progressively reduce the set of possible winners until a winner can be determined with some guarantee [Kalech et al., 2010; Lu and Boutilier, 2011; Dery et al., 2014]). The elicitation task consists in obtaining new individual preference judgements over candidates given explicitly. In this paper, we consider a slightly different elicitation context. Our aim is to resort to incremental preference elicitation to refine a multiobjective state-space search procedure. One-dimensional preferences are assumed to be known and represented by criterion functions. The elicitation burden is focused on the determination of weights used in the aggregation phase to define overall preferences over a combinatorial set of alternatives (implicitly defined as the solution paths of a state space graph).

Incremental elicitation strategies based on minimax-regret minimization have proven quite effective but require to minimize regrets for every pair of feasible solutions. This fits well to decision problems on explicit sets of alternatives. This can be used for multiobjective combinatorial optimization problems as well when the set of Pareto-optimal alternatives is not too large and can be computed in a first stage prior to preference elicitation. Our aim here is to propose a more direct approach that consists in interweaving preference elicitation and search. Starting with an initial set of possible utility functions characterized by some weighting parameters, we propose to generate preference queries during the search so as to progressively reduce the set of possible weights until an optimal solution can be determined or approximated with some guarantees. In this process, the decision model is progressively revealed and constructed during the search. However, in general, a robust solution can be found without completely specifying the model. We want to apply and test this approach on two classes of utility models. We consider first additive utility functions [Fishburn, 1968] parameterized by weights representing the importance of attributes. Then we will consider a more general model, namely the Choquet Expected Utility [Schmeidler, 1986] parameterized by a set function defining the importance of all coalitions of attributes.

A first attempt in this direction has been recently proposed for linear weighted aggregators (which are a special case of additive utilities) [Benabbou and Perny, 2015]. However, it does not extend to non-linear multiattribute utility functions because the proposed algorithm relies on pruning rules based on the Bellman principle. Unfortunately this principle does not hold anymore when multiobjective costs of paths are aggregated with a non-linear function. Another recent study concerns the case of incremental elicitation of capacity weights in Choquet integrals (see [Benabbou et al., 2014]) but assumes that the set of alternatives is given explicitly. Here we propose an approach to overcome both difficulties simultaneously: the non-linearity of the multiattribute utility function and the combinatorial nature of the set of alternatives.

The paper is organized as follows: in Section 2, we introduce the formal framework and recall some background on decision models and preference-based search. Then, Section 3 and 4 are devoted to the introduction of our procedure combining elicitation and search. The efficiency of this approach will be discussed in Section 5 where numerical experiments are reported to assess the performance of the search procedure both in terms of number of queries and computation times.

2 Preference-based Search inMOGraphs

We consider G=(N, A) a state space graph where N denotes the finite set of nodes representing all states and A is the set of arcs representing the admissible transitions. Formally, A= {(n, n′ ) : n∈N, n′ ∈S(n)} where S(n)⊆N is the set of all nodes that can be reached from node n by a single transition. The set of all paths between node n and node n′ is denoted P(n, n′ ), and each of them is characterized by a list of nodes of type 〈n, . . . , n′ 〉. In particular, the set of solution paths, starting at source node s ∈ N and reaching any goal node γ ∈

Γ, is denoted P(s, Γ). Besides, we consider Q = {1, . . . , q} a finite set of criteria (e.g. time, distance) represented by q cost functions gi : A → R+, i ∈ Q. Hence, each path p in graph G is associated with a cost vector denoted g(p) = (g1(p), . . . , gq(p)) and gi(p) = ∑(n,n′ )∈p gi((n, n′ )) for all i ∈ Q. Finally, the image of all solution paths in the space of criteria is X ={g(p) : p ∈ P(s, Γ)} and ND(X) is set of Pareto-optimal vectors in X.

Since we are in a context of cost minimization, we will use disutility functions to be minimized rather than utility functions to be maximized. Hence, we consider a multiattribute disutility function ψvω : Rq+ → [0, 1] which associates the disutility: ψvω (x) = ψω(v1(x1), . . . , vq(xq)) to any cost vector x = (x1, . . . , xq), where vi : R+ → [0, 1] is a disutility function measuring the subjective cost of consequence xi for the Decision Maker (DM) , and ψω : [0, 1]q → [0, 1] is a scalarizing function with a parameter denoted ω. A solution x is preferred to another solution y when ψvω (x) ≤ ψvω (y). We consider here that one-dimensional disutility functions vi have been already elicited in a prior step, using standard techniques (see e.g [Keeney and Raiffa, 1976; Bana e Costa and Vansnick, 2000]) and we focus on the elicitation of paremeters ω = (ω1, . . . , ωm) so as to approximate DM's preferences with a proper scalarizing function. Throughout the paper, we will consider two main families of utility functions:

- Additive utilities: U v ω (x) = ∑qi=1 ωivi(xi) where ω = (ω1, . . . , ωq) is a vector of positive weights adding up to 1. Note that this family virtually includes also quasi-arithmetic means of the formM φ ω (x) = φ-1 (∑qi=1 ωiφ(xi)) for strictly increasing φ. Minimizing M φ ω (x) is indeed equivalent to minimizing φ(M φ ω (x)) = U v ω (x) for vi(z) = φ(z). This includes as special case the weighted Lp norm obtained for φ(z) = zp , the geometric mean for φ(z) = ln(z) and the standard weighted sum for φ(z) = z. More generally additive utilities can use distinct one-dimensional disutility functions vi to encode preferences on the different criteria.

- Choquet expected utilities: generalize additive utilities by C vω (x) = ∑qi=1 [v(i)(x(i)) - v(i-1)(x(i-1))] ω(X(i)) where (.) denotes a permutation of (1, . . . , q) such that v(i)(x(i)) ≤ v(i+1)(x(i+1)) for all i = 1, . . . , q - 1, x(0) is a ficticious value such that vi(x(0)) = 0, and X(i) = {(i), . . . , (q)} is the subset of indices j ∈ Q corresponding to the n+1-i largest disutility values vj(xj). In this case ω is a capacity, i.e. a set-function ω : 2Q → [0, 1] such that ω(∅) = 0, ω(Q) = 1, and ω(A) ≤ ω(B) whenever A ⊆ B (monotonicity). The monotonicity condition ensures that C vω (x) ≤ C vω (y) whenever x Pareto-dominates y (denoted x ≺P y hereafter), i.e. xi ≤ yi for all i ∈ Q and xj < yj for some j ∈ Q. The value ω(X) represents the importance attached to a coalition of criteria X ⊆ Q. When ω(X) = ∑i∈X ω({i}), ω is said to be additive and C vω boils down to U v ω . For more details see [Grabisch et al., 2009].

If x = (14, 12, 10), y = (8, 16, 12) and ui(z) = (z/20)2 for all i ∈ Q, we obtain that x is preferred to y because:

We wish to emphasize here the interest, from a descriptive and prescriptive viewpoint, of resorting to non-linear multiattribute utility functions. This not only provides a more general and flexible class of decision models that can be tuned to the observed preferences, but it also enables to enhance the possibility of finding good compromise solutions within the Pareto set. Let us consider indeed the example given in Figure 1 based on a biobjective shortest path problem. In the figure, every point represents a feasible cost vector and red points represent the Pareto set. As can be seen from the convex hull of these points, only three points in the Pareto set can be obtained by minimizing a weighted sum of the costs. When minimizing a convex utility U v ω (e.g. vi(x) = x2 , Fig.1 left) or a convex Choquet integral C vω (e.g. vi(x) = x, Fig.1 right), we can see from the isopreference curves plotted in Figure 1 that more interesting compromise solutions can be found, even when they do not belong to the boundary of the convex hull of the feasible points.

Note that, whenever ψvω = U v ω or ψvω = C vω , the inequality ψvω (x) ≤ ψvω (y) is linear in ω for any fixed cost vectors x, y ∈ Rq+. Hence, any preference judgement of type "x is preferred to y" will be translated as a linear constraint bounding the set of admissible weighting vectors Ω. Therefore, when preference judgements are obtained from the DM, the set of admissible weights Ω is restricted by linear constraints and thus is a convex polyhedron. This will be useful for performing optimization with imprecise parameters ω.

Robust recommendations with minimax regrets

As ω is imprecisely known, a solution which remains ψvω - optimal for all ω ∈ Ω may not exist. We face a decision problem under uncertainty where Ω is the set of states of nature and any cost vector x is associated with an act (according to the definition of Savage [Savage, 1954]) characterized by the set of consequences {ψvω (x), ω ∈ Ω}. In this context, we are concerned with the determination of a robust solution, i.e. a flexible solution preserving nice perspectives with respect to the possible future evolutions of the uncertainty set Ω. More precisely, the robust solutions can be defined as those minimizing the max-regret criterion [Wang and Boutilier, 2003].

They are characterized by the following definitions, for all x, y ∈ X :

MR(x,X,Ω) is the worst-case regret of choosing x instead of any y ∈ X. Robust solutions are those minimizing MR values over X. However, given the set Ω, the worstcase loss measured by MMR might be too large for certifying the quality of the solution. In this case we are going to collect new preference information so as to reduce the uncertainty set Ω and therefore the MMR. Note that x ≺P y implies that PMR(z, x,Ω) ≥ PMR(z, y,Ω) and PMR(x, z,Ω) ≤ PMR(y, z,Ω) for any solution z ∈ X. Hence, Pareto-dominated solutions can be omitted during the search since MMR(X , Ω) = MMR(ND(X ), Ω).

3 Search with Imprecise Parameters

We introduce now a general interactive elicitation procedure alternating preference elicitation steps and search steps. The search steps of the procedure are based on recent variants of MOA∗ [Mandow and de la Cruz, 2005] and U ∗ [Dasgupta et al., 1995; Perny and Spanjaard, 2003], adapted to minimize regrets under utility uncertainty. Let us recall now the standard concepts and formalism for multiobjective statespace search. In vector-valued graphs, there possibly exists several optimal paths with different cost vectors to reach a given node. Therefore, the basic graph exploration procedure consists in iteratively expanding labels attached to subpaths rather than nodes. Labels are of the form ℓ = [nℓ, pℓ, gℓ] where pℓ denotes a path from s to nℓ and gℓ = g(pℓ) denotes its cost. At any iteration of the algorithm, a label is selected for expansion. The expansion of a label ℓ∗ generates the set of its successors {[n, pℓ∗ ◦ n, g(pℓ∗ ◦ n)] : n ∈ S(nℓ∗)}. The set of generated labels is divided into two disjoint sets: a set C of closed labels (yet expanded) and a set O of open labels (candidate to expansion). The set C (resp. O) restricted to labels ℓ such that pℓ ∈ P(s, n) is denoted C(n) (resp. O(n)). Moreover, the expanded labels corresponding to the current possibly optimal solution paths are stored in a set denoted S and the corresponding set of cost vectors is denoted gS. Another feature imported fromMOA∗ is that, for each generated label ℓ, a set F(ℓ) = {gℓ + h : h ∈ H(nℓ)} of cost vectors is computed to estimate the cost vectors of the solution paths extending pℓ, where H(nℓ) is a set of heuristic costs estimating the set {g(p) : p ∈ P(nℓ, Γ)}.

We consider now the problem of finding an optimal solution path for the minimax regret decision criterion such that the gap to optimality, quantified by the minimax regret MMR, is bounded above by threshold δ. First, we propose a pruning rule that enables, given a set of feasible weights Ω, to detect subpaths that necessarily lead to solutions with a max regret MR strictly greater than δ. This rule is based on the following dominance relation.

Then, the following property holds.

Proposition 1. For all X, Y ⊂ Rq+:

Proof. Consider X, Y ⊂ Rq+ such that X ◁δΩ Y and let y ∈ Y . Then for all ω ∈ Ω, there exists x ∈ X such that ψvω (y) - ψvω (x) > δ. Therefore, for all ω ∈ Ω, we have maxx∈X[ψvω (y) - ψvω (x)] > δ, and in particular we have minω∈Ωmaxx∈X[ψvω (y) - ψvω (x)] > δ. Consider now X, Y ⊂Rq+ such that minω∈Ω, maxx∈X [ψvω (y)-ψvω (x)] > δ for all y ∈Y . In that case, for all y ∈ Y and all ω ∈ Ω, we have maxx∈X [ψvω (y)-ψvω (x)] > δ and so there exists x ∈ X such that ψvω (y) - ψvω (x) > δ. Hence we have X ◁δΩ Y .

Thus, since Ω is a convex polyhedron and ψvω (x) is linear in ω for any fixed x ∈ Rq+, ◁δΩ-dominance tests can efficiently be performed using linear programming. Hence, we propose a pruning rule based on the following proposition:

Proposition 2. For any ℓ′∈O, if gS ◁δΩ F(ℓ′ ), then path pℓ′ cannot be part of a solution path with a MR below δ.

Proof. Let ℓ′ ∈ O be such that gS ◁δΩ F(ℓ′ ). For any path p′ ∈ P(nℓ′ , Γ) and any Ω′ ⊆ Ω, we want to prove that MR(g(pℓ′ ◦ p′ ),X,Ω′ ) > δ. Since H is admissible, there exists h′ ∈H(nℓ′) such that h′ Pareto-dominates g(p′ ), and so gℓ′ + h′ Pareto-dominates gℓ′ + g(p′ ) = g(pℓ′ ◦ p′ ). Since ψvω is increasing with Pareto-dominance, then we have ψvω (gℓ′+h′ ) ≤ ψvω (g(pℓ′◦p′ )) for all ω∈Ω′ . Moreover, since we have gS ◁δΩ F(ℓ′ ) = {gℓ′ + h : h∈H(nℓ′ )}, then for all ω∈Ω′ , there exists ℓ∈S such that ψvω (gℓ′+h′ )-ψvω (gℓ)>δ, and so we have ψvω (g(pℓ′ ◦ p′ )) - ψvω (gℓ) > δ. Hence, for all ω ∈ Ω′ , we have maxℓ∈S[ψvω (g(pℓ′ ◦ p′ )) - ψvω (gℓ)] > δ. Then, we have maxp∈P (s,Γ)[ψvω (g(pℓ′ ◦ p′ )) - ψvω (g(p))]>δ for all ω∈Ω′ since {pℓ : ℓ∈S}⊆P(s, Γ). Therefore, we have maxω∈Ω′ maxp∈P(s,Γ)[ψvω (g(pℓ′ ◦ p′ )) - ψvω (g(p))] >δ, i.e. MR(g(pℓ′ ◦ p′ ), X , Ω′ ) > δ.

Thus, if there exists a label ℓ′ ∈ O such that we have gS ◁δΩ F(ℓ′ ) at some point of the search procedure, then Proposition 2 ensures that path pℓ′ cannot be completed into a solution path with a max regret MR below δ (even if we further restrict the set of feasible weights Ω by asking preference queries to the DM). This result can be used to insert a pruning rule in the search so as to detect faster a solution path with a MR below δ, if it exists. However, for a given set Ω, it may be the case that no such path exists. We introduce now a sufficient condition on MMR(gS,Ω) to guarantee the existence of a path with MR below δ:

Proposition 3. If MMR(gS,Ω) ≤ δ at the end of the search procedure, then MR(g(p∗ ), ND(X ), Ω) ≤ δ, for any solution path p∗ ∈ arg min pℓ :ℓ∈S MR(gℓ, gS , Ω).

Proof. Let p∗ ∈ argminpℓ:ℓ∈S MR(gℓ, gS,Ω). We want to prove that PMR(g(p∗ ), g(p′ ), Ω)≤δ for any solution path p′ such that g(p′ ) ∈ ND(X). Two cases may occur:

Case 1: There exists ℓ ∈ S such that p′ = pℓ. In that case, we can directly infer the result because PMR(g(p∗ ), g(p′ ), Ω) ≤

Case 2: There exists no ℓ ∈ S such that p′ = pℓ. In that case, there exists S ′ ⊆ S and a generated label ℓ′ such that path pℓ′ is a subpath of p′ and gS ′ ◁δΩ F(ℓ′ ). Thus, for all h ∈H(nℓ′) and all ω ∈Ω, there exists a path phω ∈ {pℓ : ℓ ∈ S ′} such that ψvω (gℓ′ + h) - ψvω (g(phω )) > δ. Then, since H is admissible, there exists h′ ∈ H(nℓ′) such that gℓ′ + h′ Pareto-dominates g(p′ ), and since ψvω is increasing with Pareto-dominance, then we have ψvω (gℓ′ + h′ ) ≤ ψvω (g(p′ )). Therefore, we have ψvω (g(p′ )) - ψvω (g(ph′ ω )) > δ, which can be rewritten ψvω (g(ph′ ω )) - ψvω (g(p′ )) < -δ. Moreover, we necessarily have ψvω (g(p∗ )) - ψvω (g(ph′ ω )) ≤ δ since S ′ ⊆ S and MR(g(p∗ ), gS,Ω) ≤ δ. Finally, we have ψvω (g(p∗ )) - ψvω (g(p′ )) < 0 ≤ δ by summing the two previous inequalities and therefore PMR(g(p∗ ), g(p′ ), Ω)≤δ.

Therefore, if we ensure that MMR(gS,Ω) is smaller than threshold δ at the end of the procedure, then any solution p∗ ∈ argminpℓ:ℓ∈S MR(gℓ, gS,Ω) satisfies MR(g(p∗ ),ND(X),Ω) ≤ δ. In order to decrease the minimax regret MMR(gS,Ω), we can, at any step of the search procedure, ask preference queries to reduce the set of feasible parameters Ω. Indeed, it can easily be checked that Ω′ ⊆ Ω implies MMR(gS,Ω′ ) ≤ MMR(gS,Ω). For example, we may use a query selection strategy proposed in [Boutilier et al., 2006] that consits of asking the DM to compare x∗ and y∗ where x∗ is the current MR optimal vector in gS and y∗ is the worse adversary choice (i.e. the vector maximizing PMR(x∗ , y,Ω) for y ∈ gS). The answer to this query induces a linear constraint that can be used to restrict Ω.

We have implemented this first procedure on state space graphs (numerical results are reported in Section 5). When δ is small, the guarantee on regrets is good but the number of queries is quite important. As δ increases, the number of queries diminishes but the procedure becomes significantly slower due to the size of the uncertainty set Ω that makes the pruning rule less efficient. For this reason, we propose in the next section a sophistication of our procedure using an approximation algorithm, that will be much more efficient while still providing guarantees on MMR values.

4 Combining Approximation and Elicitation

In order to obtain a faster search algorithm, we are going to work on near optimal cost vectors with respect to functions ψvω , ω ∈ Ω. For this reason we introduce the following dominance relation:

Similarly to ◁δΩ- dominance tests, ≾εΩ-dominance tests can be performed using linear programming due to the following:

Proposition 4. For all X, Y ⊂ Rq+:

The proof is deliberately omitted because it is very similar to that of Proposition 1. Let us show now that ≾εΩ is a relaxation to the ◁δΩ dominance introduced in Definition 1.

Proposition 5. For all X, Y ⊂ Rq+: X◁δΩ Y ⇒X≾εΩ Y

Proof. Consider X, Y ⊆ Rq+ such that X◁δΩ Y . Let y ∈ Y and ω ∈ Ω. Since X◁δΩ Y , then there exists x ∈ X such that ψvω (y) - ψvω (x) > δ ≥ 0, i.e. such that ψvω (y) ≥ ψvω (x). Moreover, we have (1 + ε)ψvω (y) ≥ ψvω (y) since ε ≥ 0 and ψvω (y) ≥ 0, and therefore (1 + ε)ψvω (y) ≥ ψvω (x). Hence we have X≾εΩ Y .

As a consequence, using ≾εΩ-dominance instead of ◁δΩdominance to prune open labels in MOA∗ may reduce the number of generated labels (and probably solution times). However, when using this sharper pruning rule, we loose the guarantee obtained for MR values in Proposition 3. In order to restore a guarantee when using the pruning rule based on the ≾εΩ-dominance we propose to work with the following definition of regrets.

These regrets are obviously an extension of the initial notions of regrets introduced in Section 3. When ε = 0, they are identical to the initial definition of regrets. When ε > 0 their definition enables to establish the following counterpart of Proposition 3:

Theorem 1. If MMRε(gS,Ω) ≤ (1 + ε)δ at the end of the search procedure, then MR(g(p∗ ),ND(X),Ω) ≤ δ, for any solution path p∗ ∈ arg min pℓ :ℓ∈S MR(gℓ, gS , Ω).

Proof. Let p∗ ∈ argminpℓ:ℓ∈S MRε(gℓ, gS,Ω). We want to prove that PMR(g(p∗ ), g(p′ ), Ω)≤δ for any solution p′ such that g(p′ )∈ND(X). Let λ=(1 + ε)δ. Two cases may occur:

Case 1: There exists ℓ ∈ S such that p′ = pℓ. In that case, we have PMRε(g(p∗ ), g(p′ ), Ω) ≤ λ since MMRε(gS , Ω) ≤ λ, i.e. (1 + ε)ψvω (g(p∗ )) - ψvω (g(p′ )) ≤ λ for all ω ∈ Ω. Then, we have (1 + ε)ψvω (g(p∗ )) - (1 + ε)ψvω (g(p′ )) ≤ λ since ε ≥ 0, and so ψvω (g(p∗ )) - ψvω (g(p′ )) ≤ λ/(1 + ε) = δ. Hence we have PMR(g(p∗ ), g(p′ ), Ω) ≤ δ.

Case 2: There exists no ℓ ∈ S such that p′ = pℓ. In that case, there exists S ′ ⊆S and a generated label ℓ′ such that pℓ′ is a subpath of p′ and {gℓ : ℓ ∈S ′} ≾εΩ F(ℓ′ ). Therefore, for all ω ∈ Ω and all h ∈ H(nℓ′), there exists phω ∈ {pℓ : ℓ ∈ S ′} such that (1 + ε)ψvω (gℓ′ + h) ≥ ψvω (g(phω )). Moreover, since H is admissible, there exists h′ ∈ H(nℓ′) such that gℓ′ + h′ Pareto-dominates g(p′ ), and since ψvω is compatible with Pareto-dominance, we have ψvω (gℓ′ + h′ ) ≤ ψvω (g(p′ )). Therefore, we have (1 + ε)ψvω (g(p′ )) ≥ ψvω (g(phω )). Moreover, since S ′ ⊆ S and MMRε(gS,Ω) ≤ λ, then we have (1 + ε)ψvω (g(p∗ )) - ψvω (g(phω )) ≤ λ. Finally, we obtain (1+ε)ψvω (g(p∗ ))-(1+ε)ψvω (g(p′ )) ≤ λ from the two previous inequalities, i.e. ψvω (g(p∗ ))-ψvω (g(p′ )) ≤ λ/(1+ε) = δ. Hence, we have PMR(g(p∗ ), g(p′ ), Ω) ≤ δ.

Therefore, if we obtain MMRε(gS,Ω) ≤ (1 + ε)δ at the end of the search procedure, then any solution path p∗ in argminpℓ:ℓ∈S MR(gℓ, gS,Ω) is such that MR(g(p∗ ),ND(X),Ω) ≤ δ. In order to decrease MMRε(gS,Ω), we can, here also, ask preference queries to reduce the set of admissible parameters Ω. This is less straightforward than in Section 3 due to the use of MMRε instead of standard MMR. However the query selection strategy used in Section 3 can be adapted as shown by the following proposition:

Proposition 6. If ε ≤ δ/(1 - δ), then there exists a questionnaire that enables to reduce Ω in such way that MMRε(gS , Ω) ≤ (1 + ε)δ.

Proof. Let G = (V, E) be the directed graph defined as follows: V is a set of nodes, one node denoted vℓ per label ℓ∈S, and E is a set of arcs where node vℓ is linked to node vℓ′ if and only if ψvω (gℓ) ≤ ψvω (gℓ′ ) for all ω ∈ Ω. Note that for every cycle of type 〈vℓ1 , . . . , vℓk , vℓ1 〉 in G, we necessarily have ψvω (gℓ1 )= . . . =ψvω (gℓk ) for all ω∈Ω. Hence, each maximal cycle can be reduced to a single node. Let ̂ G = (̂ V, ̂ E) be the directed acyclic graph obtained after these reductions. Then, consider the following elicitation procedure.

While graph ̂ G have more than one source:

• Determine x∗0 as one solution minimizing MR(x, gS , Ω) and y∗ 0 a solution that maximizes PMR(x∗0 , y,Ω). Let x∗ and y∗ be respectively an ancestor of x∗0 and y∗ 0 that have no predecessor. If x∗0 has no ancestor, then x∗ = x∗0 (the same applies to y∗ 0 ).
• Ask the DM to compare the two solutions associated with x∗ and y∗ .
• Update graph G by inserting new arcs induced by the new preference information obtained and ̂ G accordingly.

At the end, we obtain a connected digraph, the source of which is denoted vℓ∗. By construction, for all ℓ ∈ S, we have ψvω (gℓ∗) ≤ ψvω (gℓ) for all ω ∈ Ω. Therefore, we have PMRε(gℓ∗ , gℓ, Ω) =maxω∈Ω{(1 + ε)ψvω (gℓ∗ ) - ψvω (gℓ)} ≤ maxω∈Ω{(1+ε)ψvω (gℓ∗ )-ψvω (gℓ∗ )}=ε×maxω∈Ω ψvω (gℓ∗ ). Then, since ψvω (gℓ∗) ≤ 1 for all ω ∈ Ω, we have PMRε(gℓ∗ , gℓ, Ω) ≤ ε. Hence PMRε(gℓ∗ , gℓ, Ω) ≤ (1 + ε)δ directly follows from ε ≤ δ/(1-δ). Thus MRε(gℓ∗ , gS , Ω)≤ (1 + ε)δ and MMRε(gS , Ω)≤(1 + ε)δ.

5 Numerical Tests

We have evaluated the performance of the two algorithms respectively presented in Section 3 and 4 in terms of computation times (in seconds) and number of queries. Results are obtained by averaging over 30 runs and linear optimizations are performed using the Gurobi library of Java. The algorithm based on MR minimization is denoted R∗ hereafter whereas the one based on MRε minimization is denoted R∗ ε .

In a series of experiments, we consider instances of graphs G = (N,A) where all nodes in N are uniformly drawn in the two dimension grid {1, . . . , 1000} × {1, . . . , 1000}, but source node s and goal node γ are respectively located in (1, 500) and (1000, 500). Each node is linked to 30 randomly chosen nodes and the associated cost vectors are randomly drawn using Gaussian distributions parametrized according to Euclidean distances. For each node n ∈ N, we set H(n) = {I(n)} where I(n)=(I1(n), . . . , Iq(n)) is the ideal point defined by Ii(n) = minp∈P(n,γ) gi(p) for all i ∈ Q. We consider S-shaped disutility functions vi, i ∈ Q, of the form:

where xi is the ith component of cost vector x; ai and bi are parameters enabling respectively to control the amplitude of the 'S' and the position of the 'S' along the i-th criterion.

To evaluate the impact of the model complexity (in terms of number of parameters), we consider additive utilities (U v ω ) and Choquet integrals (Cvω ) of type:

This is indeed a Choquet expected utility associated with the capacity ω(X) = ∑i∈X mi + ∑i,j∈X:i<j mi,j for X ⊆ Q. This specific subclass of capacity is said to be 2-additive because it only involves a number of parameters which is quadratic in the number of criteria.

For algorithm R∗ ε , we have estimated the value of ε that enables a balanced trade-off between the computation time and the number of queries. Table 1 shows that the larger parameter ε, the smaller the number of queries and the computation time. Hence, the best option is definitely to set ε to its maximum feasible value, i.e. ε = δ/(1 - δ). Therefore, in the following experiments, we only consider this value for ε.

Then, we have compared R∗ and R∗ ε algorithms. In Table 2, we can see that computation times drastically increase with respect to δ for the R∗ algorithm. In other words, when lowering δ (the required guarantee of quality), algorithmR∗ reduces the number of queries but increases significantly computation times, a drawback that does not appear for R∗ ε . Moreover, R∗ ε is much faster than R∗ , e.g. 3000 times faster for q = 2 and δ = 0.1. The time difference between the two algorithms increases with q, the number of criteria.

Finally, we have investigated the impact of the number of parameters, on the performance of R∗ ε . As it could be expected, the number of queries and the computation times needed for elicitating the 2-additive Choquet model are more important than for elicitating the additive utility model (the former model involves q(q + 1)/2 parameters, the latter only q). This is the price to pay for higher descriptive and prescriptive possibilities but in any case the overall number of queries remains quite admissible as the number of criteria increases.

6 Conclusion

We have introduced a new approach combining nearadmissible state-space search and incremental elicitation procedures to solve search problems in vector-valued graphs. It makes it possible to elicit the weighting parameters of nonlinear models such as the additive utility model and the Choquet expected utility. Our approach is based on a sophistication of MOA∗ search and U ∗ search involving new pruning rules implemented with an LP solver. The search procedure is interweaved with an incremental elicitation procedure allowing to approximate, more and more accurately, the preference parameters controlling the importance of criteria, or sets of criteria, and thus the value system of the decision maker.

The numerical tests reported show the efficiency of this approach both in terms of number of queries and in terms of solution times. The elicitation procedure based on MRε regrets minimization is shown to provide robust solutions, i.e. solutions with a gap to optimality guaranteed to fall below a desired threshold δ.

A natural extension of this work would be to integrate the elicitation of one dimensional utility functions in the whole regret minimization process, instead of eliciting them in a preliminary stage. This seems to be a challenging question because in this case, regret minimization will require to solve quadratic optimization problems at every step of the search procedure.

Acknowledgments

This work is part of the ELICIT project supported by the French National Research Agency through the Idex Sorbonne Universit´es under grant ANR-11-IDEX-0004-02.