Explaining Multi-Criteria Decision Aiding Models with an Extended Shapley Value

1 Introduction

Decision Aiding plays a central role in many systems and processes, ranging from recommender systems to system engineering. Any complex decision process is characterized by the presence of multiple and often conflicting criteria. To facilitate this process, Multi-Criteria Decision Aiding (MCDA) proposes a wide variety of models to aggregate the criteria, and dedicated methods to respect the preferences of the decision maker (DM). The criteria are usually organized hierarchically with several nested aggregation functions, in order to represent the natural decomposition of the decision reasoning into points of view and sub-points of view. The next example presents a hierarchical MCDA model.

Example 1 The mission of Maritime Patrol is to monitor a maritime area and seek for illegal activity. It evaluates in real time a Priority Level (PL) associated to each ship in this area, where the PL increases when there is a suspicion of illegal activity or when it is urgent to intercept the ship. The PL is intrinsically based on multiple criteria: 1. Incoherence between Automatic Identification System (AIS) data and radar detection; 2. Suspicion of drug smuggling on the ship; 3. Suspicion of human smuggling on the ship; 4. Current speed (since fast boats are often used to avoid being easily intercepted); 5. Maximum speed since the first detection of the ship (it represents the urgency for the potential interception); 6. Proximity of the ship to the shore (since smuggling ships often aim at reaching the shore as fast as possible).

In this running example, the criteria will only take intuitive values 'High/Yes', which correspond to higher PL, or 'Low/None/No'. More intermediate or continuous values can be defined without any loss of generality. According to the operational commander (OC), the six criteria are organized as in Fig. 1. There are four aggregation nodes, with the following semantics: 7. Suspicion of illegal activity; 8. Kinematics; 9. Capability to escape interception; 10. Overall PL.

The OC has the following needs:

• N1 (Interpretability): In order to trust the PLmodel, theOC needs to have a general interpretation of the PL model: What are the most important attributes on average?
• N2 (Explicability): Beyond the PL score itself, the OC needs further analysis to determine whether to intercept a ship: Why is the PL higher for this ship? Why has the PL of this ship significantly increased over last minutes?
• N3 (Sensibility Analysis): For a ship with a low PL score, the OC wonders what changes in the attribute values would increase the PL most significantly. The maritime patrol will then put more means in identifying as early as possible whether these identified attributes vary.

The answers to the previous questions require explanation capabilities of the MCDA model. Explanations are also important to build acceptance and trust for all users.

The OC is not looking for complete explanations (see [Miller, 2017]) - such as proofs - as the OC is under stress and time pressure, and is not specialist in MCDA (and is unable to follow a complex MCDA reasoning). On the contrary, we are aiming at simple and incomplete explanations, such as: the PL has significantly increased mainly because of 'AIS/radar incoherence' status change, and not because of the increasing current speed. Such explanations can be derived from sensitivity analyses [Ribeiro et al., 2016]. To this end, we construct an index measuring the influence of each attribute on the decision (e.g. the comparison between the PL for two ships). In the previous example, the influence of attribute 1 would be important and that of attribute 4 would be small.

The influence index can be defined in many different ways. The existing proposals only consider a flat organization of criteria, and are defined for specific models (see Section 3). In order to derive the correct expression, we adopt an axiomatic approach, thereby defining a set of desirable properties (axioms) for such indices. Some of these axioms are related to the tree structure of the criteria. This new index is an extension of the Shapley value (defined in Cooperative Game Theory) on trees. Note that the use of values has recently gained interest for interpretability in Classification [Datta et al., 2016; Lundberg and Lee, 2017].

The main contributions of this paper are now summarized:

• Our influence index is formally justified by an axiomatic approach, where we have shown that it is the only index that fulfills some natural properties (Sect. 4 and 5);
• Our influence index is easily interpretable as it can be derived from an intuitive construction (Sect. 5);
• Despite of exponential complexity, its computation can be drastically reduced by considering a reduced tree, making it usable in practical applications (Sect. 6);
• Its application is relevant on the running example for the three needs N1, N2 and N3, and we illustrate its benefits over the existing proposals in an example (Sect. 7).

2 Model and Notations

2.1 MCDAModel

Multi-Criteria Decision Aiding (MCDA) models aim at representing the preferences of a Decision Maker (DM) over a set of criteria N = {1, . . . , n}, each criterion i ∈ N being associated with an attribute Xi, either discrete or continuous. The alternatives are characterized by a value on each attribute and are thus associated to an element in X = X1 × · · · ×Xn. Even if some elements of X may not correspond to real alternatives, we will call X the set of alternatives. We assume that the preferences of the DM over X are represented by a cardinal utility model U : X → R. It is classical to write U in the decomposable way [Keeney and Raiffa, 1976]:

where the ui : Xi → R are called the utility functions and H : Rn → R is an aggregation function.

2.2 Structuring Criteria in a Hierarchy

