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

Christophe Labreuche
email: christophe.labreuche@thalesgroup.com

Monotone decomposition of 2-additive Generalized Additive Independence models

Keywords: conjoint measurement, multicriteria decision making, capacity, generalized additive independence, multichoice game

The GAI (Generalized Additive Independence) model proposed by Fishburn is a generalization of the additive value function model, which need not satisfy preferential independence. Its great generality makes however its application and study difficult. We consider a significant subclass of GAI models, namely the discrete 2-additive GAI models, and provide for this class a decomposition into nonnegative monotone terms. This decomposition allows a reduction from exponential to quadratic complexity in any optimization problem involving discrete 2-additive models, making them usable in practice.

Introduction

Conjoint measurement provides an adequate and widely studied framework for the representation of preferences in decision making with multiple objectives or criteria (see, e.g., the monograph of [START_REF] Krantz | Foundations of measurement[END_REF], as well as the survey paper by [START_REF] Bouyssou | Conjoint measurement tools for MCDM[END_REF], containing many references). The most representative model in conjoint measurement is the additive value function model U(x) = i u i (x i ), whose characteristic property is (preferential) independence, stipulating that the preference among two alternatives should not depend on the attributes where the two alternatives agree.

However, it is well known that in real situations, preferential independence could be easily violated, because of the possible interaction between objective/criteria. Referring to the example of evaluation of students in [START_REF] Grabisch | The application of fuzzy integrals in multicriteria decision making[END_REF] where students are evaluated on three subjects like mathematics, physics and language skills, the preference The aim of this paper is to provide a first step in making GAI models usable in practice, by proving a fundamental result on decomposition, in a subclass of GAI models which is significant for applications. Specifically, we are interested in GAI models where, first, the collection S is made only of singletons and pairs, thus limiting the model to a sum of univariate or bivariate terms, and second, the attributes take discrete values. We call this particular class 2-additive discrete GAI models. In addition, we assume that weak independence holds.

The main result of this paper shows that for a given 2-additive GAI model that fulfills weak independence, it is always possible to obtain a decomposition into nonnegative monotone nondecreasing terms. The result is proved by using an equivalence between 2-additive discrete GAI models and 2-additive k-ary capacities, and amounts to finding the set of extreme points of the polytope of 2-additive k-ary capacities. Going back to the first difficulty mentioned earlier, using this decomposition provides a semantics to the value functions u S as they have the same monotonicity as the overall value function U. Secondly, thanks to this result, it is possible to replace the monotonicity conditions on U by monotonicity conditions on each term u S , which reduces the number of monotonicity constraints from exponential to quadratic complexity. This is of extreme importance in practice.

As a final remark on the aim and scope of the paper, we would like to emphasize that, despite all the apparatus on conjoint measurement and decision theory which is used, our aim is by no means an axiomatization of the 2-additive GAI model, based on properties of the preference relation . Rather, we place ourselves in a more practical point of view, where we suppose to have some partial knowledge of , and try to find a value function U of the 2-additive GAI type, which best represents the available pieces of preference, by solving an optimization problem. This is referred to as the learning approach. Our main result ensures that the optimization problem will have a polynomial size and that the resulting function U will be easily interpretable.

The paper is organized as follows. Section 2 introduces the necessary concepts and notation in conjoint measurement and GAI models, as well as the decomposition problem. Section 3 introduces discrete p-additive GAI models, and shows the equivalence with p-additive k-ary capacities. Section 4 explains the complexity problem behind the identification of 2-additive discrete GAI models, and proves that a decomposition into nonnegative monotone nondecreasing terms is always possible, which constitutes the main result of the paper.

Background

Multicriteria decision making and conjoint measurement

(we refer the reader to, e.g., [START_REF] Bouyssou | Conjoint measurement tools for MCDM[END_REF] for a detailed introduction to the topic) We consider objects or alternatives described by several attributes, and represent them as vectors x = (x 1 , . . . , x n ), where x i is the value of the ith attribute for x, i = 1, . . . , n. We denote by X i the set of all possible values taken by attribute i, i = 1, . . . , n. The set of all potential alternatives is X = X 1 × • • • × X n , considering all possible combinations of the values of the attributes. We set N = {1, . . . , n} the index set of attributes, and suppose throughout the paper that n ≥ 2. We denote by (x A , y -A ) ∈ X the compound alternative taking value x i if i ∈ A and value y i otherwise. Accordingly, we introduce X A = × i∈A X i and X -A = × i ∈A X i .

We assume that the decision maker has a preference on the alternatives, represented by a complete preorder (reflexive and transitive binary relation) on X. Ordinal measurement amounts to finding a numerical function U : X → R representing the preference in the following sense:

x y ⇔ U(x) ≥ U(y).

U is called a value function. A classical situation in multicriteria decision making is when the value function can be put into an additive form:

U(x) = n i=1 u i (x i ) (1)
where u i : X i → R are the marginal value functions on each attribute. It is well known that a necessary condition for the additive model to hold is that satisfies an independence property, defined as follows. For any ∅ = I ⊂ N, we say that is (preferentially) independent for I if for every x, y, z, t ∈ X,

(x I , z -I ) (y I , z -I ) ⇔ (x I , t -I ) (y I , t -I ).
If is independent for any ∅ = I ⊂ N, then we say that is (preferentially) independent. Under this condition plus some other simple technical conditions, the preference relation can be represented by an additive value function, unique up to a positive affine transformation.

As we explained in the introduction, preferential independence is quite a strong condition which is not always met in practice. A much weaker condition is weak independence where for all i ∈ N, all x i , y i ∈ X i and all z -i , t -i ∈ X -i

(x i , z -i ) (y i , z -i ) ⇐⇒ (x i , t -i ) (y i , t -i ) (
x i is at least as good as y i ceteris paribus).

Let us define for any ∅ = I ⊆ N the following binary relation on X I :

x I I y I iff (x I , z -I ) (y I , z -I ) ∀z -I ∈ X -I .
Denoting {i} simply by i , it is well known and easy to check that if satisfies weak independence, then i is a complete preorder on X i , and moreover, monotonicity holds in the following sense: for all x, y ∈ X,

x i i y i ∀i ∈ N ⇒ x y.
(2)

Generalized Additive Independence (GAI) model

