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

Remarkable polyhedra related to set functions, games and capacities

Keywords: TU-game, capacity, nonadditive measure, pseudo-Boolean function, Möbius transform, supermodular game, p-additive game, multichoice game, core

Set functions are widely used in many domains of Operations Research (cooperative game theory, decision under risk and uncertainty, combinatorial optimization) under different names (TU-game, capacity, nonadditive measure, pseudo-Boolean function, etc.). Remarkable families of set functions form polyhedra, e.g., the polytope of capacities, the polytope of p-additive capacities, the cone of supermodular games, etc. Also, the core of a set function, defined as the set of additive set functions dominating that set function, is a polyhedron which is of fundamental importance in game theory, decicion making and combinatorial optimization. This survey paper gives an overview of these notions and studies all these polyhedra.

Introduction

Set functions, that is, functions assigning a real number to any subset of a universal set, are encountered in many domains of Operations Research and discrete mathematics, often under different names. Let us give some examples. In (cooperative) game theory, the characteristic function of a game with transferable utility is a set function vanishing on the empty set. They are often abbreviated as TU-games, or simply games. In decision under risk or uncertainty, recent nonadditive models use generalizations of probability measures which are called capacities (Choquet [6]), or nonadditive measures (Denneberg [START_REF] Denneberg | Non-Additive Measure and Integral[END_REF]), fuzzy measures (Sugeno [START_REF] Sugeno | Theory of fuzzy integrals and its applications[END_REF]), monotone measures, etc. These are set functions vanishing on the empty set (hence games) and monotone w.r.t. set inclusion. Pseudo-Boolean functions, introduced by Hammer and Rudeanu [START_REF] Hammer | Boolean Methods in Operations Research and Related Areas[END_REF], are real-valued mappings whose domain is the set of Boolean vectors, and are therefore equivalent to set functions. They have many applications in computer sciences, graph theory, data mining, etc. (see, e.g., Crama and Hammer [7,Ch. 13], and O'Donnell [START_REF] Donnell | Analysis of Boolean functions[END_REF]). In combinatorial optimization, submodular and monotone set functions are considered, since they appear as the rank function of a matroid. They are studied at length in the monograph of Fujishige [START_REF] Fujishige | Submodular functions and optimization[END_REF].

Many of the above cited domains are related to optimization problems, linear programming and polyhedra. One of the reasons is that remarkable families of set functions are defined by linear inequalities, and therefore form polyhedra. This is the case for capacities (monotone normalized set functions), supermodular games, or p-additive games, defined through their Möbius transform. Another reason is that the core of a set function is a fundamental concept in most of the above cited domains. It is the set of additive set functions dominating a given set function, and is therefore a polyhedron. In game theory, it is one of the most popular solution concept. In decision theory, it gives the set of compatible probability measures. In combinatorial optimization, it is known as the base polyhedron associated to a polymatroid.

The aim of the paper is to make a survey of these aspects, summarizing most relevant classical results, showing recent ones, and exploring some generalizations like games with restricted domain, multichoice games, the k-additive core, etc. It also aims at enhancing the close connections between cooperative game theory, combinatorial optimization, decision theory and Operations Research in general. Indeed, as it will be seen, many results have been proved at the same time in different domains. Many other aspects of set functions, games and capacities can be found in the monograph of the author [START_REF] Grabisch | Set Functions, Games and Capacities in Decision Making[END_REF].

The paper is organized as follows. Section 2 gives the necessary background on games, capacities, pseudo-Boolean functions, posets and lattices, the Möbius transform, multichoice games and k-ary capacities. Sections 3 to 6 study the polyhedra formed by various families of set functions (capacities, p-additive capacities, k-ary capacities, and supermodular games). The core of games is studied in detail in Section 7, for classical games and for games with a restricted domain. Finally, the k-additive core is studied in Section 8.

Background

Throughout the paper, we consider a finite set N with |N | = n. We often omit braces for singletons and sets, as far as no ambiguity menaces, writing, e.g., S ∪ i instead of S ∪ {i}, 12 instead of {1, 2}, etc.

Basic definitions: set functions, games and capacities. A set function on N is a mapping ξ : 2 N → R assigning to every subset S ⊆ N a real number. A game on N is a set function v vanishing on the empty set: v(∅) = 0. We say that a game is monotone if S ⊆ T ⊆ N implies v(S) ≤ v(T ), and normalized if v(N ) = 1. In decision theory, a monotone normalized game is called a capacity1 (Choquet [START_REF] Choquet | Theory of capacities[END_REF]), which we denote by µ. 2 A 0-1-capacity (a.k.a. simple game) is a capacity taking value on {0, 1}. A zero-normalized game v is a game such that v({i}) = 0 for every i ∈ N . We denote the set of capacities on N by C(N ), and the set of games on N by G(N ).

The conjugate of a game v is a game v defined by

v(S) = v(N ) -v(N \ S) (S ∈ 2 N ).
A game is said to be:

(i) additive if for every disjoint S, T in 2 N , we have v(S ∪ T ) = v(S) + v(T ); (ii) supermodular if for every S, T ∈ 2 N , we have v(S ∪ T ) + v(S ∩ T ) ≥ v(S) + v(T ); (1)
(iii) submodular if the reverse inequality holds.

Instances in Operations Research. In cooperative game theory, N represents the set of players, and the function v (whose exact name is characteristic function of a game with transferable utility) gives for each coalition S ⊆ N of players its worth v(S), defined as the maximal benefit or cost saving achievable by cooperation of the members of S.

In decision theory, N is typically the set of states of nature, subsets of N are called events, and µ(S) quantifies the uncertainty pertaining to the realization of S.

Particular set functions arise also in combinatorial optimization and Operations Research. In combinatorial optimization, a pair (N, ρ) where ρ is a submodular capacity, is called a polymatroid (see, e.g., Fujishige [START_REF] Fujishige | Submodular functions and optimization[END_REF]). This refers to the rank function of a matroid, which is always submodular. In reliability theory, set functions model the structure of a multicomponent system and permit to study its lifetime: given a n-component system and supposing that each component can be in two states (0: failure, 1: functioning), the state of the whole system is ruled by a function φ : {0, 1} n → {0, 1}. It is most often assumed that φ is nondecreasing in each place, hence φ is nothing other than a 0-1-capacity (or simple game).

Pseudo-Boolean functions. Set functions can also be seen as pseudo-Boolean functions, a widely developed area in Operations Research, after the seminal work of Hammer and Rudeanu [START_REF] Hammer | Boolean Methods in Operations Research and Related Areas[END_REF] (see Crama and Hammer [7,Ch. 13]). A pseudo-Boolean function is a function f : {0, 1} n → R; they are equivalent to set functions through the isomorphism {0, 1} n ≡ 2 N , where a set S is represented by its characteristic function 1 S :

f ↔ ξ f (1 S ) ↔ ξ(S).
It is easy to check that any pseudo-Boolean function can be put under the form:

f (x) = T ⊆N f (1 T ) i∈T x i i∈T c (1 -x i ) (x ∈ {0, 1} n ). (2)
Rearranging the terms so as to obtain a sum of monomials, we get:

f (x) = T ⊆N a T i∈T x i (x ∈ {0, 1} n ). ( 3
)
The degree of a pseudo-Boolean function is the highest degree of the monomials in [START_REF] Bilbao | The core of games on convex geometries[END_REF], where the degree of the monomial i∈T x i is simply |T |.

Posets and lattices.

A poset (partially ordered set) (P, ) is a set P endowed with a partial order (reflexive, antisymmetric and transitive binary relation). If x ≺ y and there is no z such that x ≺ z ≺ y, we write x ≺ • y and say that x is a predecessor of y. For any two elements x, y in a poset (P, ) such that x y, the interval [x, y] is defined by [x, y] = {z ∈ P | x z y}. A lattice (L, ) is a poset satisfying the following property: for every x, y ∈ L, their infimum (greatest lower bound) x ∧ y and supremum (least upper bound

) x ∨ y exist. A lattice is distributive if ∨, ∧ obey distributivity, i.e., x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) (equivalently, x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)).
In a lattice (L, ), an element x ∈ L is said to be join-irreducible if it is not the least element of L and it cannot be written as a supremum of other elements. In a finite lattice, this is equivalent to say that x has only one predecessor. We denote by J (L, ) or J (L) if is clear from the context the set of join-irreducible elements of L.

Q ⊆ P is a downset of a poset (P, ) if x ∈ Q and y x imply y ∈ Q. The set of all downsets of a poset (P, ) is denoted by O(P, ) or simply O(P ). An important result of Birkhoff [START_REF] Birkhoff | On the combination of subalgebras[END_REF] says that a lattice (L, ) is distributive if and only if it is isomorphic to the lattice (O(J (L)), ⊆).

A chain in a poset (P, ) is a sequence x 1 , . . . , x q of distinct elements in P such that x 1 ≺ • • • ≺ x q . A chain is maximal if no supersequence is a chain. Two elements x, y ∈ (P, ) are incomparable if none of x y or y x holds. An antichain is a set of elements in P which are pairwise incomparable.

We illustrate the previous notions and result with N = {1, . . . , n} the set of players. The set 2 N endowed with ⊆ is a lattice, called a Boolean lattice. Any subcollection F of 2 N can be seen as a poset when endowed with ⊆. F can be a lattice, but in this case, infimum and supremum are not necessarily intersection and union. For instance, take n = 3, F = {∅, 1, 2, 3, 123}. Then 1 ∨ 2 = 123 = 1 ∪ 2. If (F, ⊆) is a distributive lattice, then Birkhoff's result amounts to saying that there exists a partial order on N generating F, by taking all downsets of (N, ) and ordering them by inclusion. The converse being true as well, there is a bijection between partial orders on N and collections F that are distributive lattices. It is to be noted that with this construction, the supremum and infimum in F are union and intersection. This is illustrated in Figure 1. The Möbius transform. (Rota [START_REF] Rota | On the foundations of combinatorial theory I. Theory of Möbius functions[END_REF]) Let us consider a poset (P, ), and suppose that it is locally finite (i.e., all intervals [x, y] are finite), and has a least element 0. Consider the following system of equations, where f is given:

f (x) = y x g(y) (x ∈ P ). (4)
There is always a unique solution to (4), i.e., it is always possible to express g in terms of f . Then g is called the Möbius inverse of f , and is given by

g(x) = y x µ(y, x)f (y) (5)
where µ, called the Möbius function, is defined inductively by

µ(x, y) =    1, if x = y -x t≺y µ(x, t), if x ≺ y 0, otherwise. (6)
We apply this general theory to set functions, that is, the poset under consideration is (2 N , ⊆). We find that to any set function ξ on N we can associate its Möbius inverse m ξ : 2 N → R, unique solution of the linear system:

ξ(S) = T ⊆S m ξ (T ) (S ∈ 2 N ), (7)
and explicitely given by

