Christophe Labreuche
email: christophe.labreuche@thalesgroup.com

Michel Grabisch
email: michel.grabisch@univ-paris1.fr

Using multiple reference levels in Multi-Criteria Decision Aid: the Generalized-Additive Independence model and the Choquet integral approaches

Keywords:

In many Multi-Criteria Decision problems, one can construct with the decision maker several reference levels on the attributes such that some decision strategies are conditional on the comparison with these reference levels. The classical models (such as the Choquet integral) cannot represent these preferences. We are then interested in two models. The first one is the Choquet with respect to a p-ary capacity combined with utility functions, where the p-ary capacity is obtained from the reference levels. The second one is a specialization of the Generalized-Additive Independence (GAI) model, which is discretized to fit with the presence of reference levels. These two models share common properties (monotonicity, continuity, properly weighted,. . .), but differ on the interpolation means (Lovász extension for the Choquet integral, and multi-linear extension for the GAI model). A drawback of the use of the Choquet integral with respect to a p-ary capacity is that it cannot satisfy decision strategies in each domain bounded by two successive reference levels that are completely independent of one another. We show that this is not the case with the GAI model.

Choquet integral; Reference Levels; Interpolation.

Introduction

Many models have been defined and studied in Multi-Criteria Decision Analysis (MCDA) with various levels of preference representation power and of elicitation complexity. While many of them are sufficient when the Decision Maker (DM) has only standard preferences, there are however situations in which the DM wishes to express much richer and specific decision strategies. We consider in this paper the case where there is an inherent complexity in the DM preferences coming from the presence of reference levels in the decision problem.

Reference elements on the attributes play an important role in MCDA. In the MACBETH approach, two reference elements are defined on each attribute, and they serve to give a semantics to the concept of weight of criteria1 [START_REF] Bana E Costa | MACBETH[END_REF]. In MR-Sort, an alternative is assigned to the upper class if the set of criteria above a given threshold forms a winning coalition [START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in MCDM I: The case of two categories[END_REF][START_REF] Bouyssou | An axiomatic approach to noncompensatory scoring methods in MCDM, II: More than two categories[END_REF]. A similar idea operates in reference point methods [START_REF] Rolland | Reference-based preferences aggregation procedures in multicriteria decision making[END_REF]. In psychology, reference levels such as the neutral level -demarcating between positive and negative stimulis [START_REF] Kahneman | Judgment under uncertainty: Heuristics and biases[END_REF][START_REF] Slovic | The affect heuristic[END_REF]-and the satisficing level that is considered as good and completely satisfactory if the DM could obtain it, even if more attractive elements could exist [START_REF] Simon | Rational choice and the structure of the environment[END_REF], are welldeveloped. The existence of a neutral level characterizes bipolar scales.

Decision strategies are often affected by reference elements. Let us cite a few examples. Conditional Relative Importance depicts a decision strategy that is dependent on the value of a bipolar attribute being above or below the neutral level: the relative importance between two criteria is conditional on a third (bipolar) criterion being good (above the neutral level) or bad (below the neutral level). This strategy arises in many situations -see [START_REF] Ch | The representation of conditional relative importance between criteria[END_REF] for an example.

The following example also illustrates decision strategies that are dependent on the values of some attributes.

Example 1. The chief technical officer (CTO) of a company has to decide on which products to develop and then sell to customers. Five attributes are considered to evaluate potential products:

• Expected Revenue (ER), which is a number in M Euro;

• Risk Level (RL), taking values in {low, medium, high};

• Reputation of the Company (RC) on the market targeted by the product, taking qualitative values between 1 (very low) to 5 (very high);

• Position with respect to Competitors (PC), taking values among DT(disruptive technology), SOTA(at the state of the art), BSOTA(below state of the art);

• Risk Mitigation (RM), taking values among T(collaborate with another partner to develop the technology -called "Team" strategy, to support the development of the technology), II(internal investment), N(do nothing).

Usually, the risk and revenue attributes can be split into two domains -low/high risk and low/high revenue respectively. The decision strategies depend on which domain the potential product belongs to. The ideal situation is clearly for low risk and high revenue products, whereas the worst situation is for high risk and low revenue products. Most products are represented by the other two situations.

Low risk and low revenue products can correspond to niche products. Here the reputation (RC) is a very important criterion. The product does not necessarily need to be sophisticated, because of the "niche" situation. The last two criteria PC and RM are thus less important. Lastly, high risk and high revenue products can secure the future of the company. But the competition is high on these markets, so that criteria PC and RM are now very important.

The previous example implicitly exhibits reference levels on attributes ER and RL, and the decision strategies depend on these levels.

The question that naturally arises is how to represent such decision strategies with MCDA models. As we will see more precisely, it is not possible to represent these preferences with standard MCDA models. The additive utility model is not suitable as the relative importance between some criteria depends on the values on some other criteria, and more generally, criteria interact each other. Reference-based models cannot help to compare alternatives in the same domain (e.g. high risk and high revenue products in Ex. 1) [START_REF] Rolland | Reference-based preferences aggregation procedures in multicriteria decision making[END_REF]. Despite its ability to model interacting criteria, the Choquet integral fails to represent these preferences as it cannot model different decision strategies depending on whether attributes are judged good or bad [START_REF] Ch | The representation of conditional relative importance between criteria[END_REF]. Actually the Choquet integral is based on only two levels and it cannot model various changes of preferences depending on the ranges of the attributes: The decision strategy at intermediate values is simply an interpolation of those for extreme values.

We show that two models can represent decision strategies that are conditional on the comparison with the reference levels. The first one is the Choquet integral w.r.t. a p-ary capacity [START_REF] Grabisch | Bi-capacities -II : the Choquet integral[END_REF][START_REF] Grabisch | Bipolarization of posets and natural interpolation[END_REF], combined with utility functions. Here the p-ary capacity represents the overall value at the different reference levels.

The second one is a specialization of the Generalized Additive Independence (GAI) model that is discretized to fit with the presence of reference levels.

The concept of p-ary capacity and the associated Choquet integral have been defined as a mathematical tool that naturally extends capacities. However, their complexity makes it very hard to use them in real applications. Up to our knowledge, the only attempt in this direction was for the representation of restaurant customer satisfaction [START_REF] Rolland | Elicitation of 2-additive bi-capacity parameters[END_REF], although limited to bi-capacities. The aim of this paper is to show the interest of the GAI model and the Choquet integral w.r.t. p-ary capacities in applications, and especially in those exhibiting reference levels.

The main contributions of this paper can be summarized as follows:

• We present a motivating example taken from a real application in the engineering domain, to illustrate situations where decision strategies are dependent on several reference levels (Section 3). In engineering, the different levels are successive levels of requirements from the simplest to satisfy to the most difficult one. There are different decision strategies associated to these levels. For instance, the smallest level is generally considered as a hard constraint, whereas the largest level is seen as a bonus (the customer is expected to have a crush in such a situation). This example is running throughout the document, and we show that it cannot be represented by the classical MCDA models.

• Which model can represent the motivating example? (Section 4). We provide two models able to represent the reference levels-dependent multicriteria decision problems: the Choquet integral w.r.t. p-ary capacities and the GAI models.

Regarding the GAI model, we provide a specialization of this model to the presence of reference levels, which is new. The GAI model is then seen as a generalization of the UTA approach, where continuous attributes are discretized. This is important to do so in practice in order to reduce the computational complexity [START_REF] Grabisch | Monotone decomposition of 2-additive generalized additive independence models[END_REF].

• How to choose between the two aggregation models? (Section 5). These two models share common properties (monotonicity, continuity, properly weighted,. . .), but differ on the interpolation method (Lovász extension for the Choquet integral, and multi-linear extension for the GAI model). A drawback of the use of the Choquet integral w.r.t. a p-ary capacity is that the possible decision strategies satisfied in each domain bounded by two successive reference levels are not completely independent of one another.

We call this phenomenon contamination. This was already noted with the conditional relative importance strategy [START_REF] Ch | The representation of conditional relative importance between criteria[END_REF]. We show that this is not the case with the GAI model.

We also present the pros and cons of choosing each of these two models.

• How to elicit the two models? (Section 6). The question of the elicitation of MCDA models is central in applications. This problem might be seen as intractable for the GAI model or the Choquet integral w.r.t. a p-ary capacity due to the large number of parameters. We propose a simple elicitation procedure that focuses on alternatives with balanced profiles (i.e., alternatives in-between two identical levels on all attributes) and fill the model on the other cases by using a cautious principle.

Preliminaries

General model

We are given a set of n attributes indexed by N = {1, . . . , n}. Each attribute i ∈ N is represented by a set X i . The alternatives are characterized by a value on each attribute, and are thus represented by an element in

X = X 1 ו • •×X n .
We assume that we are given a preference relation over X. It is supposed to be represented by an overall utility function

U : X → IR, (1)
i.e., such that x y iff U (x) ≥ U (y).

For x, y ∈ X and A ⊆ N , we denote by X A the set i∈A X i , by x A the restriction of x on attributes A, and by (x A , y N \A ) ∈ X the compound alternative taking value x i for attribute i in A, and value y i otherwise. For x, y, z ∈ X and A, B ⊆ N with A ∩ B = ∅, we also denote by (x A , y B , z N \(A∪B) ) the alternative taking value x i for attribute i in A, value y i for i in B, and value z i otherwise.

Preference relation is said to satisfy weak separability [START_REF] Krantz | Foundations of measurement[END_REF] if: for all i ∈ N , all x i , y i ∈ X i , and all a N \{i} , b N \{i} ∈ X N \{i}

(x i , a N \{i} ) (y i , a N \{i} ) ⇐⇒ (x i , b N \{i} ) (y i , b N \{i} ). (2)
Under this assumption, one can derive, for every i ∈ N , a preference relation i over attribute i from : for all x i , y i ∈ X i

x i i y i ⇔ (x i , a N \{i} ) (y i , a N \{i} ) (3)
for some a N \{i} ∈ X N \{i} . Weak separability simply says that the preference over the values of an attribute, ceteris paribus, should be independent of the values of the other attributes. If we consider the simple example of choosing a car on the basis of its price, its comfort and its maximal speed, weak separability is clearly satisfied: all other criteria being fixed, the smaller the price the better, and similarly for all criteria: the higher the comfort, the better, and the higher the maximal speed, the better. The latter statements are depicted by relations i 's. We denote by i and ∼ i the asymmetric and symmetric parts of i respectively. In order to avoid unnecessary heavy notation and details, we assume that the partial preferences i are monotone: the larger the value of the attributes, the better (

x i i y i ⇐⇒ x i ≥ y i ).
Under weak separability, utility U shall fulfill the following monotonicity conditions, which states that it should be consistent with each relation i :