In many applications, the number of criteria can be relatively large - beyond 20 or more. It is then common to decompose H in a hierarchical way, with intermediate aggregation nodes. This structure helps to keep the number of aggregated elements to a reasonable number for each aggregation node (see the Miller law [Miller, 1956]), so that the DM can easily express preferences to elicit each aggregation function separately, as the OC would do in Ex. 1.

The hierarchy of criteria is represented by a rooted tree T , defined by the set of nodes MT (i.e. the set of criteria and aggregation nodes), and the children ChT (l) of node l (i.e. the nodes that are aggregated at each node l) [Diestel, 2005]. We also denote by NT ⊆MT the set of leaves of tree T (i.e. the criteria), by sT ∈ MT the root of tree T (i.e. the top aggregation node), by DescT (l) the set of descendants of l, and by LeafT (l) the leaves at or below l ∈ MT . Unless specified, we assume that the leaves of tree T are exactly the criteria: NT = N. We will consider two particular cases of trees: flat organizations of criteria, having only one aggregation node sT (i.e. MT = N ∪ {sT}), and coalition structures where each leaf is at depth exactly 2 to the root.

Representation (1) can be further decomposed on the tree structure T. For x ∈ X, we can compute U(x) recursively from a function vU i defined at each node i ∈MT :

• vU i (x) = ui(xi) for every leaf i ∈ NT ,
• vU l (x) = Hl ((vU k (x))k∈ChT (l) ) for every aggregation node l ∈ MT \NT , where Hl is an aggregation function,
• U(x) = vU sT (x) is the overall utility.

By abuse of notation, U will denote the vector U := ((ui)i∈NT , (Hi)i∈MT\NT ) of local functions characterizing U, as well as function yielding U(x). We denote by UT the set of such vectors U of local functions defined on T .

Example 2 (Ex. 1 continued) We have MT = {1, . . . , 10}, sT = 10 and NT = N = {1, 2, 3, 4, 5, 6}. The tree is defined by ChT (7) = {2, 3} (node 7 aggregates nodes 2 and 3), ChT (8) = {4, 5}, ChT (9) = {6, 8} and ChT (10) = {1, 7, 9}. Then we have U = (u1, . . . , u6,H7, . . . ,H10), and U(x) = vU 10 (x), with vU i (x) = ui(xi) for all i ∈ NT , vU 7 (x) = H7(vU 2 (x), vU 3 (x)), vU 8 (x) = H8(vU 4 (x), vU 5 (x)), vU 9 (x) = H9(vU 6 (x), vU 8 (x)), and vU 10 (x) = H10(vU 1 (x), vU 7 (x), vU 9 (x)).

2.3 Examples of AggregationModels

The goal of this paper is to design a generic explanation method, which can be applied to any model U and aggregation functions Hl. However, for illustrative purpose, we describe in this section two such models, classically used. Consider an aggregation node l ∈ MT \ N, which children are ChT (l). For the sake of simplicity, we assume that the components that are aggregated by Hl are simply denoted by the vector a = (a1, . . . , anl ), with nl = |ChT (l)|.

Weighted Sum. The weighted sum is a widely used aggregation function. It takes the following form

where wi is the weight assigned to node (criterion) i. This model assumes the independence among the criteria. This assumption is often violated (presence of interaction among criteria), as we will see in the running example.

Choquet Integral. The Choquet integral [Choquet, 1953], which is an extension of the weighted sum, is a powerful aggregation function thanks to its ability to represent many types of interaction in a versatile way [Grabisch, 1996]. Interaction is materialized by non-linear terms. A very good compromise between the representation power of the model and its elicitation and interpretation burden is obtained by restricting to interactions between pairs of criteria [Grabisch, 1997]. This is the 2-additive Choquet integral [Grabisch, 1997]:

where all coefficients wi, w∧ ij , w∨ ij are non-negative and sumup to one. The choice of min and max operators for the non-linear part (rather than other operators such as the product) comes from the fact that we need to satisfy idempotency (the overall score of an alternative having the same score α ∈ [0, 1] on all criteria shall be equal to α, i.e. CI(α, . . . , α) = α). We note that the min and max operators are the numerical counterparts of the AND and OR connectives respectively.

Term w∧ ij (resp. w∨ ij ) corresponds to complementarity (resp. redundancy) between criteria i and j in the sense that the better the achievement on one criterion, the more (resp. less) significant it is to improve on the other. This model is rich enough to capture most real life decision strategies.

Thanks to relation ai ∧ aj + ai ∨ aj = ai + aj , (2) can be rewritten in a more compact form [Grabisch, 1997]:

where mi = wi + ∑j̸=i w∨ ij andmi,j = w∧ ij -w∨ ij are called the M¨obius coefficients.

In order to interpret more easily these coefficients (e.g. to identify which criteria are the most important), the mean importance of criterion i is defined by [Grabisch, 1997]

If m corresponds to a weighted sum (i.e. mi,j = 0 for all i, j), then Impi(ChT (l),m) is the weight of criterion i. One can readily see that the Choquet integral is piecewise linear. More precisely, it is a weighted sum in each domain Σσ = {a ∈ [0, 1]nl : aσ(1) ≤ aσ(2) ≤ · · · ≤ aσ(nl)}, where σ is a permutation on {1, . . . , nl}:

where ∆ai = mi + ∑j̸=i, aj>ai mi,j + ∑j̸=i, aj=ai mi,j 2 . The previous three expressions (2), (3) and (5) will be used throughout this paper.

The next example illustrates this model.

Example 3 (Ex. 2 cont.) After eliciting the OC's preferences, the aggregation functions are given by:

Node 7: There is suspicion of illegal activity whenever either drug or human smuggling is detected. Hence there is redundancy (operator ∨) between criteria 2 and 3. As human smuggling (crit. 3) is slightly more important than criterion 2, we obtain vU 7 (x) = 0.2 vU 3 (x) + 0.8 vU 2 (x) ∨ vU 3 (x);

Node 8: vU 8 (x) = (vU 4 (x) + vU 5 (x))/2;

Node 9: Nodes 6 and 8 are redundant (operator ∨), since there is a high risk that the ship escapes interception when it is either close to the shore (crit. 6) or very fast (node 8). Hence vU 9 (x) = 0.2vU 6 (x)+0.2vU 8 (x)+0.6vU 6 (x)∨vU 8 (x), Node 10: Nodes 1 and 7 are redundant (operator ∨) since there is a suspicion on the ship when the score is high on either node 1 or 7. Nodes 7 and 9 are complementary (operator ∧) as the risk is not so high for a suspicious ship (high value at node 7) that is easy to intercept (low value at node 9), or for a ship that is difficult to intercept but that is not suspicious. We have the same behavior between nodes 1 and 9. Hence vU 10 (x) = (vU 1 (x)∨vU 7 (x)+vU 1 (x)∧vU 9 (x)+vU 7 (x)∧ vU 9 (x))/3.

For x = (Yes,None,None,High,High,High), we obtain u2(x) = u3(x) = 0, ui(x) = 1 for i ∈ {1, 4, 5, 6}, vU 7 (x) = 0, vU 8 (x) = vU 9 (x) = 1 and U(x) = vU 10 (x) = 2 3 .

Many other models can be used, such as the Generalized Additive Independence (GAI) model [Fishburn, 1967].

A tree can be reduced to a flat structure when all aggregation functions are weighted sums, thanks to linearity. This is no more true with the GAI model and the Choquet integral. Having a hierarchical structure is then a way to capture new aggregation functions not representable by a flat structure. For instance, the model of Ex. 3 cannot be rewritten as a single Choquet integral of the six attributes.

2.4 Subtrees

In order to hide unnecessary details for some DMs, we consider subtrees of T having the same root. Let TT be the set of trees T ′ such that sT ′ = sT , MT ′ ⊆ MT , and ChT ′(l) = ChT (l) for all l ∈ MT ′ \ NT ′ . The elements of TT are interpreted as different levels of details on the original tree T. Fig. 2 illustrates this concept.

Given U = ((ui)i∈NT , (Hi)i∈MT \NT ) ∈ UT and T ′ ∈ TT , we can define UT ′ = ((u′i )i∈NT′ , (H′ i )i∈MT′\NT′ ) ∈ UT ′ by u′i = ui for i ∈ NT ′ ∩ NT , u′i (xi) = xi for i ∈ NT ′ \ NT and H′ i = Hi for i ∈ MT ′ \ NT ′ . We set Xi = R for every i ∈ MT \ NT . Then for x ∈ X, U(x) = UT ′(xT ′ ) where xT ′ ∈ XT ′ is defined by xT ′ i = xi if i ∈ NT ′ ∩ NT and xT ′ i = vU i (x) otherwise.

Example 4 (Ex. 3 cont.) For T ′ given by Fig. 2 and x = (Yes,None,None,High,High,High), we obtain xT ′ i = xi for i ∈ {1, 2, 3}, xT ′ 9 = vU 9 (x) = 1, vUT′ 7 (xT ′ ) = 0 and UT ′(xT ′ ) = vUT′ 10 (xT ′ ) = 2 3 . Hence UT ′(xT ′ ) = U(x).

A particular subtree is when a node j ∈ MT of T becomes a leaf, and thus all descendants of j are encapsulated and represented by j. We define the restricted tree T[j] by MT[j] := (MT \ DescT (j)) ∪ {j}, NT[j] := (NT \ LeafT (j)) ∪ {j}, sT[j] := sT , and ChT[j] (l) = ChT (l) for all l ∈MT[j] \NT[j] . Fig. 2 corresponds to T[9] where T is defined by Fig. 1.

For x, y ∈ XNT′ and S ⊆ NT ′ , (yS, x-S) ∈ XNT′ denotes the alternative taking value yi for i ∈ S and value xi for i ∈ NT ′ \ S.

2.5 Shapley Value

A game (with transferable utility) is a set function v : 2N → R such that v(∅) = 0. In Cooperative Game Theory (CGT), N is the set of players, and v(S) (for S ⊆ N) is the amount of wealth produced by S when they cooperate. The Shapley value is a fair share of the global wealth v(N) produced by all players together, among themselves [Shapley, 1953]:

It is characterized by four properties: Additivity (φSh i (N, v + w) = φSh i (N, v) +φSh i (N,w)), Null player (if v(S ∪ {i}) = v(S) for all S ⊆ N \ {i}, then φSh i (N, v) = 0), Symmetry (φSh πk (πN, πv) = φSh k (N, v) for every permutation π on N), and Efficiency (∑i∈N φSh i (N, v) = v(N)) [Shapley, 1953].

3 RelatedWorks

In MCDA, complete explanations have been proposed for the additive utility model [Belahcene et al., 2017] and the majority model [Labreuche et al., 2012]. The explanation can also be obtained thanks to a surrogate model [Zhong et al., 2014] or to explanation schema [Labreuche, 2011; Nunes et al., 2014].

Sensitivity-Based Explanation and the Idea of Compellingness. Sensitivity analysis can be used as an explanation means, by computing the degree to which the parameters can be changed, while keeping untouched the decision. Alvarez applies this principle to decision trees, by identifying the list of the tests of the tree that are the most sensitive to a change in the input data [Alvarez, 2004]. In [Visser et al., 2014], a hierarchical qualitative preference model is explained, by tracing from the top overall node down to elementary criteria, which element counts in the decision.

In the family of methods based sensitivity analysis, some authors have defined the contribution level of each criterion in some decision. For the weighted sumWS model, the compellingness is a measure of the contribution of criterion i in the differences of scores WS(a) - WS(b) in the comparison of two options a and b in [0, 1]n , with compel(i, a, b) := wi |ai - bi| [Klein, 1994; Carenini and Moore, 2006].

The notion of compellingness has been extended to the Choquet integral: compel(i, a, b) = ∣∣ai ∆ai - bi ∆bi ∣∣ [Montmain et al., 2005]. The explanation then consists in displaying the K largest values of the compellingness, where K can be derived by several strategies [Klein, 1994; Carenini and Moore, 2006].

For the weighted sum, the compellingness is a relevant measure of the contribution of each criterion in the decision. On the other hand, the compellingness defined for a Choquet integral [Montmain et al., 2005] has several drawbacks. First of all, if a ∈ Σσ is close to being ordered by another order σ′ , this means that changing slightly a could yield a completely different explanation (thereby using σ′ instead of σ). Hence the explanation is not continuous (stable) in a. Continuity is an important principle as the values of the alternatives on the attributes may be imprecise and affected by small errors. Secondly, focusing on only one ranking σ amounts to doing as if the Choquet integral (which can represent interaction among criteria) behaved linearly, as a simple weighted sum. Interaction is a global behavior that cannot be explained by only looking at the local weights. Interaction comes from the fact the local weights depend on the value of the scores. Lastly, the approach of [Montmain et al., 2005] is designed for a specific aggregation function within a flat organization of the criteria, and therefore cannot apply for more general hierarchical models, such as the multi-linear model or the GAI model. The influence index we are trying to construct in this paper aims at being applicable to any utility-based MCDA model U (a Choquet integral, a GAI model, a weighted sum,. . .) defined on a hierarchy of criteria, and thus it should work directly on the utility function U rather on weights.

4 Axiomatic Properties

Due to the potential large number of criteria, the presence of interacting criteria and the hierarchical structure, we are aiming at an explanation emphasizing on the main contributing attributes. Given a tree T of criteria, we wish to construct an index Ii(x, y, T, U) ∈ R measuring the influence of attribute i in the difference of scores U(y) - U(x) (comparison between alternatives x and y by model U) on tree T. When there is no confusion, it will be simply denoted by Ii(x, y).

In Ex. 1, the OC might be interested in the influence of aggregation nodes such as "kinematics" (node 9) in the comparison of x and y. Hence Ii has to be defined for every i ∈ MT . Moreover, the results of the explanation can be useful for different DMs, who have different roles and competences. In Ex. 1, the Provincial Governor (PG) might be involved to validate a decision on a specific suspicious ship. The PG is not interested in too many details and a simplified tree might be presented to them, such as the one in Fig. 2. If the subtree representing the concerns of a DM is T ′ ∈ TT , one shall thus also compute indices Ii(xT ′ , yT ′ , T ′ , UT ′ ).

We denote by ∆T the set of vectors (x′ , y′ , T ′ ,U ′ ) where T ′ ∈ TT , x′ , y′ ∈ XNT′ and U ′ ∈ UT ′ . Index I is thus seen as a mapping from ∆T onto a vector of real numbers, where, for (x′ , y′ , T ′ ,U ′ ) ∈ ∆T , I(x′ , y′ , T ′ ,U ′ ) = (Ii(x′ , y′ , T ′ , U ′ ))i∈MT ′ .

We adopt an axiomatization approach. As the axioms may not uniquely specify the influence, we consider a set I(∆T ) of such mappings I. The following axioms will be given on I(∆T ).

Property #1: Restricted Values.