m v (S) = T ⊆S (-1) |S\T | v(T ) (S ∈ 2 N ). ( 8
)
Considering the mapping ξ → m ξ on R 2 N as a transform over the set of set functions, we call m ξ the Möbius transform of ξ. In game theory, the Möbius transform of a game is known as the Harsanyi dividends (Harsanyi [START_REF] Harsanyi | A simplified bargaining model for the n-person cooperative game[END_REF]). Comparing ( 7) with (3), one can see that they are the same up to the isomorphism f ↔ ξ, from which we conclude that the coefficients a T are nothing other than the Möbius transform of ξ (or f ).

Unanimity games. Given ∅ = T ⊆ N , the unanimity game centered on T is a game defined by:

u T (S) = 1, if S ⊇ T 0, otherwise.
It is well known that the set of unanimity games constitutes a basis of the (2 n -1)-dim vector space of games. Adding the set function u ∅ defined by u ∅ (S) = 1 for every S ∈ 2 N , we get a basis for the 2 n -dim vector space of set functions. The expression of any set function in this basis is therefore:

ξ = T ⊆N a T u T which yields ξ(S) = T ⊆N a T u T (S) = T ⊆S a T ,
from which it becomes obvious that the coordinates a T of a set function in this basis are simply the Möbius transform of ξ (see [START_REF] Crama | Boolean functions[END_REF]).

p-additive games and capacities. A game (or a capacity) v on N is (at most) p-additive (p ∈ {1, . . . , n}) if its Möbius transform satisfies

m v (S) = 0 if |S| > p.
1-additive games are ordinary additive games. p-additive games correspond to pseudo-Boolean functions whose polynomial representation is of degree at most p. Clearly, p-additive games with p < n require less coefficients to be defined, precisely at most

κ(p) = n 1 + n 2 + • • • + n p .
The set of at most p-additive capacities is denoted by C ≤p (N ).

Multichoice games and k-ary capacities. Identifying 2 N with {0, 1} N and considering any game v, the quantity v(S) can be rewritten as v(1 S ), replacing coalitions by profiles of participation (0: do not participate, 1: participate). The idea of multichoice games (Hsiao and Raghavan [START_REF] Hsiao | Multichoice cooperative games[END_REF]) is to consider several levels of participation: 0, 1, . . . , k. Specifically, a multichoice game or k-choice game is a mapping v : {0, 1, . . . , k} N → R such that v(0, . . . , 0) = 0, which assigns to any participation profile z a number v(z). A multichoice game is monotone

if z ≤ z ′ (coordinatewise) implies v(z) ≤ v(z ′ ), and normalized if v(k, . . . , k) = 1. With k = 1
, classical games are recovered. Monotone normalized k-multichoice games are called kary capacities (Grabisch and Labreuche [START_REF] Grabisch | Capacities on lattices and k-ary capacities[END_REF]). The set of k-ary capacities is denoted by C k (N ).

The Möbius transform m v of a multichoice game v can be obtained from the general formula (4), which becomes in this case

v(z) = y≤z m v (y) (z ∈ {0, . . . , k} N ).
The unique solution of this system is

m v (z) = y≤z : z i -y i ≤1∀i∈N (-1) i∈N (z i -y i ) v(y) (z ∈ {0, . . . , k} N ).
Based on this definition, a multichoice game is (at most) p-additive if m v (z) = 0 for every profile z whose support contains more than p elements, i.e., |supp(z)| > p, where

supp(z) = {i ∈ N | z i > 0}.
The set of at most p-additive k-ary capacities is denoted by C ≤p k (N ).

The polytope of capacities

The set C(N ) of capacities (monotone normalized games) on N being defined by a set of linear equalities, it is a convex closed polyhedron of dimension 2 n -2, which is bounded. Facets of this polytope are the irredundant monotonicity conditions

µ(S ∪ i) -µ(S) ≤ 0 (i ∈ N, S ⊆ N \ i).
The extreme points (vertices) of this polytope have been determined by Stanley [START_REF] Stanley | Two poset polytopes[END_REF], and rediscovered by Radojevic [START_REF] Radojevic | The logical representation of the discrete Choquet integral[END_REF].

Theorem 1. The set of extreme points of C(N ) is the set of 0-1-capacities (simple games).

As is well known, simple games are determined through their collection of winning coalitions. A coalition S is winning for a simple game v if v(S) = 1. By monotonicity, it follows that a simple game v is entirely determined by the collection of its minimal (in the sense of inclusion) winning coalitions. By definition, if S, T are two minimal winning coalitions, S ⊆ T and T ⊆ S hold, so that the collection of minimal winning coalitions forms an antichain in the lattice (2 N , ⊆). It is known that the number of antichains in 2 N , or equivalently, the number of monotonic Boolean functions of n variables is the Dedekind number M (n). It follows that the number of vertices of the polytope of capacities on N is M (n) -2 (because the antichain {∅}, corresponding to the constant set function 1, and the empty antichain, corresponding to the null set function, have to be removed).

There is no known closed-form formula for an exact computation of these numbers. Up to now, only the nine first numbers are known. Observe that by Theorem 1, this polytope is inscribed into the unit hypercube {0, 1} 2 n -2 , and the main diagonal belongs to the polytope. It follows that the diameter of the polytope of capacities is the length of the diagonal, i.e., √ 2 n -2. An interesting question is: in which hypercube is inscribed the set of capacities when they are expressed through the Möbius transform, i.e., in the basis of unanimity games? The exact bounds of the Möbius transform of a capacity have been investigated by Grabisch and Miranda [START_REF] Grabisch | Exact bounds of the Möbius inverse of monotone set functions[END_REF]. The result is surprising: the bounds grow exponentially fast with n.

Theorem 2. For any capacity µ, its Möbius transform satisfies for any A ⊆ N , |A| > 1:

- |A| -1 l ′ |A| ≤ m µ (A) ≤ |A| -1 l |A| , with l |A| = 2 |A| 4 , l ′ |A| = 2 |A| -1 4 + 1 (9)
and for |A| = 1 < n:

0 ≤ m µ (A) ≤ 1,
and m µ (A) = 1 if |A| = n = 1. These upper and lower bounds are attained by the normalized capacities µ * A , µ A * , respectively:

µ * A (B) = 1, if |A| -l |A| ≤ |B ∩ A| 0, otherwise µ A * (B) = 1, if |A| -l ′ |A| ≤ |B ∩ A| 0, otherwise for any B ⊆ N .
- 4 n 2 πn 2 ≤ m µ (N ) ≤ 4 n 2 πn 2 . ( 10
)
The theorem directly gives the coordinates of the vertices of the (2 n -2)-dim smallest rectangle inscribing the polytope of capacities. Finding its diameter is however more difficult. Table 3: Computation of the upper (red) and lower (blue) bounds of m µ (N ). The value of the capacity µ is 1 for the k + 1 first lines of the lattice 2 N . Each entry (n, k) equals m µ (N ) that the value of m µ (N \ i) for any i ∈ N is given by the entry (n -1, k -1), and so forth: the successive values of m µ lie on the diagonal (n, k), (n -1, k -1), (n -2, k -2), . . .. Observe that for n ≤ 5, choosing k which yields the upper bound or the lower bound gives a diagonal passing only through upper or lower bounds. This guarantees that the coordinates of the corresponding capacities in the basis of unanimity games are maximal, which permits to find the diameter. Taking for example n = 5, k = 2 yields the upper bound (µ * N ) and k = 3 yields the lower bound (µ N * ). The coordinates of these capacities are:

n = 1 1 n = 2 1 -1 n = 3 1 -2 1 n = 4 1 -3 3 -1 n = 5 1 -4 6 -4 1 n = 6 1 -5 10 -10 5 -1 n = 7 1 -6 15 -20 15 -6 1 n = 8 1 -7 21 -35 35 -21 7 -1 n = 9 1 - 8
A |A| = 1 |A| = 2 |A| = 3 |A| = 4 |A| = 5 m µ * N (A) 0 0 1 -3 6 m µ N * (A) 0 1 -2 3 - 4
Therefore the Euclidean distance between them is (discarding the coordinates for ∅ and N since the dimension is 2 n -2)

d(m µ * N , m µ N * ) = 5 2 • 1 + 5 3 • 3 2 + 5 4 • 6 2 = √ 280.
This is the diameter for n = 5 (compare with the diameter in original coordinates √ 30). For higher values of n, we conjecture that the same method also yields the diameter.

The polytope of p-additive capacities

The set of p-additive capacities is a subpolytope of the polytope of capacities, because the additional restrictions are linear inequalities. For p = 1, we obtain the polytope of additive capacities, i.e., probability measures. It is easily found that the set of extreme points of this polytope is the set of unanimity games centered on singletons, u {i} , i ∈ N . Remark that these are exactly the additive 0-1-capacities.

For p = 2, the same type of result holds: the vertices of the polytope of 2-additive capacities are simply those vertices of the polytope of capacities which are 2-additive. Theorem 3. (Miranda et al. [START_REF] Miranda | Extreme points of some families of non-additive measures[END_REF]Prop. 11]) The set C ≤2 (N ) of 2-additive capacities is a (κ(2) -1)-dimensional polytope, whose extreme points are all at most 2-additive 0-1-capacities. These 0-1-capacities are of three different types:

(i) The unanimity games u {i} , i ∈ N (these are the extreme points of C 1 (N ));

(ii) The unanimity games u {i,j} , {i, j} ⊆ N ;

(iii) The conjugate of the unanimity games u {i,j} , {i, j} ⊆ N , given by u {i,j,} = u i + u ju {i,j} .

Moreover, the convex decomposition of any

µ ∈ C ≤2 (N ) is µ = {i,j}⊆N : m µ (ij)<0 (-m µ (ij))u {i,j} + {i,j}⊆N : m µ (ij)>0 m µ (ij)u {i,j} + i∈N m µ (i) + j∈N \i : m µ (ij)<0 m µ (ij) u {i} , (11)
with the shorthand ij standing for {i, j}.

The above result permits to know the number of extreme points of C ≤2 (N ). Summing the cardinality of all three types of extreme points, we find

|N | + |N | 2 + |N | 2 = |N | 2 .
So far, no general result is known for p > 2. The study becomes very complex in this case because there are extreme points which are not 0-1-valued (Miranda et al. [START_REF] Miranda | Extreme points of some families of non-additive measures[END_REF]).

The polytopes of k-ary capacities and 2-additive k-ary capacities

These polytopes have been studied by Grabisch and Labreuche [START_REF] Grabisch | On the decomposition of Generalized Additive Independence models[END_REF]. We denote by L = {0, 1, . . . , k} the set of participation levels. By using a similar proof as in Theorem 1, the following is easy to show. Theorem 4. The set of extreme points of C k (N ), the polytope of k-ary capacities, is the set of 0-1-valued k-ary capacities.

However, unlike the classical case, the following result is more difficult to obtain.

Theorem 5. Let k ∈ N. The set of extreme points of C ≤2 k (N ), the polytope of 2-additive k-ary capacities, is the set of 0-1-valued 2-additive k-ary capacities.

Let us define the support of v by:

supp(v) = x∈L N :m v (x) =0 supp(x),
which means that v depends only on the variables in supp(v). Theorem 6. For every k ∈ N, the size of the support of any 0-1-valued 2-additive k-ary capacity is at most 2.