Weak independence is too weak to ensure that the additive value function model holds. Therefore, more general models have to be sought. A natural generalization of the additive model is to allow the marginal value functions to depend on several attributes:

U(x) = S∈S u S (x S ) (x ∈ X), (3)
where S ⊆ 2 N \ {∅}. This is called the Generalized Additive Independence (GAI) model. Note that S, S ′ ∈ S are not necessarily disjoint, so that some overlaps may exist between the terms of the sum. The additive value function model is a particular case of the GAI model when S is composed of singletons only.

It seems that the first occurrence of this model is due to Fishburn [START_REF] Fishburn | Interdependence and additivity in multivariate, unidimensional expected utility theory[END_REF], who introduced it in the context of expected utility. Fishburn characterized it by a condition stating that if two probability distributions P and Q over the alternatives X have the same marginals over every S ∈ S, then the expected utility of P and Q are equal. Another pioneering work is [START_REF] Bacchus | Graphical models for preference and utility[END_REF].

Unlike the additive value function model, the GAI model does not necessarily satisfy weak independence. In the Artificial Intelligence community, researchers are interested in the representation of preferences that may violate weak independence. A well-known example of such a preference is the following: consider two attributes X 1 , X 2 where X 1 pertains on the type of wine and X 2 to the type of main course in a restaurant. Then usually, one prefers 'red wine' to 'white wine' if the main course is 'meat', but 'white wine' is preferred to 'red wine' if the main course is 'fish' (the preference over attribute 'wine' is conditional on the value on attribute 'main course') [START_REF] Boutilier | UCP-networks: A directed graphical representation of conditional utilities[END_REF].

In multicriteria decision theory, it is often argued that such occurrences of preference relations which do not satisfy weak indepedence are in fact due to a poor modelling of the attributes. In the above example, weak independence can be restored by introducing a new attribute called "accordance of the main course with the wine". For this reason, following the traditional view of decision theory, we assume in this work that weak independence holds.

An important consequence of weak independence is that monotonicity holds for (see (2)), and consequently for U too:

x i i y i ∀i ∈ N ⇒ U(x) ≥ U(y) (4)

The decomposition issue

It is well known that in decision making, numerical models representing a preference relation are not unique. Often, like for the additive model, they are unique up to a positive affine transformation. This being taken for granted, GAI models have an additional difficulty: supposing the numerical representation U to be fixed, there is in general no unique way to express it mathematically. Let us consider for example the following (fixed) GAI model in two variables:

U(x 1 , x 2 ) = 2x 1 + x 2 -min(x 1 , x 2 ). (5)
U is formed of three terms, the first two being increasing while the third one is decreasing. By using the relation max(x 1 , x 2 ) + min(x 1 , x 2 ) = x 1 + x 2 , an equivalent expression is

U(x 1 , x 2 ) = x 1 + max(x 1 , x 2 ). ( 6
)
Observe that now the expression has only two terms, both of them being nondecreasing.

Clearly, the latter expression is better because it has fewer terms and the contribution for U of each of them is better understood as both terms are nonnegative and nondecreasing.

This rises the question of the decomposition of a GAI model U(x). Is it possible to relate all decompositions? Is there any "canonical" decomposition in some sense? Is it possible to always find a decomposition into nondecreasing terms? The two first questions have already found an answer in the literature. As for the third question, we will show in Section 4.1 that in practical situations where the model has to be determined from data, this question is crucial.

As for the first question, [START_REF] Fishburn | Interdependence and additivity in multivariate, unidimensional expected utility theory[END_REF] has shown that any two equivalent decompositions U(x) = S∈S u S (x S ) = S∈S u ′ S (x S ) are related as follows: (Braziunas, 2012, page 87). Moreover, even if U satisfies weak independence, it might be the case that u S does not fulfill this condition, or satisfies it but does not have the same monotonicity as U. Hence there is no well-defined semantics of the value functions u S , contrarily to what is claimed in (Braziunas, 2012, section 3.2.1.4).

u ′ S (x S ) = u S (x S ) + S ′ ∈S\{S}, S∩S ′ =∅ f S,S ′ (x S∩S ′ ) + c S where f S,S ′ : X S∩S ′ → R, and S∈S S ′ ∈S\{S}, S∩S ′ =∅ f S,S ′ (x S∩S ′ ) + c S = 0. Due to the presence of functions f S,S ′ , we do not have u S (x S ) ≥ u S (y S ) iff u ′ S (x S ) ≥ u ′ S (y S ), for any two x S , y S ∈ X S
As for the question of a canonical decomposition, Braziunas has proposed a decomposition based on the Fishburn representation. Fixing an order on S, say, S = {S 1 , . . . , S p }, the overall value function reads U(x) = S∈S u C S (x S ) with, for every j ∈ {1, . . . , p}

u C S j (x S j ) = U(x[S j ]) + K⊆{1,...,j-1} , K =∅ (-1) |K| U (x [∩ k∈K S k ∩ S j ]) (7)
where • C stands for "canonical", O ∈ X is any element in X seen as an anchor, and (Braziunas, 2012, page 94)). Note that the expression depends on the chosen ordering of the elements of S. The two equivalent decompositions ( 5) and ( 6) were obtained with a particularly simple example. The previous remark provides a more systematic way to derive several equivalent decompositions of GAI models, as illustrated in the next example.

x[S] ∈ X defined by (x[S]) i = x i if i ∈ S and (x[S]) i = O i otherwise
Example 1. Consider the following function

U(x 1 , x 2 , x 3 ) = x 2 + x 1 x 3 + max(x 1 , x 2 ). We have S = {S 1 , S 2 , S 3 } with S 1 = {2}, S 2 = {1, 3} and S 3 = {1, 2}.
Then the canonical decomposition gives, with O = (0, 0, 0):

u C S 1 (x 2 ) = U(x[S 1 ]) = U(O 1 , x 2 , O 3 ) = 2 x 2 u C S 2 (x 1 , x 3 ) = U(x[S 2 ]) -U(x[S 1 ∩ S 2 ]) = U(x 1 , O 2 , x 3 ) -U(O) = x 1 (x 3 + 1) u C S 3 (x 1 , x 2 ) = U(x[S 3 ]) -U(x[S 1 ∩ S 3 ]) -U(x[S 2 ∩ S 3 ]) + U(x[S 1 ∩ S 2 ∩ S 3 ]) = U(x 1 , x 2 , O 3 ) -U(O 1 , x 2 , O 3 ) -U(x 1 , O 2 , O 3 ) + U(O) = max(x 1 , x 2 ) -x 1 -x 2 = -min(x 1 , x 2 )
We note that U is nondecreasing in all variables, even though, for the canonical decomposition, u C S 3 is nonincreasing in its two coordinates. Let us take now the order