It is difficult to identify which attribute is the most influential in the comparison between x and y, as, in general, x and y take different values on all attributes. In order to identify the most influential variables, one can analyze the consequence of going from xi to yi on attribute i - the values on the other attributes being fixed. The move from xi to yi can be done in several ways: in only one move, with a finite number of intermediate steps, or in a continuous way. Yet the attributes can be discrete or continuous. Moreover, xi and yi can be the only values of Xi. In Ex. 1, all Xi have only two values. As we wish to use the same treatment in all cases, we consider the move from xi to yi which makes the fewest assumptions: directly from xi to yi with no intermediate point. Hence we do not use other values than xi, yi fromXi. As this happens for all attributes in N, the influence index I shall depend only on the overall utility of alternatives of the form (yS, x-S):

Restricted Values (RV): For (x, y, T ′ ,U) ∈ ∆T and I ∈ I(∆T ), index I(x, y, T ′ , U) depends only on {U(yS, x-S) , S ⊆ NT ′}.

Property #2: Null Attribute.

Attribute i ∈ NT ′ is said to be null for x, y,U when U(yS∪{i}, x-(S∪{i})) = U(yS, x-S) for all S ⊆ NT ′ \ {i}. Then, changing value xi to yi on attribute i has no impact on the utility, whatever the value of the remaining attributes. In Ex. 3, comparing x = (Yes,None,High,High,High,High) with y = (Yes,High,High,Low,Low,Low), the second attribute is null (as attribute 3 takes value 'High'). Note that this comes from the redundancy between criteria 2 and 3 (see Ex. 3). Hence its influence should be zero.

Null Attribute (NA): Let (x, y, T ′ ,U) ∈ ∆T and I ∈ I(∆T ). If an attribute i ∈ NT ′ is null for x, y,U, then

Property #3: Restricted Equal Treatment.

For k, l ∈ NT ′ , we say that k ∼x,y,T ′ ,U l when U(yS∪{k}, x-(S∪{k})) = U(yS∪{l}, x-(S∪{l})) for all S ⊆ NT ′ \ {k, l}. This means that attribute k is as desirable as l, as they return the same utility if we switch the values between these two attributes, whatever the values on the remaining attributes. In the case of a flat organization of criteria, due to symmetry reasons, attributes k and l should have the same influence level if k ∼x,y,T ′ ,U l. For a general tree structure T ′ , this argument is still valid when attributes k and l belong to the same part in the tree, i.e. when they have the same parent in T ′ (i.e. there exists j ∈ MT ′ such that k, l ∈ ChT ′(j)). In Ex. 3, attributes 4 and 5 are treated symmetrically in H8. Hence if x4 = y4 and x5 = y5, then 4 ∼x,y,T ′ ,U 5, and attributes 4 and 5 deserve to have the same influence. More generally, two equivalent attributes according to ∼x,y,T ′ ,U should have the same influence.

Restricted Equal Treatment (RET): Let (x, y, T ′ ,U) ∈ ∆T and I ∈ I(∆T ). If k, l ∈ NT ′ have the same parent in T ′ and k ∼x,y,T ′ ,U l, then

Property #4: Additivity.

Most utility models U have some decomposability property. For instance, the weighted sum, the Choquet integral and the GAI model are written as a sum of submodels focused on less attributes. One could use this additivity property to compute the influence index of U from the influence indices computed for each submodel. This would help to reduce the computation burden. The additivity property says that the influence for a sum of two utilities is equal to the sum of the influences for the two utilities.

Note: we have seen in Sect. 3 that the compellingness for the Choquet integral is not continuous in U, but also justified that continuity is an important property. In this respect, requirement for additivity is very convenient as it automatically ensures continuity.

Property #5: Generalized Efficiency.

We wish to explain the comparison between two options x and y. This shall cover the preference relation between x and y (x is preferred/indifferent/less preferred to y), but also the intensity of preference (e.g. x is slightly/significantly/extremely preferred to y). The intensity of preference is quantified by U(y) - U(x). We wish to identify how U(y) - U(x) is shared among the nodes and attributes in T. As the influence is defined for each node in T, the influence of the top node sT is set by convention to U (y) - U (x).

As for the efficiency property in CGT, U(y)-U(x) shall be split among the attributes: ∑i∈NT ′ Ii(x, y, T ′ , U) = U(y) - U(x). To go one step further, the influence at an aggregation node l ∈ MT \ NT shall be split into the influence degree of its direct contributors ChT (l). In Ex. 1, the influence of node 7 is the sum of the influences of nodes 2 and 3. More formally, we obtain the following property.

Generalized Efficiency (GE): Let (x, y, T ′ , U) ∈

∆T and I ∈ I(∆T ). Then

Example 5 (Ex. 3 cont.) In the tree T ′ of Fig. 2, relations (10) and (11) give I10(x, y, T ′ ,U) = U(y) - U(x) = I1(x, y, T ′ , U) + I7(x, y, T ′ , U) + I9(x, y, T ′ , U), I7(x, y, T ′ , U) = I2(x, y, T ′ , U) + I3(x, y, T ′ , U).

Property #6: Consistency with Restricted Tree.