Comparing with Theorem 3, we see that results that were true for classical 2-additive capacities still hold for k-ary capacities, for any k ∈ N: vertices are 0-1-valued, and the size of their support is at most 2.

We give more insight in the extreme points of this polytope. By the above theorem, we know that the size of the support of an extreme point is at most 2. If the size is 1, these vertices are simply the unanimity games u x with x of the form (0, . . . , 0, ℓ, 0, . . . , 0), ℓ ∈ {1, . . . , k}. Now, take a vertex, i.e., a 0-1-valued capacity v ∈ C ≤2 k (N ), with support of size 2, say {1, 2}. By analogy with the classical case, a profile x ∈ L N is winning for a 0-

1-valued v ∈ C ≤2 k (N ) if v(x) = 1,
and it is minimal winning if there is no other winning profile y such that y ≤ x coordinatewise. Therefore, minimal winning profiles are antichains in L N , and moreover, these antichains are in L {1,2} . Denumbering vertices amounts therefore to denumbering the number of antichains in L {i,j} for any i = j. This permits to count the total number of vertices of

C ≤2 k (N ), which is: 2k + 2 k + 1 -2 n(n -1) 2 -kn(n -2).
For a given antichain x 1 , . . . , x q in L {1,2} , supposing

x 1 1 ≤ • • • ≤ x q 1
, the Möbius transform of the corresponding extreme point is easy to obtain: put the value +1 for all elements x 1 , . . . , x q , -1 for all elements x ℓ ∨ x ℓ+1 , ℓ = 1, . . . , q -1 and 0 otherwise (see Figure 2). defining this cone. Indeed, many inequalities are redundant if [START_REF] Bilbao | Cooperative games on combinatorial structures[END_REF] is considered for all S, T ∈ 2 N . In terms of polyhedra, facets correspond to irredundant inequalities, and for the cone of supermodular games, are given by:

v(S ∪ {i, j}) + v(S) ≥ v(S ∪ i) + v(S ∪ j)
for all distinct i, j ∈ N and all S ⊆ N \ {i, j}.

The cone of supermodular games is not pointed as it contains the set of additive games, which form a linear space. We consider instead the cone of zero-normalized supermodular games, which is pointed because the only zero-normalized additive game is the null game 0. Let us denote the latter by G ♦ (N ). The problem of finding the extremal rays of G ♦ (N ) is difficult, and was already considered by Shapley in 1971 [START_REF] Shapley | Cores of convex games[END_REF]. He gave in this paper the 37 extremal rays of G ♦ (N ) with |N | = 4, but no indication for the general case. Later, Rosenmüller and Weidner [START_REF] Rosenmüller | Extreme convex set functions with finite carrier: general theory[END_REF] find all extremal rays of the cone of nonnegative supermodular games (it differs from G ♦ (N ) only by the addition of the extremal rays u {i} , i ∈ N ) by representing each such game as a maximum over shifted additive games:

v = max(φ 1 -α 1 , . . . , φ t -α t )
where φ 1 , . . . , φ t are additive games and α 1 , . . . , α t ∈ R + . Up to some additional conditions, the above representation can be put into a unique canonical form. For a given v and some H ⊆ {1, . . . , t}, |H| ≥ 2, where t pertains to the canonical form, consider the collection S H of sets such that v(S) = φ i (S)α i for every i ∈ H. Then v is an extremal ray if and only if φ 1 , . . . , φ t are the unique solution of the systems

φ i (S) -α i = v(S) (i ∈ H, S ∈ S H )
for all H ⊆ {1, . . . , t}, |H| ≥ 2. We refer the readers to Rosenmüller and Weidner [START_REF] Rosenmüller | Extreme convex set functions with finite carrier: general theory[END_REF] for the details.

More recently, Studený and Kroupa [START_REF] Studený | Core-based criterion for extreme supermodular functions[END_REF] proposed another criterion for finding the extremal rays of G ♦ (N ), based on the fact that supermodular games are exact and their core coincides with the Weber set (see below for definitions).

The core of games

Given a game v on N , its core is defined by core

(v) = {x ∈ R N | x(S) ≥ v(S) ∀S ∈ 2 N , x(N ) = v(N )}
where we use the shorthand x(S) = i∈S x i , S ⊆ N (the notation suggests to consider x as an additive game).

The core is an important concept which has been studied in depth, not only in cooperative game theory where it was introduced by Gillies [START_REF] Gillies | Some theorems on n-person games[END_REF] and studied by Shapley [START_REF] Shapley | On balanced sets and cores[END_REF][START_REF] Shapley | Cores of convex games[END_REF], but also in decision theory and combinatorial optimization. In game theory, vectors x ∈ core(v) are seen as payment vectors. v(N ) is the total benefit or cost saving achieved by cooperation of all players in N , which has to be shared among the players. Then x i represents the part of the "cake" which is given to player i. The condition x(N ) = v(N ) means that the whole cake is shared (this is called efficiency), while the condition x(S) ≥ v(S) means that the part given to coalition S is at least as big as the amount of benefit that S could have realized by itself (this is called coalitional rationality).

In decision theory, capacities are considered instead, so that the core of a capacity µ is the set of probability measures dominating µ (these are also called compatible probability measures). The interpretation is the following: µ(A) quantifies the amount of certainty of some event A ⊆ N . If not enough statistical information is available, µ is not a probability measure, but represents a lower bound of it. Therefore it makes sense to search for all probability measures which dominates µ. Now, the lower envelope of the core of µ does not necessarily give µ back. If this is true, µ is said to be exact (Schmeidler [START_REF] Schmeidler | Cores of exact games I[END_REF]). The situation described in this paragraph is a particular case of imprecise probabilities; see Walley [START_REF] Walley | Coherent lower (and upper) probabilities[END_REF].

In combinatorial optimization, where submodular games are considered, the dual notion of core was introduced by Edmonds [START_REF] Edmonds | Submodular functions, matroids, and certain polyhedra[END_REF], namely the base polyhedron associated to a polymatroid (N, ρ):

B(ρ) = {x ∈ R N + | x(A) ≤ ρ(A) ∀A ∈ 2 N , x(N ) = ρ(N )}.
It is easy to see that B(ρ) = core(ρ), the core of the conjugate game. Following Edmonds, the properties of the base polyhedron were studied in depth by Fujishige and Tomizawa [START_REF] Fujishige | A note on submodular functions on distributive lattices[END_REF] (see a summary in Fujishige [START_REF] Fujishige | Submodular functions and optimization[END_REF]Sec. 3.3]).

The core of games on N

The core may be empty: it suffices for example that i∈N v({i}) > v(N ) to make the core empty. When nonempty, the core is a bounded closed convex polyhedron, whose dimension is at most n -1. A necessary and sufficient condition for nonemptiness has been found by Bondareva [START_REF] Bondareva | Some applications of linear programming to the theory of cooperative games[END_REF] and Shapley independently [START_REF] Shapley | On balanced sets and cores[END_REF]. This condition is based on the notion of balanced collections, which are a generalization of partitions. A collection B of nonempty subsets in 2 N is balanced if there exist positive coefficients λ S , S ∈ B, such that

S∈B,S∋i λ S = 1 (i ∈ N ).
For example, taking N = {1, 2, 3}, B = {{1, 2}, {1, 3}, {2, 3}} with coefficients 1 2 , 1 2 , 1 2 is a balanced collection. Now, a game v is balanced if for any balanced collection with coefficients λ S , S ∈ B, it holds

S∈B λ S v(S) ≤ v(N ). ( 12
)
Theorem 7. The core of a game v is nonempty if and only if v is balanced.

The foregoing theorem is usually referenced as the weak form of the Bondareva-Shapley theorem. A sharp form is obtained by imposing inequality [START_REF] Derks | On the number of extreme points of the core of a transferable utility game[END_REF] only for minimal balanced collections, i.e., those balanced collections which do not contain a proper balanced subcollection.

A complete description of the core is obtained through its extreme points in the case of supermodular games. Let us consider the set of all permutations on N , denoted by S(N ). To any permutation σ ∈ S(N ), we make correspond a chain in 2 N :

∅ = S 0 ⊂ S 1 ⊂ • • • ⊂ S n = N with S i = {σ(1), . . . , σ(i)}.
Let v be a game. To each permutation σ ∈ S(N ) we assign a marginal worth vector x σ,v in R N defined by:

x σ,v σ(i) := v(S i ) -v(S i-1 ) = v(S i-1 ∪ σ(i)) -v(S i-1 ) (i ∈ N ).
Observe that

x σ,v (S i ) = v(S i ) (i = 1, . . . , n). ( 13
)
The convex hull of all marginal vectors is called the Weber set:

Web(v) = conv({x σ,v } σ∈S(N ) ).
The following inclusion always holds:

core(v) ⊆ Web(v).
The reverse inclusion holds if and only if v is supermodular. More precisely, we have:

Theorem 8.
The following are equivalent.

(i) v is supermodular;

(ii) All marginal vectors x σ,v , σ ∈ S(N ), belong to the core;

(iii) core(v) = Web(v); (iv) ext(core(v)) = {x σ,v } σ∈S(N ) .
Parts of this theorem have been shown several times. Up to the knowledge of the author, the earliest version is due to Dempster in 1967 [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF]. He proved that the marginal vectors are extreme points of the core for capacities with a nonnegative Möbius transform (usually called belief functions). Shapley showed in 1971 [START_REF] Shapley | Cores of convex games[END_REF] implications (i)⇒(ii) and (i)⇒(iv). At the same time, Edmonds proved (i)⇒(iv) [START_REF] Edmonds | Submodular functions, matroids, and certain polyhedra[END_REF], and Ichiishi proved (ii)⇒(i) in 1981 [START_REF] Ichiishi | Super-modularity: applications to convex games and to the greedy algorithm for LP[END_REF].

Note that so far, no general result is known on the vertices of the core for games which are not supermodular, except on the maximum number of vertices. Derks and Kuipers [START_REF] Derks | On the number of extreme points of the core of a transferable utility game[END_REF] established that, as for supermodular games, the upper bound of the number of vertices is n!.

Partial results on vertices have been obtained by Núñez and Rafels [START_REF] Núñez | On extreme points of the core and reduced games[END_REF][START_REF] Núñez | Characterization of the extreme core allocations of the assignment game[END_REF], in particular for almost convex games. A game v on N is almost convex if it satisfies the supermodularity condition (1) for all S, T ⊂ N (in other words, every subgame v S for ∅ = S ⊂ N is supermodular). Then, for those games, the set of extreme points of the core is given by

ext(core(v)) = i∈N ((v(N ) -v(N \ i)) i , ext(core(v i ))). ( 14
)
We explain the notation. For any i ∈ N , the game v i is a game on N \ i defined by

v i (S) = max(v(S), v(S ∪ i) -(v(N ) -v(N \ i))) (S ⊆ N \ i). Now, ((v(N )-v(N \i)) i , ext(core(v i ))) is a n-dim vector whose ith component is v(N )-v(N \i),
and n-1 remaining components are just ext(core(v i )). Núñez and Rafels show that if v is almost convex, then v i too is almost convex, for any i ∈ N . Hence ( 14) permits to recursively compute the extreme points of the core, coordinate by coordinate.

