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

Christophe Labreuche
email: christophe.labreuche@thalesgroup.com

Mustapha Ridaoui
email: mustapha.ridaoui@univ-paris1.fr

Well-formed decompositions of Generalized Additive Independence models

Keywords: Generalized Additive Independence, multichoice game, decision making, decomposition

Generalized Additive Independence (GAI) models permit to represent interacting variables in decision making. A fundamental problem is that the expression of a GAI model is not unique as it has several equivalent different decompositions involving multivariate terms. Considering for simplicity 2-additive GAI models (i.e., with multivariate terms of at most 2 variables), the paper examines the different questions (definition, monotonicity, interpretation, etc.) around the decomposition of a 2-additive GAI model and proposes as a basis the notion of well-formed decomposition. We show that the presence of a bi-variate term in a well-formed decomposition implies that the variables are dependent in a preferential sense. Restricting to the case of discrete variables, and based on a previous result showing the existence of a monotone decomposition, we give a practical procedure to obtain a monotone and well-formed decomposition and give an explicit expression of it in a particular case.

Introduction

In 1967 Fishburn introduced a generalization of the additive utility model, under the name of Generalized Additive Independence (GAI) model [START_REF] Fishburn | Interdependence and additivity in multivariate, unidimensional expected utility theory[END_REF]. The idea was to keep an additive expression of the utility, while the terms in the sum were no more single-variate but multivariate. Each multivariate term could model the interaction or dependence between these variables. Its great flexibility has made the model to become popular in the decision making literature, especially in artificial intelligence, where the variables are considered to be discrete (see, e.g., Bacchus and Grove (1995); [START_REF] Boutilier | UCP-networks: A directed graphical representation of conditional utilities[END_REF]; [START_REF] Bigot | Using and learning GAIdecompositions for representing ordinal rankings[END_REF]; [START_REF] Braziunas | Local utility elicitation in GAI models[END_REF]; [START_REF] Braziunas | Decision-theoretic elicitation of generalized additive utilities[END_REF]; [START_REF] Dubus | Fast recommendations using GAI models[END_REF]; [START_REF] Ch | GAI networks for utility elicitation[END_REF]; [START_REF] Ch | Decision making with multiple objectives using gai networks[END_REF]).

Its great generality makes the model to be difficult to use in practice and to study on a theoretical point of view (e.g., axiomatic characterization). On the practical side, the great number of parameters makes the learning/identification of the model to be difficult, and its interpretation is less easy than one could have expected from its simple form (sum of multivariate terms). On the latter aspect, the fundamental reason is that a given utility function U can have several different additive decompositions (each constituting a distinct GAI model). Each decomposition tends to indicate a certain type of behavior of the variables, but contradictions may occur among the interpretations issued from different (although equivalent) decompositions. The underlying question here is: does the existence of a multivariate term, say, u 12 (x 1 , x 2 ) necessarily implies a kind of interaction between x 1 and x 2 , or could it possible that the presence of other terms in the decomposition may cancel this interaction? On the point of view of preference representation, what does this interaction mean?

Another difficulty is that it is not easy to give a clear interpretation of the model when the terms in the decomposition are not all monotonically increasing (or all monotonically decreasing). When increasing and decreasing terms coexist, it is hard to see which one will have preponderant effect. The question is then to know whether it is always possible to avoid such situation and to guarantee the existence of a monotone decomposition. In the case of an affirmative answer, the usual questions appear: how to obtain it practically? Is it unique in some sense?

Our aim is to bring answers to these important questions, although not in full generality, continuing the contribution given by [START_REF] Grabisch | Monotone decomposition of 2-additive generalized additive independence models[END_REF], where the existence of monotone decomposition was shown, under certain conditions. We place ourselves for most parts of the paper in the family of 2-additive GAI models, that is, where the multivariate terms are limited to 2 variables. Our first contribution is to clarify what is meant by decomposition. There is indeed some ambiguity in this notion as nothing prevents to consider x 1 + x 2 as a bivariate term u 12 (x 1 , x 2 ) instead of the sum of two monovariate terms u 1 (x 1 ) + u 2 (x 2 ). We call well-formed decompositions those which adopt the latter option, i.e., each term cannot be further additively decomposed into subterms involving strictly less variables. We also introduce the more restrictive notion of well-formed-monotone decomposition (Section 3). We next introduce the notion of 2-independence based on a quaternary relation of preference, and show that a bi-variate term exists in a well-formed decomposition if and only if these variables are not 2-independent (Section 3.1). In the rest of the paper, we consider that attributes are discrete, which permits to consider (2-additive) GAI models as (2-additive) k-ary capacities or monotone multichoice games. Under this condition, it is possible to show that a monotone decomposition always exists (we recall in Section 3.2 this result, proved by [START_REF] Grabisch | Monotone decomposition of 2-additive generalized additive independence models[END_REF]), which is nothing else than the expression of a given k-ary capacity as a convex combination of vertices of the polytope P k,2 of 2-additive k-ary capacities (these vertices are studied and identified in Section 4). Lastly, we address the practical determination of a monotone decomposition. In the general case, we suggest the use of linear programming (Section 3.3), and we give an explicit monotone minimal (in the number of terms) decomposition when k = 2 (Section 5). We show that there exist several minimal monotone decompositions.

As discrete GAI models can be seen as multichoice games, our results bring a contribution to this field as well.

Preliminaries

Generalized Additive Independence (GAI) model

Let N = {1, . . . , n} be a finite set of n attributes (or criteria). We denote by X i the set of all possible values taken by attribute i ∈ N . An alternative x is identified with an element of the Cartesian product X = X 1 × • • • × X n . For x, y ∈ X and A ⊆ N , we denote by x A the restriction of x to the coordinates in A, by x -A the restriction to the coordinates in N \ A, and by (x A , y -A ) the compound alternative taking value x i if i ∈ A and value y i otherwise. Accordingly, we use X A , X -A for the restricted Cartesian products of attributes.

We assume that the preference of the decision maker over the alternatives is represented by a complete preorder (reflexive and transitive binary relation) on X, and that this preference relation can be represented by an overall utility or value function

U : X → R, i.e., x y iff U (x) ≥ U (y), ∀x, y ∈ X.
In practice, the value function U can take different forms, among which one of the simplest is called the additive independence model (or additive utility model) [START_REF] Keeney | Decision with Multiple Objectives[END_REF]:

U (x) = n i=1 u i (x i ), x ∈ X,
where u i : X i → R is the marginal value function on attribute X i , for every i ∈ N . Any additive utility model implies that the underlying preference satisfies weak independence [START_REF] Krantz | Additive and polynomial representations[END_REF]): a preference relation x y is said to satisfy weak independence if 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 ).
It is important to note that weak independence is too weak to ensure that the additive independence model holds and that this one presupposes that there is no interaction between the attributes. Hence, a natural generalization of the additive independence model is to allow some interaction among criteria [START_REF] Fishburn | Interdependence and additivity in multivariate, unidimensional expected utility theory[END_REF]Bacchus and Grove, 1995):

U (x) = S∈S u S (x S ), x ∈ X, (1)
where S is a collection of subsets of N , and u S : X S → R. This model is called the Generalized Additive Independence (GAI) model. The set S contains all subsets of attributes that interact one another. Hence, the additive independence model is a particular case of the GAI model where S is composed of only singletons.

We now introduce the notion of p-additivity for GAI models [START_REF] Grabisch | Monotone decomposition of 2-additive generalized additive independence models[END_REF].

Definition 1. A GAI model is said to be (at most) p-additive if each term u S , S ∈ S, depends on at most p variables, i.e., |S| ≤ p.

The value of p is directly related to the complexity of the model. Note that a 1-additive model is a classical additive utility model.