∀x, y ∈ X with y i i x i for every i ∈ N, U (y) ≥ U (x) (4)
There exist many different utility models of the form (1). In the rest of this section, we focus on two models: (k-ary) capacities and the Choquet integral (section 2.2), and the GAI model (section 2.3).

Capacities, the multi-linear model and the Choquet integral

When satisfies weak separability and other properties, function U takes the decomposition form [START_REF] Keeney | Decision with Multiple Objectives[END_REF] U

(x) = F (u 1 (x 1 ), . . . , u n (x n )), (5)
where u i : X i → IR is the utility function (also called value function) on X i and F : IR n → IR is an aggregation function. By aggregation function, we simply mean a non-decreasing function [START_REF] Grabisch | Aggregation functions[END_REF]. Utility function u i shall be consistent with i (i.e. u i (x i ) ≥ u i (y i ) whenever x i i y i ). Hence u i is non-decreasing. We now introduce the concept of a capacity to describe a class of aggregation functions F . Definition 1. A fuzzy measure [START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF] or capacity [START_REF] Choquet | Theory of capacities[END_REF] on N is a set function µ : 2 N → IR satisfying (1) the monotonicity conditions: µ(A) ≤ µ(B) for every A ⊆ B, and (2) the normalization conditions: µ(∅) = 0, µ(N ) = 1.

Capacities are related to the concept of pseudo-Boolean function. A pseudo-Boolean function is any function f : {0, 1} N → IR [START_REF] Hammer | On approximations of pseudo-Boolean functions[END_REF]. Writing 2 N ≡ {0, 1} N , there is a one-to-one correspondence between set functions and pseudo-Boolean functions: f (1 A ) = µ(A) for all A ⊆ N . From this correspondence, the problem of defining an aggregation function from a capacity is similar to the one of extending a pseudo-Boolean function on [0, 1] N .

In order to define extensions of pseudo-Boolean functions to [0, 1] N , it is convenient to use the Möbius transform [START_REF] Rota | On the foundations of combinatorial theory I. Theory of Möbius functions[END_REF] of µ, defined by

m µ (A) = B⊆A (-1) |A\B| µ(B). (6)
Conversely, µ can be derived from m µ by the formula µ(A) = B⊆A m µ (B).

We can now give two standard extensions of a pseudo-Boolean function f (or

equivalently µ) to [0, 1] N [25] f Π (t) = A⊆N m µ (A) • i∈A t i (7)
f ∧ (t) = A⊆N m µ (A) • i∈A t i . (8)
The first expression is the multi-linear extension of f or µ, and the second one is the Lovász extension of f or µ. Yet f ∧ corresponds to the Choquet integral w.r.t. µ [START_REF] Choquet | Theory of capacities[END_REF].

For a permutation τ on N , we define

Ω τ = {t ∈ IR N : t τ (1) ≤ t τ (2) ≤ • • • ≤ t τ (n) }. The Choquet integral of t ∈ [0, 1] N can be written in terms of the capacity µ [8] C µ (t) = n i=1 t τ (i) -t τ (i-1) µ ({τ (i), • • • , τ (n)}) , (9)
where t τ (0) := 0 and τ is a permutation on N such that t ∈ Ω τ . The Choquet integral is clearly a simple weighted sum in each domain Ω τ . In Figure 1 The use of the decomposable model ( 5) with a Choquet integral implies that the scales of the marginal utility functions u i are commensurate. A scale

L i = {u i (x i ) : x i ∈ X i }
ordered by ≥ is constructed on each criterion i. The marginal utility functions u i are then said to be commensurate if all scales L i 's can be represented by the same scale L u [START_REF] Dubois | Qualitative decision theory with preference relations and comparison uncertainty: an axiomatic approach[END_REF]. This means that one shall be able to compare the values of any two scales L i and L j , with a preference relation Li×Lj defined on L i × L j . A simple way to fulfill this assumption is to ensure that all scales are identical:

L 1 = • • • = L n = L u ,
and a ∼ Li×Lj a (value a on scale L i is indifferent to the same value a on scale L j ) for every a ∈ L u and i, j ∈ N . In other words, if u i (x i ) = u j (x j ), then value x i on attribute X i has the same satisfaction/attractiveness as value x j on attribute X j . This is the approach adopted in MACBETH for the weighted sum [START_REF] Bana E Costa | MACBETH[END_REF]. The basic principle is to construct interval scales given up to an affine transformation over each attribute X i , and to fix the two degrees of freedom of each affine transformation by assuming the existence of two reference levels on the associated attribute. It has been extended to the Choquet integral [START_REF] Ch | The Choquet integral for the aggregation of interval scales in multicriteria decision making[END_REF][START_REF] Ch | An axiomatization of the Choquet integral and its utility functions without any commensurability assumption[END_REF].

When commensurability is fulfilled, models of the form (5) are assumed to satisfy the idempotency property [START_REF] Marichal | Aggregation operators for multicriteria decision aid[END_REF], which states that F (α, . . . , α) = α for every α ∈ IR. In other words, an alternative which is scored α on all criteria, should have α as overall evaluation, because value α has the same meaning throughout all criteria.

GAI model

There are alternative utility models which do not need the commensurability assumption. The best-known model of this class is the additive utility model [START_REF] Keeney | Decision with Multiple Objectives[END_REF]

U (x) = i∈N u i (x i ) (10)
where u i : X i → IR. Note that there is an induced relation between the attributes in this model. For instance, increasing attribute i from value x i to y i is equivalent to increasing attribute j from value x j to y j , which corresponds to even-swaps [START_REF] Hammond | Even Swaps: a rational method for making trade-offs[END_REF]. But this relation is not sufficient to compare directly the values on two attributes, so that the commensurability assumption is not satisfied.

The additive utility model has been generalized to allow some interaction among criteria -under the name of the Generalized Additive Independence (GAI) model [START_REF] Fishburn | Interdependence and additivity in multivariate, unidimensional expected utility theory[END_REF][START_REF] Fishburn | Utility Theory for Decision Making[END_REF][START_REF] Bacchus | Graphical models for preference and utility[END_REF]. The GAI model takes the form of the sum of utilities over subsets of attributes:

U (x) = S∈S u S (x S ) ( 11
)
where S is a collection of subsets of N , x S ∈ X S is the restriction of x over attributes in coalition S, and

u S : X S → IR.
Note that [START_REF] Fishburn | Utility Theory for Decision Making[END_REF]Section 11.3] considers (in an expected utility context) GAI models with no assumption on the attributes (they can be discrete or continuous).

The set S contains all subsets of attributes that interact one another. Hence the additive model ( 10) is a particular case of the GAI model where S is composed only of singletons. One may consider for instance that S is the collection of all singletons and pairs of criteria, as in the utility model underlying UTA GMS -INT [START_REF] Greco | Robust ordinal regression for value functions handling interacting criteria[END_REF], which have strong connections with the GAI model.

It is important to note that the GAI does not necessarily satisfy the weak separability condition [START_REF] Braziunas | Decision-theoretic elicitation of generalized additive utilities[END_REF]. A well-known example of such a violation is the following [START_REF] Boutilier | UCP-networks: A directed graphical representation of conditional utilities[END_REF]: the problem is to choose menus in a restaurant on the basis of two attributes X 1 (main course: 'meat' or 'fish') and X 2 (wine: 'white' or 'red').

Then 'red wine' is preferred to 'white wine' if the main course is 'meat', but 'white wine' is preferred to 'red wine' if the main course is 'fish'.

Hence according to the assumption made in section 2.1, we will consider in this paper only GAI models that satisfy weak separability. It shall be noted that examples like the previous one, violating weak separability, are quite unusual in MCDA. The large majority of MCDA applications satisfy this condition. Moreover, most MCDA methods in OR require weak separability: Pareto front computation in multi-objective optimization, the rough set approach, outranking methods, the additive utility, the Choquet integral,. . . It is thus not a restriction to assume it.

A motivating example

This section introduces and discusses a motivating example in which decision strategies are conditional on where the alternatives are located relatively to some reference levels.

Description of the example