S ′ 1 = {1, 2}, S ′ 2 = {1, 3} and S ′ 3 = {2}. We obtain u C S ′ 1 (x 1 , x 2 ) = x 2 + max(x 1 , x 2 ), u C S ′ 2 (x 1 , x 3 ) = x 1 x 3 and u C S ′ 3 (x 2 ) = 0.
All terms are now nonnegative and monotone.

The previous example shows that the canonical decomposition does not guarantee to have only nondecreasing terms in the decomposition, and therefore does not solve the third question. Hence the question of finding a decomposition into nondecreasing terms (which we call hereafter a monotone decomposition) is yet unsolved and as far as we know, its existence has not been studied. As announced in the introduction, we will solve this question for discrete 2-additive GAI models.

Discrete p-additive GAI models

We consider from now on discrete GAI models, i.e., where attributes can take only a finite number of values, as it is most often the case in applications. We put

X i = {a 0 i , . . . , a m i i } (i ∈ N), with a 0 i i • • • i a m i i .
Recall that weak independence holds, so that the binary relations i , i = 1, . . . , n are complete preorders, and monotonicity (4) holds. For the sake of convenience, we normalize U (thus fixing a unique representation of ) by putting

U(a 0 1 , . . . , a 0 n ) = 0, U(a m 1 1 , . . . , a mn n ) = 1. ( 8
)
Observing that an additive model ( 1) is a particular GAI model where each term depends on a single variable, one may introduce the following definition.

Definition 1. A GAI model is said to be p-additive if each term u S , S ∈ S, depends on at most p variables, i.e., |S| ≤ p, and there exists at least one term u S with exactly p variables.

Hence, the p-additivity property acts as a kind of limitator of the complexity of the model.

Relation with k-ary capacities

There is a direct connection between discrete GAI models and k-ary capacities. This observation will be the key point for the proof of our main result.

Consider X 1 , . . . , X n as defined above. Any alternative x ∈ X is mapped to {0, . . . , m 1 }× • • • × {0, . . . , m n } by the mapping ϕ which simply keeps track of the rank of the value of the attribute:

(a j 1 1 , . . . , a jn n ) → ϕ(a j 1 1 , . . . , a jn n ) = (j 1 , . . . , j n ). We consider now the smallest (discrete) hypercube {0, . . . , k} N containing {0, . . . , m 1 } × • • • × {0, . . . , m n }, with k := max i m i . Let L = {0, 1, . . . , k}. Given a GAI model U on X, we define the mapping v : L N → R by U(x) =: v(ϕ(x)) (x ∈ X) and let v(z) := v(m 1 , . . . , m n ) when z ∈ K N \ ϕ(X).
In words, v encodes the values of U for every alternative, and fills in the missing values in the hypercube by the maximum of U. By the monotonicity of U and (8), we have that v is nondecreasing in each argument and satisfies v(0, . . . , 0) = 0 and v(k, . . . , k) = 1. Such a function on L N is called a k-ary capacity [START_REF] Grabisch | Capacities on lattices and k-ary capacities[END_REF] 1 . k-ary capacities are a generalization of the notion of capacity introduced by [START_REF] Choquet | Theory of capacities[END_REF]. Capacities correspond to 1-ary capacities, and through the identification of sets with their characteristic functions, they are usually defined as set functions v : 2 N → R + such that v(∅) = 0, v(N) = 1, and satisfying monotonicity: for any S, T ∈ 2 N such that S ⊆ T , v(S) ≤ v(T ) holds.

So far, we have identified the set of discrete GAI models with the set of k-ary capacities, where k + 1 is the maximum number of elements in an attribute. We push now the comparison a step further by identifying discrete p-additive GAI models with p-additive k-ary capacities.

We first introduce the notion of p-additivity for k-ary capacities and k-choice games, and to this end we introduce the Möbius transform. Following [START_REF] Rota | On the foundations of combinatorial theory I. Theory of Möbius functions[END_REF] and extending what is done for classical capacities (see, e.g., [START_REF] Chateauneuf | Some characterizations of lower probabilities and other monotone capacities through the use of Möbius inversion[END_REF]), the Möbius transform of a k-choice game v is a function m v : L N → R which is the unique solution of the linear system

v(z) = y≤z m v (y) (z ∈ {0, 1, . . . , k} N ). ( 9
)
It is shown in the appendix that its solution is given by

m v (z) = y≤z : z i -y i ≤1∀i∈N (-1) i∈N (z i -y i ) v(y) (z ∈ {0, 1, . . . , k} N ). (10)
It follows that any k-choice game v can be written as:

v = x∈L N m v (x)u x ,
with u x a k-ary capacity defined by

u x (z) = 1, if z ≥ x 0, otherwise.
By analogy with classical games, u x is called the unanimity game centered on x. Note that this decomposition is unique as the unanimity games are linearly independent, and form a basis of the vector space of k-choice games.

We say that a k-choice game v is (at most) p-additive for some p ∈ {1, . . . , n} if its Möbius transform satisfies m v (z) = 0 whenever |supp(z)| > p, where

supp(z) = {i ∈ N | z i > 0}.
The following lemma is fundamental in establishing the link between p-additive GAI models and p-additive k-ary capacities.

Lemma 1. Let k ∈ N and p ∈ {1, . . . , n}. A k-choice game v is p-additive if and only if it has the form

v(z) = x∈L N ,0<|supp(x)|≤p v x (x ∧ z) (z ∈ L N ) (11)
where v x : L N → R with v x (0) = 0.

Proof. Suppose that v is p-additive. By the decomposition of v in the basis of unanimity games, it follows that

v = x∈L N ,0<|supp(x)|≤p m v (x)u x ,
hence we have the required form with v x = m v (x)u x . Conversely, again by decomposition in the basis of unanimity games and since v x is a k-choice game, (11) can be rewritten as:

y∈L N m v (y)u y (z) = x∈L N ,0<|supp(x)|≤p y∈L N m vx (y)u y (x ∧ z) = y∈L N ,0<|supp(y)|≤p x∈L N ,0<|supp(x)|≤p m vx (y)u y (x ∧ z) = y∈L N ,0<|supp(y)|≤p x≥y,0<|supp(x)|≤p m vx (y) u y (z).
By uniqueness of the decomposition, it follows that v is p-additive.

Note that even if v is a capacity, the v x are not necessarily capacities. It follows from the above result that the set of p-additive discrete GAI models on X coincides with the set of (at most) p-additive k-ary capacities.

Monotone decomposition of a 2-additive GAI model

In this section, we show that it is always possible to obtain a decomposition of a 2-additive discrete GAI model into nondecreasing terms (monotone decomposition). The case of 2-additive models is of particular importance in practice, since it constitutes a good compromise between versatility and complexity. Experimental studies in multicriteria evaluation have shown that 2-additive capacities have almost the same approximation ability than general capacities (see, e.g., [START_REF] Grabisch | Subjective evaluation of discomfort in sitting position[END_REF]). A two-additive GAI model is considered in [START_REF] Bigot | Using and learning GAIdecompositions for representing ordinal rankings[END_REF], and a very similar model is defined in [START_REF] Greco | Robust ordinal regression for value functions handling interacting criteria[END_REF].

Before giving this result, we show that the existence of monotone decomposition is a crucial issue when a GAI model has to be determined from data by a learning procedure, because of algorithmic complexity.

A complexity problem in the learning procedure

Generally speaking, a learning procedure consists in collecting information on the preference relation , which is then used in an optimization problem, whose aim is to find a value function U of a given type representing at best the given preference. The variables of the optimization problem are then the parameters of the model U.

In most cases, the available data used for the identification of a model (GAI or any other decision model) consist in pairs (x, y) ∈ X 2 such that x y (see, e.g., [START_REF] Bigot | Using and learning GAIdecompositions for representing ordinal rankings[END_REF][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]). Additionnally, some more complex information can be used, as comparison of difference between alternatives, assessment or comparison on the importance of attributes or their interaction, as in [START_REF] Greco | Robust ordinal regression for value functions handling interacting criteria[END_REF], etc. In the above cited works, these data are converted into linear constraints, where the underlying variables are the parameters of the GAI model with possibly some additional "technical" variables, and the model is identified as a result of one or several linear programs. The following example is typical:

Minimize (x,y)∈D ε (x,y) subject to û ∈ C (12) ε (x,y) ∈ {0, 1}, (x, y) ∈ D U(x) -U(y) + Mε (x,y) ≥ 0, (x, y) ∈ D
where D is the learning data set (consisting here simply of pairs of alternatives (x, y) such that x y), M is a large positive constant, û is the vector of parameters of the GAI model denoted by U, and C is the set of feasible parameter vectors (we will specify û and C below). Roughly speaking, the program tries to find the best feasible vector û which maximizes the number of pairs (x, y) for which U faithfully represents the preference. Indeed, given the parameters û fixed, if U(x) ≥ U(y), then ε (x,y) can be equal to 0, otherwise, it must be equal to 1.

In other works (e.g., Fallah Tehrani et al. (2012,2014)) which follow more a regressiontype approach, the data are incorporated into the objective function, which is nonlinear. Anyway, the variables contain the vector û as above and we have the constraint û ∈ C. Moreover, û is obtained from a convex optimization problem.

In the two previous formulations, the complexity of the resolution of the optimization problem highly depends on the structure of polytope C and in particular the number of constraints.

As the vector of parameters û and the constraint û ∈ C are present in any of the approaches, we try in the sequel to determine the number of parameters as well as the number of constraints describing C. In a discrete GAI model as described in Section 3, the parameters û are the values u S (x S ) for all x S ∈ X S and all S ∈ S. If in addition we restrict to a 2-additive model and if no special information is available on S, we consider that S is the set of all singletons and all pairs of attributes. Supposing that the maximal number of elements in an attribute is k + 1, i.e., the GAI model is equivalent to a 2-additive k-ary capacity, we have |L| = k + 1 and the number of parameters is

η(k, n) = (k + 1) n 1 + (k + 1) 2 n 2 = n(k + 1) 2 2 + (k + 1)(n -1) .
Denoting by U the GAI model to be identified, C contains the monotonicity constraints saying that U is monotone nondecreasing. It is thus crucial from a computational standpoint to find efficient representation of monotonicity conditions. Such conditions on U basically take the form U(a j 1 1 , . . . , a

j i-1 i-1 , a j i +1 i , a j i+1 i+1 , . . . , a jn n ) ≥ U(a j 1 1 , . . . , a j i-1 i-1 , a j i i , a j i+1 i+1 , . . . , a jn n ) (13)
for every i ∈ N, j 1 ∈ {0, . . . , m 1 }, . . . , j i-1 ∈ {0, . . . , m i-1 }, j i ∈ {0, . . . , m i -1}, j i+1 ∈ {0, . . . , m i+1 },. . . ,j n ∈ {0, . . . , m n }. The number of elementary conditions contained in (13) (and thus of constraints in C) is equal to

i∈N m i × j∈N \{i} (m j + 1) .
In the case where m i = k for every i, this number becomes

κ(k, n) = n × k × (k + 1) n-1 .
Observe that although the number of parameters η(k, n) is quadratic in n and k, the number of constraints κ(k, n) is exponential in n. It follows that any practical identification of a GAI model based on some optimization procedure as described above, where the variables are the unknowns of the GAI model and the constraints are the monotonicity constraints ( 13) plus possibly some learning data, has to cope with an exponential number of constraints.

m i (m j + 1) + m j (m i + 1) .
In the case where m i = k for every i, this number becomes

κ ′ (k, n) = n × k × (n -1)(k + 1) + 1 , which is quadratic in n.

The main result

The following theorem states that a decomposition of a 2-additive GAI model into monotone nondecreasing terms is always possible.

Theorem 1. Let us consider a 2-additive discrete GAI model U satisfying monotonicity ( 4) and ( 8). Then there exist nonnegative and nondecreasing functions u i :