In general, GAI models do not necessarily satisfy weak independence (see, e.g., [START_REF] Braziunas | Decision-theoretic elicitation of generalized additive utilities[END_REF]). However, as it is customary in many works in the domain of multicriteria decision making, we will assume throughout the paper that weak independence holds. This implies that we can unambiguously define a preference i on X i , for every i ∈ N . We make the assumption of monotonicity or unanimity (UNA), which is basic in this field:

x i i y i ∀i ∈ N implies U (x) ≥ U (y), (2)
for every x, y ∈ X.

In most parts of this paper, we will consider that the attributes are discrete, with X i = {x 0 i , . . . , x k i i } for any i ∈ N . In addition, for every i ∈ N , we order the elements of attribute X i according to the order i , that is, x j i i x j-1 i for j = 1, . . . , k i . Without loss of generality we impose the following normalization condition (NORM):

U (x 0 1 , . . . , x 0 n ) = 0 and U (x k 1 1 , . . . , x kn n ) = 1. ( 3
)
Supposing that no two elements in X i are indifferent (otherwise, we may eliminate one of them), it turns out that we can identify an alternative (x j 1 1 , . . . , x jn n ) with (j 1 , . . . , j n ), as only the index of elements in attributes matters. Therefore, we introduce

L = L 1 × • • • × L n , with L i = {0, . . . , k i },
which replace X and the X i 's. Thanks to the ordering of the elements of each attribute, the product order ≥ on L, defined by x ≥ y iff x i ≥ y i (in the usual sense) for all i ∈ N , makes the function U to be monotonically nondecreasing under assumption (UNA). Moreover, we will use the notation x > y for x i > y i for all i ∈ N .

Finally, in order to avoid intricacies, we assume that

k 1 = • • • = k n .
The subsequent development can nevertheless be applied to the general case where the k i 's are not all equal, by letting k = max i∈N k i and extending U on {0, . . . , k} N by U (x) = U (k 1 , . . . , k n ) for every x ∈ {0, . . . , k} N \ L.

k-ary capacities

In the classical sense, a (TU) game is a set function v : 2 N → R vanishing on the empty set. Traditionally, v(S) is interpreted as follows: the coalition S of players of N can secure by cooperation the worth or benefit v(S). In this framework, a player either participates or does not participate to the game. Coding participation by 1 and nonparticipation by 0, v(S) can be rewritten v(1 S ), where 1 S is the indicator function of S. A natural generalization is to consider multichoice games [START_REF] Hsiao | Shapley value for multi-choice cooperative games, I. Discussion paper of the University of Illinois at[END_REF]. A multichoice game (or k-ary game) is any function v : L → R satisfying v(0 N ) = 0, where 0 N = (0, . . . , 0). A given x ∈ L is interpreted as the profile of participation of all players, where x i is the level of participation of player i, ranging from non participation (x i = 0) to full participation (x i = k). A k-ary capacity [START_REF] Grabisch | Capacities on lattices and k-ary capacities[END_REF] is a multichoice game satisfying the monotonicity condition, i.e., v(x) ≤ v(y) whenever x ≤ y, and the normalization condition: v(k N ) = 1, where k N = (k, . . . , k). The conjugate of a multichoice game v, denoted v is defined by

v(x) = v(k N ) -v(k N -x), x ∈ L.
From the previous section, it is apparent that a discrete GAI model satisfying (UNA) and (NORM) can be seen as a k-ary capacity.

We now introduce some technical notions on multichoice games. The Möbius transform of a multichoice game v is a mapping m v : L → R which is the unique solution [START_REF] Rota | On the foundations of combinatorial theory I. Theory of Möbius functions[END_REF] of the linear system

v(x) = y≤x m v (y), x ∈ L. (4)
It is given by

m v (x) = y≤x ∀i∈N,x i -y i ≤1 (-1) i∈N (x i -y i ) v(y), x ∈ L, (5)
By analogy with classical games, unanimity multichoice games µ x , x ∈ L \ {0 N } are defined by

µ x (y) = 1, if y ≥ x 0, otherwise.
Hence, (4) can be rewritten as v = y∈L m v (y)µ y , and since the system (4) has a unique solution, the set of unanimity multichoice games forms a basis of the set of multichoice games, and coordinates of a multichoice game in this basis are the coefficients of the Möbius transform. Note that a k-ary unanimity multichoice game is a k-ary capacity.

For convenience we may denote elements of L in the form

x = 1 S 1 2 S 2 • • • k S k , with S i = {j ∈ N | x j = i}.
For simplicity we may omit braces and commas in sets, writing, e.g., x = 1 ij 2 k instead of 1 {i,j} 2 {k} for i, j, k ∈ N . We denote by S(x) = {i ∈ N | x i > 0}, the support of x for each vector x ∈ L, and we define the support of a multichoice game v by S(v) = x∈L:m v (x) =0

S(x).

We now introduce the notion of p-additivity for k-ary games. A multichoice game v is said to be (at most) p-additive for some integer 1 ≤ p ≤ n if the Möbius transform of v vanishes for elements x whose support S(x) is such that |S(x)| > p. p-additive multichoice games therefore form a vector subspace of the vector space of multichoice games, spanned by the µ x , x ∈ L such that 0 < |S(x)| ≤ p.

In particular, the set of 2-additive multichoice games is a subspace spanned by µ i , µ ij with {i, j} ⊆ N , µ i j , with i, j ∈ N , i = j, and , ∈ {0, . . . , k}, = .

The following result shows that the set of p-additive discrete GAI models on X satisfying (UNA) and (NORM) coincides with the set of p-additive k-ary capacities.

Lemma 1. [START_REF] Grabisch | Monotone decomposition of 2-additive generalized additive independence models[END_REF] Let p ∈ {1, . . . , n} and v a multichoice game on L. v is p-additive if and only if it has the form

v(x) = y∈L,0<|S(y)|≤p v y (y ∧ x), x ∈ L,
where v y : L → R with v y (0, . . . , 0) = 0.

Decomposition of a GAI model

A central issue for GAI models in general (not necessarily discrete) is how they can be written, since there are different equivalent ways to write a given GAI model. We call decomposition of U a particular way of writing U (x) under the form of a sum of terms u s (x S ), S ∈ S. We discard any constant term, as they play no role in decision making. Let us take the following example with three variables as illustration:

U (x 1 , x 2 , x 3 ) = x 1 + 2x 2 + x 3 -min(x 2 , x 3 ). ( 6
)
We immediately notice that several decompositions are possible, among which:

U (x) = u 1 (x 1 ) + u 2 (x 2 ) + u 3 (x 3 ) + u 23 (x 2 , x 3 ) = u 12 (x 1 , x 2 ) + u 23 (x 2 , x 3 ) with u 1 = u 3 = Id, u 2 = 2Id, u 23 (x 2 , x 3 ) = -min(x 2 , x 3 ), and u 12 (x 1 , x 2 ) = x 1 + 2x 2 , u 23 (x 2 , x 3 ) = x 3 -min(x 2 , x 3
). We take the following convention: a decomposition U = S∈S u S is well-formed (w-f ) if each term u S of the decomposition satisfies two conditions:

• the set S corresponds to the set of "active" variables of u S (that is, a variable such that the derivative of u S w.r.t. this variable is not identically 0).

• It cannot be further additively decomposed into terms involving a proper subset of variables:

u S = S ∈F v S
with F ⊆ 2 S \ {S}, where S is the set of active variables of v S Note that the above first decomposition is well-formed, while the second is not because

u 12 (x 1 , x 2 ) = u 1 (x 1 ) + u 2 (x 2 )
. However, this is a loose concept as many well-formed decompositions exist: consider for example x 1