Set TT describes different granularity levels on T where some parts of T are hidden. For j ∈ MT , trees T and T[j] represent the right level of detail for two DMs (e.g. T is Fig. 1 for the OC and T[j] is Fig. 2 for the PG). There is no reason to present two different values of the influence index at a same node i to them. We enforce this condition only when i and j belong to different parts of the tree (i.e. i ̸∈ DescT (j) and j ̸∈ DescT (i)). Hence we have the next axiom.

Consistency with Restricted Tree (CRT): Let (x, y, T ′ ,U) ∈ ∆T and I ∈ I(∆T ). Let i, j ∈ MT ′ s.t. i ̸∈ DescT ′(j) and j ̸∈ DescT ′(i). Then

Example 6 (Ex. 4 cont.) For T given by Fig. 1, i = 1 and j = 9, 1 ̸∈ DescT (9) = {4, 5, 6, 8, 9} and 9 ̸∈ DescT (1) = {1}. T[9] is given in Fig. 2. CRT says that the influence index of node 1 can be computed indifferently from T (for the OC) and T[9] (for the PG), with the same result.

5 Expression of the Influence Index

We propose a construction of an influence index, taking inspiration from the Shapley value. It is not easy to determine the contribution of each attribute in U(y) - U(x), as x and y generally take different values on all attributes. In order to distinguish the contribution of each attribute, we move from x to y changing one attribute at a time, following an ordering π on N. We obtain the following sequence of options: x, (y{π(1)}, x-{π(1)}), (y{π(1),π(2)}, x-{π(1),π(2)}), . . ., y. The influence of attribute i in ordering π writes:

where Sπ(π(k)) := {π(1), . . . , π(k)}. The influence index of attribute i - in the spirit of the Shapley value - is then simply the average value of δx,y,T,U π (i) over all orderings π. Note that this corresponds exactly to the Shapley value φSh i of game vx,y,T,U : 2N → R defined by vx,y,T,U(S) = U (yS , x-S ) - U (x).

As noted by Owen, the Shapley value is not suited when players are organized in a coalition structure [Owen, 1977]. Instead of considering all permutations on N, Owen just considers the permutations preserving the coalition structure. Unfortunately, the Owen solution is only defined for coalition structures and not for general trees.

Generalizing the Owen approach, we define, for a general tree T, the set of admissible orderings Π(T) of N as the set of orderings of elements of N for which all elements of a subtree of T are consecutive. More precisely, π ∈ Π(T) iff, for every l ∈ MT \ N, indices π-1 (LeafT (l)) are consecutive. A permutation π will be assimilated to a vector of n components: π = (π(1), π(2), . . . , π(n)).

Example 7 (Ex. 1 cont.) For T given by Fig. 1, Π(T) contains, for instance, elements (5, 4, 6, 2, 3, 1) (indicating that π(1) = 5, π(2) = 4, π(3) = 6, π(4) = 2, π(5) = 3, π(6) = 1), (1, 6, 4, 5, 2, 3) and (1, 2, 3, 4, 5, 6), which all correspond to a reorganization of the tree that keeps its structure. On the other hand, Π(T ) does not contain (2, 3, 4, 5, 1, 6), since, for l = 9, the elements in π-1 (LeafT (9)) = π-1 ({4, 5, 6}) = {3, 4, 6} are not consecutive. Indeed, attribute 1 is interleaved between attributes {4, 5} and {6} in order π.

Using Π(T), the influence of attribute i ∈ NT in the tree T can be defined by (where EOw stands for Extended Owen)

The second formula follows from General Efficiency GE. The new index subsumes to the Shapley value for flat organizations and to the Owen value for coalition structures.

When U(y) > U(x), I EOw i (x, y, T,U) = 0 (resp. > 0, and < 0) means that attribute i does not contribute (resp. contributes positively, and contributes negatively) on the preference of y over x by U.

The next result shows that I EOw is the only solution fulfilling all previous axioms.

Theorem 1 There is a unique influence index satisfying RV, NA, RET, ADD, GE and CRT. It is equal to I EOw .

The proofs of Theorems 1 through 5 (see below) are omitted due to space limitation.

This result generalizes an axiomatic characterization of the Owen value to coalition structures [Owen, 1977]. We note that axioms NA, RET, ADD and E restricted to coalition structures were used in [Owen, 1977], and Owen introduced a last axiom called Intermediate Game Property, which is quite similar to (11). Lastly CRT is completely new and is related to the hierarchical structure.

6 Computational Complexity Analysis

Index I EOw i has an exponential complexity, like the Shapley value, making its computation intractable, even for small values of n. We show that we can drastically speed-up the computation time, by taking profit of symmetries among permutations in Π(T). This idea was proposed by Owen for his value [Owen, 1977]. We extend it to any tree.

The path from sT to i in T consists of the nodes r0 = sT , r1, . . ., rt = i. Iterating over CRT, the next result is shown.

The extended Owen value of node i for tree T can be computed equivalently on tree T[J].

Example 8 (Ex. 4 cont.) For T given by Fig. 1, and i = 2, we obtain J = {1, 3, 9}. Hence the influence of node 2 can be computed from T[J] given by Fig. 2.