X i → [0, 1], i ∈ N, u ij : X i × X j → [0, 1], {i, j} ⊆ N, such that U(x) = i∈N u i (x i ) + {i,j}⊆N u ij (x i , x j ) (x ∈ X) (14)
Proof (sketch of ). Recalling that the set of 2-additive monotone discrete GAI models coincides with the set of 2-additive k-ary capacities, where k is the maximal number of elements in an attribute minus one, the problem is equivalent to the decomposition of a 2-additive k-ary capacity v into a sum of 2-additive k-ary capacities whose support has size at most 2, where the support of v is defined by

supp(v) = x∈L N :m v (x) =0 supp(x).
Here are the main steps:

(i) We consider P k,2 the polytope of all 2-additive k-ary capacities.

(ii) We find the set of all vertices of P k,2 , which will be proved to be the set of all 0-1-valued 2-additive k-ary capacities.

(iii) We prove that any vertex of P k,2 has support of size at most 2.

(iv) Since any v ∈ P k,2 is a convex combination of vertices of P k,2 , which are 2-additive k-ary capacities with support of size at most 2, this convex combination yields the desired decomposition.

The detailed proof is given in Section 4.3.

We make some comments on the significance of the theorem.

• First, the theorem solves an unanswered question on the possible decompositions of a GAI model and can be stated in a rather abstract way, without refering to a preference relation and the decision theoretical machinery: Suppose U : L N → R is given with L = {0, 1, . . . , k}, has the form (3) with S containing only singletons and pairs, and is nondecreasing in each variable and normalized. Then it is possible to write U as a sum of nonnegative and nondecreasing terms depending on one or two variables. So far, no such decomposition was known, and the canonical decomposition of Braziunas does not possess this property. An immediate consequence of this is that such a decomposition yields a model which is easy to interpret, as each term brings a positive contribution to the total score U(x) of an alternative x, and each term is easily analyzable in terms of importance and interaction.

• Second, as explained in Section 4.1, the result reduces drastically the complexity of any learning procedure, from exponential to quadratic complexity. Let us summarize this issue briefly, putting it into a practical framework. Suppose that the preference relation (preorder) under consideration satisfies weak independence and is defined over finite attributes. Assuming some interaction/dependence among pairs of attributes, one seeks a 2-additive GAI model. Based on the (usually incomplete) preference relation obtained from the decision maker, there exist several approaches finding by optimization a possible GAI model, e.g., by linear programming coding the preference relation into the constraints, or by a regression approach, using nonlinear programming, where the preference relation is coded into the objective function. In both cases, the variables are the parameters of the model, whose number depends polynomially on k and n, but since U is a nondecreasing function in n variables, there are exponentially many monotonicity constraints. If it is possible to decompose U into a sum of monotone terms of at most 2 variables, then the number of constraints become quadratic. In short, we transform an intractable problem into a tractable one.

• Along the line of the identification methods where the preference relation is coded in constraints, we mention also robust methods, considering all parameters values fulfilling the constraints, rather than arbitrarily selecting one of these values. Min-Max Regret criterion is a conservative way to handle the uncertainty on the decision model [START_REF] Boutilier | Constraint-based optimization and utility elicitation using the minimax decision criterion[END_REF]. The idea is to set bounds on the worst possible loss one could have by choosing an alternative, looking at the set of possible parameters values. It is interesting to note that the scientific community that developped these approaches does not enforce monotonicity conditions. This makes the elicitation quite complex, as one needs to provide a lot of preference information to obtain the correct monotonicity conditions. Most applications in this area consider a very small size of S compared to the number of criteria, which is not always possible in practice. One would then expect a great benefit of enforcing monotonicity conditions in the MinMax Regret method. Here again, Theorem 1 is very helpful as it reduces the number of monotonicity conditions to a tractable number.

Proof of Theorem 1

In order to find the vertices of P k,2 , we first consider the vertices of P k,• , the polytope of k-ary capacities. A first easy fact is that the extreme points of P k,• are the 0-1-valued k-ary capacities.

Lemma 2. v is an extreme point of P k,• iff v is 0-1-valued.

Proof. Take v in P k,• which is 0-1-valued, and consider v, v

′ ∈ P k,• such that v+v ′ 2 = v. Then, since v is 0-1-valued, v(x) + v ′ (x) = 2, if v(x) = 1 0, otherwise.
Since v, v ′ are normalized and monotone, the only possibility to get v(x)

+ v ′ (x) = 2 is to have v(x) = v ′ (x) = 1, and similarly, v(x) + v ′ (x) = 0 forces v(x) = v ′ (x) = 0. It follows that v = v ′ = v, i.e., v is an extreme point of P k,• .
Conversely, consider a vertex v which is not 0-1-valued, and let

ǫ = min(1 -max x:v(x)<1 v(x), min x:v(x)>0 v(x)). Define v ′ (x) = v(x) + ǫ, for all x s.t. v(x) = 0, 1 v ′′ (x) = v(x) -ǫ, for all x s.t. v(x) = 0, 1, and v ′ = v ′′ = v otherwise. Then v ′ , v ′′ ∈ P k,• and v = v ′ +v ′′ 2 , a contradiction. Lemma 3. Let k ∈ N and v ∈ P k,2 . Then v is 0-1-valued iff m v is {-1, 0, 1} valued.
Proof. ⇐) By the assumption y≤x m v (y) ∈ Z for every x ∈ {0, 1, . . . , k} N . Since v ∈ P k,2 it follows that v is 0-1-valued.

⇒) Assume v is 0-1-valued and use (10) to compute the Möbius transform. For z = ℓ i with ℓ ∈ {1, . . . , k}, we have m v (z) = v(ℓ i )v((ℓ -1) i ), so that the desired result holds. Otherwise z = ℓ i ℓ ′ j with ℓ, ℓ ′ ∈ {1, . . . , k} and distinct i, j ∈ N. Then

m v (z) = v(z) -v((ℓ -1) i ℓ ′ j ) -v(ℓ i (ℓ ′ -1) j ) + v((ℓ -1) i (ℓ ′ -1) j ). ( 15
)
By the assumption and monotonicity of v, it follows that m v (z) ∈ {-1, 0, 1}.