u 1 (x 1 ) + αx 2 u α 2 (x 2 ) + (2 -α)x 2 + x 3 -min(x 2 , x 3 ) u α 23 (x 2 ,x 3 ) , which is well-formed for any α ∈ [0, 2].
Taking the identity max(x 2 , x 3 ) + min(x 2 , x 3 ) = x 2 + x 3 , we get a new expression:

U (x) = x 1 + x 2 + max(x 2 , x 3 ), (7)
with possible w-f decomposition

U (x) = u 1 (x 1 ) + u 2 (x 2 ) + u 23 (x 2 , x 3 ) (8)
with u 2 = Id and u 23 = max. The essential difference with previous decompositions is that here all terms are nondecreasing, instead of having a mix of nonincreasing and nondecreasing ones. Formally,

a decomposition U = S∈S u S is well-formed-monotone (w-f-m) if • each term u S is nondecreasing w.r.t.

each variable in S

• no term u S can be further additively decomposed into monotone terms involving subsets of S:

u S = S ∈F v S
with F ⊆ 2 S , S being the set of active variables in v S and v S is nondecreasing w.r.t each variable in S .

Observe that ( 8) is a w-f-m decomposition.

The distinction is important as a term u S with |S| > 1 in a w-f-m decomposition contains the sole contribution of all attributes in S, and what concerns proper subsets of S are put into other terms, similarly to what is done in an analysis of variance (ANOVA) 1 . For example, a term of the type u 12 = v 1 +v 2 +v 12 , with v 1 , v 2 , v 12 monotone is not allowed, while it is allowed in a w-f decomposition.

Suppose a decomposition in monotone (nondecreasing) terms exists for U . Then obtaining a w-f-m decomposition from it is just a matter of arrangement of the summands into terms u S . Therefore, the difficulty is rather to find a monotone decomposition (i.e., in nondecreasing terms), not to make it well-formed-monotone. In general, there may exist several monotone decompositions, and they are all the more easy to interpret as they contain less terms, which asks the question of the minimality of the decomposition, and also its uniqueness.

As many equivalent expressions of a given function U are possible, one may wonder if a term involving several variables, say, u 23 , could be eventually eliminated, and reduced to single variable terms u 2 , u 3 . The question is of importance, as a term u 23 suggests that variables x 2 and x 3 are dependent or interacting, while its absence indicates that x 2 , x 3 are independent.

To summarize the various issues raised above, the fundamental questions are:

(i) Assuming that U is nondecreasing w.r.t. each variable, is it possible to always find a monotone decomposition?

(ii) In the affirmative, is it possible to find a minimal one (in the sense of number of terms)? Is there a unique minimal monotone decomposition?

(iii) If a term involving attributes i and j is present in a w-f decomposition, is it present in every w-f decomposition? In other words, does a w-f decomposition reflects in an unambiguous way interaction between attributes?

We address all these questions in the rest of the paper, in the case of 2-additive GAI models exclusively. We begin in the next section by answering the last question, in full generality. Then the two first questions will be answered in the case of a discrete GAI model satisfying the (UNA) and (NORM) assumptions, in Sections 3.2 and 5 respectively.

1 An ANOVA decomposition of a function f :

X ⊆ R n → R can be defined as f (x) = A⊆N f A (x A ),
where the decomposition is orthogonal in the sense that, for all A ⊆ N , A = ∅, the expected value of f A w.r.t. any of its coordinate is zero. This ensures that a term f A does not contain a function of a strict subset of variables B A that could be put in f B .

Interaction and decomposition

In relation to the decomposition issue, we address the question of the presence of interacting attributes. Recall that the primary aim of GAI models is to be able to represent interaction among attributes, by considering multivariate terms u S (x S ), |S| > 1. The difficult point is that, since the decomposition is not unique, what can be concluded on the interaction of attributes?

In this subsection, we suppose that U is a 2-additive GAI model, but not necessarily discrete nor monotonic. As explained above, the presence of a term u ij (x i , x j ) in a GAI decomposition of U indicates that there is some interaction or dependence between attributes i and j. One would be tempted to think that the absence of a term u ij in the decomposition of U would then indicate that i and j are independent in some sense, and therefore that no decomposition of U would contain such a term u ij . This intuition reveals to be correct, provided a suitable definition of independence is given.

In order to introduce this definition, the notion of quaternary relation is needed. Recall that a quaternary (preference) relation * on X is a subset of (X 2 ) 2 , i.e., * compares pairs of alternatives (x, y) and (z, w) in X 2 with the following meaning: (x, y) * (z, w) if the difference of intensity of preference of x to y is at least as large as the difference of intensity of preference of z to w. As for binary relations, we introduce its symmetric part ∼ * , and the numerical representation of * amounts to finding a utility function U such that (x, y) * (z, w) if and only if U (x) -U (y) ≥ U (z) -U (w). Conditions for such a representation are known, and are called difference mesurement conditions, see, e.g., [START_REF] Krantz | Additive and polynomial representations[END_REF].

We say that attributes i and j have no interaction or are 2-independent if for every

x i , y i ∈ X i , x j , y j ∈ X j , z -ij ∈ X -ij , (x i , x j , z -ij ), (y i , x j , z -ij ∼ * (x i , y j , z -ij ), (y i , y j , z -ij ) , (9)
As a remark, this reminds the condition of weak difference independence [START_REF] Krantz | Additive and polynomial representations[END_REF]:

(x i , t -i ), (y i , t -i ) * (z i , t -i ), (w i , t -i ) ⇔ (x i , s -i ), (y i , s -i ) * (z i , s -i ), (w i , s -i ) , for any x i , y i , z i , w i ∈ X i , s, t ∈ X.
Assuming that the usual conditions of difference measurement are satisfied and that U represents * , (9) translates into

U (x i , x j , z -ij ) + U (y i , y j , z -ij ) = U (x i , y j , z -ij ) + U (y i , x j , z -ij ).
Lemma 2. Assume that U (x) = S∈S u S (x S ) and {i, j} / ∈ S. Then i, j are 2-independent.

Proof. We have

U (x) = {k}∈S u k (x k ) + {i,k}∈S k =j u ik (x i , x k ) + {j,k}∈S k =i u jk (x j , x k ) + {k, }∈S k, ∈N \{i,j} u k (x k , x ). Therefore U (x i , x j , z -ij ) -U (y i , x j , z -ij ) = u i (x i ) -u i (y i ) + {i,k}∈S k =j u ik (x i , z k ) -u ik (y i , z k ) = U (x i , y j , z -ij ) -U (y i , y j , z -ij ),
implying the 2-independence of i, j.

Recall that in a well-formed decomposition, no term u ij can be additively decomposed as v i (x i ) + v j (x j ) + c. Lemma 3. Assume that {i, j} ∈ S in a decomposition S∈S u S (x S ) of U . Then i, j are 2-independent for U if and only if u ij can be additively decomposed.

Proof. Write U = U + u ij and S = S \ {i, j}, so that S is the collection of sets in the decomposition of U . Then by Lemma 2, i, j are 2-independent for U . Therefore, 2-independence of i, j for U is equivalent to 2-independence of i, j in u ij .

If u ij can be additively decomposed, it is easy to see that i, j are 2-independent. Conversely, suppose that i, j are 2-independent. Then for any x i , y i ∈ X i , x j , y j ∈ X j , we have

u ij (x i , x j ) + u ij (y i , y j ) = u ij (x i , y j ) + u ij (x j , y j ) (10) Choose 0 i ∈ X i , 0 j ∈ X j and define v i (x i ) = u ij (x i , 0 j ) and v j (x j ) = u ij (0 i , x j ), for all x i ∈ X i , x j ∈ X j .
By letting y i = 0 i , y j = 0 j in (10), we get

u ij (x i , x j ) = v i (x i ) + v j (x j ) -u ij (0 i , 0 j ),
i.e., u ij can be additively decomposed.

The above lemmas lead to the main result of this section.

Theorem 1. Let U be a 2-additive GAI model and i, j be distinct attributes. The following are equivalent:

(i) i, j are 2-independent for U ;

(ii) There exists a well-formed decomposition of U without a term u ij ;

(iii) No well-formed decomposition of U contains a term u ij .

Proof. (iii) implies (ii) is clear. Now (ii) implies (i) by Lemma 2. Finally, as a w-f decomposition does not contain an additively decomposable term, (i) implies (iii) by Lemma 3.

Monotone decomposition of a 2-additive GAI model

The following theorem shown by [START_REF] Grabisch | Monotone decomposition of 2-additive generalized additive independence models[END_REF] establishes the existence of a monotone decomposition for discrete 2-additive GAI models.

Theorem 2. Let us consider a 2-additive discrete GAI model U satisfying (UNA) and (NORM). Then a well-formed-monotone decomposition exists.

The result yields a model in which each term is easily analyzable in terms of importance and interaction. Moreover, it is proved in [START_REF] Grabisch | Monotone decomposition of 2-additive generalized additive independence models[END_REF]) that if U is obtained through a learning procedure, the existence of a monotone decomposition reduces the number of monotonicity constraints from exponential to quadratic complexity.