Consider the following example.

Example 2. The design of a system, like an embedded system, is a complex activity [START_REF] Ch | Extension of the MACBETH approach to elicit an OWA operator[END_REF][START_REF] Pignon | Combining experimentation and multi-criteria decision aid: A way to improve NEC systems of systems architecting[END_REF]. The aim is to help the system architect to select the best architecture. System engineers classically define (soft) requirements on key attributes. Such attributes could be the latency of a functional chain, or the weight of the embedded system. Requirements can be specified with the help of several levels 2 such as "the system 'Must have' at least/most value x M i ", "the system 'Should have' at least/most value x S i ", and "it is 'Nice to have' for the system at least/most value x N i ". The system architect expresses the following preferences. If any of the attributes is below the 'Must have' level, then the system is unacceptable. If the two attributes are between the 'Must have' and 'Should have' levels, then the experts are intolerant and look at the worst satisfied criterion. Architectures which values on the two attributes are between the 'Should have' and 'Nice to have' levels are completely satisfactory so that the two attributes are fully compensatory.

The situation where the two attributes are above the 'Nice to have' levels is ideal, and the DM basically looks at bonus represented by the best satisfied criterion.

And so on. The preferences are depicted in Figure 2.

X

Unacceptable tolerant

Attempt to represent these preferences

Let us try to model the previous example with a Choquet integral. It is convenient, for the construction of the model, that each decision strategy occurs in a domain that is bounded by two reference levels. This is not entirely the case in Example 2, as there is a decision strategy below the lowest level 'Must have' and one above the highest level 'Nice to have'. As a result, we add two other reference levels: 'Worst value' (below level 'Must have') and 'Best value'

(above level 'Nice to have'). Hence, at the end, we have five reference levels

(p i = 5).
We need first to define utility functions. We can choose u i (Worst value) = 0,

u i (Must have) = α, u i (Should have) = β, u i (Nice to have) = γ and u i (Best value) = 1
, where 0 < α < β < γ < 1 are first identified (using for instance MACBETH approach [START_REF] Bana E Costa | MACBETH[END_REF]).

The architect expresses separate decision strategies for each range of values of the attributes. They can be modeled by the following capacities:

• v(∅) = v({1}) = v({2}) = 0 and v({1, 2}) = 1, below the 'Must have'
levels, as the two criteria are veto;

• v(∅) = 0, v({1}) = v({2}) = 0.2, v({1, 2}) = 1, between the 'Must have'
and 'Should have' levels, which is indeed an intolerant model;

• v(∅) = 0, v({1}) = v({2}) = 0.5, v({1, 2}) = 1, between the 'Should
have' and 'Nice to have' levels, which is a simple weighted sum and is thus indeed a completely compensatory model; Reference point methods are extensions of the outranking methods based on the presence of reference levels. Non-Compensatory Sorting assigns at least a category to an alternative if the set of attributes that beats the reference profile of the category forms a winning coalition [START_REF] Bouyssou | An axiomatic approach to noncompensatory sorting methods in MCDM I: The case of two categories[END_REF][START_REF] Bouyssou | An axiomatic approach to noncompensatory scoring methods in MCDM, II: More than two categories[END_REF]. In ranking with multiple profiles, alternatives are compared only on the basis of the set of attributes for which each alternative beats each reference level [START_REF] Rolland | Reference-based preferences aggregation procedures in multicriteria decision making[END_REF][START_REF] Bouyssou | Multiattribute preference models with reference points[END_REF]. In particular, there is no possible strict preference between two alternatives which belong to the same domain (same comparison with the reference levels). Hence it is not possible to represent the preferences of Ex. 2 with reference point methods.

• v(∅) = 0, v({1}) = v({2}) = 0.8, v({1, 2}) = 1,

Two aggregation models based on several reference levels

This section describes two models able to distinguish decision strategies depending on the position with respect to reference elements. The first one is an extension of the Choquet integral to cope with multiple levels (see Section 4.1).

The second one is a specialization of the GAI model that allows, by construction, separate decision strategies in each domain (see Section 4.2). We will show that these models are able to capture the preferences expressed in the motivating example.

The set of reference levels on attribute X i is denoted by

D i = {a 0 i , a 1 i , . . . , a pi i }, with a 0 i < • • • < a pi i . We set p = (p 1 , . . . , p n ).

p-ary capacity and the Choquet integral

The concept of a capacity is based on reference levels {0, 1} on each criterion.

It has been generalized to an arbitrary number of reference levels over each criterion. For p = (p 1 , . . . , p n ), we define

Q p (N ) = {0, . . . , p 1 } × • • • × {0, . . . , p n }, (12)
and ≤ on Q p (N ) by, for every q = (q 1 , . . . , q n ), q = (q 1 , . . . , q n ) ∈ Q p (N )

q ≤ q iff a qi i ≤ a q i i ∀i ∈ N. (13)
We may call Q p (N ) the grid of reference levels. A standard capacity is characterized by two reference elements a 0 i and a 1 i that are mapped onto 0 and 1 respectively, thanks to the utility function u i . Likewise, the p i + 1 reference elements a 0 i , a 1 i , . . . , a pi i are mapped onto values {0, 1, 2, . . . , p i } respectively, by We consider here the simplest utility function fulfilling this condition, that is making linear interpolations (see Figure 3):

u i : ∀i ∈ N ∀l ∈ {0, 1, 2, . . . , p i } u i (a l i ) = l. ( 14
)
u i a 0 i s 0 a 1 i s 1 a 2 i s 2 a 3 i s 3
u i (x i ) =          0 if x i ≤ a 0 i xi-a l i a l+1 i -a l i (l + 1) + a l+1 i -xi a l+1 i -a l i l = l + xi-a l i a l+1 i -a l i if a l i ≤ x i < a l+1 i p i if x i ≥ a pi i (15)
A more general form of u i satisfying ( 14) can be envisaged.

We can now define p-ary capacities, where a usual capacity is a (1, . . . , 1)-ary capacity.

Definition 2 ( [START_REF] Grabisch | Capacities on lattices and k-ary capacities[END_REF][START_REF] Grabisch | Bipolarization of posets and natural interpolation[END_REF]). A p-ary capacity on N is a function v : Q p (N ) → IR satisfying the monotonicity conditions:

∀q, q ∈ Q p (N ) s.t. q ≤ q , v(q) ≤ v(q ), (16)
and the normalization conditions: v(0, . . . ,

0) = 0, v(p 1 , . . . , p n ) = 1.
This definition is a slight generalization of that presented in [START_REF] Grabisch | Capacities on lattices and k-ary capacities[END_REF][START_REF] Grabisch | Bipolarization of posets and natural interpolation[END_REF] in the sense that

p 1 = p 2 = • • • = p n =: k in these references.
A p-ary capacity is said to be non-normalized if we relax the normalization condition v(p 1 , . . . , p n ) = 1. In the context of cooperative game theory, this concept is similar to multichoice games [START_REF] Hsiao | Shapley value for multichoice cooperative games[END_REF].

Let us define Q p (N ) = {q ∈ Q p (N ) : q i < p i ∀i ∈ N }. For q ∈ Q p (N ), let V q = [a q1 1 , a q1+1 1 ] × [a q2 2 , a q2+1 2 ] × • • • × [a qn n , a qn+1 n ].
Let x ∈ X. A p-ary capacity can be seen as a superposition of p 1 ×p 2 ו • •×p n capacities (over each domain V q for q ∈ Q p (N )) so that the Choquet integral with respect to v at x is simply the Choquet integral with respect to one of these capacities. One needs thus to identify the capacity associated to x. The latter is characterized by two successive reference levels on each attribute. We define q(x) ∈ Q p (N ) by

q i (x) =          0 if x i < a 1 i l if a l i ≤ x i < a l+1 i (l ∈ {1, . . . , p i -2}) p i -1 if x i ≥ a pi-1 i ( 17
)
for all i ∈ N . Then x is attached to domain V q(x) . The (non-normalized) capacity attached to x is µ q(x) associated to domain V q(x) , where, for q ∈ Q p (N )

and S ⊆ N , µ q (S) is defined by

µ q (S) = v((q + 1) S , q N \S ) -v(q), (18)
where ((q + 1) S , q N \S ) takes value q i + 1 if i ∈ S and value q i otherwise. We clearly have that u i (x i ) ∈ [q i (x), q i (x) + 1]. An illustration of q(x) can be found in Figures 4 and5.

X 1 X 2 a 0 1 a 1 1 a 2 1 a 3 1 a 0 2 a 1 2 a 2 2 (a q1(x) 1 , a q2(x) 2 ) x Figure 4: Point x belongs to the square [a 1 1 , a 2 1 ] × [a 0 2 , a 1 2 ]. Hence q 1 (x) = 1 and q 2 (x) = 0.
We define

∀i ∈ N φ i (x) = u i (x i ) -q i (x) ∈ [0, 1]. ( 19
)
Figure 5 illustrates the concepts of utilities and φ i in the criteria space (output of the utility functions).

Crit. 1

Crit. 2

0 1 2 3 0 1 (u 1 (x 1 ), u 2 (x 2 )) φ 1 (x) φ 2 (x) q(x)
Figure 5: Illustration of q(x), φ 1 (x) and φ 2 (x).