We recall that a m × n matrix is totally unimodular if the determinant of every square submatrix is equal to -1, 0 or 1. A polyhedron is integer if all its extreme points have integer coordinates. Then a matrix A is totally unimodular iff the polyhedron {x | Ax ≤ b} is integer for every integer vector b. In particular it is known that the vertex-arc matrix M of a directed graph, i.e., whose entries are M x,a = 1 if the arc a leaves vertex x, -1 if a enters x, and 0 otherwise, is totally unimodular (in other words, each column of M has exactly one +1 and one -1, the rest being 0).

We are now in position to characterize the extreme points of P k,2 .

Proposition 1. Let k ∈ N. The set of extreme points of P k,2 , the polytope of 2-additive k-ary capacities, is the set of 0-1-valued 2-additive k-ary capacities.

Proof. By Lemma 2, we need only to prove that any extreme point of P k,2 is 0-1-valued. 1. We prove that A k,• , the matrix defining the polytope of k-ary capacities, is totally unimodular. The argument follows the one given for classical capacities by Miranda et al. (Miranda et al., 2006, Th. 2). We prove that A ⊤ k,• is totally unimodular, which is equivalent to the desired result. Since the monotonicity constraints are either of the form v(1 i ) ≥ 0 or v(x)v(x ′ ) ≥ 0 where x ′ is a lower neighbor of x (i.e. x ′ = x -1 i for some i), the matrix A ⊤ k.• has the form (I, B), where I is a submatrix of the (k n -1)-dim identity matrix I k n -1 , and B is a matrix where each column has exactly one +1 and one -1. Hence B is totally unimodular, and so is (I k n -1 , B) as it easy to check. Since A ⊤ k,• is a submatrix of it, it is also totally unimodular.

It follows from

Step 1 that the polytope P k,• (b) given by A k,• v ≤ b is integer for every integer vector b. Next, consider the (k n -1) ×(k n -1)-matrix Z expressing the Zeta transform, i.e., Zm v = v, as given by ( 9). This matrix has only 0 and 1 as entries, and its inverse Z -1 exists and its entries are 0, -1, +1 only (see ( 10)). Consider the polytope

P m k,• (b) given by A m k,• m ≤ b with A m k,• = A k,
• Z, the image by the linear transform Z of the polytope P k,• (b). It is easy to check that v is an extreme point of P k,• (b) iff Z -1 v is an extreme point of P m k,• (b). Evidently, the coordinates of Z -1 v are integer, therefore P m k,• (b) is integer for every integer vector b. We conclude that A m k,• is totally unimodular. 3. Inasmuch as a submatrix of a totally unimodular matrix is itself totally unimodular, it follows from Step 2 that A m k,2 , the matrix defining the set of 2-additive k-ary capacities in Möbius coordinates, is also totally unimodular. As a conclusion, the extreme points of P m k,2 are integer-valued. 4. We show that the extreme points of P m k,2 are {-1, 0, 1}-valued. Then Lemma 3 permits to conclude. It suffices to show that |m v (z)| ≥ 2 cannot happen. If z = ℓ i with ℓ ∈ {1, . . . , k}, we find by ( 10) that m v (z) = v(ℓ i )v((ℓ -1) i ), so that the claim holds since v ∈ P k,2 . Otherwise, z = ℓ i ℓ ′ j with ℓ, ℓ ′ ∈ {1, . . . , k} and distinct i, j, and m v (z) is given by ( 15). Since v is monotone and normalized, the claim easily follows.

The last step is to prove that a 0-1-valued 2-additive k-ary capacity has a support of size at most 2.

Proposition 2. Consider a 2-additive k-ary capacity u on N which is 0-1-valued. Then the support of u is restricted to at most two attributes.

Proof. Preliminary Step. u being 2-additive, its expression is

u(x) = {i,j}⊆N u i,j (x i , x j ) (x ∈ X). (16)
If we set u ′ i,j (x i , x j ) = u i,j (x i , x j )u i,j (0, 0), we obtain u(x) = {i,j}⊆N u ′ i,j (x i , x j ) + C, where C = -{i,j}⊆N u i,j (0, 0). By (8) and u ′ i,j (0, 0) = 0, one gets C = 0. This proves that in decomposition ( 16), one can always assume that ∀{i, j} ⊆ N u i,j (0, 0) = 0.

We wish to prove that u depends only on one term u i,j in (16). In order to avoid cases where such a term u i,j depends only on one variable (in which case u might also depend on another term u k,l ), we are interested in terms u i,j depending on its two variables x i and x j . We say that u i,j depends on its two variables if ∃y i ∈ X i ∃y j ∈ X j u i,j (y i , y j ) = u i,j (y i , 0) (18) ∃y ′ i ∈ X i ∃y ′ j ∈ X j u i,j (y ′ i , y ′ j ) = u i,j (0, y ′ j )

Clearly, if (18) (resp. ( 19)) is not fulfilled, then u i,j does not depend on attribute x j (resp. x i ).

The proof is organized as follows. We show in Step 1 that if there is no term u i,j that depends on its two variables, then u depends only on one variable. We then assume that at least one term u i,j depends on its two variables -denoted u 1,2 w.l.o.g.

Step 2 shows that it is not possible to have a non-zero term u i,j , with {i, j} ⊆ N \ {1, 2}.

Step 3 proves that it is not possible to have a non-zero term u i,j , with i ∈ {1, 2} and j ∈ N \ {1, 2}. We conclude that u 1,2 is the only non-zero term in the decomposition. This proves that u depends only on two variables.

Step 1: case of the additive value function model. We first start with the case where there is no term u i,j that depends on its two variables.

Claim 1. Assume that there is no term u i,j that depends on its two variables. Then the support of u is restricted to one attribute.

Proof of the Claim. If there is no term u i,j that depends on its two variables, u takes the form of an additive value function:

u(x) = i∈N u i (x i )
where u i : X i → R is not necessarily nonnegative or monotone. By (17), we have u i (0) = 0 for every i ∈ N.

Let i ∈ N, we write u(x i , 0 -i ) = u i (x i ). Hence u i is 0-1-valued and monotone. As u is not constant by ( 8), at least one term u i is not constant. W.l.o.g. let us assume it is u 1 . Then there exists x 1 ∈ X 1 such that u 1 (x 1 ) = 1. Now for every i ∈ N \{1} and x i ∈ X i , u(x 1 , x i , 0 -1,i ) = 1+u i (x i ). As u i is nonnegative and u is 0-1-valued, we conclude that u i (x i ) = 0. Hence u depends only on x 1 .