The result is proved using the equivalence between discrete 2-additive GAI models satisfying assumptions (UNA) and (NORM), and 2-additive k-ary capacities, for a suitable k. The fundamental observation is that the set of 2-additive k-ary capacities forms a polytope, denoted by P k,2 , whose vertices are of support of size 2. This means that a vertex of P k,2 , seen now as a term u S in the decomposition of the GAI model, is a nondecreasing function which depends on at most 2 variables. Now, the fact that every 2-additive k-ary capacity can be written as a convex combination of the vertices, translates as follows: every 2-additive discrete GAI model can be written as a convex combination of nondecreasing terms depending of at most 2 variables. In other words, a monotone decomposition exists.

This sketch of the proof shows several things: first, there exist extremely many different monotone decompositions, some of them having a minimal number of terms. The minimal number of terms for the decomposition is the dimension of the polytope plus one (simplex), which yields nk + k 2 n 2 . In general, several minimal decompositions may exist, as we will see in Section 5. Second, it shows that the basic ingredients are the vertices of P k,2 . It is therefore necessary to find an analytical expression of all vertices, if ones wants an explicit decomposition. Vertices will be studied and identified in Section 4, while an explicit expression of a minimal monotone well-formed decomposition will be given in Section 5, for the case k = 2. The complexity of this expression tends to indicate that an explicit decomposition is out of reach for higher values of k. This is why in the next subsection, we give an approach based on linear programming, taking as input the value of U (x) for every x ∈ L.

Linear program approach

Let us suppose that a model is given under the form of values U (x) for all x ∈ L, such that U is nondecreasing in all coordinates (UNA) and, without loss of generality, that (NORM) is satisfied. Making the assumption that this corresponds to a 2-additive (discrete) GAI model, our aim is to find a well-formed-monotone decomposition, which amounts to find values u i (x i ) and u ij (x i , x j ), for all x i , x j ∈ {0, . . . , k} and distinct i, j ∈ N , such that the functions u i : {0, . . . , k} → R and u ij : {0, . . . , k} 2 → R are nondecreasing and form a well-formed-monotone decomposition. We show below that this is achieved by the following linear program (P), whose variables are the u i (x i )'s and u ij (x i , x j )'s:

Minimize {i,j}⊆N u ij (k, k) subject to u i (x i + 1) ≥ u i (x i ), ∀i ∈ N, ∀x i ∈ {0, . . . , k -1} (11) u ij (x i + 1, x j ) ≥ u ij (x i , x j ), ∀i, j ∈ N, ∀x i ∈ {0, . . . , k -1}, ∀x j ∈ {0, . . . , k} (12) u ij (x i , x j + 1) ≥ u ij (x i , x j ), ∀i, j ∈ N, ∀x i ∈ {0, . . . , k}, ∀x j ∈ {0, . . . , k -1} (13) u i (0) = 0, ∀i ∈ N (14) u ij (0, 0) = 0, ∀i, j ∈ N (15) i∈N u i (x i ) + {i,j}⊆N u ij (x i , x j ) = U (x), ∀x ∈ L (16)
By Theorem 2, if U corresponds to a 2-additive model satisfying (UNA) and (NORM), then there exists a GAI decomposition with functions u i and u ij both nondecreasing and nonnegative. Constraints ( 11)-( 13) enforce that the u i 's and u ij 's are nondecreasing.

Recall that a w-f-m decomposition cannot contain a term u ij of the form v i (x i ) + v j (x j ) + v ij (x i , x j ) + c, with v i , v j , v ij nondecreasing and v i , v j not both constant (let us call such term reducible for short). In addition, due to our assumption (NORM), v i , v j are nonnegative and c = 0. Hence, by (NORM), we impose that the smallest value of functions u i and u ij is zero -see ( 14) and ( 15). Moreover, constraint (16) imposes that the new decomposition is equal to U pointwise. Observe that ( 16) contains an exponential number of constraints (k n ).

We note that conditions ( 11)-( 15) are not sufficient to obtain a w-f-m decomposition. Consider, e.g., the function

U (x 1 , x 2 ) = 1 2k 2 x 1 x 2 + 1 2k x 1 . Then, the decomposition U (x 1 , x 2 ) = u 12 (x 1 , x 2 ) with u 12 (x 1 , x 2 ) = 1 2k 2 x 1 x 2 + 1 2k
x 1 satisfies conditions ( 11)-( 15). However, it is not a w-f-m decomposition because the term 1 2k x 1 can be put in a function depending only on the first variable, leading to the w-f-m decomposition U (x 1 , x 2 ) = u 12 (x 1 , x 2 ) + u 1 (x 1 ) with u 12 (x 1 , x 2 ) = 1 2k 2 x 1 x 2 and u 1 (x 1 ) = 1 2k x 1 . This process of getting non-reducible interaction terms cannot be obtained by a constraint in the linear program, but by minimizing the largest value of the interaction terms u ij . This ensures that all terms that depend only on a single variable shall be transferred from interaction functions u ij to the functions u i 's. In the example, u 12 (k, k) < u 12 (k, k), which yields the suboptimality of the decomposition U (x 1 , x 2 ) = u 12 (x 1 , x 2 ). One shall then minimize each term u ij (k, k), which is turned into the minimization of their sum in (P). The next result formally shows that (P) returns a w-f-m decomposition.

Theorem 3. Any optimal solution of (P) is a well-formed-monotone decomposition.

Proof. Let ((u i ) i∈N , (u ij ) {i,j}⊆N ) := U be an optimal solution of (P). Due to the above observation, it suffices to prove that no reducible term exists. Assume by contradiction that U contains a reducible term u pq = 0. Since u pq is reducible and that no constant term exists, we have u pq (x p , x q ) = v p (x p ) + v q (x q ) + v pq (x p , x q ), with v p , v q , v pq nondecreasing and nonnegative, and v p , v q not both constant (hence not both identically zero).

We define U = ((u i ) i∈N , (u ij ) {i,j}⊆N ) by

u i = u i , i = p, q u p = u p + v p , u q = u q + v q , u ij = u ij , {i, j} = {p, q}, u pq = v pq .
We have