The computational complexity is still exponential but on a much smaller tree. More precisely, the right hand side of (14) requires C(i, T) := 2 ∏tl=1 2|ChT (rl-1)|-1 computations of an overall utility U .

We now show that this is sufficient to compute I EOw i (x, y, T,U) in reasonable time. Most real-life MCDA models contain less than 40 criteria, aggregate at most 6 nodes at each level and have maximal depth of 4. We randomly generated trees having at most 100 criteria, at most 6 children at each level and maximal depth of 5. We also randomly generated options x, y and 2-additive Choquet integrals for U. For each instance, we store the average time to compute one index I EOw i (average over i ∈ NT ). Table 1 shows the computation times over 25000 generations performed on a computer equipped with 3.1 GHz Intel Core i7.

The computations are fast and compatible with user interaction up to 40 attributes. The time increases but remains admissible for most of larger trees. We analyzed the structure of trees for which the computation time is quite large. They correspond to ill-balanced trees for which T[J] is not so different from T. Such trees are very unlikely to arise from a real-life MCDA problem. We have tested the computation time on several real-life problems. For instance, for a real-life model with 29 criteria, the time to compute one index, with and without truncation, is equal to 0.05s and 0.8s respectively.

When complexity C(i, T ) is beyond a given threshold, one may consider that the computation time is not admissible for the user. It is then possible to cut the tree T at a given depth in such a way that C(i, T ′ ) remains below the threshold, where T ′ is the cut tree. For example, cutting the tree of Fig. 1 at depth 2 means that nodes 4 and 5 are removed. Doing this means that the influence of deep nodes (not in the cut tree) are not presented to the user, which is admissible for very large trees. It is easy to find the largest cut depth fulfilling the previous requirement.

The number of alternatives is generally small in MCDA. When there is an exponential number of options, we hopefully do not need to explain all comparisons. For instance, in incremental elicitation using minmax regret [Boutilier et al., 2006], one only needs to explain the comparison between optimal minmax regret solution and its worst contester.

7 How to Answer to the Needs N1, N2 and N3?

This section describes how the influence index can serve to answer to the three needs N1, N2 and N3 (see Sect. 1).

7.1 Case of Need N1 (Interpretability)

It is not easy to provide a general interpretation of a hierarchical model U. This task can be performed thanks to our new indicator. The mean importance of attribute i is simply the influence index of comparing the two alternatives x⊥ and x⊤ having the smallest and largest possible utilities on N respectively (i.e. ui(x⊥i ) = 0 and ui(x⊤i ) = 1 for all i), as this covers the range of Xi's. The next result shows that, for the 2-additive Choquet integral, the computation becomes easy.

Theorem 3 If all aggregation functions are 2-additive Choquet integral, then

where ml are the M¨obius coefficients at aggregation node rl-1 (for l ∈ {1, . . . , t}) in the path from sT to i.

If all aggregation functions are weighted sums, we would expect that the importance of criterion i is the product of the weights of node i and its parents in the path from leaf i to the root, which is exactly what Theorem 3 gives. Formula (15) nicely generalizes this expression, as the importance of an attribute i is the product of the relative importance of this node and its parents in the path from leaf i to the root. For a flat organization, we also recover that the mean importance of attribute i is Imprl (Vl,ml ) (see Sect. 2.3). Theorem 3 shows that our influence index, despite its combinatorial expression, subsumes to a very simple and intuitive expression in the case where x and y are the extreme values. We now illustrate this on the running example on x⊥, x⊤ given by Table 2.

Example 9 (Ex. 3 cont.) I EOw i (x⊥, x⊤) is given by Table 3. We see that the three top level nodes 1, 7, 9 have the same importance, as expected from the expression of vU 10 . On the contrary, the importance of node 7 is unequally shared between nodes 2 and 3, in coherence with the expression of vU 7 .

7.2 Case of Need N2 (Explicability)

There is no competitive explanation approach for hierarchical MCDA models. In order to compare I EOw with the existing works, we restrict ourselves to flat organizations.

Weighted Sum. Consider a weighted sum on a flat organization of the criteria: U(x) = ∑i∈NT wi ui(xi). The compellingness is then compel(i, u(x), u(y)) = wi |ui(yi)- ui(xi)|, where u(x) := (u1(x1), . . . , un(xn)).

Theorem 4 For a weighted sum, we have

Our influence index differs from the compellingness only by the absolute value operator. We prefer to keep the sign in order to keep the sense of the preference between x and y.

Two-Additive Choquet Integral. Consider a flat organization of the criteria where the aggregation function is a 2-additive Choquet integral w.r.t. M¨obius coefficients m. The compellingness is then compel(i, u(x), u(y)) = ∣∣∣ui(xi) ∆u(x) i -ui(yi) ∆u(y) i ∣∣∣.

The next result gives the analytical expression of I EOw i for a 2-additive Choquet integral with M¨obius coefficients m.

Theorem 5 We have

The next example compares our solution with compel.

