Pedro Miranda
email: pmiranda@mat.ucm.es

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

An algorithm for finding the vertices of the k-additive monotone core

Keywords: Polyhedra, capacities, k-additivity, dominance, core

Given a capacity, the set of dominating k-additive capacities is a convex polytope called the k-additive monotone core; thus, it is defined by its vertices. In this paper we deal with the problem of deriving a procedure to obtain such vertices in the line of the results of Shapley and Ichiishi for the additive case. We propose an algorithm to determine the vertices of the n-additive monotone core and we explore the possible translations for the k-additive case.

Introduction

One of the main problems of cooperative game theory is to define a solution of a game v, that is, supposing that all players join the grand coalition N, an efficient pay-off vector or pre-imputation to each player represents a sharing of the total worth of the game v(N). In the case of finite games of n players, a pre-imputation can be written as a n-tuple (x 1 ,...,x n ) such that n i=1 x i = v(N). Of course, some rationality criterion should prevail when defining the sharing.

In this respect, the core is perhaps the most popular solution of a game. It is defined as the set of pre-imputations x on N such that i∈A x i ≥ v(A), ∀A ⊆ N, A = ∅ and n i=1

x i = v(N).
It is a well-known fact that the core is nonempty if and only if the game is balanced [START_REF] Bondareva | Some applications of linear programming to the theory of cooperative games[END_REF]. For games with an empty core, it is necessary to give an alternative solution. In this sense, many 1 possibilities have been proposed in the literature, as the dominance core stable sets, Shapley index, Banzhaf index, the ǫ-core, the kernel, the nucleolus, etc. (see e.g. [START_REF] Driessen | Cooperative Games[END_REF]).

On the other hand, Grabisch has defined in [START_REF] Grabisch | Alternative representations of discrete fuzzy measures for decision making[END_REF] the concept of k-additive capacities (capacities are monotone games). These capacities generalize the concept of probability and they fill the gap between probabilities and general capacities. Moreover, as they are defined in terms of the Möbius transform and this transform can be applied to the characteristic function of any game (not necessarily monotone), the concept of k-additivity can be extended to games as well.

In a previous paper [START_REF] Miranda | k-balanced games and capacities[END_REF] we have defined the so-called k-additive core. The basic idea is to remark that an imputation is nothing else than an additive game and, if the core is empty, we may allow to search for games more general than additive ones, namely k-additive games, dominating the game. We have presented a generalization of the concept of balanced games, the k-balanced games; these games are those admitting a dominating k-additive game and no dominating (k -1)-additive game. In that paper it is also defined a generalization of the concept of pre-imputation, the k-imputation; from a k-imputation, we have proposed a procedure to define a classical pre-imputation based on the pessimistic criterion.

In [START_REF] Miranda | k-balanced games and capacities[END_REF] we have seen that for general games, any game is either balanced or 2-balanced. Moreover, while the core is a polytope whose vertices have been obtained by Shapley [START_REF] Shapley | Cores of convex games[END_REF] and Ichiishi [START_REF] Ichiishi | Super-modularity: Applications to convex games and to the Greedy algorithm for LP[END_REF] for convex games, the 2-additive core is not a polytope but an unbounded convex polyhedron [START_REF] Grabisch | On the vertices of the k-additive core[END_REF].

On the other hand, when dealing with capacities, it makes sense to study the k-additive monotone core, that consists in the set of capacities dominating the capacity; it can be easily seen that the k-additive monotone core is a convex polytope, whence it can be described through its vertices. The aim of this paper is to study these vertices.