i∈N u (x i ) + {i,j}⊆N u ij (x i , x j ) = i∈N u(x i ) + {i,j}⊆N u ij (x i , x j ),
and since v p and v q are nondecreasing, U satisfies ( 16) and (??). Now, {i,j}⊆N

u ij (k, k) = {i,j}⊆N {i,j} ={p,q} u ij (k, k) + u pq (k, k) = {i,j}⊆N {i,j} ={p,q} u ij (k, k) + u pq (k, k) + v p (k) + v q (k) > {i,j}⊆N u ij (k, k),
since v p , v q are nondecreasing and not both constant. But this contradicts the optimality of U .

It may happen that (P) has several optimal solutions, in which cases several w-f-m exist for U . Take for example

U (x 1 , x 2 , x 3 ) = 1 k max(x 1 , x 2 ) + 1 k max(x 1 , x 3 ) -1 k x 1 . The w-f-m decompositions are U (x 1 , x 2 , x 3 ) = u 12 (x 1 , x 2 ) + u 13 (x 1 , x 3 ) with u 12 (x 1 , x 2 ) = 1 k max(x 1 , x 2 ) -λ k x 1 and u 13 (x 1 , x 3 ) = 1 k max(x 1 , x 3 ) -1-λ k x 1
, where λ is any number in [0, 1]. Choosing among these decompositions would necessitate to introduce some external considerations, which may be context-dependent.

The linear program (P) aims at finding a well-formed-monotone decomposition corresponding to a given GAI model U . In practice, however, U is not given and shall be constructed from an elicitation process. It is possible to adapt (P) to this situation by incorporating the elicitation process of the GAI model. This is usually done by asking to the decision maker to compare pairs of alternatives: suppose that we are given the set {(x s , y s ) ∈ L × L : s ∈ {1, . . . , r}} meaning that for every s, alternative x s is at least as good as alternative y s for the decision maker. We obtain a new linear program called (PE) (where E stands for Elicitation):

Minimize {i,j}⊆N u ij (k, k)
subject to constraints ( 11), ( 12), ( 13), ( 14), ( 15)

i∈N u i (x s i ) + {i,j}⊆N u ij (x s i , x s j ) ≥ i∈N u i (y s i ) + {i,j}⊆N u ij (y s i , y s j ), ∀s ∈ {1, . . . , r} (17)
Constraint ( 17) says that alternative x s is at least as good as alternative y s for the twoadditive GAI model. Compared to (P), constraint ( 16) is replaced by ( 17) which does not contain any more an exponential number of inequalities.

Vertices of 2-additive GAI model

In this section, we analyze the polytope of 2-additive k-ary capacities.

Monotonicity conditions on a k-ary capacity are minimally expressed by

v(x + 1 i ) -v(x) ≥ 0, for all x ∈ L, s.t. x i < k, i ∈ N.
Using the Möbius transform, each inequality can be rewritten as

0 ≤ v(x + 1 i ) -v(x) = y≤x+1 i m v (y) - y≤x m v (y) = ∀j∈N \i,y j ≤x j y i =x i +1 m v (y), for all x ∈ L, s.t. x i < k, i ∈ N.
Let us give a more explicit expression in the case of 2-additive k-ary capacities. We obtain:

m v ( i ) + j∈S(x) x j =1 m v ( i j ) ≥ 0, (i ∈ N, x ∈ L s.t. x i < k, = 1, . . . , k). ( 18
)
Using ( 18) and ( 4), we obtain the following system of inequalities:

m v ( i ) + j∈S(x) k =1 m v ( i j ) ≥ 0, (i ∈ N, x ∈ L s.t. x i = 0, = 1, . . . , k) i∈N k =1 m v ( i ) + {i,j}⊆N k =1 m v ( ij ) + i,j∈N i =j , ∈L\{0} = m v ( i j ) = 1.
This system defines P k,2 , the polytope of 2-additive k-ary capacities. Our aim is to study the vertices of this polytope. The following results are useful and have been shown in [START_REF] Grabisch | Monotone decomposition of 2-additive generalized additive independence models[END_REF].

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

Theorem 5. Consider a 2-additive k-ary capacity v which is 0-1-valued. Then the support of v has size at most 2.

We are now in position to determine all vertices of P k,2 , for a fixed k ∈ N. By Theorem 5, we know that any vertex has a support of at most two elements, hence w.l.o.g. we can restrict to elements 1 and 2. By Theorem 4, finding all vertices with support {1, 2} amounts to finding all 0-1 k-ary capacities which are linear combinations of unanimity games µ x with S(x) ⊆ {1, 2}. By analogy with classical simple games, a coalition x ∈ L is winning for v if v(x) = 1. Minimal winning coalitions are those which are minimal w.r.t. the order ≤ on L, and therefore they form an antichain in L. We show several properties of minimal winning coalitions.

Lemma 4. Let v be a 0-1-valued k-ary capacity.

(i) x is a minimal winning coalition if and only if m v (x) = 1 and m v (y) = 0 for all y < x.

(ii) S(v) ⊆ {1, 2} if and only if its minimal winning coalitions have support included in {1, 2}.

(iii) If |S(v)| = 2, there are at most k + 1 distinct minimal winning coalitions.

(iv) Suppose that S(v) ⊆ {1, 2}. Denote by x 1 , . . . , x q the minimal winning coalitions of v, arranged such that x 1 1 < x 2 1 • • • < x q 1 . Then m v (x ) = 1 for all = 1, . . . , q, m v (x ∨ x +1 ) = -1 for = 1, . . . , q -1, and m v (x) = 0 otherwise.

Proof. (i) Suppose m v (x) = 1 and m v (y) = 0 for all y < x. Then clearly x is a minimal winning coalition. Conversely, suppose first that there exists y < x such that m v (y) = 0, and choose a minimal y with this property. Then v(y) = 0, a contradiction. Then, suppose there is no such y < x but m v (x) = 1. Then v(x) = m v (x) = 1, again a contradiction.

(ii) Suppose there exists a minimal winning coalition x such that S(x) ⊆ {1, 2}. Then by (i), the support of v is not included in {1, 2}.

Conversely, suppose that there exists x ∈ L with m v (x) = 0 and S(x) ⊆ {1, 2}.

Choose a minimal such x. Use (5) to compute the Möbius transform m v (x), we can see that

m v (x) ∈ {-1, 0, 1}. Observe that m v (x) = -1 is impossible, because this would yield v(x) = -1. Then m v (x) = 1 = v(x)
, proving by (i) that x is a minimal winning coalition.

(iii) Take x being a minimal winning coalition, and suppose w.l.o.g. that S(x) ⊆ {1, 2}.

Observe that any other minimal winning coalition y must satisfy x 1 = y 1 , otherwise one of the two would not be minimal. Hence, there can be at most k + 1 distinct minimal winning coalitions.

(iv) By uniqueness of the decomposition, it suffices to check that the computation of v by v(x) = y≤x m v (y) works. By construction, any x ∈ L is greater or equal to a subset of consecutive minimal winning coalitions, say, x i+1 , x i+2 , . . . , x i+j , so that there are j -1 pairs (x i+ , x i+ +1 ), = 1, . . . , j -1. The result follows by the definition of m v .

Remark 1. The various properties in the Lemma permit to say that the vertices of P k,2 with support included into {1, 2} are in bijection with the antichains (which are of size at most k + 1) in the lattice (k + 1) 2 . Moreover, their Möbius transform is known.

Lemma 5. Let k ∈ N. Denote by κ( ) the number of antichains of elements in the lattice (k + 1) 2 , = 1, . . . , k + 1. Then

κ( ) = k + 1 2 .
Moreover, the total number of antichains on (k + 1)