Example 10 Let us consider U(z1, z2) = u1(z1)+u1(z1)∧u2(z2) 2 and the two options x, y with u(x) = (0.3, 0.9) and u(y) = (1, 0.9). We have U(x) = 0.3 and U(y) = 0.95. The two solutions return completely different results: compel(1, u(x), u(y)) = 0.2, compel(2, u(x), u(y)) = 0.45, I EOw 1 (x, y) = 0.65 and I EOw 2 (x, y) = 0. The ordering among the influences of the two attributes is even different. As attribute 2 is null (u2(x2) = u2(y2)), the influence of attribute 2 should be 0 (see NA), as obtained by I EOw . It is thus very unnatural that compel(2, u(x), u(y)) returns a much larger value than that for criterion 1.

Consider now two other options x′ , y′ close to x, y: u(x′ ) = (0.3, 1) and u(y′ ) = (0.9, 1). The two solutions now return the same result: compel(1, u(x), u(y)) = I EOw 1 (x, y) = 0.6, compel(2, u(x), u(y)) = I EOw 2 (x, y) = 0. We note that I EOw gives very stable results between x, y and x′ , y′ . On the contrary, the values of compel are completely different for x, y and for x′ , y′ , which yields stability problems.

We now illustrate the explanation on the running example.

Example 11 (Ex. 3 cont.) The maritime patrol is interested in the way the PL of a ship varies over time. Consider a ship whose state evolves from state x⊥ to x′ , which implies a very significant increase of PL (from 0 to 23 ). How to explain this? Computation in table 3 shows that I EOw 1 (x⊥, x′ ) = 12 and I EOw 9 (x⊥, x′ ) = 16 : when there is a 'low risk' (no suspicion of illegal activity, as x⊥2 = x⊥3 = x′2 = x′3 = None), 'AIS/radar incoherence' (node 1) has a larger impact on PL than having a fast boat approaching shore. Indeed, as vU 7 (x⊥) = vU 7 (x′ ) = 0, any improvement of vU 9 (resp. vU 1 ) has an impact on only the second term in vU 10 (resp. on the first two terms in vU 10 ). Hence the values of I EOw are natural. In situation of stress, the OC is asking for very simple information. The system can tell to the user that the increase of PL

between x⊥ to x′ mainly comes from node 1. The difference of influence indices between nodes 1 and 9 is all the more noticeable as the mean importance of nodes 1 and 9 are similar (I EOw 1 (x⊥, x⊤) = I EOw 9 (x⊥, x⊤)).

Let us consider another ship with state changing from x′′ to x⊤ (see Table 2). Note that the attribute changes from x′′ to x⊤ are similar to that between x⊥ and x′ . However, the explanation of the difference between x′′ and x⊤ is completely different, as it now comes from the 'Capability to escape', critical during a 'high risk' situation (suspicion of illegal activity, as vU 7 (x′′ ) = vU 7 (x⊤) = 1), since information of 'AIS/radar incoherence' is redundant with suspicion of illegal activity: I EOw 1 (x′′ , x⊤) = 1 6 and I EOw 9 (x′′ , x⊤) = 1 2 . The complete change of explanation in the previous two comparisons accurately reflects the model behavior and in particular the strong interactions present between the criteria.

7.3 Case of Need N3 (Sensibility Analysis)

We illustrate N3 on the running example.

Example 12 (Ex. 3 cont.) The OC now focuses their attention on ship x′′′ having AIS inconsistency (Att. 1). The values of attributes 2, 3, 4, 5 are unknown and set to default None/Low value. While it is crucial for the OC to determine true values of these attributes, it is too time consuming to investigate on all of them. On which attributes shall the OC focus their attention? This can be obtained from the computation of the influence degree between x′′′ and the most threatening situation x⊤. It is not so important to investigate on smuggling (att. 2 and 3) as their influence is low. The maritime patrol puts more means to identify whether the ship is a fast boat, as attributes 4 and 5 have a large influence.

8 Conclusion and Perspectives

We have defined an influence index of a MCDA model for the purpose of explanation, from two approaches: an axiomatic approach which brings a formal justification, and a constructive approach which provides a simple interpretation. We also show how to drastically reduce the complexity of its computation, making it usable in practical applications.

Our approach has several benefits. First of all, it can be applied to any quantitative MCDA model (computing a utility) on any hierarchy of criteria, whereas the existing approaches are dedicated to a specific model and are restricted to a flat organization of criteria. Moreover, it is simple enough to be employed by end-users, and without prior knowledge in MCDA. Finally it can be computed at any node in the tree of criteria and aggregation nodes, allowing the user to perform an analysis at any level.

For future work, we will aim at further reducing the computation time for particular expressions of U (e.g. for Choquet integrals), and testing the index on real users.

Apart from the new explanation approach, we introduced a new Shapley value on graphs. This value could also be used in argumentation [Amgoud et al., 2017] or inconsistencies in databases [Hunter and Konieczny, 2010].

Acknowledgments

This work has been supported by the European project H2020/CIP-2016-2017-1/740898, DEFENDER "Defending the European Energy Infrastructures ".