Remark 1. There is a clear connection between the previous definitions and some notions used in signal compression [START_REF] Conway | Sphere Packings, Lattices and Groups[END_REF][START_REF] Gersho | Vector Quantization and Signal Compression[END_REF]. In this theory, nearest neighbour quantizer of a point is the element of the lattice that is closest to this point. This is similar to q(x), which can be defined as the largest element of lattice Q p (N ) that is smaller than vector (u 1 (x 1 ), . . . , u n (x n )). The Voronoi cell of the lattice associated with q ∈ Q p (N ) is the set of points for which q(x) = q. In our case, the set of point x for which q(x) = q is the hypercube

× i∈N [a qi i , a qi+1 i ].
Lastly, the modulo-Q p (N ) operation w.r.t. the lattice is defined as the difference between the point and the associated nearest neighbour quantizer. We note that φ i (x) is the modulo-Q p (N ) operation w.r.t. the lattice of u i (x i ) (and could be denoted by u i (x i ) mod Q p (N )). The following table compares the concepts used in this paper and in signal compression.

Our definitions Counterpart in signal compression

Q p (N ) lattice q(x) nearest neighbour quantizer V (0,...,0)
basic Voronoi cell of the lattice

V q Voronoi cell associated to q φ i (x) modulo-Q p (N ) operation w.r.t.

the lattice

Then the Choquet integral w.r.t. v for alternative x is given by

U ∧ v (x) = C µ q(x) (φ(x)) + v(q(x)). (20)
Note that notation U ∧ v corresponds to the Lovász extension of v. The Choquet integral w.r.t. a p-ary capacity will be called later p-ary Choquet integral by abuse of language.

Let Ω q,τ = {t ∈ [q, q + 1]

N , t τ (1) -q τ (1) ≤ • • • ≤ t τ (n) -q τ (n) }. The Choquet integral w.r.t.
v is clearly a simple weighted sum in each domain Ω q,τ . In Figure 6, the shaded areas are the sets Ω q,τ for all values of q, with τ (2) = 1 and τ (1) = 2.

Crit. 1

Crit. 2 For x in V (0,0) : We have q 1 (x) = q 2 (x) = 0 and φ

i (x) = x i -a 0 i a 1 i -a 0 i . Then µ (0,0) (∅) = µ (0,0) ({1}) = µ (0,0) ({2}) = 0 and µ (0,0) ({1, 2}) = 0.1. Hence U ∧ v (x) = 0.1 φ 1 (x) ∧ φ 2 (x)
. This indeed corresponds to a veto (see Ex. 2). For x in V (1,1) : We have q 1 (x) = q 2 (x) = 1 and

φ i (x) = x i -a 1 i a 2 i -a 1 i . Then µ (1,1) (∅) = 0, µ (1,1) ({1}) = µ (1,1) ({2}) = 0.1 and µ (1,1) ({1, 2}) = 0.4. Hence U ∧ v (x) = 0.1 + 0.1 φ 1 (x) + 0.1 φ 2 (x) + 0.2 φ 1 (x) ∧ φ 2 (x)
. This corresponds to an intolerant behaviour (see Ex. 2).

For

x in V (2,2) : We have q 1 (x) = q 2 (x) = 2 and φ i (x) = x i -a 2 i a 3 i -a 2 i . Then µ (2,2) (∅) = 0, µ (2,2) ({1}) = 0.2, µ (2,2) ({2}) = 0.1 and µ (2,2) ({1, 2}) = 0.3. Hence U ∧ v (x) = 0.5 + 0.2 φ 1 (x) + 0.1 φ 2 (x)
. This corresponds to a complete compensation between the two attributes (see Ex. 2).

For x in V (3,3) : We have q 1 (x) = q 2 (x) = 3 and

φ i (x) = x i -a 3 i a 4 i -a 3 i . Then µ (3,3) (∅) = 0, µ (3,3) ({1}) = µ (3,3) ({2}) = 0.15 and µ (3,3) ({1, 2}) = 0.2. Hence U ∧ v (x) = 0.8 + 0.05 φ 1 (x) + 0.05 φ 2 (x) + 0.1 φ 1 (x) ∨ φ 2 (x)
. This corresponds to a tolerant behaviour (see Ex. 2).

Let us note that there is another extension of capacities -known as interval dependent (or more generally level dependent) capacities [START_REF] Greco | The Choquet integral with respect to a level dependent capacity[END_REF]. This concept is different from p-ary capacities [22, section 7]. An interval dependent capacity is composed of a partition of [0,1], in which each interval in the partition is assigned a capacity. The Choquet integral w.r.t. interval dependent capacities of a vector t ∈ [0, 1] n uses all capacities associated to levels between the smallest and the largest values of t. The Choquet integral w.r.t. interval dependent capacities satisfies cardinal tail independence [Greco, Matarazzo, Giove., 2011 -Theorem 1]. According to this property, the contribution of the l (for any l) best criteria of an alternative t is independent on the precise values of t on the other criteria (provided that they keep lower scores). In view of Example 2, consider an alternative t below the "must have" level on criterion 1, and above the "nice to have" levels on the other criteria. Hence, all the different capacities provided in Section 3.2 are used in the computation of the score of t, and thus criteria N \ {1} are aggregated using the capacities related to the "must have", "should have" and "nice to have" levels. As these last two capacities are tolerant, t gets a relatively large score, which is not what the DM wants. Hence the cardinal tail independence property prevents the level dependent capacities to satisfy the preferences in Ex. 2. By contrast, the different capacities that are used in a p-ary capacities are assigned to a specific area -namely some domain V q -so that the contribution of each capacity in the p-ary capacity v is clear.

GAI model

We have seen that the Choquet integral w.r.t. p-ary capacities can represent the motivating example. Let us see if the GAI model can also solve it. We need to specify, given the collection S, each utility u S . We treat the utility function u S for every subset S ∈ S separately. Utility u S is obtained from a learning process and thus through learning instances. The first idea is to make no assumption on u S and thus introduce an unknown u S (x S ) for every learning instance x. This is for instance the approach adopted in UTA GMS -INT [START_REF] Greco | Robust ordinal regression for value functions handling interacting criteria[END_REF]. The drawback of this method is that the number of unknowns depends on the number of values x S for all learning instances. This number can be quite large in some applications. Moreover, the problem is also how to make a recommendation on new alternatives y. Indeed, if y S is not equal to a value x S for a learning instance, then how to compute u S (y S )? This is why a robust preference relation is proposed in UTA GMS -INT [START_REF] Greco | Robust ordinal regression for value functions handling interacting criteria[END_REF].

If we consider the additive utility restriction, the most well-known method for learning it, is the UTA method. It consists in discretizing X i in a 0 i , . . . , a pi i . The unknowns are the utility at these points, and are denoted by u D i (a 0 i ), . . . , u D i (a pi i ). We set U Π := {u D S (y S ) : S ∈ S , y S ∈ D S }. The number of unknowns is equal to S∈S i∈S (p i + 1). In UTA, the value of u i for any x i is performed by affine interpolation, as for [START_REF] Grabisch | The application of fuzzy integrals in multicriteria decision making[END_REF]. Instead of a piecewise affine model, one could use a parametric model, for instance based on polynomial model [START_REF] Sobrie | Learning preferences with multiple-criteria models[END_REF][chapter 7] or multiple sigmoid functions [START_REF] Fallah Tehrani | Choquistic utilitaristic regression[END_REF]. The major difficulty is to extend these one-dimensional parametric models to subsets S of larger cardinality. For this reason, we prefer piecewise affine utility functions.

When S ∈ S contains more than one attribute, the idea is to perform a multi-linear interpolation (see [START_REF] Braziunas | Decision-theoretic elicitation of generalized additive utilities[END_REF]). Let us recall that D i = {a 0 i , a 1 i , . . . , a pi i } is 20 the set of levels, and D S = × i∈S D i . The following set

I = {i ∈ N : x i ∈ [a 0 i , a pi i ] and x i ∈ D i }
contains all attributes for which an interpolation is required. Given x i , we define

x i and x i by

x i = a qi i , x i = a qi+1 i if x i ∈ (a qi i , a qi+1 i ) x i = x i = x 0 i if x i ≤ a 0 i x i = x i = x pi i if x i ≥ a pi i x i = x i = x qi i if x i = a qi i Note that x i = x i iff i ∈ N \ I.
We wish to generalize the UTA approach and the multi-linear extension [START_REF] Braziunas | Decision-theoretic elicitation of generalized additive utilities[END_REF]. For this reason, u S will be denoted by u Π S . Function u Π S shall interpolate u D S :

u Π S (z S ) = u D S (z S ) ∀z S ∈ D S . (21)
Using multi-linear interpolation, we obtain for every

x S ∈ X S u Π S (x S ) = A⊆I∩S   i∈A x i -x i x i -x i × i∈(I∩S)\A x i -x i x i -x i × u D S (x A , x (I∩S)\A , x S\I )   (22)
where (x A , x (I∩S)\A , x S\I ) is an alternative that is equal to

x k if k ∈ A, to x k if k ∈ (I ∩ S) \ A, and to x k if k ∈ S \ I. The GAI model becomes U Π (x) = S∈S u Π S (x S ). (23)
Note that the choice of the multi-linear interpolation is motivated by the fact that it is a barycentric interpolation among all extreme points i∈I∩S {x i , x i }.