2 is k+1 =1 κ( ) = 2k + 2 k + 1 -1.
Proof. Let x ∈ (k + 1) 2 , with coordinates (x 1 , x 2 ). Considering that the 1st coordinate axis is on the left, we say that y is on the left of x if y 1 > x 1 and y 2 < x 2 . Let us denote by F 1 (x 1 , x 2 ) the number of points y to the left of x (i.e., {x, y} is an antichain). We obtain

F 1 (x 1 , x 2 ) = x 2 -1 y 2 =0 k y 1 =x 1 +1 1 = x 2 (k -x 1 ).
Note that κ(1) = F 1 (-1, k + 1) since any point in (k + 1) 2 is to the left of (-1, k + 1). Define F 2 (x 1 , x 2 ) as the number of antichains {y, z} to the left of x, with z to the left of y, i.e., {x, y, z} forms an antichain. We obtain

F 2 (x 1 , x 2 ) = x 2 -1 y 2 =1 k-1 y 1 =x 1 +1 F 1 (y 1 , y 2 ).
(note that y 2 = 0 and y 1 = k are impossible because z is on the left of y). Again remark that κ(2) = F 2 (-1, k + 1). More generally, the number of antichains of elements to the left of x is

F (x 1 , x 2 ) = x 2 -1 y 2 = -1 k-+1 y 1 =x 1 +1 F -1 (y 1 , y 2 ) (1 ≤ ≤ k + 1),
and κ( ) = F (-1, k + 1). We show by induction that

F (x 1 , x 2 ) = x 2 k -x 1 . (19)
The result has already been verified for = 1. We assume it is true up to some integer 1 ≤ ≤ k and prove it for + 1. We have

F +1 (x 1 , x 2 ) = x 2 -1 y 2 = k- y 1 =x 1 +1 F (y 1 , y 2 ) = x 2 -1 y 2 = k- y 1 =x 1 +1 y 2 k -y 1 = x 2 -1 y 2 = y 2 k- y 1 =x 1 +1 k -y 1 = x 2 + 1 k -x 1 + 1 ,
where we have used the fact that (see (Gradshteyn and Ryzhik, 2007, §0.151))

m k=0 n + k n = n + m + 1 n + 1 .
Hence ( 19) is proved. It remains to compute the total number of antichains. Using the fact that (see (Gradshteyn and Ryzhik, 2007, §0.157))

n k=0 n k 2 = 2n n ,
we find the desired result.

Observing that the antichain {0 N } does not correspond to a normalized capacity, we obtain directly from Lemma 5 and previous considerations the following result. Theorem 6. Let k ∈ N and consider the polytope P k,2 . The following holds. (i) For any i ∈ N , the number of vertices with support {i} is k.

(ii) For any distinct i, j ∈ N , the number of vertices with support included in {i, j} is 2k + 2 k + 1 -2.

(iii) The total number of vertices of

P k,2 is 2k + 2 k + 1 -2 n(n -1) 2 -kn(n -2).
We apply now the above general results to the case of 2-additive 2-ary capacities. The polytope P 2,2 of 2-additive 2-ary capacities is defined by the following set of inequalities (monotonicity conditions are obtained from (18), superscript v is omitted), defined for all i ∈ N :

m(1 i ) + j∈A m(1 ij ) + j∈B m(1 ij ) + m(1 i 2 j ) ≥ 0, A ⊆ N \ i, B ⊆ N \ (A ∪ i) (20) m(2 i ) + j∈A m(2 i 1 j ) + j∈B m(2 i 1 j ) + m(2 ij ) ≥ 0, A ⊆ N \ i, B ⊆ N \ (A ∪ i) (21) 2 =1 i∈N m( i ) + 2 =1 {i,j}⊆N m( ij ) + i,j∈N i =j m(1 i 2 j ) = 1. (22)
Note that for n = 3, this yields 54 inequalities for monotonicity.

By Remark 1, we know that the vertices of 2-additive 2-ary capacities with support included into {i, j} are in bijection with the antichains in {0, 1, 2} {i,j} . Then, by using Lemma 4 (iv) we obtain the family of vertices of P 2,2 (see Figure 1):

µ 1 i , µ 2 i , µ 1 ij , µ 2 ij , µ 1 i 2 j ,
and,

µ 1 i + µ 1 j -µ 1 ij := µ -i-j 1 ij (23) µ 1 ij + µ 2 j -µ 1 i 2 j := µ -i-j 1 i 2 j (24) µ 1 i + µ 2 j -µ 1 i 2j := µ -i-2j 1 i 2 j (25) µ 1 i 2 j + µ 2 i -µ 2 ij := µ -i-2j 2 ij (26) µ 2 i + µ 2 j -µ 2 ij := µ -2i-2j 2 ij (27) µ 1 i 2 j + µ 2 i 1 j -µ 2 ij := µ -i-j 2 ij (28) µ 2 i + µ 2 j + µ 1 ij -µ 2 i 1 j -µ 2 j 1 i := µ ∧∧ ij . (29)
Note that for n = 3, this yields 48 vertices. 0 Remark 2. Some of the above games are conjugate of unanimity games. Indeed,

1 i 2 i 1 j 2 j 1 µ 1 i 0 1 i 2 i 1 j 2 j 1 µ 1 j 0 1 i 2 i 1 j 2 j 1 µ 1 ij 0 1 i 2 i 1 j 2 j 1 µ 2 i 1 j 0 1 i 2 i 1 j 2 j 1 µ 2 ij 0 1 i 2 i 1 j 2 j 1 1 -1 µ -i-j 1 ij 0 1 i 2 i 1 j 2 j 1 1 -1 µ -i-j 1 i 2 j 0 1 i 2 i 1 j 2 j 1 1 -1 µ -i-2j 1 i 2 j 0 1 i 2 i 1 j 2 j 1 1 -1 µ -i-2j 2 ij 0 1 i 2 i 1 j 2 j 1 1 -1 µ -2i-2j 2 ij 0 1 i 2 i 1 j 2 j 1 1 -1 µ -i-j 2 ij 0 1 i 2 i 1 j 2 j 1 1 1 -1 -1 µ ∧∧ ij
µ 1 ij (x) = 1 -µ 1 ij (2 N -x) = µ -2i-2j 2 ij (x) µ 1 i 2 j (x) = 1 -µ 1 i 2 j (2 N -x) = µ -j-2i 1 j 2 i (x) µ 2 ij (x) = 1 -µ 2 ij (2 N -x) = µ -i-j 1 ij (x),
as it can be checked.

Explicit decomposition for 2-ary capacities

The linear programming approach provides a way to obtain a well-formed-monotone decomposition. In this section, we exhibit for any v ∈ P 2,2 an explicit decomposition as a convex combination of the vertices of P 2,2 . Take any v ∈ P 2,2 , and let us write its decomposition on the basis of 2-ary unanimity games:

v = i∈N (m(1 i )µ 1 i + m(2 i )µ 2 i ) + {i,j}⊆N (m(1 ij )µ 1 ij + m(2 ij )µ 2 ij ) + i,j∈N i =j m(1 i 2 j )µ 1 i 2 j . ( 30
)
As explained in Section 3.2, a minimal decomposition should contain at most 2n + 4 n 2 = 2n 2 terms.

Observe that if all the coefficients are nonnegative, we are done as (30) becomes a convex combination, because of the normalization v(1 N ) = 1. Suppose then that some coefficients are negative: this can happen only to the coefficients m(1 ij ), m(2 ij ), m(1 i 2 j ). Our strategy is to rewrite all terms m(x)µ x with m(x) < 0 using vertices which are not unanimity games (nontrivial vertices), by formulas ( 23) to (29). These substitutions must be done so that in every case the overall expression is a decomposition with nonnegative coefficients, hence convex. In addition, we want to minimize the number of terms in the decomposition, using nontrivial vertices only for substitution of terms with negative coefficients (recall that the minimal number of terms is the dimension plus one, hence 2n 2 ).