The core of games on set systems

When the domain of a game is restricted to some family F ⊂ 2 N , the study of the core becomes fairly more complicated. A survey on this topic has been done by the author in [START_REF] Grabisch | The core of games on ordered structures and graphs[END_REF], to which the reader is referred for details and other results. We give here the most fundamental results, as well as new ones.

A set system F is a subcollection of 2 N containing N and ∅. We denote by (v, F) a game on N whose domain is F (this is called a game with restricted cooperation (Faigle [START_REF] Faigle | Cores of games with restricted cooperation[END_REF])). Many examples of set systems have been studied (lattices, matroids, antimatroids, regular set systems, etc., see, e.g., the monograph of Bilbao [START_REF] Bilbao | Cooperative games on combinatorial structures[END_REF], or [START_REF] Bilbao | Cooperative games under augmenting systems[END_REF][START_REF] Bilbao | The core of games on convex geometries[END_REF]). We mainly focus in this section on set systems which are distributive lattices, that is, of the form F = O(N ) with N endowed with a partial order . Games on such kind of set systems have been introduced by Faigle and Kern [START_REF] Faigle | The Shapley value for cooperative games under precedence constraints[END_REF] under the name game with precedence constraints.

The core of a game with restricted cooperation is defined as in the classical case:

core(v, F) = {x ∈ R N | x(S) ≥ v(S) ∀S ∈ F, x(N ) = v(N )}.
While the core is still a convex closed polyhedron of dimension at most n-1, unlike the classical case, it may be unbounded, or even not pointed. We study its structure in the next paragraphs.

As a general fact, we know from the theory of polyhedra that the core is the Minkovsky sum of its convex part (the convex hull of its vertices) and the conic part, called the recession cone (conic combination of its extremal rays) and denoted by core(0, F), because it is given by core(0,

F) = {x ∈ R N | x(S) ≥ 0 ∀S ∈ F, x(N ) = 0}.
Nonemptiness. The classical result of Bondareva-Shapley still holds when 2 N is replaced by F. However, something more can be said.

Theorem 9. (Grabisch and Sudhölter [START_REF] Grabisch | The bounded core for games with precedence constraints[END_REF]) Let F = O(N, ) be a distributive lattice. If (N, ) is connected, the core of any game on F is nonempty.

Here, "connected" means that the Hasse diagram of the poset, seen as a graph, is connected.

Pointedness. Supposing core(v, F) nonempty, it is pointed if and only if the system

x(S) = 0 (S ∈ F \ {∅})
has 0 as unique solution. In this case, we say that F is nondegenerate, otherwise it is degenerate.

Example 1. Consider n = 3 and F = {∅, 1, 2, 123}. The recession cone core(0, F) reads

x 1 ≥ 0 x 2 ≥ 0 x 1 + x 2 + x 3 = 0.
The core, if nonempty, is pointed because putting equality everywhere leads to a system whose unique solution is 0. Now, the core is not bounded because the vector (1, 0, -1) belongs to core(0, F).

There are some obvious sufficient conditions for F to be nondegenerate or degenerate. For example, if {i} ∈ F for every i ∈ N , or if F contains a maximal chain of length n, then F is nondegenerate; it is degenerate if there exists a macro-player, that is, a subset K ⊂ N of at least two elements such that for any S ∈ F, either S ⊇ K or S ∩ K = ∅. In case of a set system closed under intersection, this turns out to be a sufficient and necessary condition (Faigle et al. [START_REF] Faigle | Games on concepts lattices: Shapley value and the core[END_REF]).

Boundedness The core is bounded if and only if the conic part is reduced to the zero vector: core(0, F) = {0}. The following result, shown by Derks and Reijnierse [START_REF] Derks | On the core of a collection of coalitions[END_REF], gives a necessary and sufficient condition for boundedness.

Theorem 10. Let v be a balanced game on a set system F. Then core(v, F) is bounded if and only if F is nondegenerate and F \ {∅, N } is balanced.

As we will see in the next paragraph, when F = O(N ), the core is unbounded unless (N, ) is an antichain Extremal rays of the core. Recall that in a poset (N, ), i ≺• j means i ≺ j and there is no k such that i ≺ k ≺ j. The extremal rays of the core when F = O(N ) have been found by Fujishige and Tomizawa [START_REF] Fujishige | A note on submodular functions on distributive lattices[END_REF], and rediscovered by Derks and Gilles [START_REF] Derks | Hierarchical organization structures and constraints on coalition formation[END_REF].

Theorem 11. Let F = O(N, ) be a set system. The conic part of the core reads core(0,

F) = cone(1 {j} -1 {i} | i, j ∈ N such that j ≺• i).
The above result says that there is exactly one extremal ray per link in the Hasse diagram of the poset (N, ). Consequently, under the assumption that F = O(N ), the only case where the core is bounded is when (N, ) is an antichain, i.e., F = 2 N . Example 2. Consider n = 4 and the poset (N, ) given on Figure 1. Then there are three extremal rays: (0, 0, 1, -1), (1, -1, 0, 0) and (0, -1, 1, 0).

The above result has been recently extended by Faigle et al. [START_REF] Faigle | Games on concepts lattices: Shapley value and the core[END_REF] for set systems which are closed under intersection.

Theorem 12. Let (N, ) be a poset, and consider a set system F ⊆ O(N, ) which is closed under intersection. Then 1 {i} -1 {j} is a ray of core(0, F) for every i ≺• j in the poset (N, ), but not necessarily extremal. Moreover, core(0, F) = core(0, O(N, )) if and only if any S ∈ O(N, ) \ F can be written as a union of disjoint sets in F. Observe that F \ O(N ) = {1234}, and that it is not possible to write 1234 as a union of disjoint sets. Hence core(0, F) = core(0, O(N )). This can be verified as r = (0, 0, 1, -1, 0), which is extremal in core(0, O(N )), is no more an extremal ray of core(0, F).

Extreme points of the core. We give now the generalized version of Theorem 8, valid for set systems of the form F = O(N, ). Since these set systems are closed under union and intersection, the definition of supermodularity is still valid. A permutation σ ∈ S(N ) is compatible with F if the corresponding maximal chain lies in F. We denote by S(F) the set of permutations compatible with F. Theorem 13. Let v be a game on (N, F) with F = O(N, ). The following propositions are equivalent.

(i) v is supermodular;

(ii) x σ,v ∈ core(v, F) for all σ ∈ S(F);

(iii) core(v, F) = conv({x σ,v | σ ∈ S(F)}) + core(0, F); (iv) ext(core(v, F)) = {x σ,v | σ ∈ S(F)}.
As in the classical case, this result has been shown both in combinatorial optimization, by Fujishige and Tomizawa [START_REF] Fujishige | A note on submodular functions on distributive lattices[END_REF], and in game theory, by Derks and Gilles [START_REF] Derks | Hierarchical organization structures and constraints on coalition formation[END_REF].

Bounded faces of the core. We consider in this section the case where F is of the form O(N, ). The core being unbounded unless (N, ) is an antichain, it is important to search for remarkable bounded subsets, for example bounded faces. These are obtained through the notion of normal collection (Grabisch [22]). It is well known from the theory of polyhedra that faces of a polyhedron defined by a system of inequalities are obtained by turning some of the inequalities into equalities. Since in the case of the core, inequalities correspond to subsets of N , a normal collection is a collection of sets whose corresponding face is bounded. Formally, a normal collection is any collection N ⊂ F \ {∅, N } of sets such that core N (0, F) = {x ∈ R N | x(S) ≥ 0 ∀S ∈ F, x(S) = 0 ∀S ∈ N , and x(N ) = 0} = {0}.

Note that by convention, N ∈ N . If core(v, F) = ∅, core N (v) is a bounded face of the core. It may be empty even if core(v, F) is nonempty. The union of all bounded faces of core(v, F) is called the bounded core (Grabisch and Sudhölter [START_REF] Grabisch | The bounded core for games with precedence constraints[END_REF]), and denoted by core b (v, F). It is equivalently defined by

core b (v, F) = {x ∈ core(v, F) | ∀j ≺• i, ∀ǫ > 0, x + ǫ(1 {i} -1 {j} ) ∈ core(v, F)}
and was axiomatized as a solution concept in [START_REF] Grabisch | The bounded core for games with precedence constraints[END_REF].

We give a very simple criterion to find normal collections. We say that an extremal ray r of core(0, F) is deleted by equality x(S) = 0, S ∈ F, if core {S} (0, F) = {x ∈ core(0, F) | x(S) = 0} does not contain r any more.

Lemma 1. Let F = O(N ). For i, j ∈ N such that j ≺• i, the extremal ray 1 {j} -1 {i} is deleted by equality x(S) = 0 if and only if S ∋ j and S ∋ i. The above simple example shows that in general there are many normal collections, inducing faces of various dimensions. Obviously, the most interesting ones are those of largest dimension, i.e., those defined by the smallest normal collections (in cardinality). It is proved in (Grabisch [START_REF] Grabisch | Ensuring the boundedness of the core of games with restricted cooperation[END_REF]) that a normal collection contains at least h(N ) subsets, where h(N ) is the height of (N, ), i.e., the length of a longest maximal chain. Observe that in Example 4, h(N ) = 1. It is useful to introduce the following properties of normal collections. Consider (N, ) with h(N ) > 0, and a normal collection N = {N 1 , . . . , N q }. (i) N is a minimal collection if no proper subcollection is normal.

(ii) N is a nested collection if it is a chain in F.

It turns out that for supermodular games, minimal nested normal collections are sufficient to generate all bounded faces of maximal dimension. We denote by MN N C(F) the set of minimal nested normal collections of F. Theorem 14. (Grabisch and Sudhölter [START_REF] Grabisch | On the restricted cores and the bounded core of games on distributive lattices[END_REF]) (i) For any supermodular game v and any nested normal collection

N of F, core N (v, F) = ∅. Moreover, if v is strictly supermodular, then dim core N (v, F) = n -|N | -1.
(ii) For any supermodular game v,

core b (v, F) = N ∈MN N C(F ) core N (v, F)
Moreover, no term in the union is redundant if v is strictly supermodular.

(iii) Let N be a normal collection of F. If v is strictly supermodular, then core N (v, F) = ∅ if and only if N is nested.

8 The k-additive core of games

Through the concept of k-additive games, there is a natural generalization of the core. Indeed, using the identity between a vector x ∈ R N and an additive game on N , the core of a game v can be defined as the set of additive games φ such that φ ≥ v pointwise and φ(N ) = v(N ). Since additive games are 1-additive games, it is natural to introduce the k-additive core as the set of (at most) k-additive games dominating a game v and coinciding on N :