Moreover, this is the usual interpolation. Finally it satisfies the weak difference independence [START_REF] Dyer | Measurable multiattribute value functions[END_REF], which is a well-known property in MAUT [START_REF] Keeney | Decision with Multiple Objectives[END_REF]. This property implies that one can construct interval scales over each attribute independently of the remaining attributes. The scales over each attribute need not be commensurate as expression [START_REF] Greco | The Choquet integral with respect to a level dependent capacity[END_REF] uses only sums of products (there is no comparison of the values of attributes).

Example 4 (Ex. 2 cont.). Consider the p-ary capacity given in Example 4.

For x in V (0,0) : We have

φ i (x) = x i -a 0 i a 1 i -a 0 i and U Π v (x) = 0.1 φ 1 (x) × φ 2 (x)
. This indeed corresponds to a veto.

For x in V (1,1) : We have φ i (x) = x i -a 1 i a 2 i -a 1 i and U Π v (x) = 0.1 + 0.1 φ 1 (x) + 0.1 φ 2 (x) + 0.2 φ 1 (x) × φ 2 (x)
. This corresponds to an intolerant behaviour.

For x in V (2,2) : We have φ i (x) = x i -a 2 i a 3 i -a 2 i and U Π v (x) = 0.5 + 0.2 φ 1 (x) + 0.1 φ 2 (x)
. This corresponds to a complete compensation between the two attributes.

For x in V (3,3) : We have φ i (x) = x i -a 3 i a 4 i -a 3 i and U Π v (x) = 0.8 + 0.15 φ 1 (x) + 0.15 φ 2 (x) -0.1 φ 1 (x) × φ 2 (x)
. This corresponds to a tolerant behavior.

One can easily compare these expressions with those given in Example 3.

The only difference is a matter of extension -namely Lovász extension for U ∧ and multi-linear for U Π (see Section 2.2). This is also true between a 3 i and a 4 i , as

U ∧ v can be rewritten as U ∧ v (x) = 0.8 + 0.15 φ 1 (x) + 0.15 φ 2 (x) -0.1 φ 1 (x) ∧ φ 2 (x).

How to choose between the two aggregation models?

We have shown in Section 4 that the GAI model U Π and the Choquet integral U ∧ w.r.t. p-ary capacities are in fact very similar models, despite the apparent difference between their mathematical formulation. Both are based on a p-ary capacity and only differ from the interpolation used. As the Lovász extension requires appropriate normalization of the attributes, which is not the case of the multi-linear extension, the Choquet integral model requires utility functions.

This explains the differences of their formulation.

The question that arises is which model shall one choose in applications. We first analyse the properties that these two models have in common (Section 5.1).

Then we discuss on a specific property satisfied by the Choquet integral that might appear as a drawback in some situations (Section 5.2). Lastly we provide a comparison of the pros and cons of each of these two models (Section 5.3).

Properties of U ∧ and U Π

U ∧ and U Π have in common to provide the ability to define a different model in each domain V q . This allows to have different decision strategies in each area of X.

U ∧ and U Π have as unknown v and u D respectively. Formally these unknowns are linked by relation u D (x) = v(r(x)) for all x ∈ D, where r(x) = (r 1 (x 1 ), . . . , r n (x n ) with r i (x k i ) = k. Conversely, v(q) = u D (a q1 1 , . . . , a qn n ) for all q ∈ Q p (N ). It is thus equivalent to consider an interpolation of v or u D . For convenience, we will focus on u D . Let us show that U ∧ and U Π share similar properties as interpolation functions of v and u D .

General properties

This section describes important properties that the interpolation function shall satisfy. In order to comply with the GAI decomposability property, we are interested in interpolation operators I S for every non-empty S ⊆ N . Operator I S maps a function f D S : D S → IR to its interpolation f S : X S → IR. Let us give some wished properties.

The following property states that I S shall be an extension.

Interpolation. For all x ∈ D S , I S f D S (x) = f D S (x). We note that this is a generalization of the Properly Weighted property of the Choquet integral [START_REF] Marichal | An axiomatic approach of the discrete Choquet integral as a tool to aggregate interacting criteria[END_REF].

Continuity is an essential property of the interpolation.

Continuity. Function x → I S f D S (x) is continuous in X S .
We are interested in interpolating a utility model satisfying the GAI form [START_REF] Dyer | Measurable multiattribute value functions[END_REF]. We must thus perform two operations: interpolation and addition over the subsets in S. The next axiom says that whatever the order in which these two operations are done, the result shall be the same.

Stability of interpolation regarding additivity. For all x ∈ X,

S∈S I S f D S (x S ) = I N S∈S f D S (x).
Finally, we impose monotonicity.

Monotonicity. For any i ∈ S,

I S f D S is monotone in i∈N [a 0 i , a pi i ]
. These four properties are simple and appealing in applications. We now show that they are satisfied by the two models.

Satisfaction of these properties by the GAI model

The next lemma shows that the four properties are fulfilled by the multilinear expression [START_REF] Greco | The Choquet integral with respect to a level dependent capacity[END_REF]. Proof : Property Interpolation is clearly fulfilled by [START_REF] Grabisch | Aggregation functions[END_REF].

On the other hand, we have

I N S∈S u D S (x) = A⊆I   i∈A x i -x i x i -x i × i∈I\A x i -x i x i -x i × S∈S u D S (x A∩S , x (S∩I)\A , x S\I )   = S∈S A⊆I∩S   i∈A x i -x i x i -x i × i∈(S∩I)\A x i -x i x i -x i T S u D S (x A∩S , x (S∩I)\A , x S\I )  
where

T S = B⊆I\S i∈B x i -x i x i -x i × i∈I\(S∪B) x i -x i x i -x i = i∈I\S x i -x i x i -x i + x i -x i x i -x i = 1
Hence

I N S∈S u D S (x) = S∈S I S u D S (x S )
Hence Stability of interpolation regarding additivity is fulfilled.

To show the continuity, we only have to prove continuity w.r.t. an attribute, say k ∈ N . Let then x, x , x ∈ X such that

x i = x i = x i ∀i ∈ N \ {k} x k < x k = x k = x k < x k and x k ∈ D k Let S k and I = {i ∈ N : x i ∈ [a 0 i , a pi i ] and x i ∈ D i }. We have k ∈ I (as x k ∈ D k ) and u Π S (x S ) = A⊆I∩S   i∈A x i -x i x i -x i × i∈(I∩S)\A x i -x i x i -x i × x k -x k x k -x k × u D S (x A , x (I∩S)\A , x k , x S\(I∪k) )   + A⊆I∩S   i∈A x i -x i x i -x i × i∈(I∩S)\A x i -x i x i -x i × x k -x k x k -x k × u D S (x A , x k , x (I∩S)\A , x S\(I∪k) )   ----→ x k →x k A⊆I∩S   i∈A x i -x i x i -x i × i∈(I∩S)\A x i -x i x i -x i × u D S (x A , x (I∩S)\A , x S\I )   = u Π S (x S )
and

u Π S (x S ) = A⊆I∩S   i∈A x i -x i x i -x i × i∈(I∩S)\A x i -x i x i -x i × x k -x k x k -x k × u D S (x A , x (I∩S)\A , x k , x S\(I∪k) )   + A⊆I∩S   i∈A x i -x i x i -x i × i∈(I∩S)\A x i -x i x i -x i × x k -x k x k -x k × u D S (x A , x k , x (I∩S)\A , x S\(I∪k) )   -----→ x k →x k A⊆I∩S   i∈A x i -x i x i -x i × i∈(I∩S)\A x i -x i x i -x i × u D S (x A , x (I∩S)\A , x S\I )   = u Π S (x S )
Hence continuity is proved.

Finally, it is well-known that the multi-linear extension is monotone in

[0, 1] N . Hence U Π is monotone is monotone in each domain V q and thus in i∈N [a 0 i , a pi i ].

Satisfaction of these properties by the Choquet integral

We show some properties for the Choquet integral in this section.

(x) = v(r(x)), u D S (x S ) = v S (r(x S )), then U ∧ v (x) = S∈S U ∧ v S (x S )). Proof : Let us first show that U ∧ v satisfies Continuity. Let x ∈ X such that J := i ∈ N : x i ∈ D i \ {a 0 i , a pi i } = ∅. The Choquet integral is continuous. Hence U ∧ v is continuous in each domain V q .
We need to show that it is continuous across these domains.

Let q ∈ Q p (N ) such that x ∈ V q . For i ∈ N \ J, x i belongs to [a qi i , a qi+1 i ] and not to another interval. For i ∈ J, x i can belong to [a qi-1 i , a qi i ] or [a qi i , a qi+1 i ].
To show the continuity, we need to show that U ∧ v (x) does not depend on which interval

x i is associated to. Let S ⊆ J such that x i is associated to [a qi-1 i , a qi i ] (resp. [a qi i , a qi+1 i ]) for i ∈ S (resp. i ∈ J \ S). Then φ i (x i ) = 1 if i ∈ S, and
φ i (x i ) = 0 if i ∈ J \ S. The elements of N \ J are denoted by {π(1), . . . , π(f )}, where f = |N \ J| and 0 ≤ φ π(1) (x π(1) ) ≤ • • • ≤ φ π(f ) (x π(f ) ) ≤ 1. We set q ∈ Q p (N ) by q i = q i if i ∈ N \ S and q i = q i -1 if i ∈ S. Then x ∈ V q . Moreover U ∧ v (x) = v(q ) + C µ q (φ(x)) = v(q ) + f i=1 φ π(i) (x π(i)
) [µ q ({π(i), . . . , π(q)} ∪ S) -µ q ({π(i + 1), . . . , π(q)} ∪ S)] + µ q (S)