To achieve this goal, the general idea is as follows. We use the notation ↓ x to denote the principal ideal of x, i.e., ↓ x = {y ∈ L|y ≤ x}. We introduce the following multichoice games:

v ↓x = y≤x m(y)µ y
for every x of the form 1 ij , 2 i 1 j , 2 ij , and where m is the Möbius transform of v, as well as those of the form v ↓x∪↓y = z≤x or z≤y m(z)µ z .

Then, for every maximal x such that m(x) < 0 (i.e., no y ≥ x is s.t. m(y) < 0), make adequate substitutions so that v ↓x is decomposed only with nonnegative coefficients. If it happens that m(x) < 0, m(y) < 0 with x, y maximal and ↓ x ∩ ↓ y = ∅, and the elements in the intersection are either of the form 1 i or 2 i , just subtract m(1 i )µ 1 i (or m(2 i )µ 2 i ).

The case where the intersection contains 1 ij requires special care and needs to consider v ↓x∪↓y . Then finally, add all missing terms m(x)µ x .

We prove that the above method works and explain it in detail. For any 2-ary capacity v (L = {0, 1, 2} N ), we denote by [v] a monotone decomposition of v as a linear combination of vertices of P 2,2 . The decomposition will be monotone if it is a decomposition with nonnegative coefficients (hence a convex combination). The decomposition is minimal if it contains at most 2n 2 terms. The elements in L of support at most of size 2 are of the form 1 i , 2 i , 1 ij , 2 i 1 j , 2 ij . For x, y ∈ L, ↓ x ∩ ↓ y is nonempty for the following pairs only (excluding the case ↓ y ⊆ ↓ x) (i, j, k denote three distinct elements of N ):

(2 ij , 2 ik ), (2 ij , 2 i 1 k ), (2 ij , 1 i 2 k ), (2 ij , 1 ik ), (2 i 1 j , 2 i 1 k ), (2 i 1 j , 1 i 2 k ), (2 i 1 j , 1 j 2 k ), (1 ij , 1 ik ), (2 i 1 j , 2 j 1 i ). ( 31
)
Observe that, except for the last case, the intersection ↓ x ∩ ↓ y reduces either to 1 i or 2 i , 1 i . For the last case, the intersection is 1 ij .

In the Appendix, we write monotone decompositions of v ↓x , for x of the form 1 ij , 2 i 1 j , 2 ij (because only these elements may have a negative Möbius transform). Since the case (2 i 1 j , 2 j 1 i ) requires special care, we have to find a monotone decomposition of v ↓2 i 1 j ∪↓2 j 1 i .

Finally, a minimal monotone decomposition of v is obtained by the following procedure:

Minimal Monotone Decomposition. 1. Find the maximal elements of the set {x ∈ L | m(x) < 0}; discard from them all the pairs of the form (2 i 1 j , 2 j 1 i ), and denote by x 1 , . . . , x q the resulting elements, and by ↓ x 1 , . . . , ↓ x q the corresponding downsets.

2. For every discarded pair (2 i 1 j , 2 j 1 i ) in Step 1, build the downset ↓ 2 i 1 j ∪ ↓ 2 j 1 i ; denote by X 1 , . . . , X r all these downsets.

3.

Find all nonempty pairwise intersections among the downsets ↓ x 1 , . . . , ↓ x q , X 1 . . . , X r , denote their elements by y 1 , . . . , y s (they are necessarily of the form 1 i or 2 i ).

For every y

, = 1, . . . , s, build K = {x | ↓ x y } ∪ {X | X y }.
5. The decomposition is then given by

[v] = q =1 [v ↓x ]+ r =1 [v X ]- s =1 (|K |-1)m(y )µ y + x∈L\ q =1 ↓x ∪ r =1 ↓X m(x)µ x , (32
) where the adequate substitutions have to be done for [v ↓x ], [v X ], using formulas (34) to (50).

Theorem 7. The decomposition given by ( 32) is monotone and minimal.

Proof. 1. It is easy to see that (32) is a decomposition, since it is a rewriting of (30) where all redundant terms from the intersections have been subtracted.

2. We prove that the decomposition is monotone. The sum of monotone decompositions is evidently monotone. Also, observe that the last term in (32) has only nonnegative coefficients, because all x ∈ L s.t. m(x) < 0 are in the downsets ↓ x 1 , . . . , ↓ x q , X 1 . . . , X r . Therefore it remains to prove that [v ]

:= q =1 [v ↓x ]+ r =1 [v X ]-s =1 (|K |-1
)m(y )µ y is monotone. Consider y = 1 i (the reasoning is much the same for y = 2 i ). The term µ 1 i is present in each of the decompositions [v ↓x ] for x ∈ K and [v X ] for X ∈ K , and only in these ones, with coefficients either m(1 i ), (m(1 ij )+m(1 i )) or (m(2 j 1 i )+m(1 ij )+m(1 i )) (see Formulas (34) to ( 50)). Now, each such x (resp., X ) depends only on i and another j ∈ N (resp., another k ), and all the elements i, j , k for all are distinct. Hence the coefficient of µ 1

i in [v ] is of the form m(1 i ) + j∈A m(1 ij ) + j∈B (m(1 ij ) + m(1 i 2 j ))
which is nonnegative by (20).

3. We prove that the decomposition is minimal. This amounts to showing that the decomposition has at most 2n 2 terms in every case. As shown above, the decompositions

q =1 [v ↓x ] + r =1 [v X ] -s =1 (|K | -1)m(y )µ y and q =1 [v ↓x ] + r =1 [v X ]
have exactly the same number of terms. Hence, it suffices to prove the minimality of each decomposition [v ↓x ] and [v X ] for proving minimality of [v]. The decomposition of [v ↓x ] is minimal if the number of terms is the number of elements in ↓ x , and similarly for [v X ]. We find that ↓ 1 ij has 3 terms, ↓ 2 i 1 j has 4 terms, ↓ 2 i 1 j ∪ ↓ 2 j 1 i has 7 terms, and ↓ 2 ij has 8 terms. It can be checked through formulas ( 34) to (50) that each decomposition has the required number of terms.

Example 1. Take n = 3, and suppose that the following elements have a negative Möbius transform: 220, 110, 021 and 012. The maximal elements are x 1 = 220, and 021 and 012 which have to be discarded while we have to consider the downset X 1 =↓ 021∪ ↓ 012. The elements in intersection are 020 and 010, both in ↓ x 1 and X 1 . The formula is

[v] = [v ↓220 ] + [v ↓021∪↓012 ] -m(020)µ 020 -m(010)µ 010 + m(202)µ 202 + m(022)µ 022 +m(102)µ 102 + m(201)µ 201 + m(101)µ 101 , now, [v ↓220
] is given by either (45), or (47) or (49), and [v ↓021∪↓012 ] is given by either (39), or (40) or (41).

The following example illustrates the fact, explained in footnote 2 in the Appendix, that the decomposition, although minimal, is not unique.

Conclusion

In this paper, we derived several results we consider as fundamental regarding the problem of the decomposition of a GAI model. Our first finding is the notion of well-formed and well-formed-monotone decomposition. The former permits to relate bi-variate terms with preferential dependence, and solves the ambiguity problem of how combining terms of one or several variables. The latter is a much more restricted notion (although not enough strong to impose uniqueness: but examples given in the paper shows that this cannot be reached in general), which is probably the best way to decompose a GAI model, in terms of interpretability and complexity.