core k (v) = {φ ∈ G ≤k (N ) | φ(S) ≥ v(S), ∀S ∈ 2 N , φ(N ) = v(N )}.
The k-additive core has been proposed by Vassil'ev [START_REF] Vassil'ev | Polynomial cores of cooperative games[END_REF] and rediscovered later by Grabisch and Miranda [START_REF] Grabisch | On the vertices of the k-additive core[END_REF][START_REF] Miranda | k-balanced games and capacities[END_REF]. The main advantage of the k-additive core is that, contrarily to the core, it is never empty as soon as k ≥ 2. However, it is unbounded. Theorem 15. (Miranda and Grabich [START_REF] Miranda | k-balanced games and capacities[END_REF]) The k-additive core is a convex polyhedron, nonempty for every game as soon as k ≥ 2.

Theorem 16. (Gonzalez and Grabisch [START_REF] Gonzalez | Preserving coalitional rationality for non-balanced games[END_REF]) For all k ≥ 2, the k-additive core is unbounded and pointed. Moreover, for k = 2, its extremal rays are of the form 1 i -1 ij , for all i = j ∈ N .

The k-additive core as a solution concept in cooperative game theory

Though its interpretation in cooperative game theory is not immediately clear, it can still be explained in terms of payoff vectors, thus giving a new concept of solution of a game. Indeed, any φ ∈ core k (v) can be written as, using [START_REF] Crama | Boolean functions[END_REF] and recalling that φ is k-additive:

φ(S) = T ⊆S |T |≤k m φ (T ) (S ∈ 2 N ).
Now, m φ can be interpreted as a general payoff vector, in the sense that a payoff is given not only to individuals, but also to coalitions, up to size k. Payments may be negative, but the total sum allocated to a coalition S is always at least as large as v(S). If a payment only to individuals is eventually required, then a second step is necessary, consisting in sharing the payment given to coalitions among their individuals. This can be done by different means, e.g., sharing functions, bargaining, or when the payment is negative, by using rules for bankruptcy problems. Let us focus only on sharing functions. A sharing function is a mapping q

: 2 N \ {∅} × N → [0, 1] satisfying q(K, i) = 0 if i ∈ K, i∈K q(K, i) = 1, ∅ = K ⊆ N.
We denote by Q(N ) the set of all sharing functions. Given φ ∈ core k (v) and a sharing function q, x q (φ) ∈ R N is an efficient payoff vector defined by

x q i (φ) = S∋i q(S, i)m φ (S) (i ∈ N ).
Now, the set of all such payoff vectors, considering all possible sharing functions, is the selectope of φ (Derks, Haller and Peters [START_REF] Derks | The selectope for cooperative games[END_REF]):

sel(φ) = {x q (φ) | q ∈ Q(N )}.
A surprising result shown by Grabisch and Li [START_REF] Grabisch | On the set of imputations induced by the k-additive core[END_REF] is the following: if the sharing function gives, for every K, a nonnull portion of m φ (K) to every i ∈ K, then the selectope of φ is the set of all efficient payoff vectors. Formally:

Theorem 17. Let 2 ≤ k ≤ n.
For any q ∈ Q(N ) such that q(K, i) > 0 for all ∅ = K ⊆ N and i ∈ K, for any game v, we have

{x q (φ) | φ ∈ core k (v)} = {x ∈ R N | x(N ) = v(N )}.
This result shows that the k-additive core is a very large set, and some selection has to be made in it. This problem has been addressed by Gonzalez and Grabisch [START_REF] Gonzalez | Preserving coalitional rationality for non-balanced games[END_REF]. They propose to take those elements in core k (v) which minimize the total amount of payment to non-singleton coalitions.

Vertices of the k-additive core

A result similar to Theorem 8 has been obtained for the k-additive core, giving extreme points of it for a certain class of games. However, the study of the extreme points is much more complex than for the classical case, and not all vertices are known so far. We present below the machinery to find some of them, details can be found in (Grabisch and Miranda [START_REF] Grabisch | On the vertices of the k-additive core[END_REF]).

We begin by introducing some notation and new notions. We denote by P k (N ) the collection of subsets of N containing at most k elements, and we use also P k * (N ) = P k (N ) \ {∅}. Given ℓ ≥ 2, a game v is said to be ℓ-monotone if for any family A 1 , . . . , A ℓ of sets in 2 N , it holds:

v( ℓ i=1 A i ) ≥ K⊆{1,...,ℓ} K =∅ (-1) |K|+1 v( j∈K A j ).
Observe that 2-monotonicity is nothing but supermodularity. A game is totally monotone if it is ℓ-monotone for every ℓ ≥ 2. Totally monotone capacities are called belief functions. It is well known that v is totally monotone if and only if m v (S) ≥ 0 for all S ⊆ N , |S| > 1.

We consider the subset of the k-additive core formed by all core elements which are totally monotone: core k ∞ (v) = {φ ∈ core k (v) | m φ (S) ≥ 0, ∀S ∈ 2 N , |S| > 1}. In order to find vertices, the main idea is to find a substitute of marginal vectors, hence of permutations on N . Since now the payment is done to every coalition of size at most k instead to individuals, permutations ahould be defined on P k * (N ) instead of N . Let us then consider a given total order ≺ on P k * (N ). We consider now orders with peculiar properties. A total order ≺ is said to be (i) compatible if for all i, j ∈ N , i ≺ j implies S ∪ i ≺ S ∪ j, for any S ∈ P k-1 (N ), i, j ∈ S;

(ii) ⊆-compatible if A ⊆ B implies A ≺ B;

(iii) strongly compatible if it is compatible and ⊆-compatible;

(iv) weakly compatible if it is compatible but not ⊆-compatible.

Observe that in Ex. 5, the order is compatible but not strongly compatible. It can be shown that if ≺ is compatible, then A(B) is either empty or an interval [B, B], that is, a Boolean lattice. Moreover, A(B) is nonempty for all B ∈ P k * (N ) if and only if ≺ is ⊆-compatible. It follows that for strongly compatible orders, all achievable families are nonempty Boolean lattices.

Achievable families play the rôle of maximal chains. As it can be easily checked, with k = 1, total orders on singletons are permutations on N , and all these orders are strongly compatible. Moreover, taking a permutation σ on N and considering the order σ(1) ≺ • • • ≺ σ(n), we get A({σ(j)}) = [{σ(j)}, {σ(1), . . . , σ(j)}],

i.e., the top element of the lattice is {σ(1), . . . , σ(j)}. Then the collection of all top elements gives the maximal chain associated to σ (see Example 6 below).

The next step is to define the counterpart of marginal vectors. Consider a game v on N , and a total order ≺ on P k * (N ). The game v ≺ is defined through its Möbius transform m ≺ by

m ≺ (B) := A∈A(B) m(A), if A(B) = ∅ 0, otherwise, (15)
for all B ∈ P k * (N ), and m ≺ (∅) := 0.

Example 6. We consider n = 3, k = 1 and the order on singletons 2 ≺ 1 ≺ 3. The achievable families as well as the corresponding maximal chain is given in Figure 5. Computing m ≺ by

Figure 1 :

 1 Figure 1: n = 4. Left: a poset (N, ). Right: the set of downsets of (N, ), ordered by inclusion. It is a distributive lattice (F, ⊆). Its join-irreducible elements are in red, and the poset of join-irreducible elements (J (F), ⊆) is isomorphic to (N, )

7

  Documents de travail du Centre d'Economie de la Sorbonne -2016.81 . of m µ (A) 1(0) -1 -2 -3 -4 -10 -. of m µ (A) -35 -56 -126 -252 -462

  1 -10 45 -120 210 -252 210 -120 45 -10 1 n = 12 1 -11 55 -105 330 -462 462 -330 165 -55 11 -1

Figure 2 :

 2 Figure 2: Vertices of C ≤2 k (N ) with k = 4. In red: an antichain in L {1,2} ; values in blue indicate the Möbius transform of the corresponding vertex

Example 3 .

 3 Consider n = 5 and F ⊂ O(N ) depicted on Figure 3 together with (N, ).

Figure 3 :

 3 Figure 3: Left: a poset (N, ). Right: a set system F ⊂ O(N ). Join-irreducible elements are in red. O(N ) \ F = {1234}

Example 4 .

 4 (Ex. 3 continued) The three extremal rays can be deleted simply by the subset {1, 3}. Hence N = {{1, 3}} is a normal collection, but N = {{1}, {3}} and N = {{1}, {3}, {1, 3}} are normal collections as well.

Example 5 .

 5 For any B ∈ P k * (N ), we define the achievable family of B induced by ≺ byA(B) := {A ⊆ N | A ⊇ B, ∀K ⊆ A, K ∈ P k * (N ), K B}.Let us take n = 3, k = 2, and the total order 1 ≺ 2 ≺ 12 ≺ 13 ≺ 23 ≺ 3 on P 2 * (N ). The achievable families are given on Figure4in red. Observe that A({3}) is a Boolean lattice, and that A(13) = ∅.

Figure 4 :

 4 Figure 4: A total order (in blue) on P 2 * (N ) with n = 3 and the induced achievable families (in red)

Table 1 :

 1 The Dedekind numbers M (n) for 0 ≤ n ≤ 8

	n	M (n)
	0	2
	1	3
	2	6
	3	20
	4	168
	5	7581
	6	7828354
	7	2414682040998
	8 56130437228687557907788

Table 2

 2

	below gives the first values of the bounds. Using the Stirling's approximation 2n n ≃ 4 n √ πn for n → ∞, we obtain the asymptotic behavior of the bounds:

Table 2 :

 2 Lower and upper bounds for the Möbius transform of a capacity Observe that the capacities µ * N , µ N * are such that their value is 1 on the first lines of the Boolean lattice 2 N , and 0 otherwise. Table3(from which Table2is obtained) gives the values of m µ (N ) for all capacities µ on N such that their value on the first k + 1 lines is 1, and 0 otherwise. Considering an entry (n, k) of the table, which gives the value of m µ (N ), observe

	n/k	0	1	2	3	4	5	6	7	8	9 10 11

Documents de travail du Centre d'Economie de la Sorbonne -2016.81

In general, normalization is not required. We assume it throughout this paper for convenience.

As far as possible, we stick to these notations: ξ for set functions, v for games and µ for capacities. 2 Documents de travail du Centre d'Economie de la Sorbonne -2016.81

Documents de travail du Centre d'Economie de la Sorbonne -2016.81

Documents de travail du Centre d'Economie de la Sorbonne -2016.81

 Theorem 18. A game v is (k + 1)-monotone if and only if for all compatible orders ≺, v ≺ is an element of the k-additive core. Moreover, when v is (k + 1)-monotone,

However, unlike the classical case k = 1, the above construction based on strongly compatible orders is far from giving all vertices. In fact, the number of vertices obtained by this construction is at most n! k! (observe that with k = 1, we recover that the maximum number of vertices of the core is n!). When k = n -1, it is however possible to get all vertices, as shown in the next theorem.

Theorem 19. Let v be any game in G(N ), with Möbius transform m v .

vertices, among which n vertices come from strongly compatible orders. They are given by their Möbius transform:

vertices, of which none comes from a strongly compatible order. They are given by their Möbius transform:

for all B 0 ⊂ N such that |N \ B 0 | is even.


Holger Heumann
email: holger.heumann@inria.fr