For A ⊆ N \ J and B ⊆ J, µ q (A ∪ B) = v((q + 1) A∪B , q N \(A∪B) ) -v(q ). Then

µ q (A ∪ S) = v((q + 1) A , q N \(J∪A) , ((q -1) + 1) S , q J\S ) -v(q ) = v((q + 1) A , q N \(J∪A) , q J ) -v(q ) We note that µ q (A ∪ S) is independent of S. Hence U ∧ v (x) is continuous.
Taking the previous expressions with x ∈ D, we obtain that

U ∧ v (a q1 1 , . . . , a qn n ) = v(q) = U D (a q1 1 , . . . , a qn n ) for every q ∈ Q p (N ). Hence U ∧ v satisfies Interpola- tion.
The Monotonicity property is satisfied. Indeed, the Choquet integral is known to be monotone, so that U ∧ is monotone in each domain V q . Moreover, monotonicity is ensured across the boundaries, as U ∧ is continuous (in particular around the boundaries of domains V q ). Consider finally axiom Stability of interpolation regarding additivity.

If u D (x) = S∈S u D S (x S ), and u D (x) = v(r(x)), u D S (x S ) = v S (r(x S )), then v(A) = S∈S v S (A ∩ S).
The result follows from the linearity of the Choquet integral with respect to the capacity.

Contamination effect of the Choquet integral

When the Choquet integral satisfies some properties in a given area of the space, then this property is usually also satisfied in a neighbourhood. This is what we call contamination effect. We show that this is not the case with the GAI model. We first describe this effect on the condition relative importance (section 5.2.1). Then we study more general decision strategies (section 5.2.2).

The contamination effect of the Choquet integral is important in practice, as it might forbid the DM to express very different decision strategies in two neighbour cells.

Case of conditional relative importance