Monotone (well-formed) decompositions are closely related, at least in the 2-additive case, to the vertices of the polytope of 2-additive k-ary capacities. Our paper gives a complete description of these vertices, which independently of the context of this paper, is a result of general interest in combinatorial optimization and discrete mathematics. Lastly, we have shown that obtaining an explicit monotone decomposition is not an easy task, even for the simple case k = 2, since its complete expression is amazingly more complex than the decomposition for classical (k = 1) capacities.

A natural continuation of this work would be to address the case of p-additive models with p greater than 2. If the relation between preferential dependence and multivariate terms in a well-formed decomposition is expected to be easily generalized, the existence of a monotone decomposition will certainly reveal to be much more difficult to obtain, as it is known that vertices of the polytope of p-additive capacities for p > 2 has a much more complex (and yet unknown) structure.

• Case 4: Suppose m(2 ij ) < 0.

-Case 4a: m(2 i 1 j ) < 0 and m(2 j 1 i ) < 0. We make the substitution

m(2 ij )µ 2 ij = -m(2 ij ) µ -2i-2j 2 ij -µ 2 i -µ 2 j which yields v ↓2 ij = m(2 ij )µ 2 ij +v ↓2 i 1 j ∪↓2 j 1 i = -m(2 ij ) µ -2i-2j 2 ij -µ 2 i -µ 2 j +v ↓2 i 1 j ∪↓2 j 1 i . (42)
It remains to substitute in the above the expression of v ↓2 i 1 j ∪↓2 j 1 i by ( 38) to (41) successively. Observe that only the coefficients of µ 2 i , µ 2 j are affected, and they are changed m(2 ij ) + m(2 i 1 j ) + m(2 i ) and m(2 ij ) + m(2 j 1 i ) + m(2 j ) respectively, which are nonnegative.

-Case 4b: m(2 i 1 j ) < 0 and m(2 ij ) + m(2 j 1 i ) ≥ 0. We make the substitution

m(2 ij )µ 2 ij = -m(2 ij ) µ -2j-i 2 ij -µ 2 i -µ 2 j 1 i which yields v ↓2 ij = -m(2 ij ) µ -2j-i 2 ij -µ 2 i -µ 2 j 1 i + v ↓2 i 1 j + m(2 j 1 i )µ 2 j 1 i + m(2 j )µ 2 j = v ↓2 i 1 j + |m(2 ij )|µ -2j-i 2 ij + (m(2 j 1 i ) + m(2 ij ))µ 2 j 1 i + m(2 j )µ 2 j + m(2 ij )µ 2 i . (43)
It remains to substitute in the above the expression of v ↓2 i 1 j by ( 35) to (37) successively. Observe that only the coefficient of µ 2 i is affected.

-Case 4c: m(2 i 1 j ) < 0, m(2 j 1 i ) ≥ 0 and m(2 ij ) + m(2 j 1 i ) < 0. We make the substitution

m(2 ij )µ 2 ij = m(2 j 1 i ) µ -2j-i 2 ij -µ 2 i -µ 2 j 1 i +(-m(2 ij )-m(2 j 1 i )) µ -2i-2j 2 ij -µ 2 i -µ 2 j which yields v ↓2 ij = m(2 j 1 i ) µ -2j-i 2 ij -µ 2 i -µ 2 j 1 i + (-m(2 ij ) -m(2 j 1 i )) µ -2i-2j 2 ij -µ 2 i -µ 2 j + v ↓2 i 1 j + m(2 j 1 i )µ 2 j 1 i + m(2 j )µ 2 j = v ↓2 i 1 j + m(2 j 1 i )µ -2j-i 2 ij + (-m(2 ij ) -m(2 j 1 i ))µ -2i-2j 2 ij + m(2 ij )µ 2 i + (m(2 ij ) + m(2 j 1 i ) + m(2 j ))µ 2 j . (44)
It remains to substitute in the above the expression of v ↓2 i 1 j by ( 35) to (37) successively. Observe that only the coefficient of µ 2 i is affected.

-Case 4d: m(2 ij ) + m(2 i 1 j ) ≥ 0 and m(2 ij ) + m(2 j 1 i ) ≥ 0. We make the substitution m(2 ij )µ

2 ij = -m(2 ij ) µ -i-j 2 ij -µ 2 i 1 j -µ 2 j 1 i which yields v ↓2 ij = -m(2 ij ) µ -i-j 2 ij -µ 2 i 1 j -µ 2 j 1 i + v ↓2 i 1 j + m(2 j 1 i )µ 2 j 1 i + m(2 j )µ 2 j = v ↓2 i 1 j + |m(2 ij )|µ -i-j 2 ij + m(2 ij )µ 2 i 1 j + (m(2 j 1 i ) + m(2 ij ))µ 2 j 1 i + m 2j µ 2j .
We have two subcases:

Figure 1 :

 1 Figure 1: Vertices of 2-additive 2-ary capacities. In red: an antichain in {0, 1, 2} {i,j} . Values in blue indicate the Möbius transform of the corresponding vertex.

Example 2 .

 2 Take n = 3, and suppose that m(210) < 0 (with m(110) + m(210) ≥ 0 and m(010) + m(210) ≥ 0). Consider the vertices v 1 210 = µ 200 + µ 010 -µ 210 and v 2 210 = µ 200 + µ 110 -µ 210 . The formula of v (we replace µ 210 by µ 200 + µ 010 -v 1 210 ) is v = m(110)µ 110 + m(220)µ 220 + |m(210)|v 1 210 + m(200) + m(210) µ 200 + m(010) + m(210) µ 010 + m(120)µ 120 + m(101)µ 101 + m(202)µ 202 + m(201)µ 201 + m(102)µ 102 + m(011)µ 011 + m(022)µ 022 + m(021)µ 021 + m(012)µ 012 + m(100)µ 100 + m(020)µ 020 + m(001)µ 001 + m(002)µ 002 . By using µ 210 = µ 200 + µ 110 -v 2 210 , an equivalent expression is v = m(110) + m(210) µ 110 + m(220)µ 220 + |m(210)|v 2 210 + m(200) + m(210) µ 200 + m(010)µ 010 + m(120)µ 120 + m(101)µ 101 + m(202)µ 202 + m(201)µ 201 + m(102)µ 102 + m(011)µ 011 + m(022)µ 022 + m(021)µ 021 + m(012)µ 012 + m(100)µ 100 + m(020)µ 020 + m(001)µ 001 + m(002)µ 002 .

This is not the only way to proceed. The substitution with µ -2i-j 2i1j can be done as well, yielding a branching with the condition m(1 ij ) + m(2 i 1 j ) ≥ 0 or < 0 and a different expression for[v ↓2i1j ]. This is illustrated in Example 1.

Appendix: Monotone decompositions of v ↓x , for x of the form 1 ij , 2 i 1 j , and 2 ij

• Case 1: Suppose m(1 ij ) < 0. We make the substitution

which yields

• Case 2: Suppose m(2 i 1 j ) < 0 and m(2 j 1 i ) ≥ 0.

-Case 2a: m(1 ij ) < 0. We make the substitution

which yields, combined with (33):

We make the substitution

• Case 3: Suppose m(2 i 1 j ) < 0 and m(2 j 1 i ) < 0. Then the intersection ↓ 2 i 1 j ∩ ↓ 2 j 1 i contains 1 ij , so that we need a monotone decomposition for v ↓2 i 1 j ∪↓2 j 1 i .

-Case 3a: m(1 ij ) < 0. We make the substitution

which yields, together with (33)

As above, we have two cases, which yield:

Distinguishing the two cases yields, assuming m(

In all formulas (34) to (50), it can be checked using (20) to ( 22) that all coefficients are nonnegative, hence they are indeed monotone decompositions.