Francesca Rapetti
email: francesca.rapetti@unice.fr

Minh Duy Truong
email: truongminhduy91@yahoo.com

FEMs on composite meshes for plasma equilibrium simulations in tokamaks

We rely on a combination of different finite element methods on composite meshes, for the simulation of axisymmetric plasma equilibria in tokamaks. One mesh with Cartesian quadrilaterals covers the vacuum chamber and one mesh with triangles discretizes the region outside the chamber. The two meshes overlap in a narrow region around the chamber. This approach gives the flexibility to achieve easily and at low cost higher order regularity for the approximation of the flux function in the area that is covered by the plasma, while preserving accurate meshing of the geometric details in the exterior. The continuity of the numerical solution across the boundary of each subdomain is enforced by a new mortar-like projection.

Introduction

The possibility of using composite meshes in finite element (FE) simulations of industrial problems is a recurrent topic [START_REF] Mote | Global-local finite element[END_REF][START_REF] Steger | On the use of composite grid schemes in computational aerodynamics[END_REF][START_REF] Fish | Elements with embedded localization zones for large deformation problems[END_REF][START_REF] Chesshire | Composite overlapping meshes for the solution of partial differential equations[END_REF][START_REF] Parter | On the overlapping grid method for elliptic boundary value problems[END_REF]. Composite meshes are involved as soon as the global discretization of a PDE combines discretizations on local (overlapping or non-overlapping) subdomains, each suitably triangulated by non-matching grids. The reason for using composite meshes are various: fitting the geometry or the local smoothness of the solution, resolving multiple scales in regions with irregular data, using fast solvers on structured grids or a divide-andconquer/domain decomposition approach to very large problems on parallel machines.

In the present case, we are looking for a simple and practical approach to introduce in certain parts of the computational domain FE functions that are not only continuous, but have also first order, second order or higher order continuous derivatives. In general it is very difficult to introduce FE spaces over simplicial unstructured meshes with such properties. On the other hand, if we work with Cartesian meshes this becomes very simple. It is sufficient to use tensor products of spline spaces with sufficiently high regularity. So, as it is naive to expect that technical devices can be entirely triangulated with Cartesian meshes, we introduce composite meshes involving Cartesian meshes in those subdomains where we want high regular FE representations and triangular unstructured meshes in those subdomains where we want conformity with the geometry.

The industrial application we consider concerns the free boundary plasma equilibrium in tokamaks for nuclear fusion [START_REF] Blum | Numerical Simulation and Optimal Control in Plasma Physics[END_REF], mathematically described by the force balance and Maxwell's equations in the eddy-current approximation. By symmetry considerations, the free boundary plasma equilibrium problem can be reduced to a scalar semi-linear elliptic one for the poloidal flux. As the magnetic field and the current density are tangential to the level sets of the poloidal flux, the precise calculation of the level set distribution for the poloidal flux is fundamental in tokamak science. Hence, it is important to have good approximations not only of the poloidal flux but also of its derivatives.

In Figure 1 we show a sketch of the cross section of a tokamak. It contains the geometrical details such as coils, passive structures and the iron core, that need to be accurately resolved by a triangulation. A peculiarity of the free boundary plasma equilibrium problem is the unknown plasma domain, that is implicitly given as the domain that is bounded by the largest level set that it not intersected by the limiter. At the beginning, in tokamak devices the plasma was always attached to the limiter, later the focus shifted towards devices with so called divertors that allow to create plasmas that are completely detached from material. The boundary of such a plasma is characterized by saddle points, also called X-points, of the poloidal flux. The magnetic axis, located at the maximum of the poloidal flux, is another important critical point to be computed. So, here again, continuous higher derivatives of approximations of the poloidal flux, are very desirable. In [START_REF] Heumann | A finite element method with overlapping meshes for free-boundary axisymmetric plasma equilibria in realistic geometries[END_REF], we showed that the numerical calculation of free boundary plasma equilibria highly benefits from approximating the poloidal flux through some higher regular FE functions in the interior of the limiter. In the present paper, we rather analyse the precision of the proposed approach, by varying the discretization parameters. We thus compute the approximation error between the computed and the synthetic solution of a model problem for the same method adopted in [START_REF] Heumann | A finite element method with overlapping meshes for free-boundary axisymmetric plasma equilibria in realistic geometries[END_REF], by varying, for example, the local polynomial degree in the subdomains, the size of the overlap between the meshes, the local size of the mesh elements. Indeed, FE methods on composite meshes are widely used in practice, but their theoretical foundation is fairly limited in the literature. Therefore, we report here experimental convergence results for different discretization schemes involving composite meshes.

The outline is the following: In section 2 we recall the classical mortar element method (MEM) for overlapping meshes in order to introduce, in the following section 3, a modified method (MEM-M) that simplifies the implementation by avoiding integrals over cut elements. We then present experimental convergence results.

The mortar element method (MEM) with overlapping meshes

We consider the following Poisson problem for the unknown ψ in the bounded domain Ω ⊂ R n with boundary Γ = ∂ Ω :

-∇ • (∇ψ) = f in Ω and ψ |∂ Ω = ψ 0 in Γ , (1)
where ∇ (resp. ∇• ) is the gradient (resp. divergence) operator in R n . The righthand side f and the Dirichlet data ψ 0 are given. Let L 2 (Ω ), be the functional space of measurable functions on Ω that are square integrable in Ω and

H 1 (Ω ) = {u ∈ L 2 (Ω ), ∇u ∈ L 2 (Ω ) 2 } the Hilbert space endowed with the norm u 2 H 1 (Ω ) = u 2 Ω + |u| 2 H 1 (Ω ) where |u| 2 H 1 (Ω ) = ∇u 2 Ω . Let Ω in ⊂ Ω be a subdomain with Ω in ∩ Γ = / 0 and Ω ex = Ω \ Ω in the complement of Ω in in Ω .
Further, the boundary of Ω in , γ := ∂ Ω in , is the interface between Ω ex and Ω in . To formulate (1) as a variational problem in a domain decomposition framework, let us introduce the functional space

H g = {(v, w) ∈ H 1 (Ω ex ) × H 1 (Ω in ), v |Γ = g, v |γ = w |γ }.
Then, the weak formulation of (1) is:

Find (ψ ex , ψ in ) ∈ H ψ 0 s.t. for all (v, w) ∈ H 0 Ω ex ∇ψ ex • ∇v dx + Ω in ∇ψ in • ∇w dx = Ω ex f v dx + Ω in f w dx . (2)
We wish to introduce different types of meshes T ex and T in in the two subdomains Ω ex and Ω in . To achieve a maximum of flexibility we do not expect the meshes T ex and T in to be conforming with Ω ex and Ω in . More precisely, we denote by Ω ex h and Ω in h the domains covered by the mesh elements of T ex and T in , resp., and we only require that

Ω ex ⊂ Ω ex h ⊂ Ω , Γ ⊂ ∂ Ω ex and Ω in ⊂ Ω in h ⊂ Ω .
Hence the approximation of (2) enters into the framework of overlapping domain decomposition methods. Let

γ ex = ∂ Ω ex h \ Γ and γ in = ∂ Ω in h be the two boundaries of Ω ex h and Ω in h
in Ω that replace the interface γ. Then we introduce the space

V g = {(v, w) ∈ V ex × V in , v |Γ = Π Dir g, v |γ ex = Π ex w, w |γ in = Π in v} ,
where V ex and V in are H 1 (Ω ex h ) and H 1 (Ω in h ) conforming FE spaces defined over T ex and T in . The operators Π Dir , Π ex and Π in are projections onto the Dirichlet trace spaces V Γ = tr |Γ V ex , V ex γ := tr |γ ex V ex and V in γ := tr |γ in V in . The MEM with overlapping domains [START_REF] Kuznetsov | Overlapping domain decomposition with non-matching grids[END_REF][START_REF] Cai | Overlapping nonmatching grid mortar element methods for elliptic problems[END_REF][START_REF] Achdou | The mortar element method with overlapping subdomains[END_REF] applied to (2) reads: Find (ψ ex , ψ in ) ∈ V ψ 0 such that

a ex s (ψ ex , v) + a in t (ψ in , w) = ex s ( f , v) + in t ( f , w) ∀(v, w)∈V 0 , (3) where a
M s (ψ, v) := Ω M h ∇ψ • ∇v dx - Ω ex h ∩Ω in h s ∇ψ • ∇v dx , M s ( f , v) := Ω M h f v dx - Ω ex h ∩Ω in h s f v dx ,
for M = ex and M = in. Optimal convergence results are available when s + t = 1 and Π ex , Π in , are the L 2 projections onto tr |γ ex V ex , tr |γ in V in , resp. [START_REF] Cai | Overlapping nonmatching grid mortar element methods for elliptic problems[END_REF][START_REF] Achdou | The mortar element method with overlapping subdomains[END_REF]. However, two very restrictive disadvantages occur with the formulation (3):

1. The assembling of the stiffness matrices associated to a ex s (•, •) and a in t (•, •) involves products of basis functions defined on different meshes. Similarly, the assembling of the load vectors corresponding to ex s ( f , •) and in t ( f , •) involves integration over intersections of elements from different meshes. 2. The stability of MEMs requires the projections Π ex and Π in to be stable in H 1 2 . The obvious choice of L 2 projections involves again surface integrals of products of basis functions defined on different meshes.

In the following section we will introduce two mortar-like mappings different from the standard L 2 projection, that allow to choose s = t = 0 in (3) and hence avoid the assembling of the stiffness matrix for basis functions on two different meshes.

A Modified Mortar Mapping (MEM-M)

We recall that the FE spaces V ex and V in can be represented as direct sums

V ex = V ex • ⊕ V ex γ and V in = V in • ⊕ V in γ where V ex γ = tr |γ ex V ex and V in γ = tr |γ in V in are the earlier introduced trace spaces of V ex and V in . Let us define two mappings Π ex f ψ in for ψ in = ψ in • + ψ in γ , with ψ in • ∈ V in • , ψ in γ ∈ V in γ and Π in f ψ ex for ψ ex = ψ ex • + ψ ex γ , with ψ ex • ∈ V ex • , ψ ex γ ∈ V ex γ with: Π ex f ψ in := Π ex (ψ in γ +Ψ in • ), with a in 0 (Ψ in • , w) = in 0 ( f , w) -a in 0 (ψ in γ , w) ∀w ∈ V in • ,
where Π ex is either the L 2 -projection or standard nodal interpolation operator onto V ex γ and Π in f analogously defined. We then introduce the space

V g, f = {(v, w) ∈ V ex × V in , v |Γ = Π Dir g, v |γ ex = Π ex f w, w |γ in = Π in f v} ,
and obtain the following modified version of the MEM for overlapping meshes:

Find (ψ ex , ψ in ) ∈ V ψ 0 , f such that a ex 0 (ψ ex , v) + a in 0 (ψ in , w) = ex 0 ( f , v) + in 0 ( f , w) ∀(v, w)∈V 0,0 , (4)
A similar approach with the lowest order FE spaces in the non-destructive testing context has been adopted in [START_REF] Christophe | An overlapping non-matching grid mortar element method for Maxwell's equations[END_REF][START_REF] Christophe | A mortar element approach on overlapping non-nested grids: application to eddy current non-destructive testing[END_REF]. It can be shown that ( 4) is equivalent to the following formulation. Find (ψ ex , ψ in ) ∈ V ex × V in , ψ ex |Γ = Π Dir g such that:

a ex 0 (ψ ex , v) + a in 0 (ψ in , w) = ex 0 ( f , v) + in 0 ( f , w) ∀(v, w)∈V ex • × V in • , v |Γ =0 ψ ex |γ ex = Π in ψ in , ψ in |γ in = Π ex ψ ex , (5)
which corresponds to the numerical zoom formulation in [START_REF] Hecht | Numerical zoom and the Schwarz algorithm[END_REF]. When the Π ex and Π in are interpolation operators and V ex and V in are lowest order Lagrangian FE spaces we can recall an optimal convergence result from [START_REF] Lozinski | Numerical zoom for advection diffusion problems with localized multiscales[END_REF]Theorem 1] for the error in the L ∞ -norm.

Numerical Experiments

For the numerical experiments, we consider a rectangular domain Ω = [-1, 1] 2 and define Ω in as the polygon with vertices (-0.125, 0.5), (0.375, 0.25), (0.375, -0.375), (0, -0.5), (-0.375, -0.375), and (-0.5, 0.25). The meshes T in and T ex for the interior and exterior domain will be a Cartesian mesh and a triangular mesh. For simplicity we prefer to take Ω ex h = Ω ex = Ω \Ω in . For the numerical test, we choose the data f (x, y) and ψ 0 such that ψ(x, y) = cos(πx) sin(πy) is the solution of (1). If h ex (resp. h in ) is the maximal diameter of elements in T ex (resp. T in ), and p ex (resp. p in ) the local polynomial degree of the FE spaces V ex (resp. V in ), one has optimal convergence if, for a smooth solution, the approximation error in the H 1 (Ω ex h ) and H 1 (Ω in h )-norms behaves as O(h p-1 ), with h = max(h ex , h in ) and p = min(p ex , p in ) (in L 2 (Ω ex h ) and L 2 (Ω in h )-norms one dares to obtain O(h p )). To keep the presentation as clear as possible we show in the following figures always the maximum between the error in Ω ex h and that in Ω in h .

-1 -0.5 0 0. Fig. 3 Left and Center: Sketch of the two different settings. We may choose Ω in h to have a minimal overlap with Ω ex h (left), that is γ ex is contained in the layer of elements of T in which define γ in . Otherwise, we say that Ω in h has a large overlap with Ω ex h (center). Right: Adaptive definition of γ in in the case of minimal overlap between Ω in h and Ω ex h . Note that, γ ex (magenta) remains fixed, while γ in (red) changes due to the refinements in Ω in h . The interior edges of elements of T ex and T in are omitted for clearness.

We consider two different pairings of FE spaces V ex -V in . The first denoted with P1-Q1 uses lowest order linear FEs over T ex and lowest order bilinear FEs over T in . The second pair, denoted with P2-Q3 uses quadratic FEs over T ex and bicubic FEs over T in . The elements of P2-Q3 are not only continuous on Ω in h and Ω ex h but have also continuous gradients on Ω in h .

10 0 h = max(h ex , h in ) L 2 P1-Q1 minimal L 2 P2-Q3 minimal H 1 P1-Q1 minimal H 1 P2-Q3 minimal L 2 P1-Q1 large L 2 P2-Q3 large H 1 P1-Q1 large H 1 P2-Q3 large O(h 1 ) O(h 2 ) O(h 3 )
Fig. 4 Convergence in L 2 and H 1 of the scheme MEM-M using L 2 -projection (left) or nodal interpolation (right).

We focus on the overlapping MEM-M (4) which uses the modified mortar mappings and is equivalent to [START_REF] Christophe | An overlapping non-matching grid mortar element method for Maxwell's equations[END_REF]. We also analyse the influence on the error curves of using either L 2 projections interpolation to realize the gluing across γ ex and γ in for the MEM-M. We start with the case where Ω in h has minimal overlap with Ω ex h (see Fig. 3, left). Thus γ in is adapted with the refinements in Ω in h as shown in Fig. 3. Convergence results with MEM-M are presented in Fig. 4. The convergence rate with MEM-M is optimal for the error in the H 1 -norm. The results look slightly better if we apply the interpolation instead of the L 2 projection in the definition of the mortar mapping.

Next, we study the convergence rates for MEM-M when Ω in h has a large overlap with Ω ex h (see Fig. 3, right). Note that both γ ex and γ in remain fixed during the refinements in Ω in h . Once again, the MEM-M yields optimal convergence rate in the H 1 norm (see Fig. 4). Moreover in the case of larger overlap we observe even optimal convergence in the L 2 -norm. There is no qualitative difference between MEM-M based on the L 2 -projection or on the interpolation.

With the classical overlapping MEM (3) with the parameters s and t set to zero (MEM-0), the convergence rates in the H 1 and L 2 norms are not optimal in the case of minimal overlap between Ω in h and Ω ex h . The MEM-0 does not yield convergence in the case of a large overlap between Ω in h and Ω ex h .

Fig. 1 Fig. 2

 12 Fig. 1 Right: Geometric description of the tokamak in the poloidal plane. Left and middle: Sketch for characteristic plasma shapes. The plasma boundary touches the limiter (middle) or the plasma is enclosed by a flux line that goes through an X-point (right).

h

  = max(h ex , h in )


domain: phys math

text:
Maarten Blommaert
email: m.blommaert@fz-juelich.de

Martine Baelmans

Holger Heumann

Yannick Marandet

Hugo Bufferand

N R Gauger

D Reiter

Magnetic Field Models and their Application in Optimal Magnetic Divertor Design

Keywords: Vacuum approach, magnetic equilibrium, divertor design, adjoint optimization, power deposition

published or not. The documents may come

Introduction

At present, several plasma boundary codes exist that attempt to describe the complex interactions in the divertor SOL (Scrape-Off Layer) [1,2,3,4]. The predictive capability of these edge codes at present is still very limited. Yet, in parallel to major efforts to mature edge codes, we face the design challenges for next step fusion devices. One of them is the design of the helium and heat exhaust system. Recently, automated design methods were introduced for the purpose of divertor design. While these were initially oriented to improve the shape of the divertor targets for more equal distribution of the target heat load [5], the methods were later applied to magnetic configuration design [6]. To this end, divertor coils were controlled to improve the magnetic configuration. Results of these studies indicated large potential reductions in peak heat load by an increased magnetic flux divergence towards the target structures [6,7].

The model used to achieve these results combines a magnetic field model using the so-called "vacuum approach" (VA) with a plasma edge transport model. In the VA it is assumed that magnetic field changes due to small coil perturbations can be sufficiently described by analyzing the effect of external coil changes in vacuum. The influence of altering plasma currents and their position is hereby neglected for the small changes concerned. Another application of the VA is to assess the effect of resonant magnetic perturbations [8].

Because of the rather large magnetic field changes that were found in past automated design studies, the legitimacy of the perturbation approach has to be questioned. Therefore, a MATLAB version of the CEDRES++ free boundary magnetic equilibrium (FBE) solver [9] was recently included into the simulation framework to improve the magnetic field model and its in parts adjoint sensitivities were validated [10]. The evident research question asked in this paper is if at all and under which conditions the VA is an acceptable substitute for the FBE model. Furthermore, the question arises how the optimal design is affected by this change in models.

The paper is structured as follows. In section 2, we analyze under which conditions the simplified perturbation approach is legitimate by comparing both models. Afterwards, the plasma edge transport model and the optimization approach are briefly outlined in section 3. Finally, first results are shown in section 4 for an optimized heat exhaust of the new WEST (Tungsten Environment in Steady-state Tokamak) divertor currently under construction in the Tore Supra tokamak at CEA (Commissariat à l'Energie Atomique, France) [11,12].

2 Poloidal magnetic flux models

Description of the magnetic flux models

The magnetic field in tokamaks is constituted by the coils around the vacuum chamber as well as the field induced by the plasma currents themselves. Considering a cylindrical coordinate system (R, , Z), the poloidal magnetic flux per radian is everywhere (in and outside the vacuum vessel) governed by the toroidal component of Ampères law

r • ✓ 1 µR r ◆ = J , (1)
with J the current density in the toroidal direction and µ the relative magnetic permeability, which equals the permeability of vacuum µ 0 inside the vacuum vessel. In the domain ⌦ p bounded by the last closed flux surface (LCFS), the toroidal current density J can approximately be described by the Grad-Shafranov equation, which balances Lorentz force against plasma pressure [13]. Outside the LCFS, plasma currents are negligible, resulting in the free boundary equilibrium problem

J = 8 > < > : J P = Rp 0 ( ) + 1/(µ 0 R) FF 0 ( ) in ⌦ p ( ) , I /S
in the coils, 0 anywhere else,

with p and F flux functions associated to the pressure and the R-scaled toroidal magnetic field component, respectively, and where the accent denotes a differentiation with respect to the poloidal flux . I represents the current in toroidal coils. The profiles p 0 and FF 0 are given in the form [14]

p 0 ( ) = R 0 (1 ¯ ↵ ) and FF 0 ( ) = (1 )µ 0 R 0 (1 ¯ ↵ ) , (3)
with ¯ the normalized magnetic flux, which equals 0 at the magnetic axis (MA) and 1 at the LCFS. The physical meaning and choice of the profile parameters ↵, , is dealt with in [START_REF] Blum | Numerical simulation and optimal control in plasma physics[END_REF]. is a scaling variable that assures that the total plasma current I P is kept constant. In the CEDRES++ framework, these equations are spatially discretized using a first order finite element (FE) method and solved for using a Newton method. It is clear that the nonlinear dependence of the plasma boundary ⌦ p on contributes to the complexity of this code. More information can be found in [9].

The vacuum approach essentially assumes that in the linearization of the FBE solution = 0 + all plasma currents changes J P can be neglected at the one hand and, at the other, that the magnetic permeabilities µ of surrounding materials can be approximated as µ 0 . The Biot-Savart law can then be used to calculate the magnetic field. Moreover, if one assumes additionally that the conductors can be modelled as being of infinitesimal size, a semi-analytical expression for the poloidal magnetic flux change due to a single coil at location (r 0 , z 0 ) is obtained [START_REF] Dnestrovskii | Controlled Fusion and Numerical Simulation[END_REF]:

(R, Z, r 0 , z 0 ) = µ 0 R I ,ext k⇡ r r 0 R ✓ 1 k 2 2 ◆ K(k) E(k) , where (4)
k 2 = 4Rr 0 (R + r 0 ) 2 + (Z z 0 ) 2 . (5)

I

,ext is the additional external conductor current and K and E are complete elliptical integrals of the first and second kind that can be evaluated fast numerically. It is obvious that the reduced complexity and increased speed are the main assets of this approach. The latter approach will be referred to as the perturbation model (PM).

Analysis of model assumptions

In this subsection, we show that the FBE model and PM are indeed equivalent if the assumptions introduced in the former section are made. As such, the correctness of implementation is verified and the effect of the different assumptions can be estimated. We demonstrate this using the reference equilibrium 0 from the "far" configuration of [17]. The WEST tokamak, for which the study in this paper is performed, is shown in figure 1a with coils, iron and the vacuum chamber clearly indicated. The divertor coils (numbered 10-19) will be of specific importance further on to control the magnetic configuration in the vacuum chamber. The reference magnetic equilibrium 0 is obtained using the FBE code described in section 2.1, with ↵ = 1, = 1.5, = 0.9, I p = 0.47 MA. The magnetic fields of both approaches will now be compared for an increase by 1 kA of all lower divertor coils (coil numbers 14-17).

Fig. 1 a) The WEST machine. Coils are numbered and iron structures are indicated in light gray b-e) Close-up of the magnetic field change at a perturbation of 1kA of coils 14-17 at the vacuum vessel (black line) using: b) the FBE FE simulation, c) the FE simulation with JP = 0, d) the FE simulation with JP = 0 and neglecting permeability of iron, e) PM (numerical evaluations of equations ( 4) and ( 5)).