Let us consider conditional relative importance [START_REF] Ch | The representation of conditional relative importance between criteria[END_REF] that is the baseline of most of motivations of the Choquet integral [START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid[END_REF][START_REF] Ch | Generalized Choquet-like aggregation functions for handling ratio scales[END_REF]. Given three criteria, with the first criterion being bipolar, the decision strategy is as follows: criterion 2 is more important than criterion 3 when criterion 1 is repulsive (below 0), and criterion 2 is less important than criterion 3 when criterion 1 is attractive (above the neutral level 0). Hence with

X 1 = [-1, 1] and X 2 = X 3 = [0, 1] ∀x 1 ∈ [-1, 0) ∀x 2 , x 3 ∈ [0, 1] ∂U ∂x 2 (x 1 , x 2 , x 3 ) > ∂U ∂x 3 (x 1 , x 2 , x 3 ) ( 24
)
∀x 1 ∈ (0, 1] ∀x 2 , x 3 ∈ [0, 1] ∂U ∂x 2 (x 1 , x 2 , x 3 ) < ∂U ∂x 3 (x 1 , x 2 , x 3 ) (25)
where the importance of criterion k at point x is measured by ∂U ∂x k (x) [START_REF] Ch | An axiomatization of the Choquet integral and its utility functions without any commensurability assumption[END_REF]. It has been shown that this cannot be strictly represented by the Choquet integral or its extensions (and even any piecewise affine functions) [START_REF] Ch | The representation of conditional relative importance between criteria[END_REF]. More precisely, if [START_REF] Hammer | On approximations of pseudo-Boolean functions[END_REF] is satisfied, then necessarily, we also have ∂U ∂x2 (x 1 , x 2 , x 3 ) > ∂U ∂x3 (x 1 , x 2 , x 3 ) whenever 0 ≤ x 1 ≤ min(x 2 , x 3 ) [START_REF] Ch | The representation of conditional relative importance between criteria[END_REF].

The next lemma shows that this decision strategy can easily be modelled by the GAI model with a multi-linear interpolation.

Lemma 3. We write U (x 1 , x 2 , x 3 ) = U 1,2 (x 1 , x 2 ) + U 1,3 (x 1 , x 3
). We assume 3 reference levels -1, 0, +1 on attribute 1, and two reference levels 0, 1 on the other attributes. Then the GAI model with multi-linear interpolation can simultaneously fulfil [START_REF] Hammer | On approximations of pseudo-Boolean functions[END_REF] and [START_REF] Hammer | Boolean Methods in Operations Research and Related Areas[END_REF].

Proof : We consider the unknowns u D 1,2 : {-1, 0, 1} × {0, 1} → IR of u 1,2 . If x 1 < 0, then, by (22) u 1,2 (x 1 , x 2 ) = u D 1,2 (-1, 0) × (-x 1 ) × (1 -x 2 ) + u D 1,2 (0, 0) × (x 1 + 1) × (1 -x 2 ) + u D 1,2 (-1, 1) × (-x 1 ) × x 2 + u D 1,2 (0, 1) × (x 1 + 1) × x 2 = u D 1,2 (0, 0) + x 1 u D 1,2 (0, 0) -u D 1,2 (-1, 0) + x 2 u D 1,2 (0, 1) -u D 1,2 (0, 0)
+ x 1 x 2 u D 1,2 (-1, 0) -u D 1,2 (0, 0) -u D 1,2 (-1, 1) + u D 1,2 (0, 1)
and thus

∂u 1,2 ∂x 2 (x 1 , x 2 ) = u D 1,2 (0, 1) -u D 1,2 (0, 0) + x 1 u D 1,2 (0, 1) -u D 1,2 (0, 0) + u D 1,2 (-1, 0) -u D 1,2 (-1, 1) . Now if x 1 > 0, then u 1,2 (x 1 , x 2 ) = u D 1,2 (0, 0) × (1 -x 1 ) × (1 -x 2 ) + u D 1,2 (1, 0) × x 1 × (1 -x 2 ) + u D 1,2 (0, 1) × (1 -x 1 ) × x 2 + u D 1,2 (1, 1) × x 1 × x 2 = u D 1,2 (0, 0) + x 1 u D 1,2 (1, 0) -u D 1,2 (0, 0) + x 2 u D 1,2 (0, 1) -u D 1,2 (0, 0) + x 1 x 2 u D 1,2 (0, 0) -u D 1,2 (1, 0) -u D 1,2 (0, 1) + u D 1,2 (1, 1)
and thus

∂u 1,2 ∂x 2 (x 1 , x 2 ) = u D 1,2 (0, 1) -u D 1,2 (0, 0) + x 1 u D 1,2 (0, 0) -u D 1,2 (1, 0) -u D 1,2 (0, 1) + u D 1,2 (1, 1) .
We consider the unknowns u D 1,3 : {-1, 0, 1} × {0, 1} → IR of u 1,3 . If x 1 < 0, then

∂u 1,3 ∂x 3 (x 1 , x 3 ) = u D 1,3 (0, 1) -u D 1,3 (0, 0) + x 1 u D 1,3 (0, 1) -u D 1,3 (0, 0) + u D 1,3 (-1, 0) -u D 1,3 (-1, 1) . Now if x 1 > 0, we obtain ∂u 1,3 ∂x 3 (x 1 , x 3 ) = u D 1,3 (0, 1) -u D 1,3 (0, 0) + x 1 u D 1,3 (0, 0) -u D 1,3 (1, 0) -u D 1,3 (0, 1) + u D 1,3 (1, 1) .
Condition [START_REF] Hammer | On approximations of pseudo-Boolean functions[END_REF] gives

∀x 1 ∈ [-1, 0) ∀x 2 , x 3 ∈ [0, 1] ∂u 1,2 ∂x 2 (x 1 , x 2 ) > ∂u 1,3 ∂x 3 (x 1 , x 3 ) ⇐⇒ ∀x 1 ∈ [-1, 0) (-x 1 ) u D 1,2 (-1, 1) -u D 1,2 (-1, 0) + (1 + x 1 ) u D 1,2 (0, 1) -u D 1,2 (0, 0) > (-x 1 ) u D 1,3 (-1, 1) -u D 1,3 (-1, 0) + (1 + x 1 ) u D 1,3 (0, 1) -u D 1,3 (0, 0) ⇐⇒ u D 1,2 (-1, 1) -u D 1,2 (-1, 0) > u D 1,3 (-1, 1) -u D 1,3 (-1, 0) and u D 1,2 (0, 1) -u D 1,2 (0, 0) ≥ u D 1,3 (0, 1) -u D 1,3 (0, 0)
Condition [START_REF] Hammer | Boolean Methods in Operations Research and Related Areas[END_REF] gives

∀x 1 ∈ (0, 1] ∀x 2 , x 3 ∈ [0, 1] ∂u 1,2 ∂x 2 (x 1 , x 2 ) < ∂u 1,3 ∂x 3 (x 1 , x 3 ) ⇐⇒ ∀x 1 ∈ (0, 1] (1 -x 1 ) u D 1,2 (0, 1) -u D 1,2 (0, 0) + x 1 u D 1,2 (1, 1) -u D 1,2 (1, 0) < (1 -x 1 ) u D 1,3 (0, 1) -u D 1,3 (0, 0) + x 1 u D 1,3 (1, 1) -u D 1,3 (1, 0) ⇐⇒ u D 1,2 (0, 1) -u D 1,2 (0, 0) ≤ u D 1,3 (0, 1) -u D 1,3 (0, 0) and u D 1,2 (1, 1) -u D 1,2 (1, 0) < u D 1,3 (1, 1) -u D 1,3 (1, 0)
Hence preferences [START_REF] Hammer | On approximations of pseudo-Boolean functions[END_REF] and ( 25) are equivalent to the following conditions

u D 1,2 (-1, 1) -u D 1,2 (-1, 0) > u D 1,3 (-1, 1) -u D 1,3 (-1, 0) (26)
u D 1,2 (0, 1) -u D 1,2 (0, 0) = u D 1,3 (0, 1) -u D 1,3 (0, 0) (27)
u D 1,2 (1, 1) -u D 1,2 (1, 0) < u D 1,3 (1, 1) -u D 1,3 (1, 0) (28)
These constraints are not conflicting so that the GAI model with multi-linear interpolation can fulfill [START_REF] Hammer | On approximations of pseudo-Boolean functions[END_REF] and (25).

A more general situation

For the sake of simplicity, we assume that a k i = k for every level k.

Lemma 4. For a given q ∈ Q p (N ) with q i < p i for every i ∈ N , and j ∈ N , we have

∂U ∧ ∂x j (x) = v(q j + 1, q N \j ) -v(q) (29)
for every x ∈ IR N such that q(x) (see [START_REF] Grabisch | Bi-capacities -II : the Choquet integral[END_REF]) has the form (q S -1, q N \S ) for some S ⊆ N \ j, and φ k (x k ) ≤ φ j (x j ) ≤ φ i (x i ) (see [START_REF] Grabisch | A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid[END_REF]) for all i ∈ S and

k ∈ N \ (S ∪ j).
This lemma shows that the same weight v(q j + 1, q N \j ) -v(q) of criterion j can be obtained from all cells C = [r, r + 1] with r = (q S -1, q N \S ) and S ⊆ N \ j .

This is contamination as if the relative importance of criterion j is fixed in one of these cells, then the relative importance of criterion j necessarily takes the same value for all other cells in C. This contamination phenomenon is very important in practice. It can be expected in some applications as it ensures some kind of smoothness of the decision strategies across the cells. In other applications, it can be undesirable as it forbids representing very different decision strategies in neighbour cells.

Proof : We have

∂U ∧ ∂x j (x) = ∂u j (x j ) ∂x j × µ q(x) ({j, π(k + 1), . . . , π(n)}) -µ q(x) ({π(k + 1), . . . , π(n)}) where φ π(1) (x π(1) ) ≤ • • • ≤ φ π(n) (x π(n) ) and π(k) = j. As a k i = k for all k, then ∂uj (xj ) ∂xj = 1.
Let S ⊆ N \ j. Assume that q(x) = (q S -1, q N \S ) and

φ k (x k ) ≤ φ j (x j ) ≤ φ i (x i ) for all i ∈ S and k ∈ N \ (S ∪ j). Then ∂U ∧ ∂x j (x) = µ q(x) (S ∪ {j}) -µ q(x) (S)
= v(q S , q j + 1, q N \(S∪{j}) ) -v(q S , q N \(S) )

= v(q j + 1, q N \j ) -v(q)

The previous contamination phenomenon does not occur the GAI model as the multi-linear extension interpolates with non-zero coefficients among all vertices of the cell [q(x), q(x) + 1].

Synthesis: pros and cons of the two models

We have seen that the two models satisfied the four basic properties (Interpolation, Continuity, Monotonicity and Stability of interpolation regarding additivity). Moreover, unlike the GAI model, the Choquet integral satisfies a contamination property: some decision strategies fulfilled by the Choquet integral in a cell are necessarily fulfilled also in some neighbour cells. This property comes from the parsimonious interpolation used in the Lovász extension.

To continue the comparison between these two models, we propose the following table presenting the assets and disadvantages of these models.

Advantages of U Π Advantages of U ∧

• No separation between utilities and weights. Hence the model is linear in its parameters and is thus easier to learn (same as UTA).

• no "contamination" for GAI (see Section 5.2) • Separation between utilities and weights. Hence it is complex to learn all parameters of the model at the same time.

•
• The "contamination" phenomenon is unavoidable (see Section 5.2)

• Commensurability across the criteria is required, which can be complex to obtain 6. How to elicit the two models?

This section addresses the elicitation of the previous models, which is very important in practice. We have seen in Section 5.1 that the parameters of a GAI model can be put in the form of a p-ary capacity. Hence in order to address the elicitation of the two models that are considered in this paper, it is sufficient to consider the elicitation of a p-ary capacity.

Elicitation by linear programming

A capacity contains 2 n parameters, whose elicitation requires a significant amount of preference information. In order to reduce the elicitation burden, some sub-models of capacities have been defined. One can mention the 2additive capacities using n(n+1) 2 parameters. These models are identified using Linear Programming (LP) in which the variables are the parameters of the (2-additive) capacity, the constraints are the monotonicity conditions and the fulfilment of the preference information of the DM (e.g. some comparisons of options), and the objective function aims for instance at maximizing the entropy of the capacity [START_REF] Kojadinovic | Estimation of the weights of interacting criteria from the set of profiles by means of information-theoretic functionals[END_REF].

One could think of directly extending this approach to p-ary capacities, which are defined by i∈N (p i + 1) parameters. However, the DM cannot reasonably provide enough preference information in order to identify this model, and one has to find suitable submodels. A two-additive p-ary capacity is a p-ary capacity of the form:

v(q) = {i,j}∈S2 v i,j (q i , q j ) + i∈N v i (q i ), (30)
where S 2 is a subset of the set of pairs in N , v i,j depends only on criteria i and j, and v i depends only on criterion i. It contains thus {i,j}∈S2 (p i + 1) × (p j + 1) + i∈N (p i + 1) parameters. It has been shown in this case that the number of monotonicity conditions on v can be reduced from an exponential number to a quadratic number, as it is sufficient to enforce monotonicity conditions on terms v i and v i,j with no restriction on modelling power of v [START_REF] Grabisch | Monotone decomposition of 2-additive generalized additive independence models[END_REF].

The elicitation of a two-additive p-ary capacity using LP has been described in [START_REF] Greco | Robust ordinal regression for value functions handling interacting criteria[END_REF] for a utility model which has strong connections with the GAI model, and also in [START_REF] Ch | Use of the GAI model in multi-criteria decision making: inconsistency handling, interpretation[END_REF]. In this LP, the unknowns are the parameters of the p-ary capacity, and the constraints are the monotonicity conditions and the fulfilment of the preference information given by the DM. In [START_REF] Greco | Robust ordinal regression for value functions handling interacting criteria[END_REF][START_REF] Ch | Use of the GAI model in multi-criteria decision making: inconsistency handling, interpretation[END_REF], a Mixed Integer LP is used in order to find the p-ary capacity of the form [START_REF] Kojadinovic | Estimation of the weights of interacting criteria from the set of profiles by means of information-theoretic functionals[END_REF], satisfying the previous constraints, and minimizing the number of terms in S 2 .

Elicitation by expert knowledge

We propose here a more parsimonious approach, where some domain expertise brought by the DM allows the analyst to save some elicitation time. This expertise concerns the decision strategies related to the various reference levels and their relationship.

We assume for simplicity that we have the same number of levels for all attributes: p 1 = p 2 = • • • = p n =: k. Moreover, levels a l 1 , a l 2 , . . . , a l n (for any l ∈ {0, 1, . . . , k}) are supposed to have the same semantics and thus to be Let us fix q = (q 1 , . . . , q n ) ∈ Q q (N ). The basic idea is that the decision strategy in domain V q is inherited from the decision strategy in domain on the diagonal associated to the worst level of q, namely V q , where q = (h, . . . , h), and h = min(q 1 , . . . , q n ). This induces a decision behaviour focused on the worst levels, which seems to be natural in most applications. In Example 2, when assessing an alternative x, the architect looks firstly at whether x is above all "must have" thresholds, secondly at whether x is above the "should have" thresholds, and lastly at whether some "nice to have" requirements are met. For instance, fulfilling a "nice to have" requirement cannot compensate being below "must have" on another attribute.

In order to define the p-ary capacity for the points in V q , we first give the expression of U ∧ v (x) for x ∈ V q , and then extend this formula to points in V q . By (20), the overall score of an alternative x ∈ V q is given by

U ∧ v (x) = C µq (φ(x))+v(q) = C ν h (u 1 (x 1 )-h, . . . , u n (x n )-h)+w(a h ), (33)
as µ q = ν h . In order to extend the right hand side of (33) to x ∈ V q , one may directly use this formula with x ∈ V q . However, u i (x i ) -h is equal to 0 at x i = a h i , to 1 at a h+1 i , to 2 at a h+2 i , . . ., to q i -h at a qi i , . . . These values are somewhat arbitrary. As a matter of fact, utility values 0, 1, . . . , k in u i (see [START_REF] Grabisch | The application of fuzzy integrals in multicriteria decision making[END_REF]) have no precise numerical meaning, and shall be seen only as successive labels. Instead, we replace u i by a utility function derived from w, as w represents the DM preferences regarding the difference of satisfaction between the different levels. It is defined by

w i (x i ) =          w(a 0 ) if x i ≤ a 0 i w(a l ) + (w(a l+1 ) -w(a l )) xi-a l i a l+1 i -a l i if a l i ≤ x i ≤ a l+1 i w(a k ) if x i ≥ a k i so that w i (a l i ) = w(a l ) for every l ∈ {0, . . . , k}. As u i (x i )-h = wi(xi)-w(a h ) w(a h+1 )-w(a h ) for x i ∈ [a h i , a h+1 i ], we have U ∧ v (x) = C ν h w 1 (x 1 ) -w(a h ) w(a h+1 ) -w(a h ) , . . . , w n (x n ) -w(a h ) w(a h+1 ) -w(a h ) + w(a h ) (34)
for every x ∈ V q . This formula will be used for x ∈ V q . Hence the value of the p-capacity at q is given by: v(q) = C ν h w 1 (q 1 ) -w(a h ) w(a h+1 ) -w(a h ) , . . . , w n (q n ) -w(a h ) w(a h+1 ) -w(a h ) + w(a h ). ( 35)

Example 5 (Ex. 2 continued). Figure 7 gives the expression of U ∧ v for the four decision strategies. Between levels a 0 and a 1 , the overall utility is given by z 1 ∧ z 2 (for z 1 , z 2 ∈ [0, 0.1]). This expression is used to derive v(l, 0) = 0 and v(0, l) = 0 (for l ∈ {2, 3, 4}). Between levels a 1 and a 2 , the overall utility is given by z1+z2 4 + z1∧z2 2 (for z 1 , z 2 ∈ [0.1, 0.5]). This expression is used to derive v(l, 1) and v(1, l) (for l ∈ {3, 4}). For instance v(1, 3) = 0.3 is obtained by applying the previous expression with z 1 = 0.1 and z 2 = 0.9. Between levels a 2 and a 3 , the overall utility is given by 0.375 z 1 + 0.625 z 2 (for z 1 , z 2 ∈ [0.5, 0.9]). This expression is used to derive v(4, 2) and v(2, 4). For instance v(4, 2) = 0.8125 is obtained by applying the previous expression with z 1 = 0.5 and z 2 = 1. All values of v are given in Figure 8. (that is stability of the interpolation with respect to an additive decomposability property of the overall utility). These properties are satisfied by the two models. A major difference between these models is related to the contamination property: If the Choquet integral satisfies some decision strategies in a cell, then this strongly sets constraints on some neighbour cells. This is not the case with the GAI model. Finally, we have described two approaches to elicit the models at stake. The first one relies on Linear Programming, which is the standard approach in OR.

The second one consists first in identifying the decision strategies between any two successive levels, and then extending these strategies for profiles having diverse values on the attributes using a pessimistic principle: a profile inherits from the decision strategy corresponding to the worst level in the profile. The latter elicitation approach can be used in real applications as the elicitation workload is kept to a reasonable amount. Formula U ∧ v (x) = Cν h (u 1 (x 1 )h, . . . , un(xn)-h)+w(a h ) is written in two different ways. In the first one, we use new variables y i := u i (x i ) -h. Then U ∧ v (x) is equal to U L (y) := Cν h (y) + w(a h ) (where L refers to the fact that variables y are Local to domain Vq). The second expression is based on [START_REF] Ch | Generalized Choquet-like aggregation functions for handling ratio scales[END_REF]. With the new variables z i = w i (x i ), ( 34) is equal to U G (z) := Cν h z 1 -w(a h ) w(a h+1 )-w(a h ) , . . . , zn-w(a h ) w(a h+1 )-w(a h ) + w(a h ) (where G stands for Global). The figure presents the two expressions U L (y) and U G (z) for the four capacities. They are presented at the four diagonal blocs.

Figure 2 :

 2 Figure 2: Decision strategies in Example 2.

Figure 3 :

 3 Figure 3: Piecewise affine utility function u i with p i = 3.

Figure 6 :Example 3 .

 63 Figure 6: Example with k = 3. The shaded triangles represent the areas where φ 1 (x) ≥ φ 2 (x).

Lemma 1 .

 1 The multi-linear extension satisfies Interpolation, Continuity, Stability of interpolation regarding additivity and monotonicity.

Lemma 2 .

 2 U ∧ v satisfies Interpolation, Continuity, Monotonicity and Stability of interpolation regarding additivity (If u D (x) = S∈S u D S (x S ), and u D

21 ]

 21 no commensurability requirement among the partial utilities u S • interpretability of model: the separation between utilities and weights allows us to better interpret the model and thus explain a decision • the Choquet integral is the most parsimonious interpolation method in the sense that it uses only n + 1 point in ndimension [Disadvantages of U Π Disadvantages of U ∧ • Needs to have bounded attributes (otherwise, multilinear extension is nonmonotone)

  This paper considers MCDA situations in which the decision strategies are conditional on the position of the values of the alternative on the attributes comparatively to several reference levels. Two examples of such situations have been given. Standard MCDA approaches cannot handle these cases. We have seen that the Choquet w.r.t. a p-ary capacity and a specialization of the GAI model, which is discretized to fit with the presence of reference levels, can fulfil these examples. The latter model can be seen as an extension of the UTA approach. A convenient representation of the unknowns of these two models is given by a function u D defined on the Cartesian product D of the reference levels over all attributes. The overall model is then obtained as an interpolation of this function u D . Four basic properties have been defined on this interpolation: Interpolation (the overall utility shall be identical to u D on D), Continuity, Monotonicity and Stability of interpolation regarding additivity

1 U L = 0.1 y 1 ∧ y 2 U G = z 1 ∧ z 2 U 2 U G = z 1 +z 2 4 + z 1 ∧z 2 2 U

 122242 L = 0.1 + 0.1 (y 1 + y 2 ) + 0.2 y 1 ∧ y L = 0.5 + 0.15 y 1 + 0.25 y 2 U G = 0.375 z 1 + 0.625 z 2 U L = 0.9 + 0.02 (y 1 + y 2 ) + 0.06 y 1 ∨ y 2 U G = 0.2 (z 1 + z 2 ) + 0.6 z 1 ∨ z 2

Figure 7 :

 7 Figure 7: Expression of the overall utility in Example 2. Formula U ∧v (x) = Cν h (u 1 (x 1 )h, . . . , un(xn)-h)+w(a h ) is written in two different ways. In the first one, we use new variables

  2) = 0.2 v(2, 2) = 0.5 v(3, 2) = 0.65 v(4, 2) = 0.6875 v(0, 3) = 0 v(1, 3) = 0.3 v(2, 3) = 0.75 v(3, 3) = 0.9 v(4, 3) = 0.98 v(0, 4) = 0 v(1, 4) = 0.325 v(2, 4) = 0.8125 v(3, 4) = 0.98 v(4, 4) = 1

Figure 8 :

 8 Figure 8: Value of the p-ary capacity in Example 2. The black balls correspond to the values of v that are directly given by ν 0 , ν 1 , ν 2 , ν 3 . The other values of v (gray balls) are obtained by (35).

  Figure 1: Set of vectors t = (t 1 , t 2 ) such that t 1 ≥ t 2 .

	Crit. 2
	1
	0	Crit. 1
	0	1
		, the
	shaded area represents Ω τ with n = 2, τ (1) = 2 and τ (2) = 1. The Choquet
	integral is one of the most versatile aggregation function as it is able to capture
	various decision strategies representing interaction among criteria [8, 15, 19].

The importance of a criterion is the difference of utility going from the lower reference level to the upper one on an attribute, the other attributes being fixed to any value.

See MoSCoW method for setting priorities among requirements, among "Must have" (critical to the delivery), "Should have" (important but not necessary for delivery), "Could have" (desirable but not necessary), "Won't have/Would like" (not included in the current delivery.

commensurate, as in Example 2. We denote by a 0 , a 2 , . . . , a k the k + 1 semantic levels. They are ordered from the lowest one a 0 to the best one a k . We suppose that the k + 1 reference levels delimit k different decision strategies, namely between a 0 and a 1 , between a 1 and a 2 , etc.

In order to elicit the p-ary capacity v, we proceed in three steps:

• Elicitation of the p-ary capacity on the diagonal : We construct a utility function w on the k + 1 semantic levels {a 0 , a 2 , . . . , a k }, with the normalization w(a 0 ) = 0 and w(a k ) = 1. This can be done for instance with the help of the MACBETH approach [START_REF] Bana E Costa | MACBETH[END_REF]. Due to the commensurability assumption among levels a l 1 , a l 2 , . . . , a l n , and the idempotency property, alternative (a l 1 , a l 2 , . . . , a l n ) has the same level w(a l ) on all attributes and thus w(a l ) should be its overall evaluation. Hence for every l ∈ {0, . . . , k}

• Elicitation of the p-ary capacity around the diagonal : For each l ∈ {0, 1, . . . , k -1}, we construct the decision strategy of the DM when all criteria take value between a l and a l+1 , i.e., inside domain V (l,...,l) . It is represented by a non-normalized capacity ν l : 2 n → IR (which can be 2-additive) such that ν l (∅) = 0 and ν l (N ) = w(a l+1 ) -w(a l ), the latter condition ensuring that (31) holds. This capacity can be constructed by standard capacity elicitation techniques, and permits to determine the p-ary capacity on V (l,...,l) :

Observe that (31) holds.

• Implicit determination of the p-ary capacity outside the diagonal:

Formula (32) specifies v at points ((l+1) S , l N \S ), l ∈ {0, 1, . . . , k-1}, S ⊆ N (i.e., around the diagonal). It remains to fix v for the other points.

We propose to do so without asking any further information from the DM, in order to reduce the elicitation burden.