Moreover, there are other fields in which it is interesting to find the set of probabilities dominating a capacity. For instance, Dempster [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF] and Shafer [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] have proposed a representation of uncertainty based on a "lower probability" or "degree of belief", respectively, to every event. Their model needs a lower probability function, usually non-additive but having a weaker property: it is a belief function [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. This requirement is perfectly justified in some situations (see [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF]). The general form of lower probabilities has been studied by several authors (see e.g. [START_REF] Walley | Towards a frequentist theory of upper and lower probability[END_REF][START_REF] Wolfenson | Bayes-like decision making with upper and lower probabilities[END_REF]). Moreover, in many decision problems, in which we have not enough information, decision makers often feel that they are only able to assign an interval value for the probability of events. In other words, they do not know the real probability distribution but there exists a set of probabilities compatible with the available information. Let us call this set of all compatible probabilities P 1 and let us define µ := inf P ∈P 1 P ; then, µ is a capacity (but not necessarily a belief function [START_REF] Walley | Coherent lower (and upper) probabilities[END_REF]); µ is called "coherent lower probability", and it is the natural "lower probability function". Of course, if P ′ is a probability measure dominating µ, it is clear that E P ′ (f ) ≥ f dµ, for any function f ,w h e r e fdµ represents Choquet integral [START_REF] Choquet | Theory of capacities[END_REF]. Chateauneuf and Jaffray use this fact and that µ ≤ P, ∀P ∈P 1 in [START_REF] Chateauneuf | Some characterizations of lower probabilities and other monotone capacities through the use of Möbius inversion[END_REF] to obtain an easy method for computing a lower bound of inf P ∈P 1 E P (f )w h e nµ satisfies some additional conditions (namely µ is 2-monotone). Their method is based on obtaining the set of all probability distributions dominating µ.T h es a m e can be done for obtaining an upper bound. In this case, we can find a similar motivation for studying the set of all k-additive capacities dominating a capacity.

The paper is organized as follows: In next section we give the basic concepts about k-additive capacities and about the set of dominating probabilities. Section 3 is devoted to characterize the vertices for the n-additive case and, in Section 4, we deal with possible generalizations for the k-additive case. In Section 5 we outlined the case of dominated k-additive capacities. We finish with the conclusions and open problems.

2B a s i c c o n c e p t s

We will use the following notation throughout the paper: we suppose a finite universal set with n elements, N = {1, ..., n}. Subsets of N are denoted by capital letters A, B, and so on. The set of subsets of N is denoted by P(N), while the set of subsets whose cardinality is less or equal than k is denoted by P k (N).

Definition 1. [21]

A game over N is a mapping v :

P(N) → R (called characteristic func- tion) satisfying v(∅)=0.
If, in addition, 1. v satisfies v(A) ≤ v(B) whenever A ⊆ B, the game v is said to be monotone;

2. v satisfies v(A ∪ B)=v(A)+v(B) whenever A, B ⊆ N, A ∩ B = ∅,
the game is said to be additive;

3. v satisfies v(A ∪ B)+v(A ∩ B) ≥ v(A)+v(B)
, for all A, B ⊆ N, the game is said to be convex.

From the point of view of Game Theory, for any A ⊆ N, the value v(A) represents the minimum asset the coalition of players A will win if the game is played, whatever the remaining players may do, i.e., v(A) is the payoff that coalition A can guarantee for itself. We will denote by G(N) the set of all games on N. Definition 2. A non-additive measure [START_REF] Denneberg | Non-additive measures and integral[END_REF] or capacity [START_REF] Choquet | Theory of capacities[END_REF] or fuzzy measure [START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF] µ over N is a monotone game with µ(N)=1.

Consider a monotone game different from the trivial game defined by v(A)=0 , ∀A ⊆ N.I n this case, we can divide all the values of v by v(N) so that we obtain a new game µ equivalent to v. Then, µ is a capacity and we conclude that any monotone game can be equivalently represented by a capacity. Observe that the set of all capacities on N is a convex polytope, that we will denote FM(N).

There are other set functions that can be used to equivalently represent a game. We will need in this paper the so-called Möbius transform. Definition 3. [START_REF] Rota | On the foundations of combinatorial theory I. Theory of Möbius functions[END_REF][START_REF] Harsanyi | A simplified bargaining model for the n-person cooperative game[END_REF] Let v be a game on N.T h eMöbius transform (or dividends)o fv is a set function on N defined by

m v (A):= B⊆A (-1) |A\B| v(B), ∀A ⊆ N.
The Möbius transform given, the original characteristic function can be recovered through the Zeta transform [START_REF] Chateauneuf | Some characterizations of lower probabilities and other monotone capacities through the use of Möbius inversion[END_REF]:

v(A)= B⊆A m v (B). (1)
The value m(A) represents the strength of subset A in any coalition in which it appears.

Let us turn to the concept of k-additivity, originally defined for capacities. In order to define a capacity, 2 n -2 values are necessary; the number of coefficients grows exponentially with n, and so does the complexity of the problem. This drawback reduces considerably the practical use of capacities. Then, some subfamilies of capacities have been defined in an attempt to reduce the complexity. Examples of subfamilies include the λ-measures [START_REF] Sugeno | A model of learning based on fuzzy information[END_REF], the k-intolerant capacities [START_REF] Marichal | Tolerant or intolerant character of interacting criteria in aggregation by the Choquet integral[END_REF], the k-additive capacities [START_REF] Grabisch | k-order additive discrete fuzzy measures[END_REF], the p-symmetric capacities [START_REF] Miranda | p-symmetric fuzzy measures[END_REF], the decomposable capacities [START_REF] Dubois | A class of fuzzy measures based on triangular norms[END_REF], etc. In this paper we will use k-additive capacities.

Definition 4. [10]

A game v is said to be k-order additive or k-additive for short if its Möbius transform vanishes for any A ⊆ N such that |A| >k,and there exists at least one subset A of exactly k elements such that m(A) =0.

Additive games are 1-additive games, and so probability measures are 1-additive capacities; thus, k-additive capacities generalize probability measures. More about k-additive capacities can be found, e.g., in [START_REF] Grabisch | k-order additive discrete fuzzy measures and their representation[END_REF]. We will denote by

FM k (N) (resp. G k (N)) the set of all k ′ -additive capacities (resp. games) with k ′ ≤ k. Observe that FM k (N) is a subpolytope of FM(N). Notice also that FM n (N)=FM(N).
Let us now introduce the concept of k-additive monotone core.

Definition 5. Let v, v * be games in G(N). We say that v * dominates v,a n dw ed e n o t ei t v * ≥ d v,i fa n do n l yi f v * (A) ≥ v(A), ∀A ⊂ N, v * (N)=v(N).
Definition 6. Let v be a game. We say that a vector :

x =( x 1 ,...,x n ) ∈ R n is a pre- imputation for v if it satisfies n i=1 x i = v(N).
Remark 1. For any x ∈ R n , it is convenient to use the notation x(A):= i∈A x i , for all A ⊆ N, with the convention x(∅)=0.T h u s ,x identifies with an additive game.

The value x i is the asset player i receives when sharing v(N). Suppose that the pre-imputation satisfies x(A) ≥ v(A), for all A ⊆ N. Then, no subcoalition of players has interest to form, since they will receive more by the sharing (x 1 ,...,x n ). In other words, any such (x 1 ,...,x n )i sa possible satisfactory pre-imputation for all players. Definition 7. [START_REF] Shapley | Cores of convex games[END_REF] Let v be a game. The core of v, denoted by C(v), is defined by

C(v):={x ∈ R n | x(A) ≥ v(A), ∀A ⊆ N, x(N)=v(N)}.
Since by Remark 1 any x ∈ R n induces an additive game, the core can be equivalently defined as the set of additive games dominating v; if we are dealing with capacities, the core consists in the set of probabilities dominating the capacity. When nonempty, the core is usually taken as the solution of the game. If the core is not empty, it is a convex polytope and its vertices are known when the game is convex:

Definition 8. A maximal chain in 2 N is a sequence of subsets A 0 := ∅,A 1 ,...,A n-1 ,A n := N such that A i ⊂ A i+1 , i =0,...,n-1. The set of maximal chains of 2 N is denoted by M(2 N ).
To each maximal chain

C := {∅,A 1 ,...,A n = N} in M(2 N ) corresponds a unique permutation σ on N such that A 1 = σ(1), A 2 \ A 1 = σ(2), ..., A n \ A n-1 = σ(n).
The set of all permutations over N is denoted by S(N). Let v be a game. Each permutation σ (or maximal chain C) induces an additive game φ σ (or φ C )o nN defined by:

φ σ ({σ(i)}):=v({σ(1),...,σ(i)}) -v({σ(1),...,σ(i -1)}) or φ C ({σ(i)}):=v(A i ) -v(A i-1 ), ∀i ∈ N,
with the above notation.

Theorem 1. The following propositions are equivalent.

1. v is a convex game.

2. All additive games φ σ , σ ∈ S(N), belong to the core of v.

3. C(v)=co({φ σ } σ∈S(N ) ). 4. ext(C(v)) = {φ σ } σ∈S(N ) ,
where co(•) and ext(•) denote respectively the convex hull of some set, and the extreme points of some convex set.

(i) ⇒ (ii) and (i) ⇒ (iv) are due to Shapley [START_REF] Shapley | Cores of convex games[END_REF], while (ii) ⇒ (i) was proved by Ichiishi [START_REF] Ichiishi | Super-modularity: Applications to convex games and to the Greedy algorithm for LP[END_REF]. Suppose the core of the game is empty. Since from Remark 1 the core is the set of 1-additive dominating games, it is natural to look for 2-additive games dominating v; if this set is empty too, then look for 3-additive games dominating v and so on. This leads us to the following definition.

Definition 9. [19]

A game v on N is called k-balanced if there exists a k-additive game dominating it and no game in G k-1 (N) dominates v. Definition 10. [START_REF] Miranda | k-balanced games and capacities[END_REF] Given a game v, we define the k-additive core of v, denoted by C k (v), as the set of all k-additive games dominating v, i.e.,

C k (v):={v * ∈G k (N) | v * ≥ d v}.
In [START_REF] Miranda | k-balanced games and capacities[END_REF], the following has been proved: Proposition 1. For any k ≥ 2 and any game v ∈G(N), C k (v) = ∅.

Consequently, for the general case, only the core and the 2-additive core make sense. Moreover, it has been shown in [START_REF] Grabisch | On the vertices of the k-additive core[END_REF] that the 2-additive core is an unbounded convex polyhedron.

On the other hand, when dealing with capacities, the following notion makes sense: Definition 11. A capacity µ on N is k-balanced monotone if there exists a k-additive capacity dominating it and no capacity in FM k-1 (N) dominates µ.

Definition 12. Given a k-balanced monotone capacity µ,w ed e fi n et h ek-additive monotone core of µ, denoted by MC k (µ), as the set of all k-additive capacities dominating µ.

Notice that if µ is a balanced capacity,

C 1 (µ)=MC 1 (µ)=C(µ).
If nonempty, it is easy to see that MC k (µ) is a polytope. In next sections we will study its vertices.

3T h e s e t MC n (µ).

In this section we provide an algorithm for obtaining all the vertices of MC n (µ)f o rag i v e n capacity µ. We consider the following procedure.

• Let ≺ be a linear order on P(N) \{N, ∅}. This order allows us to rank the different subsets of N,

A 1 ≺ A 2 ≺ ... ≺ A 2 n -2 .
• Next, define a partition P = {U, L} on P(N) \{N, ∅}, where U or L could be empty.

The aim of the procedure is to define a capacity µ ≺,P dominating µ.

• Initializing step: Let us define

µ 0 (A i ):=1,µ 0 (A i ):=µ(A i ), ∀A i .
• Iterating step:F o ri =1un tili =2 n -2, do:

-

If A i ∈U, then assign µ ≺,P (A i ):=µ i-1 (A i ).
Redefine: For µ i , we put

µ i (B)= max{µ i-1 (A i ),µ i-1 (B)} if B ⊇ A i µ i-1 (

B)o t h e r w i s e

For µ i , we put µ i (B)=µ i-1 (B), ∀B ⊂ N.

-

If A i ∈L, then assign µ ≺,P (A i )=µ i-1 (A i ).
Redefine: For µ i , we put

µ i (B)= min{µ i-1 (A i ), µ i-1 (B)} if B ⊆ A i µ i-1 (

B)o t h e r w i s e

For µ i , we put µ i (B)=µ i-1 (B), ∀B ⊂ N.

The idea of the procedure is the following: In step i, the values for µ ≺,P (A 1 ), ..., µ ≺,P (A i-1 ) are fixed. Consider A i ;i fA i ∈U , we assign to µ ≺,P (A i ) the largest possible value keeping dominance and monotonicity, which is µ i (A i ). Similarly, if A i ∈L , we assign to µ ≺,P (A i )t h e smallest possible value keeping dominance and monotonicity, which is µ i (A i ). Once the value of µ ≺,P (A i ) is fixed, we need to actualize the lower and upper bounds for A j ,j > i. These lower and upper bounds are stored in µ i and µ i , respectively. For example, for A i ∈Land for any B such that B ⊂ A i whose value has not been fixed yet, in order to keep monotonicity, the value of the capacity on B cannot exceed µ i-1 (A i ), whence the maximum value that the capacity on B can attain is given by min{µ i-1 (A i ), µ i-1 (B)}.

A similar argument applies if A i ∈U.

Note that µ itself is a vertex of MC n (µ), appearing when L = P(N) \{N, ∅} and U = ∅, no matter which order ≺ is considered. Similarly, the measure attaining value 1 for every subset except the empty set is another vertex of MC n (µ), appearing when U = P(N) \{N, ∅} and L = ∅, no matter which order ≺ is considered. The capacity µ is the least element of this set. Similarly, the measure attaining value 1 for every subset except the empty set is the greatest element of MC n (µ).

The figure explains the performance of the algorithm for the special case of |N| =2 . In this case, P(N) \{N, ∅} = {{1}, {2}} and we have an antichain. Then, ≺ has no relevance in the algorithm. The set MC n (µ) is clearly the yellow square in the figure below. We can see that MC 2 (µ) has four vertices, corresponding to the four possibilities for U and L.

µ ≺,P ({1}) µ ≺,P ({2}) µ µ max U = ∅ L = {{1}, {2}} U = {{2}} L = {{1}} U = {{1}, {2}} L = ∅ U = {{1}} L = {{2}}
In next results we will prove that the function µ ≺,P obtained through this procedure is a vertex of MC n (µ) and that any vertex can be obtained through a suitable choice of ≺ and P. Proposition 2. µ ≺,P ∈MC n (µ).

The proof of this result is based on the following lemmas, that provide us with additional properties of the sequences {µ i (B)} 2 n -2 i=0 and {µ i (B)} 2 n -2 i=0 .

Lemma 1. For any B ⊂ N, the sequence {µ i (B)} 2 n -2 i=1 is nondecreasing. Similarly, the sequence {µ i (B)} 2 n -2 i=0 is nonincreasing. Proof: The result is obvious from the definition of µ i and µ i in each iteration.

Lemma 2. µ i , µ i ∈FM(N), ∀i =0, ..., 2 n -2.

Proof: We show the result for µ i ;t h es a m ec a nb ed o n ef o rµ i . Clearly, in each iteration µ i (B) ∈ [0, 1], ∀B ⊂ N. Thus, it suffices to show the monotonicity. We will prove the result by induction on i.

Consider A, B ⊂ N such that A ⊂ B. In the initializing step, µ 0 (A)=µ 0 (B)=1a n dt h e result holds. Therefore, assume the result is true for iterations 0, 1, ..., i -1.

• If A i ∈U, then µ i = µ i-1 and the result holds by the induction hypothesis.

• If A i ∈L, we have three different possibilities.

-

If A ⊂ B ⊆ A i , then µ i (A)=min{µ i-1 (A i ), µ i-1 (A)}≤min{µ i-1 (A i ), µ i-1 (B)} = µ i (B),
as µ i-1 (A) ≤ µ i-1 (B) by the induction hypothesis. Thus, the result holds.

-If A ⊆ A i , then µ i (A)=µ i-1 (A)a n dµ i (B)=µ i-1 (B), and the result holds by the induction hypothesis.

-

If A ⊆ A i ,B ⊆ A i , then µ i (A)=min{µ i-1 (A i ), µ i-1 (A)}≤µ i-1 (A) ≤ µ i-1 (B),
applying again the induction hypothesis. On the other hand, µ i (B)=µ i-1 (B), so that the result holds.

Lemma 3. µ i ≥ d µ i , ∀i =0, ..., 2 n -2.
Proof: We will prove the result by induction on i. For the initializing step, the result trivially holds. Take B ⊂ N and assume then that the result is true for iterations 0, 1, ..., i -1.

Suppose A i ∈U, the other case being symmetric.

• If A i ⊆ B, then µ i (B)=µ i-1 (B)a n dµ i (B)=µ i-1 (B)
, whence the result holds by induction.

• Otherwise, µ i (B)=µ i-1 (B)a n d

µ i (B)=max{µ i-1 (A i ),µ i-1 (B)}.
Note that µ i-1 (B) ≥ µ i-1 (A i )a sµ i-1 ∈F M (N) (Lemma 2). On the other hand, µ i-1 (B) ≥ µ i-1 (B) by induction, whence µ i (B) ≥ µ i (B)i nt h ei-th iteration and the result holds.

Proof of the proposition: First, let us see that µ ≺,P ∈FM(N).

Clearly, µ ≺,P (B) ∈ [0, 1], ∀B ⊂ N. Thus, it suffices to check the monotonicity. Take A, B ⊂ N such that A ⊂ B. Suppose A ≺ B; a similar proof can be derived when B ≺ A. Thus, A = A i and B = A j for some i, j such that j>i .

• If A ∈L, then µ ≺,P (A)=µ i-1 (A). By Lemma 2, µ i-1 (A) ≤ µ i-1 (B), µ i-1 (A) ≤ µ i-1 (B).

Now,

-If B ∈L , then µ ≺,P (B)=µ j-1 (B) and result holds because, by Lemma 1, we know that

{µ i (B)} 2 n -2 i=1 is a nondecreasing sequence. -Otherwise, B ∈U, whence µ ≺,P (B)=µ j-1 (B) ≥ µ j-1 (B)
by Lemma 3 and the result holds again applying Lemma 1.

• If A ∈U, then µ ≺,P (A)=µ i-1 (A). By construction, µ i (B)=max{µ i-1 (A),µ i-1 (B)}≥µ ≺,P (A).

-If B ∈L , then µ ≺,P (B)=µ j-1 (B) and result holds because, by Lemma 1, we know that {µ i (B)} 2 n -2 i=1 is a nondecreasing sequence. -Otherwise, B ∈U, whence µ ≺,P (B)=µ j-1 (B) ≥ µ j-1 (B) by Lemma 3 and the result holds, again applying Lemma 1.

Therefore, the result holds.

Let us now prove that µ ≺,P ≥ d µ.

In the initializing step, we have µ 0 (A)=µ(A), ∀A ⊂ N. Besides, by Lemma 2, we know that

{µ i (A)} 2 n -2
i=1 is a nondecreasing sequence. Moreover, by Lemma 3, µ i (A) ≤ µ i (A), ∀i.T h u s ,a s µ ≺,P (A)i se i t h e rµ i (A)o rµ i (A)f o rs o m ei,w ea l w a y so b t a i nµ ≺,P (A) ≥ µ(A).

Indeed, it can be easily seen that µ i ≤ µ ≺,P ≤ µ i , ∀i. Moreover, the following holds.

• Otherwise,

µ i-1 (A i )=min{µ ≺,P (A j ) | j<i ,A j ∈L,A j ⊃ A i }.
By the induction hypothesis, µ ≺,P (A j )=µ * (A j ), ∀j<i ,whence

µ i-1 (A i )=min{µ * (A j ) | j<i ,A j ∈L,A j ⊃ A i }.
By construction of L, we have µ * (A j ) < 1, ∀A j ∈L . Thus, µ i-1 (A i ) < 1. On the other hand, A i ∈U, whence µ * (A i ) = 1 by construction of U. But then, there exists A j ⊃ A i such that µ * (A i ) >µ * (A j ), whence µ * is not monotone, a contradiction. Therefore, this second case is not possible.

We conclude that if A 1 = P(N) \{N, ∅}, then µ * = µ ≺,P and we are done. Otherwise, define

A 2 := {A ∈ (P(N) \{N, ∅}) \A 1 | µ * (A)=µ * (B),B ∈A 1 ,B ⊂ A or B ⊃ A}.
Range the subsets in A 2 in any way after the subsets in A 1 . If A ∈A 2 and µ * (A)=µ * (B)f or B ∈A 1 and B ⊃ A, then A ∈U. Otherwise, A ∈L.

As in the previous case, if A 2 =(P(N) \{N, ∅}) \A 1 , then it can be checked that µ * = µ ≺,P and we are done.

Otherwise, we can reiterate the process defining A 3 and so on. If at some step the whole P(N) \{N, ∅} is recovered, then µ * = µ ≺,P and the result holds. Let us see that this is always the case.

Suppose there exists an i such that A i = ∅ and A 1 ∪ ... ∪A i-1 = P(N) \{N, ∅}. Then, we can define

µ 1 (B)= µ * (B)i f B ∈A 1 ∪ ... ∪A i-1 µ * (B)+ǫ otherwise µ 2 (B)= µ * (B)i f B ∈A 1 ∪ ... ∪A i-1 µ * (B) -ǫ otherwise
As we are dealing with a finite number of subsets, it is possible to take an ǫ>0 such that µ 1 ,µ 2 ∈FM (N). Moreover, ǫ can be chosen so that µ 1 ,µ 2 ∈M C n (µ). But µ * = 1 2 µ 1 + 1 2 µ 2 , whence µ * is not a vertex of MC n (µ), a contradiction. This finishes the proof.

Note that these results allow us to derive an upper bound for the number of vertices of MC n (µ).

Proposition 5. The number of vertices of MC n (µ) is bounded by

(2 n -2)!2 2 n -2 .
Proof: The number of possible orders ≺ is (2 n -2)!. On the other hand, for a fixed order, there are 2 2 n -2 possible partitions P.

Observe that the number of vertices can be far below this bound as it could be the case that some possibilities lead to the same capacity. For example, we have already seen that µ can be obtained by taking L = P(N) \{N, ∅}, no matter the order ≺ . Even more, if µ(A)=1, ∀A = ∅, then MC n (µ)={µ} and consequently, all possibilities lead to the same vertex µ.

Remark 2. An interesting case arises when µ is an extreme point of FM(N). In this case, µ is a {0, 1}-valued measure [START_REF] Radojevic | The logical representation of the discrete Choquet integral[END_REF], and it can be trivially seen that the procedure developed in this section leads to {0, 1}-valued measures, i.e. vertices of FM(N). This means that the set of vertices of MC n (µ) is the set of vertices of FM(N) dominating µ. As a vertex of the polytope of fuzzy measures is characterized by the family of minimal subsets [START_REF] Miranda | Extreme points of some families of non-additive measures[END_REF], the smallest subsets such that µ(A)=1, if {C 1 , ..., C k } are the minimal subsets of µ,t h e n

MC n (µ)={µ * ∈FM(N):µ * (A)=1∀A |∃ C i ⊆ A}.
On the other hand, it has been proved in [START_REF] Combarro | Adjacency on the order polytope with applications to the theory of fuzzy measures[END_REF] that FM(N) is an order polytope [START_REF] Stanley | Two poset polytopes[END_REF] for the poset P(N)\{∅,N} and the partial order defined by the containing condition.

Remark that MC n (µ) fixes the values of some subsets of N; then, we can partitionate P(N)\{∅,N} in terms of subsets of N with the same value; this partition π on the poset P(N)\{∅,N} is given by the classes

[C] ∪{[A]:={A},C i ⊆ A, i =1, ..., k} where [C]={A ∈P(N)\{∅,N}|∃ C i ⊆ A}.
This partition is trivially compatible with the containing partial order and it is also a connected partition of the poset P(N)\{∅,N}.T h u s ,t h es e tMC n (µ) can be seen as a quotient of the order polytope FM(N) [START_REF] Combarro | Adjacency on the order polytope with applications to the theory of fuzzy measures[END_REF], and we can apply the results of [START_REF] Stanley | Two poset polytopes[END_REF] to conclude that MC n (µ) is indeed a face of the polytope FM(N).

4T h e c a s e o f MC k (µ)

In this section we treat the general k-additive case, 1 ≤ k<n .The basic idea is to translate the results of the previous section to this case. In order to do this, we will need to solve two new problems:

• For a fixed value of µ * (A), the possible lower and upper bounds of µ * (B),B = A are not trivial, as it happened for the n-additive case. Moreover, if we are dealing with MC k (µ), it could be the case that µ ∈F M k (N). Thus, µ cannot be taken as the least element for MC k (µ), and it could be the case that MC k (µ) have not a least element, so that µ 0 could not be defined. Similarly, the measure attaining value 1 for every subset is n-additive and thus, it is no longer in MC k (µ), whence it could be the case that MC k (µ)h a v en o ta greatest element, so that µ 0 could not be defined.

Contrary to FM n (N), the structure of the polytope FM k (N) is not known for k ≥ 3. Indeed, it has been proved in [START_REF] Miranda | Extreme points of some families of non-additive measures[END_REF] that there are vertices of FM k (N),k ≥ 3 that are not {0, 1}-valued measures; moreover, to our knowledge, no description of these vertices has been achieved. However, it could be the case that some of these vertices are in MC k (µ). How can they be characterized?

In order to partially solve the first problem, we will study in this section the particular case in which µ ∈FM k (N). Then, MC k (µ) = ∅ and has a least element (µ itself). Moreover, µ can be used as the lower bound in the initial step. Notice that in the n-additive case these properties trivially hold.

Note also that for a capacity in FM k (N), if we consider its Möbius transform, we only need to define the values for subsets in P k (N)\{∅}. As the Möbius transform is an equivalent representation of the capacity by Eq. ( 1), we conclude that we only need to consider the values of the capacity on subsets whose cardinality lies between 1 and k in order to completely define a k-additive capacity.

Taking these facts in mind, the procedure goes as follows:

• IN:

-Let us consider a total order on P k (N) \ {∅}. This total order allows us to rank the subsets: • Look for s i+j := min µ * ∈A j-1 {µ * (A i+j )}.

A
• Define A j := {µ * ∈A j-1 |µ * (A i+j )=s i+j }.

• j = j +1.

• If A j = {µ * }, define µ i := µ * .

Let us explain the procedure. The whole process spins around the capacities µ i . By construction µ i ∈F M k (N), ∀i ≥ 1. Observe also that µ i can be built because µ 0 = µ ∈F M k (N). Moreover, µ i ≤ d µ i+1 , ∀i. Indeed, µ i represents the lower bounds for A j ,j > i when the values on A 1 , ..., A i are fixed. Thus, following the same spirit as in the previous section, we want n-th Dedekind number; simulations carried out for the k-additive case [START_REF] Combarro | On the structure of the k-additive fuzzy measures[END_REF] seem to show that the number of vertices of FM k (N) is even greater, due to vertices that are not {0, 1}-valued. This problem could make unfeasible to store all the vertices of the k-additive monotone core in some cases.

1 ≺ A 2 ≺ 2 .

 122 ... ≺ A r , where r = k i=1 n k .-Next, take a partition P = {U, L} on P k (N) \ {∅}, where U or L could be empty.• OUT:-Initializing step: Let us define µ 0 := µ -Iterating step:F o ri =1un tili = r do: * If A i ∈L, then µ i = µ i-1 .* Otherwise A i ∈U.1. Let us consider the subset given byB := {µ * ∈FM k (N) | µ * ≥ d µ i-1 ,µ * (A j )=µ i-1 (A j ),j =1, ..., i -1}. Look for s := max µ * ∈B {µ * (A i )}. 3. Define A 0 := {µ * ∈B|µ * (A i )=s}. (a) If A 0 = {µ * }, then define µ i := µ * . (b) Otherwise: • Initialize j =1. • Repeat until |A j | =1.

Acknowledgements

This research has been supported in part by grant numbers MTM2007-61193, MTM2009-10072 and BSCH-UCM910707.

We also thank a referee for pointing out the special structure of MC n (µ)w h e nµ is a vertex of FM(N).

Proposition 3. µ ≺,P is a vertex of MC n (µ).

Proof: Consider µ ≺,P and let us suppose that there exist µ 1 ,µ 2 ∈MC n (µ) such that µ ≺,P = αµ 1 +(1α)µ 2 ,α∈ (0, 1). We will prove by induction on i that µ ≺,P (A i )=µ 1 (A i )=µ 2 (A i ).

Consider A 1 . If A 1 ∈U, then µ ≺,P (A 1 )=1, whence µ 1 (A 1 )=µ 2 (A 1 )=1. Otherwise, A 1 ∈L and µ ≺,P (A 1 )=µ(A 1 ), whence µ 1 (A 1 )=µ 2 (A 1 )=µ(A 1 ) because they dominate µ. Now, suppose the result holds until i -1. Assume A i ∈L, the other case being symmetric.

• If µ ≺,P (A i )=µ(A i ), then µ 1 (A i )=µ 2 (A i )=µ(A i ) because they dominate µ.

• Otherwise, by construction of µ i-1 , there exists j<isuch that A j ⊂ A i and A j ∈U satisfying µ j-1 (A j )=µ j-1 (A i )=µ i-1 (A i ).

Consequently, µ ≺,P (A j )=µ j-1 (A j )=µ i-1 (A i )=µ ≺,P (A i ). On the other hand, µ 1 (A j )= µ 2 (A j )=µ ≺,P (A j ) by induction. As µ 1 ∈FM(N), it follows by monotonicity that µ 1 (A i ) ≥ µ 1 (A j )=µ ≺,P (A j )=µ ≺,P (A i ).

Similarly, µ 2 (A i ) ≥ µ ≺,P (A i ) whence

Finally, it can be seen that all the vertices can be derived from this procedure.

Proposition 4. If µ * is a vertex of MC n (µ), then there exists an order ≺ and a partition P of P(N) \{N, ∅} such that µ * = µ ≺,P .

Proof: Take µ * a vertex of MC n (µ). We will show that we can build an order ≺ and a partition P such that µ * = µ ≺,P .

Let us define

Take any linear order ≺ on A 1 . If A ∈A 1 and µ * (A)=1, then A ∈U. Otherwise, A ∈L.

If A 1 = P(N) \{N, ∅}, let us prove by induction that µ * = µ ≺,P . Take A 1 .I fA 1 ∈U, then µ ≺,P (A 1 )=µ 0 (A 1 )=1 , whence µ ≺,P (A 1 )=µ * (A 1 ) and the result holds. Otherwise, A 1 ∈Land µ ≺,P (A 1 )=µ 0 (A 1 )=µ(A 1 ), whence µ ≺,P (A 1 )=µ * (A 1 )a n dt h e result holds.

Take i>1 and assume the result holds until i -1. Suppose A i ∈U, the case A i ∈Lbeing symmetric. Let us show that µ ≺,P (A i )=1=µ * (A i ). As A i ∈U , it follows that µ ≺,P (A i )= µ i-1 (A i ). We have two different cases:

• If there exists no j<isuch that A j ∈Land A j ⊃ A i , then by the construction of the procedure, it is µ i-1 (A i )=µ 0 (A i ) = 1 and the result holds.

that, at step i,t h ev a l u e sf o rA 1 , ..., A i-1 are already fixed. This is done through the property µ i (A j )=µ i+1 (A j ), ∀j<ithat appears in the definition of B. Suppose we are in step i, so that we are dealing with A i . If A i ∈U, we look for a capacity µ i whose value on A i is the largest possible value provided that µ i ≥ d µ i-1 and that the values µ i (A 1 ), ..., µ i (A i-1 ) are already fixed; the possible candidates are capacities in B. As FM k (N) is a polytope, so is B. Thus, for A i , it follows that the capacity on A i c a nv a r yi na ni n t e r v a l whose lower bound is µ i-1 (A i ), and whose upper bound is s. For the n-additive case, once this value is found, the procedure modifies the upper and lower bounds for the values on A k ,k > i.

In the present case, the problem is not that simple because it might be the case that no greatest element exist. Thus, we only look for the lower bounds.

We proceed as follows: Once s is obtained, it could be the case that several capacities reach this value, i.e. it could happen that A 0 is not a singleton. Our capacity µ i should be chosen in A 0 and ideally, it should be the least element in this set. However, it could be the case that such least element do not exist; in other words, we can find several capacities that are not dominated for any other capacity in A 0 , i.e. these capacities are not comparable as vectors. In order to solve this problem, we take as µ i the capacity in A 0 that takes the minimum value on A i+1 ,A i+2 , ...; this is done through A 1 , A 2 , ... This finishes in a finite number of steps because necessarily A r-i is a singleton.

On the other hand, if A i ∈L , then we look for the smallest k-additive capacity dominating µ i-1 , that is µ i-1 itself because µ i-1 ∈FM k (N). And we define µ i := µ i-1 for next iteration.

Therefore this algorithm coincides with the algorithm of the previous section for the n-additive case.

Consider µ r , the capacity obtained in the last iteration. We will prove that it is a vertex of MC k (µ).

Lemma 4. The measure µ r is an extreme point of MC k (µ).

Proof: Consider µ r and let us suppose that there exist µ 1 ,µ 2 ∈MC k (µ) such that µ r = αµ 1 + (1α)µ 2 ,α∈ (0, 1). We will prove by induction on iteration i that µ r (A i )=µ 1 (A i )=µ 2 (A i ).

Consider A 1 . If A 1 ∈U , then µ r (A 1 ) attains the maximum possible value for a measure in MC k (µ), whence µ 1 (A 1 )=µ 2 (A 1 )=µ r (A 1 ).

Otherwise, A 1 ∈Land µ r = µ(A 1 ), whence µ 1 (A 1 )=µ 2 (A 1 )=µ(A 1 ) because both of them belong to MC k (µ). Now, take i>1 and assume the result holds until i -1. Suppose A i ∈L . By construction of µ r , it is µ r (A i )=µ i-1 (A i ). On the other hand, by construction of µ i-1 , this capacity is such that it assigns to µ i-1 (A i ) the smallest possible value keeping dominance on µ and satisfying

Similarly, if A i ∈U, by construction µ r assigns to A i the greatest possible value while keeping dominance on µ and satisfying

However, this method does not obtain all the vertices of MC k (µ), as next example shows: It has been proved in [START_REF] Miranda | Extreme points of some families of non-additive measures[END_REF] that µ * is an extreme point of FM 3 (N). On the other hand, µ * ≥ u {1,4} , whence µ * is an extreme point of MC 3 (u {1,4} ). Let us check that µ * cannot be obtained through the previous algorithm, no matter the order considered.

Assume A 1 ∈U.

• If A 1 = {2} then we can consider the capacity µ ′ whose Möbius transform is given by

Thus, we have obtained a dominating capacity in FM 3 (N) such that µ ′ (2) = 1, whence µ * could not be derived. The same can be done if A 1 = {3}.

• If A 1 = {1} then we can consider the capacity whose Möbius transform is given by

Thus, we have obtained a dominating capacity in FM 3 (N) such that µ ′ (1) = 1, whence µ * could not be derived. The same can be done if A 1 = {4}.

• If A 1 = {1, 3} then we can consider the capacity whose Möbius transform is given by

Thus, we have obtained a dominating capacity in FM 3 (N) such that µ ′ (1, 3) = 1, whence µ * could not be derived. The same can be done for any pair different from {1, 4} and {2, 3}.

• Suppose A 1 = {2, 3} and consider the capacity whose Möbius transform is given by

In this case, we obtain a 3-additive measure dominating u {1,4} and thus, it is possible to obtain µ 1 (2, 3) = 1. Therefore, µ * cannot be derived in this case.

• If A 1 = {1, 2, 3}, we can consider the capacity whose Möbius transform is given by

Thus, we have obtained a dominating capacity in FM 3 (N) such that µ ′ (1, 2, 3) = 1, whence µ * could not be derived.

• For the other possibilities, we have u {1,4} (A 1 )=1, whence the value is fixed. Consequently, it is not possible to obtain µ * if A 1 ∈U . Thus, assume A 1 ∈L . This fixes µ 1 (A 1 )=u {1,4} (A 1 ).

• If A 1 ∈{{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, then µ 1 (A 1 )=0, whence µ * cannot be recovered.

• For other possibilities, we fix a value either 0 or 1.

But then, we can repeat the process for A 2 with the same results. Thus, µ * cannot be obtained through the procedure.

5 On the polytope of dominated k-additive capacities

In the previous sections we have considered a profit game, the value µ(A) representing the payoff that the coalition A can guarantee, i.e. we are dealing with winning quantities. A dual problem arises if µ(A) denotes losing quantities. In this case, we look for dominated capacities instead of dominating capacities and the concepts of core, k-additive core, and so on can be translated to this case accordingly.

Let µ be a capacity and suppose that we are interested in the set of k-additive capacities that are dominated by µ. As before, it can be seen that this set is a polytope, so that it suffices to study its vertices.

In this case, we can apply the results of the previous sections. For this, it suffices to note that

where µ denotes the dual capacity of µ, defined by

Observe that µ = µ and that the dual of a k-additive capacity is a k-additive capacity [START_REF] Miranda | On the structure of some families of fuzzy measures[END_REF]. Moreover, if µ ′ is a vertex of the polytope of the dominated k-additive capacities, then µ ′ is a vertex of dominating k-additive capacities of µ. For if there exist

As µ 1 and µ 2 are k-additive capacities dominated by µ, we conclude that µ ′ is not a vertex of the set of dominated k-additive capacities, a contradiction.

Consequently, for a given capacity µ, we can consider µ, apply the results of the previous sections and then apply again duality. For example, the procedure for obtaining the set of vertices of the polytope of dominated n-additive capacities can be written as:

• Let ≺ be a linear order on P(N) \{N, ∅}. This order allows us to rank the different subsets of N,

• Next, define a partition P = {U, L} on P(N) \{N, ∅}, where U or L could be empty.

The aim of the procedure is to define a capacity µ ≺,P dominated by µ.

• Initializing step: Let us define

• Iterating step:F o ri =1un tili =2 n -2, do:

-If A i ∈U, then assign µ ≺,P (A i ):=µ i-1 (A i ).

Redefine:

For µ i , we put

B)o t h e r w i s e

For µ i , we put µ i (B)=µ i-1 (B), ∀B ⊂ N.

-If A i ∈L, then assign µ ≺,P (A i )=µ i-1 (A i ).

Redefine: For µ i , we put

For µ i , we put µ i (B)=µ i-1 (B), ∀B ⊂ N.

Conclusions

In this paper, we have characterized the vertices of the n-additive core; these results generalize the Shapley-Ichiishi theorem of probabilities for the general case. Observe that in this case no conditions on µ are required, while in the Shapley-Ichiishi theorem convexity is needed. Next, we have treated the possible extensions for the k-additive case. Finally, the dual case for dominated k-additive capacities is treated.

It should be noted that in Example 1 we have considered a capacity u {1,4} of FM 3 (N)a n da vertex of FM 3 (N) dominating u {1,4} . Notice that this vertex is not {0, 1}-valued. In [START_REF] Miranda | Extreme points of some families of non-additive measures[END_REF], it has been proved that these vertices might appear for the polytope FM k (N)w h e n3≤ k ≤ n -1. On the other hand, the vertices of FM 1 (N), FM 2 (N)a n dFM n (N) (the general case) are {0, 1}-valued. Thus, it arises the question of whether this algorithm holds for k =1, 2.

If k =1andµ is a probability, then the set MC 1 (µ)=C(µ)={µ}. In this case the algorithm holds and the problem is trivial. The 2-additive case remains an open problem and deeper research is needed.

Related to Example 1, we have the problem of whether the procedure developed in Section 4 obtains all the vertices of MC k (µ)t h a ta r en o tv e r t i c e so fFM k (N). If this holds, then the vertices of MC k (µ) could be completed using the procedure developed in [START_REF] Combarro | On the structure of the k-additive fuzzy measures[END_REF]. However, verifying this hypothesis seems to be a difficult problem and more research is needed.

In order to determine the vertices of MC k (µ), we could apply a modified version of the procedure developed in [START_REF] Combarro | On the structure of the k-additive fuzzy measures[END_REF], but the complexity should be investigated in order to study its practical applicability.

Another important problem arising in the k-additive case is the number of vertices of the k-additive core. For the general n-additive case, the set of vertices of FM(N) coincides with the