Comparing the change in flux function

= 0 of the FBE model (figure 1b) with that of the PM (figure 1e) gives a significant difference. Especially in the core region of 1b, a clear difference in magnetic field is present that can be attributed to the absence of the nonlinear interaction with plasma currents in the PM. This can be confirmed by evaluating with the FE code for input parameters I P = 0 and the coils loaded with a current I (figure 1c), so that the additional plasma currents J P are put to zero. The comparison between FE code and PM is now in better agreement. Removing the relative permeability of iron finally gives a good agreement of the FE code with the PM (figure 1d). The local effect of supposing infinitesimal coil currents for the PM can be clearly seen when comparing (figure 1d) and (figure 1e), but the latter assumption has almost no consequence on the magnetic field in the vacuum chamber.

Comparison of sensitivities

Next, we compare the first order behavior of the stationary points of for both models. Indeed, X-points are an important characteristic of the magnetic field. The sensitivities @p/@' of the movement of such a point with respect to the coil current magnitudes is found by using a simple forward finite difference approach on both magnetic models, where the perturbation size k 'k = ✏ The results of this study are shown in figure 2. Remark that overall, big discrepancies are found in the sensitivity analysis and that both models sometimes even have sensitivity contributions of opposite sign. However, reasonable agreement is found for the sensitivities of the lower X-point with respect to coils 14-17 and those of the upper X-point with respect to coils 10-13. This is a logical consequence of the fact that these coils are in the direct vicinity of these respective X-points under consideration. The magnetic field caused by a current decreases approximately with the squared distance from the current source, so that close enough to the coils the effect of the coil current dominates that of the plasma currents.

We now illustrate the discrepancies between the models with a simple example. Suppose that X-points, MA and a divertor coil are aligned as illustrated in figure 2b. One can then study the first order effect of plasma currents on the X-point location. The displacement

~ p = [ p R , p Z ]
> of a stationary point in can be obtained by linearizing the spatial derivative of around the stationary point location p = p0 with respect to ~ p, @ @p = @ @p p0 + @ 2 @p 2 p0 ~ p and thus

~ p = @ 2 @p 2 p0 ! 1 @ @p p0 , (6)
where the latter equality holds because @ /@p ⌘ 0 at a stationary point of . The X-point movement caused by a small change in coil current I (in positive ˆ direction) is then given by

@p @I = @ 2 @p 2 p0 ! 1 @ 2 @p @I p0 , with @ 2 @p @I =  R @B Z @I , R @B R @I > (7)
and where B = B R e R + B e + B Z e Z is the magnetic flux density. The Hessian matrices, with respect to R and Z, H

x = @ 2 @p 2 px at the X-points and H ma = @ 2 @p 2 pma at the MA pma are in this case of the form H

x = diag ( a 1 , a 2 ) and H ma = diag ( a 3 , a 4 ), respectively, with coefficients a 1 , a 2 , a 3 , a 4 2 R + . The well-known right hand rule can be used to find the direction of @ B/@I I at the lower X-point caused by a positive perturbation I1 . Hence, equation ( 7) retrieves an upwards movement px = @ px /@I I of the lower Xpoint. If one involves the plasma current I P , the conclusion is less straightforward. Suppose the plasma currents can be represented using a single coil tied to the MA. The movement of the MA and therefore that of the plasma current can then be analyzed using equation (7). One finds that the MA moves in the opposite direction of the X-point (downwards) and thus creates a counteracting magnetic field at the lower X-point. The direction of the X-point movement now depends on the current I P , the mutual distances of the variables and the coefficients a 2 and a 4 . The resulting movement direction becomes less predictable because of this indirect effect.

Looking again at figure 2, one sees that this simplified analysis without plasma current indeed shows the right tendency for coils 14-17 of the lower X-point and for coils 10-13 at the upper X-point for the PM. One also sees that all other sensitivities using the PM are relatively close to zero because of the large distance between coil and stationary point. One may thus conclude that in those cases, the indirect effect of the plasma currents dominates, since the plasma currents are closer to those stationary points then the perturbed coil. Finally, it appears from figure 2 that the movement of the MA in the FBE model is not correctly predicted by the simplified analysis, since the reduction of the plasma currents to a coil at the MA is not a good approximation. Although further examination of alternative perturbative models with preprocessed determination of the plasma current "gravity center" are possible, the authors have decided to incorporate the FBE model in the optimal design approach.

Optimal magnetic divertor design

The FBE model for magnetic flux simulation is combined with a plasma edge grid generator and plasma edge transport code for optimization of the target heat load in an optimal design approach. The plasma edge model can be found in [6] and features ion continuity and momentum conservation, a neutral pressure diffusion equation, and an internal energy equation, solved for a combined ion-electron-neutral temperature T . The aim is to avoid heat peaks at the target surface, by minimizing the objective functional

Î (') = 1 2 Q Z St (Q ? (') Q d,t ) 2 d + 1 2 ' ' > ' (8)
using the dimensionless coil currents ', where the surface integral with elementary surface vector d integrates over the target surface area S t . Q ? is the heat flux density perpendicular to the target surface and Q d,t a desirable spatially constant heat flux profile. The second term is a Tikhonov regularization term, which physically penalizes excessive Joule losses.

Q and ' are both a normalization and a weighting factor for their corresponding terms. Furthermore, the optimization is augmented with design constraints of the form ĥ(')  0. Constraints are imposed on the coil currents to represent the conductor and current source limits. Additionally, a minimal distance is set between X-point and target surface to guarantee the existence of a divertor configuration and avoid excessive flux of impurities to the core region. Other constraints are imposed but are not discussed, since they do not influence the results presented in section 4. The optimization is then solved using gradient based descent, where the sensitivities of the objective functional with respect to the coil currents @ ' Î are calculated using an in parts adjoint method presented in [7] and elaborated and verified for the FBE model in [10]. The sequential quadratical programming method used for optimization is discussed in [6].

Results and discussion

The optimization algorithm is used to find an improved magnetic configuration of the WEST configuration presented earlier in section 2.2, by making use of the coil currents in coils 10-17 (see figure 1a) 2 . A core input power of 7.93 MW is imposed together with a fixed density at the core boundary of 2.7 • 10 19 m 3 . For further information about plasma edge transport parameters and boundary conditions we refer to [10], were the same set-up was used. The optimization algorithm was stopped when it settled after five optimization cycles. Moreover, 92% of the changes in cost functional was realized in the first two cycles. The entire optimization came at the cost of roughly twelve plasma edge simulation equivalents, with free boundary equilibrium calculation and grid generation cost negligible to that of a plasma edge simulation. Remark that this can be easily reduced to six plasma edge simulation equivalents for practical design purposes.

In figure 3 a and b, the heat load and magnetic field change resulting from the optimization are given, respectively. It is observed in figure 3a that the peak heat load is reduced by 56% and in 3b that this is realized by a significantly enlarged projected area through flux expansion. The latter effect on the heat load clearly dominates the effect of the reduced connection length in the current plasma regime. Note that a detached configuration might hold a different balance between these two means to spread the heat flux. Moreover, the total coil current was reduced by 94 kA. Nevertheless, the current in coil 14 was increased to 75 kA to accommodate for the large flux expansion. The increase and decrease of neighbouring coils 14 and 15, respectively, has a clear similarity with the X-divertor [18] in the way the flux expansion is realized.

The optimization was also repeated with the perturbation model. A similar tendency was found there. Again, the movement of the X-point towards the target accompanied flux expansion and a decreased heat load. Yet, the optimal currents were different and changes in currents had to be significantly larger to realize a similar change in magnetic configuration. Due to the design constraints on the current sizes, the peak heat load was only reduced by 34 % in the optimal configuration. We conclude that by ignoring plasma currents, the perturbation model significantly underestimates the effect coil currents can have on the magnetic configuration.

Conclusion

In the comparative study of a perturbation model with VA and a full FBE model to simulate the magnetic flux function, it is found that the use of the perturbation model only gives a reasonable estimation of the poloidal magnetic flux in the divertor region in the direct vicinity of the divertor coils. In a first optimal magnetic divertor design study that incorporates the FBE solver, significantly different optimal currents were found. The integration of a FBE solver is therefore indispensable for realistic magnetic field design. In ongoing work, we attempt to maximize the heat load under a restricted target temperature. Thus, we aim to assist the WEST project, which attempts to create circumstances similar to those of the future ITER tests. In first trials it was found that a direct maximization of the objective functional used in this paper induces a physically irrelevant maximum. Model assumptions and objective functional will therefore have to be revised to achieve the former goal.

1 / 3 m

 13 is linked to the machine precision ✏ m , p = R e R + Z e Z is the position vector in the poloidal plane and ' i = I ,i /I c = I ,i (10 5 A) are the dimensionless control variables.

Fig. 2 a

 2 Fig. 2 a) Comparison of the sensitivities of the lower and upper X-point and MA positions with respect to the divertor coil currents (FBE: plain symbols, PM: empty symbols, R-component: squares, Z-component: triangles). Coil numbers as given in figure 1. b) Simplified analysis of the movements in the VA. The magnetic field change at the X-point due to a positive coil perturbation I is shown in red and the corresponding movement of the X-point with a double arrow.

Fig. 3 a

 3 Fig. 3 a) Heat load profile on the target surface in comparison to the desired profile Q d , before (dotted) and after optimization (solid line). b) Close-up of the magnetic configuration change at the divertor region from initial (dashed) to optimized (solid). The colorbar indicates the change in current magnitudes I. The dotted line represents the design constraint.

Copyright line will be provided by the publisher

The right hand rule follows directly from Ampères law.Copyright line will be provided by the publisher

Notice that this is an illustrative test case, since in reality coils 10-13 and 14-17 are connected in series.Copyright line will be provided by the publisher

Acknowledgements We are grateful to Eric Nardon for his valuable assistance to set up the WEST equilibrium calculations.