Step 2: Case where u has two non-zero terms with non-overlapping support, e.g., u 1,2 and u 3,4 . We now focus on the situation where at least one term u i,j depends on its two variables. W.l.o.g., we assume it is u 1,2 .

We consider the general case where there are at least 4 attributes. The restriction with only 3 attributes will be handled in Step 3. For every j ∈ N \ {1, 2}, we choose k(j) ∈ N \{1, 2, j} (where k(j) = k(j ′ ) for j = j ′ ). For every i ∈ {1, 2} and j ∈ N \{1, 2}, we set u ′ i,j (x i , x j ) = u i,j (x i , x j )u i,j (x i , 0)u i,j (0, x j ) u ′ 1,2 (x 1 , x 2 ) = u 1,2 (x 1 , x 2 ) + j∈N \{1,2}

(u 1,j (x 1 , 0) + u 2,j (x 2 , 0)) u ′ j,k(j) (x j , x k(j) ) = u j,k(j) (x j , x k(j) ) + u 1,j (0, x j ) + u 2,j (0, x j )

Then u(x) = {i,j}⊆N u ′ i,j (x i , x j ). Moreover u ′ i,j (x i , 0) = 0 and u ′ i,j (0, x j ) = 0 for i ∈ {1, 2}, j ∈ N \ {1, 2}, x i ∈ X i and x j ∈ X j . Hence in decomposition (16), we can assume that ∀i ∈ {1, 2} ∀j ∈ N \{1, 2} ∀x i ∈ X i ∀x j ∈ X j u i,j (x i , 0) = 0 and u i,j (0, x j ) = 0. (20)

Thanks to ( 17) and ( 20), we have

u(x 1 , x 2 , 0 -1,2 ) = u 1,2 (x 1 , x 2 ) (21)
Hence u 1,2 is 0-1-valued and monotone. ( 22) By ( 22), conditions ( 18) and ( 19) with i = 1, j = 2 give u 1,2 (y 1 , y 2 ) = 1 , u 1,2 (y 1 , 0) = 0 u 1,2 (y ′ 1 , y ′ 2 ) = 1 , u 1,2 (0, y ′ 2 ) = 0 (23)

  The following tables, obtained with k = 4, shows that the underlying optimization problem becomes rapidly intractable.

	n	4	6	8	10
	η(4, n)	170	405	740	1175
	κ(4, n)	2000 75 000 2 500 000 78 125 000
	n	12		14	20
	η(4, n)	1710		2345	4850
	κ(4, n)	2 343 750 000 68 359 375 000 1.526E + 15
	However, if a decomposition into nonnegative nondecreasing terms is possible, one has
	only to check monotonicity of each term. Then the number of monotonicity conditions
	drops to
	m i +
	i∈N	{i,j}⊆N

  The following table (k = 4) shows that the optimization problem becomes tractable even for a large number of attributes.

	n	4	6	8	10	12	14	20
	κ ′ (4, n)	256 624 1152 1840 2688 3696 7680

When nondecreasingness is not required, they coincide with multichoice or k-choice games[START_REF] Hsiao | Multichoice cooperative games[END_REF].

Assume by contradiction that there exists a non-zero u i,j for some {i, j} ⊆ N \ {1, 2}. W.l.o.g., we assume it is u 3,4 . Then there exists z 3 ∈ X 3 and z 4 ∈ X 4 such that u 3,4 (z 3 , z 4 ) = 0. As for (20), we can transfer, for i ∈ {3, 4} and j ∈ N \ {1, 2, 3, 4}, the term u i,j (x i , 0) in u 3,4 . Hence we can assume that ∀i ∈ {3, 4} ∀j ∈ N \ {1, 2, 3, 4} ∀x i ∈ X i u i,j (x i , 0) = 0.

(24)

Thanks to ( 17), ( 20) and ( 24), we have u(x 3 , x 4 , 0 -3,4 ) = u 3,4 (x 3 , x 4 ) (25) Hence u 3,4 is 0-1-valued, monotone, and u 3,4 (z 3 , z 4 ) = 1.

(26)

Claim 2. If u 1,2 depends on its two variables, then u 3,4 is identically zero.

Proof of the Claim. We set v(x 1 , x 2 , x 3 , x 4 ) = u(x 1 , x 2 , x 3 , x 4 , 0 -1,2,3,4 ). We write v(x 1 , x 2 , x 3 , x 4 ) = 1≤i<j≤4 u i,j (x i , x j ).

Analysis with y and z:

• v(y 1 , y 2 , z 3 , z 4 ) = u 1,2 (y 1 , y 2 )

• v(y 1 , y 2 , z 3 , 0)

=1 by monotonicity = 1 + u 3,4 (z 3 , 0) + u 1,3 (y 1 , z 3 ) + u 2,3 (y 2 , z 3 ). Hence

• v(y 1 , y 2 , 0, z 4 )

=1 by monotonicity = 1 + u 3,4 (0, z 4 ) + u 1,4 (y 1 , z 4 ) + u 2,4 (y 2 , z 4 ). Hence

• v(0, y 2 , z 3 , z 4 )

=1 by monotonicity

• From (30), ( 31) and ( 27),

=1 by (32) +u 3,4 (z 3 , 0)+u 2,3 (y 2 , z 3 ). Moreover, v(0, y 2 , z 3 , 0) ≥ v(0, y 2 , 0, 0) = u 1,2 (0, y 2 ) = 1. Hence u 3,4 (z 3 , 0) + u 2,3 (y 2 , z 3 ) = 0 and u 2,3 (y 2 , z 3 ) ∈ {-1, 0}.

(33)

• v(0, y 2 , 0, z 4 ) = 1 + u 3,4 (0, z 4 ) + u 2,4 (y 2 , z 4 ). Moreover, v(0, y 2 , 0, z 4 ) ≥ v(0, y 2 , 0, 0) = u 1,2 (0, y 2 ) = 1. Hence

From ( 27) and (30), we get u 2,3 (y 2 , z 3 )+u 2,4 (y 2 , z 4 ) = -1. As u 2,3 (y 2 , z 3 ), u 2,4 (y 2 , z 4 ) ∈ {-1, 0} (by ( 33) and ( 34)), we have two cases:

• Case 1: u 2,3 (y 2 , z 3 ) = -1 and u 2,4 (y 2 , z 4 ) = 0. Then

All values are determined.

• Case 2: u 2,3 (y 2 , z 3 ) = 0 and u 2,4 (y 2 , z 4 ) = -1. Then

All values are determined.

Analysis with y ′ and z: The analyses with y and z, and with y ′ and z are similar. By (23), we just need to invert the two attributes 1 and 2. Hence a similar reasoning to the previous analysis can be done. We obtain thus the two cases 1 ′ and 2 ′ which are deduced from cases 1 and 2 just by switching attributes 1 and 2:

• Case 1':

Synthesis: Cases 1 and 2' are incompatible, and so are cases 2 and 1'. We have thus the alternative:

• Case 1 and 1'. Gathering the values of partial value functions, we get

We obtain a contradiction as u(y ′ 1 , y 2 , z 3 , z 4 ) ≥ u(0, 0, z 3 , z 4 ) = 1.

• Case 2 and 2'. Gathering the values of partial value functions, we get

We obtain a contradiction as u(y ′ 1 , y 2 , z 3 , z 4 ) ≥ u(0, 0, z 3 , z 4 ) = 1. A contradiction is raised in all situations. Hence it is not possible to have u 3,4 non-zero, knowing that u 1,2 depends on its two variables.

Step 3: Case where u has two non-zero terms with overlapping support, e.g., u 1,2 and u 1,3 . In the last case, term u 1,2 depends on its two variables, and there is no non-zero term u i,j , with i, j = 1, 2, that depends on its two variables.

We proceed as in the beginning of Step 2, assuming that

Then relations ( 21) through ( 23) also hold in this case. Assume by contradiction that there exists a non-zero u i,j for some i ∈ {1, 2} and j ∈ N \ {1, 2}. W.l.o.g., we assume it is u 1,3 . There exists thus z 1 ∈ X 1 and z

One can transfer term u i,3 (0, x 3 ), for i = 1, 3, to u 1,3 (proceeding as in the beginning of

Step 2). Hence we can assume that

Claim 3. If u 1,2 depends on its two variables, then u 1,3 is identically zero.

Proof of the Claim. We set v(x 1 , x 2 , x 3 ) = u(x 1 , x 2 , x 3 , 0 -1,2,3 ). Then

Analysis with y and z: We write thanks to (21) and to the monotonicity of v

Hence u 1,3 (z 1 , z 3 ) ≥ 0, which gives by ( 36)

We have the following basic relations:

Analysis with compound alternatives: We distinguish between two cases:

• Assume first that z 1 ≥ y 1 . By ( 22) and ( 23), we have

By monotonicity, v(z 1 , y 2 , z 3 ) = 1 (as v(z 1 , 0, z 3 ) = u 1,2 (z 1 , 0)+1 and thus v(z 1 , 0, z 3 ) = 1). Hence ( 38) and ( 42) give

By monotonicity, v(y 1 , y 2 , z 3 ) = 1 (as v(y 1 , y 2 , 0) = u 1,2 (y 1 , y 2 ) = 1). From ( 41) and previous relation, we have

• Assume then that z 1 < y 1 . We have v(y 1 , 0, z 3 ) = 1 by monotonicity of v (as v(z 1 , 0, z 3 ) = 1). Then (40) proves that (45) holds. This implies that (44) also holds, thanks to (41).

By monotonicity, v(z 1 , y 2 , z 3 ) = 1 (as v(z 1 , 0, z 3 ) = 1). Hence ( 42) and ( 44) show that ( 43) is satisfied.

In the two cases, we have proved that relations ( 43), ( 44) and ( 45) are true.

We make the following reasoning.

• We write

Therefore u 1,3 (0, z 3 ) ≥ 1. We also see that u 1,3 (0, z 3 ) ∈ {0, 1} as v(0, 0, z 3 ) = u 1,3 (0, z 3 ). Hence

• We have v(0, y ′ 2 , z 3 )

=1 by monotonicity and (47)

=1 by ( 22) and ( 48)

=0 by ( 50)

We obtain a contradiction as v(y ′ 1 , y 2 , z 3 ) = 1 (thanks to monotonicity of v, and to (47)).

A contradiction is raised in all situations. Hence it is not possible to have u 1,3 non-zero, knowing that u 1,2 depends on its two variables.

Finally, we have proved that if u 1,2 depends on its two variables, no other term can be non-zero. This proves that u depends only on two variables.

In summary, we have proved that the extreme points of P k,2 are the 2-additive 0-1valued k-ary capacities, and that these capacities have a support of size at most 2. It follows that any v ∈ P k,2 can be written as a convex combination of 2-additive k-ary capacities with support of size at most 2, which proves Theorem 1.

A Möbius transform of a k-ary capacity

The result can be easily obtained by using standard results of the theory of Möbius functions (see, e.g., [START_REF] Aigner | Combinatorial Theory[END_REF]). Given a finite poset (partially ordered set) (P, ≤), its Möbius function µ : P × P → R is defined inductively by:

Then the solution of the system f (x) = y≤x g(y), x ∈ P , is given by

and g is called the Möbius transform (or inverse) of f . Note that in the case of capacities, (P, ≤) is taken as (2 N , ⊆).

Considering two posets (P, ≤), (P ′ , ≤ ′ ), and the product poset (P × P ′ , ≤) where ≤ is the product order, i.e., (x, y) ≤ (x ′ , y ′ ) if x ≤ x ′ and y ≤ ′ y ′ , it is easy to show that the Möbius function on P × P ′ is the product of the Möbius functions on P and P ′ : µ((x, t), (y, z)) = µ P (x, y)µ P ′ (t, z) (x, y ∈ P, t, z ∈ P ′ ).

Let us apply this result to k-ary capacities. It is easy to see that the Möbius function on the chain {0, 1, . . . , k} is given by µ {0,1,...,k} (x, y) = (-1) y-x , if 0 ≤ yx ≤ 1 0, otherwise.

(51)

It follows that the Möbius transform m v of a k-ary capacity v is given by m v (x) = y≤x:x i -y i ≤1∀i∈N

(-1) i∈N (x i -y i ) v(y).

B Acknowledgments

The corresponding author thanks the Agence Nationale de la Recherche for financial support under contract ANR-13-BSHS1-0010 (DynaMITE).