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

The core of games on ordered structures and graphs *

Keywords: 91A12, 06A06, 90C27 TU-game, solution concept, core, feasible coalition, communication graph, partially ordered set

The core of games on ordered structures and graphs

Introduction

Let N := {1, . . . , n} be a finite set of players. We consider the situation where these players can form coalitions, and the profit given by the cooperation of the players in a coalition can be freely distributed among its members: this is in general referred to as cooperative profit games with transferable utility, which we will abbreviate in the sequel as TU-games (see, e.g., [START_REF] Driessen | Cooperative Games, Solutions and Applications[END_REF]; [START_REF] Peleg | Introduction to the theory of cooperative games[END_REF]; [START_REF] Brânzei | Models in cooperative game theory: crisp, fuzzy and multichoice games[END_REF]).

Let v be a TU-game, that is, a set function v : 2 N → R such that v(∅) = 0, assigning to each coalition S ⊆ N its worth (profit) v(S). Let us assume that forming the grand coalition N is the best way to generate profit. One of the main problems in cooperative game theory is to define a rational sharing among all players of the total worth v(N) of the game. Any sharing is called a solution of the game, since it solves the (difficult) problem of sharing the cake.

The literature on solutions of TU-games is very abundant, and many concepts of solution have been proposed. One may distinguish among them two main families, namely those solutions which are single-valued, and those which are set-valued. In the first category, to each game is assigned a single solution, which most of the time exists. Best known examples are the Shapley value [START_REF] Shapley | A value for n-person games[END_REF], the Banzhaf value [START_REF] Banzhaf | Weighted voting doesn't work: A mathematical analysis[END_REF] and any other power index used in voting theory (see, e.g., [START_REF] Machover | The Measurement of Voting Power: Theory and Practice, Problems and Paradoxes[END_REF]), the nucleolus [START_REF] Schmeidler | The nucleolus of a characteristic function game[END_REF], the τ -value [START_REF] Tijs | Bounds for the core and the τ -value[END_REF], etc. In the second category, to each game a set of solutions is assigned. This is the case of the core [START_REF] Gillies | Some theorems on n-person games[END_REF][START_REF] Shapley | Core of convex games[END_REF], the bargaining set [START_REF] Aumann | The bargaining set for cooperative games[END_REF][START_REF] Davis | Existence of stable payoff configurations for cooperative games[END_REF], the kernel [START_REF] Davis | The kernel of a cooperative game[END_REF], etc.

Among all these solution concepts, the core remains one of the most appealing concepts, due to its simple and intuitive definition. Roughly speaking, it is the set of sharing vectors for which "nobody can complain", or more exactly, which are coalitionally rational. This means that no coalition can be better off by splitting from the grand coalition N, i.e., for every S ⊆ N, the payoff x(S) given to S is at least equal to v(S), the profit that S can make without cooperating with the other players. The core may be empty, but when nonempty, it ensures in some sense the stability of the set of players, hence its interest.

The core is an important notion in economics. In an exchange economy, the core is defined as the set of situations where no coalition of agents can improve the utility of its members by reassigning the initial resources of its own members among them [START_REF] Debreu | A limit theorem on the core of an economy[END_REF]. Besides, there are many examples in economics where a common good or resource has to be shared among several users (e.g., a river supplying the water of several towns). The problem of sharing the cost among all the users in a rational way precisely amounts to find a solution like the core [START_REF] Ambec | Sharing a river[END_REF][START_REF] Van Den Brink | A class of consistent share functions for cooperative games in coalition structure[END_REF][START_REF] Van Den Brink | Component efficient solutions in line-graph games with applications[END_REF][START_REF] Khmelnitskaya | Values for rooted-tree and sink-tree digraph games and sharing a river[END_REF]. The core is also well known in decision theory and in the field of imprecise probabilities (see the monograph of [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF], and also [START_REF] Chateauneuf | Some characterizations of lower probabilities and other monotone capacities through the use of Möbius inversion[END_REF]): given a capacity, i.e., a monotonic game v such that v(N) = 1 [START_REF] Choquet | Theory of capacities[END_REF] representing the uncertainty on the set of states of nature, its core is the set of probability measures compatible with the available information on uncertainty. Conversely, given a family of probability measures representing some uncertainty on the set of states of nature, its lower envelope defines a capacity.

The core has been widely studied, and its properties are well known. In particular, when nonempty it is a bounded convex polyhedron, and the famous Bondareva theorem tells us when the core is nonempty [START_REF] Bondareva | Some applications of linear programming to the theory of cooperative games[END_REF], while [START_REF] Shapley | Core of convex games[END_REF] and later [START_REF] Ichiishi | Super-modularity: applications to convex games and to the greedy algorithm for LP[END_REF] found the vertices of the core for convex games.

The classical view in cooperative game theory is to consider that every coalition can form, i.e., a game v is a mapping defined on 2 N , the set of all subsets of N. A view closer to reality reveals that it is not always possible to assume that every coalition can form, so that one should distinguish between feasible and unfeasible coalitions. For example, some hierarchy may exist on the set of players, and feasible coalitions are those which respect this hierarchy, in the sense that subordinates should be present (games with precedence constraints, [START_REF] Faigle | The Shapley value for cooperative games under precedence constraints[END_REF]). Another example is when coalitions are the connected subgraphs of a communication graph, depicting who can communicate with whom (Myerson, 1977b). More simply, when considering political parties, leftist and rightist parties cannot in general make alliance. In fact, many authors have studied the case where the set of feasible coalitions is a subcollection of 2 N , as this paper will show.

The study of the core under such a general framework becomes much more difficult. Surprisingly, even if the core, when nonempty, is still a convex polyhedron, it need not be bounded, and moreover, it need not have vertices. The structure of the core for convex games, perfectly clear in the classical case, is complicated by the fact that it is not always possible to speak of convex games in the usual sense, because the definition of convexity works for a collection of feasible coalitions closed under union and intersection. The aim of this survey, which is an updated version of [START_REF] Grabisch | The core of games on ordered structures and graphs[END_REF], is precisely to give a unified view of the scattered results around these questions.

The paper is organized as follows. Section 2 introduces the basic material on partially ordered sets and polyhedra. Then Section 3 is devoted to a comparative study of various families of set systems (collections of feasible coalitions). Section 4 defines the core and the positive core, and gives the main classical results that are valid when all coalitions are feasible. Section 5 studies the structure of the core under various assumptions on the set system, while Section 6 does the same for the positive core. Finally, Section 7 studies the case of communication graphs.

Throughout the paper, the following notation will be used: we denote by R + the set of nonnegative real numbers; N = {1, . . . , n} is the set of players; for any subset S ⊆ N, 1 S denotes the characteristic function (or vector) of S. For singletons, pairs, etc., we often omit braces and commas to avoid a heavy notation: we write S \ i, 123 instead of S \ {i} and {1, 2, 3}.

2 Some prerequisites

Partially ordered sets

The reader can consult, e.g., [START_REF] Davey | Introduction to Lattices and Orders[END_REF], [START_REF] Birkhoff | Lattice Theory[END_REF], and Grätzer (1998) for more details. A partially ordered set (or poset for short) (P, ≤) (or simply P if no confusion occurs) is a set P endowed with a partial order ≤ (i.e, a reflexive, antisymmetric and transitive binary relation). As usual, x < y means x ≤ y and x = y, while x ≥ y is equivalent to y ≤ x. Two elements x, y ∈ P are incomparable, and we denote this by x||y, if neither x ≤ y nor y ≤ x hold. A useful example of poset in this paper is (2 N , ⊆). We say that x is covered by y, and we write x ≺ y, if x < y and there is no z ∈ P such that x < z < y. A chain in P is a sequence of elements x 1 , . . . , x q such that x 1 < • • • < x q , while in an antichain, any two elements are incomparable. A chain from x 1 to x q is maximal if no other chain can contain it, i.e., it is a sequence of elements x 1 , . . . , x q such that x 1 ≺ • • • ≺ x q . The length of a chain is its number of elements minus 1.

A subset Q ⊆ P is a downset of P if for any x ∈ Q, y ≤ x implies y ∈ Q (and similarly for an upset)1 . The set of all downsets of P is denoted by O(P ). For any x ∈ P , ↓ x := {y ∈ P | y ≤ x} is the downset generated by x (often called principal ideal ).

An element x ∈ P is maximal if there is no y ∈ P such that y > x (and similarly for a minimal element). x ∈ P is the (unique) greatest element (or top element) of P if x ≥ y for all y ∈ P (and similarly for the least element, or bottom element). Suppose P has a least element ⊥. Then x is an atom of P if x ≻ ⊥. Let Q ⊆ P . The element x ∈ P is an upper bound of Q if x ≥ y for all y ∈ Q (and similarly for a lower bound ). For x, y ∈ P , the supremum of x, y, denoted by x ∨ y, is the least upper bound of {x, y}, if it exists (and similarly for the infimum of x, y, denoted by x ∧ y).

A poset L is a lattice if every pair of elements x, y ∈ L has a supremum and an infimum.

A lattice L is distributive if ∨, ∧ obey distributivity, that is, x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) or equivalently x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
, for all x, y, z ∈ L. If L is finite, then it has a least and a greatest element, which we denote by ⊥, ⊤ respectively. An element x = ⊥ is join-irreducible if it cannot be expressed as a supremum of other elements, or equivalently, if it covers only one element. Atoms are join-irreducible elements. We denote by J (L) the set of all join-irreducible elements. An important result which will be useful in the sequel is the theorem of [START_REF] Birkhoff | On the combination of subalgebras[END_REF]: it says that if the lattice (L, ≤) is distributive, then it is isomorphic to O(J (L)), where it is understood that J (L) is endowed with ≤, and that the set of downsets is endowed with inclusion. Conversely, any poset P generates a distributive lattice O(P ). This is illustrated on Figure 1 Middle: the poset J (L) of join-irreducible elements. Right: the set O(J (L)) of all downsets of J (L) ordered by inclusion, which is isomorphic to L Let P be a poset, and x ∈ P . The height of x is the length of a longest chain in P from a minimal element to x. The height of a lattice L is the height of its top element, i.e., it is the length of a longest chain from bottom to top. When the lattice is distributive, its height is |J (L)|.

Inequalities and polyhedra

We recall only some basic facts useful for the sequel (see, e.g., [START_REF] Ziegler | Lectures on polytopes[END_REF], [START_REF] Faigle | Algorithmic Principles of Mathematical Programming[END_REF] for details). Our exposition mainly follows Fujishige (2005, §1.2) We consider a set of linear equalities and inequalities with real constants

n j=1 a ij x j ≤ b i (i ∈ I) (1) n j=1 a ′ ij x j = b ′ i (i ∈ E).
(2)

This system defines an intersection of halfspaces and hyperplanes, called a (closed convex)

polyhedron. A set C ⊆ R n is a convex cone (or simply a cone) if x, y ∈ C implies that αx + βy ∈ C for all α, β ≥ 0 (conic combination). The cone is pointed if C ∩ (-C) = {0}
(equivalently, if it has an extreme point, see below). An affine set A is the translation of a subspace of the vector space R n . Its dimension is the dimension of the subspace. A line is a one-dimensional affine set, and a ray is a "half-line", i.e., a translation of a set given by {αx | α ≥ 0} for some x ∈ R n , x = 0. An extreme ray of a cone is a ray whose supporting vector cannot be expressed as a convex combination of the supporting vectors of other rays. Any cone can be expressed as the conic combination of its extreme rays. An extreme point or vertex of a polyhedron P is a point in P which cannot be expressed as a convex combination of other points in P . A polyhedron is pointed if it contains an extreme point. The recession cone C(P ) of a polyhedron P defined by ( 1) and ( 2) is defined by

n j=1 a ij x j ≤ 0 (i ∈ I) (3) n j=1 a ′ ij x j = 0 (i ∈ E). (4)
The recession cone is either a pointed cone (possibly reduced to {0}) or it contains a line.

The following basic properties are fundamental:

(i) P has rays (but no line) if and only if C(P ) is a pointed cone different from {0};

(ii) P is pointed if and only if C(P ) does not contain a line, or equivalently, if the system (4) and

n j=1 a ij x j = 0 (i ∈ I)
has 0 as unique solution.

(iii) P is a polytope (i.e., a bounded polyhedron) if and only if C(P ) = {0}.

The fundamental theorem of polyhedra asserts that any pointed polyhedron P defined by a system (1) and ( 2) is the Minkowski sum of its recession cone (generated by its extreme rays; this is the conic part of P ) and the convex hull of its extreme points (the convex part of P ): P = cone(r 1 , . . . , r k ) + conv(ext(P ))

where r 1 , . . . , r k are the extreme rays of C(P ), cone() and conv() indicate respectively the set of all conic and convex combinations, and ext() is the set of extreme points of some convex set. If P is not pointed, then it reduces to its recession cone up to a translation.

Finally, suppose that in the system (1) and (2) defining a polyhedron P , the equalities in (2) are independent (i.e., P is (n -|E|)-dimensional). A p-dimensional face (0 ≤ p ≤ n -|E|) of P is a set of points in P satisfying in addition q = n -|E|p independent equalities in (1). In particular, P itself is a face of P (q = 0), a facet is a (n -|E| -1)dimensional face (q = 1), and a vertex is a 0-dimensional face (q = n -|E|). Clearly, no vertex can exist (i.e., P is not pointed) if |I| < n -|E|.

Set systems

Our study deals with games defined on a collection of feasible coalitions. In this section, we introduce various possible structures for these collections. The weakest requirement we introduce is that the collection should include the grand coalition, and for mathematical convenience, the empty set. There are however exceptions to this rule.

A set system F on N is a subset of 2 N containing ∅ and N. Endowed with inclusion, F is a poset with top and bottom elements N, ∅ respectively. The set of maximal chains from ∅ to N in F is denoted by C(F ). For any S ⊆ N, we put F (S) := {T ∈ F | T ⊆ S}.

A set system F is atomistic if {i} ∈ F for all i ∈ N.

For any collection F ⊆ 2 N , we introduce

F := {S ∈ 2 N | S = F 1 ∪ • • • ∪ F k , F 1 , . . . , F k ∈ F pairwise disjoint}
the family generated by F [START_REF] Faigle | Cores of games with restricted cooperation[END_REF].

Let F be a set system. A TU-game (or simply game) on F is a mapping v : F → R such that v(∅) = 0. The game is monotonic if for S, T ∈ F such that S ⊆ T , we have v(S) ≤ v(T ) (and therefore v is nonnegative).

When F = 2 N , the notion of convexity and superadditivity are well known. A game is said to be convex if for any S, T ∈ 2 N , we have

v(S ∪ T ) + v(S ∩ T ) ≥ v(S) + v(T ).
A game v is superadditive if the above inequality holds for disjoint subsets, i.e., for all

S, T ∈ 2 N such that S ∩ T = ∅, v(S ∪ T ) ≥ v(S) + v(T ).
The above notions generalize as follows. Assume F is a (set) lattice. A game v on F is convex if for any S, T ∈ F ,

v(S ∨ T ) + v(S ∧ T ) ≥ v(S) + v(T ).
Superadditivity amounts to the above inequality restricted to subsets S, T such that S ∧ T = ∅. Obviously, one could not speak of convex game if the set system is not a lattice. It is however possible to find alternative definitions for weaker structures, as will be seen in the sequel (see Section 6.1, and supermodular games in Section 6.2).

The Möbius transform of v on F is a real-valued mapping m v on F given implicitely by the system of equations

v(S) = F ⊆S,F ∈F m v (F ), S ∈ F .
As it is well known, when F = 2 N , we obtain m v (S) = F ⊆S (-1) |S\F | v(F ). The Möbius transform is known as the Harsanyi dividends [START_REF] Harsanyi | A simplified bargaining model for the n-person cooperative game[END_REF] in game theory.

Given these general definitions, we turn to the study of the main families of set systems.

Regular set systems

Let 1 ≤ k ≤ n. A set system is k-regular if all maximal chains from ∅ to N have the same length k [START_REF] Xie | The core of games on k-regular set systems[END_REF]. A n-regular set system is simply called a regular set system [START_REF] Honda | An axiomatization of entropy of capacities on set systems[END_REF][START_REF] Lange | Values on regular games under Kirchhoff's laws[END_REF]. Equivalently, F is regular if and only if for S, T ∈ F such that S ≻ T , we have |S \ T | = 1. Any regular set system satisfies:

(i) One-point extension: if S ∈ F , S = N, then ∃i ∈ N \ S such that S ∪ i ∈ F ; (ii) Accessibility: if S ∈ F , S = ∅, then ∃i ∈ S such that S \ i ∈ F .
The converse is not true (see Figure 2). In a k-regular set system F , for any S, T ∈ F , all maximal chains from S to T have the same length.

Remark 1. Obviously, regular set systems (and to a less extent, k-regular set systems) offer a convenient mathematical framework because all maximal chains have length n, and for this reason many notions (in particular marginal worth vectors, and therefore the Shapley value [START_REF] Shapley | A value for n-person games[END_REF] and the Weber set (see Section 4)) can be defined as in the classical case F = 2 N . One can however find motivations for such structures which are more game-theoretically oriented: (i) The set of connected coalitions in a connected communication graph is a regular set system (see Section 7). The converse is false: {i} ∈ F for all i ∈ N is a necessary condition (for necessary and sufficient conditions: see augmenting systems in Section 3.7).

(ii) Maximal chains correspond to permutations on N (or total orders on players). A regular set system forbids some permutations, i.e., some orderings of the players to enter the game. With k-regular set systems, k < n, players may enter the game by groups.

Convex geometries and antimatroids

A convex geometry F [START_REF] Edelman | The theory of convex geometries[END_REF] is a collection of subsets of N containing the empty set, closed under intersection, and satisfying the one-point extension property. Necessarily N ∈ F , hence it is a set system, and moreover a regular set system.

An antimatroid F [START_REF] Dilworth | Lattices with unique irreducible representations[END_REF] is a collection of subsets of N containing the empty set, closed under union, and satisfying the accessibility property. Any antimatroid satisfies the augmentation property:

S, T ∈ F with |T | > |S| ⇒ ∃i ∈ T \ S s.t. S ∪ i ∈ F .
If F satisfies F = N, then N ∈ F . Such antimatroids are called normal by van den Brink (to appear).

Remark 2. [START_REF] Algaba | Cooperative games on antimatroids[END_REF] relate antimatroids to permission structures; see Section 3.4. However, the relation is somewhat artificial since antimatroids do not always correspond to permission structures (this is the case of systems closed under ∪, ∩). The unusual word "poset antimatroids" is used, and means the set of upsets (or downsets) of a poset. These are antimatroids closed under intersection. But it is well known that such set systems are distributive lattices O(N) (and so could be called poset convex geometries as well), hence closed under union and intersection (see Section 2.1).

Set lattices

If a set system is a lattice, we call it a set lattice. It need not be closed under ∩, ∪, nor be a k-regular set system (see for example the pentagon on Figure 4 (ii)).

If the lattice is distributive, then we benefit from Birkhoff's theorem and we know that it is generated by a poset P . However this poset is not always N endowed with some partial order. The following can be easily proved and clarifies the situation (see [START_REF] Xie | The core of games on k-regular set systems[END_REF]):

Proposition 1. Let F be a distributive set lattice on N of height k. The following holds.

(i) F is a k-regular set system, which is generated by a poset P of k elements, i.e., F is isomorphic to O(P ).

(ii) F is closed under union and intersection if and only if F is isomorphic to O(P ), where P can be chosen to be a partition of N.

(iii) k = n if and only if F is isomorphic to O(N).
Figure 3 shows the relative situation of set lattices and k-regular set systems. Figure 4 shows that all inclusions are strict.

Systems closed under union and intersection

As seen in Section 3.3, these are particular set lattices, which are distributive and generated by a partition of N. [START_REF] Derks | Hierarchical organization structures and constraints on coalition formation[END_REF] proved that they are equivalent to (conjunctive) permission structures of [START_REF] Gilles | Games with permission structures: the conjunctive approach[END_REF]. A (conjunctive) permission structure is a mapping σ : N → 2 N such that i ∈ σ(i). The players in σ(i) are the direct subordinates of i. "Conjunctive" means that a player i has to get the permission to act of all his superiors. Consequently, an autonomous coalition contains all superiors of every member of the

set lattices k-regular set systems, 1 ≤ k ≤ n distributive lattices closed under ∪, ∩ 1 ≤ k < n O(N ), k = n
is F σ = {S ∈ 2 N | S ∩ σ(N \ S) = ∅}.
Then F is closed under union and intersection if and only if F = F σ for some permission structure σ.

See also [START_REF] Algaba | Cooperative games on antimatroids[END_REF] for similar results related to antimatroids (see Section 3.2). They characterize acyclic permission structures (i.e., where, for all i ∈ N, in the set of all subordinates (not limited to the direct ones) of i, i is not present) by distributive lattices O(N) (called there poset antimatroids).

Weakly union-closed systems

A set system F is weakly union-closed if F ∪F ′ ∈ F for all F, F ′ ∈ F such that F ∩F ′ = ∅.
An important consequence is that for any S ⊆ N, F (S) := {F ∈ F | F ⊆ S} has pairwise disjoint maximal elements.

The basis of F is the collection of sets S in F which cannot be written as Bilbao, 2000, Chap. 6). All singletons and pairs of F are in the basis. Clearly, knowing the basis permits to recover F . Remark 3. (i) This terminology is used by [START_REF] Faigle | A discrete Choquet integral for ordered systems[END_REF]. Weakly unionclosed systems have been studied under the name union stable systems by Algaba (1998) (summarized in Bilbao (2000, Chap. 6)).

S = A ∪ B, with A, B ∈ F , A, B = S, A ∩ B = ∅ (
(ii) They are closely related to communication graphs because if F represents a communication graph (i.e., F is the collection of connected coalitions of the graph; see Section 7), then the union of two intersecting connected coalitions must be connected. van den Brink (to appear) characterized those weakly union-closed collections which correspond to communication graphs: F ⊆ 2 N is the set of connected coalitions of some comunication graph if and only if ∅ ∈ F , F is normal (i.e., F = N), weakly union-closed, and satisfies 2-accessibility (i.e., S ∈ F with |S| > 1 implies that there exist distinct i, j ∈ S such that S \ i and S \ j belong to F ). Another characterization is due to Bilbao through augmenting systems (see Section 3.7). (iii) Similarly, they are also related to the more general notion of conference structures of [START_REF] Myerson | Conference structures and fair allocation rules[END_REF], which generalize communication graphs. A conference structure Q is a collection of subsets of N of cardinality at least 2. Two players i, j are connected if there is a sequence S 1 , . . . , S k of sets in Q such that i ∈ S 1 , j ∈ S k , and S ℓ ∩S ℓ+1 = ∅ for ℓ = 1, . . . , k -1. Then, F := {S ⊆ N | ∀i, j ∈ S, i and j are connected} is a weakly union-closed system. Conversely, given a weakly union-closed system F , the basis of F restricted to sets of cardinality at least 2 can be considered as a conference structure. An equivalent view of this is given by van den Nouweland et al. through hypergraphs (van den Nouweland et al., 1992), since in a hypergraph, a (hyper)link joins several nodes (and thus can be viewed as a subset of cardinality at least 2). Thus, a path in a hypergraph corresponds to a sequence S 1 , . . . , S k as described above.

Partition systems

They were studied by Bilbao (2000, §5.1) and [START_REF] Algaba | A unified approach to restricted games[END_REF]. A partition system is a collection F ⊆ 2 N containing the empty set, all singletons, and such that for every S ⊆ N, the maximal subsets of S in F form a partition of S (equivalently, F contains ∅, all singletons and is weakly union-closed).

Any set system induced by a communication graph is a partition system. If F is a partition system, then F = 2 N .

Augmenting systems

An augmenting system [START_REF] Bilbao | Cooperative games under augmenting systems[END_REF]Bilbao andOrdóñez, 2009, 2008) is a collection F ⊆ 2 N containing ∅, being weakly union-closed, and satisfying [START_REF] Bilbao | Cooperative games under augmenting systems[END_REF], it is required in addition that F = N (obviously, this property should always be required when dealing with collections of subsets).

∀S, T ∈ F s.t. S ⊆ T, ∃i ∈ T \ S s.t. S ∪ i ∈ F . Remark 4. (i) In
(ii) N does not necessarily belong to F . If N ∈ F , the above property implies that all maximal chains from ∅ to N have the same length n, and thus F is a regular set system. The converse is false.

If N ∈ F , by weak union-closure, all maximal sets in F , say F 1 , . . . , F k , are disjoint, and no F ∈ F can intersect two distinct maximal subsets. Therefore, F can be partitioned into augmenting subsystems F 1 , . . . , F k on F 1 , . . . , F k respectively, which are all regular. Hence, it is sufficient to study the case where N ∈ F .

(iii) An augmenting system is an antimatroid (respectively, convex geometry) if and only if F is closed under union (respectively, intersection).

(iv) Augmenting systems are of particular importance since they permit to characterize communication graphs (see Section 7). Specifically, if G is a communication graph, the set of connected coalitions is an augmenting system. Conversely, an augmenting system is the collection of connected coalitions of a communication graph if {i} ∈ F for all i ∈ N. Each connected component of the graph corresponds to the augmenting subsystems F 1 , . . . , F k mentionned in (ii).

Augmenting systems are also closely related to the previously introduced structures, as shown in the next proposition.

Proposition 2. F is an augmenting system containing N if and only if it is regular and weakly union-closed.

Proof. The "only if" part has been already noticed above. Now, suppose it is regular. Take S ⊆ T in F , then they lie on some chain. Since the system is regular, there are ts -1 subsets between S and T , which implies the augmentation property.

The various relations between regular set systems, weakly union-closed systems and augmenting systems are illustrated on Figure 5. Figure 6 shows that it is possible to have regular set lattices which are not weakly union-closed, and weakly union-closed regular systems not being a lattice.

Coalition structures

Our last category is of different nature since it is not a set system in our sense, and its motivation is very different from the notion of feasible coalition. Its origin comes from the domain of coalition formation. We nevertheless mention it here due to its importance, although the topic of coalition formation falls outside the scope of this survey (see, e.g., [START_REF] Holler | Power Indices and Coalition Formation[END_REF]Owen (2001), van Deemen (1997)). A coalition structure on N is a partition of N [START_REF] Aumann | Cooperative games with coalition structures[END_REF]. It is called by [START_REF] Owen | Values of games with a priori unions[END_REF] a priori union structures.

Let v be a game on 2 N , and consider a coalition structure B := {B 1 , . . . , B m }. Given a payoff vector x, B k ∈ B, we define the game v *

x on 2 B k by

v * x (S) = max T ⊆N \B k (v(S ∪ T ) -x(T )), S ⊂ B k , S = ∅ v(S), S = B k or ∅.
Remark 5. The above definition considers a game in the classical sense, and not on the blocks of the partition. Another type of game suited for coalition structures is global games and games in partition function form. We mention them without further development since their nature is too far away from coalitional games. A global game [START_REF] Gilboa | Global games[END_REF]) is a real-valued mapping defined on the set Π(N) of partitions of N: it assigns some worth to any coalition structure. A game in partition function form [START_REF] Thrall | n-person games in partition function form[END_REF]) is a mapping v assigning a real number to a coalition S and a partition π containing S: knowing that the coalition structure is some π ∈ Π(N) such that S ∈ π, v(S, π) is the worth of S in this organization of the society.

The core and related notions

Let v be a game on a set system F . A payoff vector is any x ∈ R n . It represents some amount of money given to the players. By commodity we write x(S) := i∈S x i for any S ⊆ N. A payoff vector is efficient if x(N) = v(N). The pre-imputation set of v is the set of all efficient payoff vectors. We define the imputation set of v as

I(v) := {x ∈ R n | x i ≥ v({i}) if {i} ∈ F and x(N) = v(N)}.
The core of v is defined by

core(v) := {x ∈ R n | x(S) ≥ v(S) for all S ∈ F and x(N) = v(N)}.
The positive core of v is defined by [START_REF] Faigle | Cores of games with restricted cooperation[END_REF]:

core + (v) := {x ∈ R n + | x(S) ≥ v(S) for all S ∈ F and x(N) = v(N)}.
Remark 6. (i) The classical definition of the core [START_REF] Shapley | Core of convex games[END_REF]) is recovered with F = 2 N . It should be noted that the definition is meaningful only if the game is a profit game. For cost games, the inequalities should be reversed. The core is the set of payoff vectors which are coalitionally rational: no coalition can have a better profit if it splits from the grand coalition N.

(ii) If F contains all singletons and the game is monotonic, the distinction between the core and the positive core is void since they coincide. The positive core retains imputations which are nonnegative, which means that in no case the players would have to pay something instead of being rewarded. This notion is natural essentially if the game is monotonic, for otherwise there would exist players with negative contribution to the game, and those players should be penalized; see also Remark 14.

(iii) The (positive) core is also well known in decision under risk and uncertainty: it is the set of probability measures dominating a given capacity (monotonic game); see, e.g., [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF]. More surprisingly, the (positive) core with the reversed inequalities is a well-known concept in combinatorial optimization, under the name of base polyhedron of a polymatroid [START_REF] Edmonds | Submodular functions, matroids, and certain polyhedra[END_REF], where a polymatroid is nothing else than a submodular 2 monotonic game. As we will see, many theorems shown in game theory about the core were already known in combinatorial optimization; see the excellent monograph of [START_REF] Fujishige | Submodular functions and optimization[END_REF].

We recall the classical results on the core when F = 2 N .

A first important question is to know whether the core is empty or not. A collection B of nonempty subsets of 2 N is balanced if there exist positive coefficients λ B , B ∈ B, such that

B∈B λ B 1 B = 1 N .
The vector λ := (λ B ) B∈B is called the balancing vector. Balanced collections generalize the notion of partitions. [START_REF] Derks | Orderings, excess functions, and the nucleolus[END_REF] have shown that a collection is balanced 2 When F is closed under ∪, ∩, a submodular game, also called concave, satisfies the inequality v(S ∪

T ) + v(S ∩ T ) ≤ v(S) + v(T ) for all S, T ∈ 2 N .
if and only if for all y ∈ R n such that y(N) = 0 (side-payment vector), if y(S) > 0 for some S ∈ B, then it exists S ′ ∈ B such that y(S ′ ) < 0.

A game v on 2 N is balanced if for every balanced collection B with balancing vector λ it holds

B∈B λ B v(B) ≤ v(N).
This could be interpreted by saying that there is no advantage in dividing the grand coalition into balanced collections. The following well-known result is an easy consequence of the duality theorem of linear programming (or Farkas Lemma).

Theorem 1. [START_REF] Bondareva | Some applications of linear programming to the theory of cooperative games[END_REF] Let v be a game on 2 N . Then core(v) = ∅ if and only if v is balanced.

A strong version exists where only minimal balnced collections are used. Obviously, the interest of the theorem is more mathematical than algorithmical. It cannot reasonably be used for testing the nonemptiness of the core of a given game. Since the core is a set of linear inequalities, classical tools testing the feasability of a set of inequalities, like the Fourier-Motzkin elimination, or simply a linear programming solver, should be used.

Assuming that the core is nonempty, it is a polytope, and therefore the question of knowing its vertices arises. To each maximal chain C ∈ C(2 N ) with C = {∅, S 1 , . . . , S n = N}, corresponds bijectively a permutation σ ∈ S(N), the set of permutations on N, such that S i = {σ(1), . . . , σ(i)}, i = 1, . . . , n.

Considering a game v on 2 N , to each permutation σ (or maximal chain C) we assign a marginal worth vector φ σ (or φ C ) in R n by:

φ σ σ(i) := v(S i ) -v(S i-1 ) = v(S i-1 ∪ σ(i)) -v(S i-1
). The Weber set is the convex hull of all marginal worth vectors:

W(v) := conv(φ C | C ∈ C(2 N )).
The following inclusion always holds core(v) ⊆ W(v).

Theorem 2. The following assertions are equivalent. [START_REF] Shapley | Core of convex games[END_REF] proved (i)⇒(ii) and (i)⇒(iv), while [START_REF] Ichiishi | Super-modularity: applications to convex games and to the greedy algorithm for LP[END_REF] proved (ii)⇒(i). [START_REF] Edmonds | Submodular functions, matroids, and certain polyhedra[END_REF] proved the same result as Shapley. This is also mentionned in [START_REF] Lovász | Submodular functions and convexity[END_REF]. This result clearly shows why convexity is an important property for games. Indeed, in this case, the core is nonempty and its structure is completely known. In the subsequent sections, we will see that much effort is done for games defined on set systems in order to preserve these properties as far as possible.

(i) v is convex (ii) All marginal vectors φ C , C ∈ C(2 N ) (or φ σ , σ ∈ S(N)), belong to the core (iii) core(v) = conv({φ σ } σ∈S(N ) ) (iv) ext(core(v)) = {φ σ } σ∈S(N ) .
5 Structure of the core

General results for arbitrary set systems

We begin by some simple considerations on the imputation set. If F is atomistic, then

I(v) = ∅ if and only if v(N) ≥ i∈N v({i}). If F is not atomistic, then it is always true that I(v) = ∅. Indeed, if {j} ∈ F , just take x i = v(i) if {i} ∈ F , x j = v(N)-{i}∈F v(i),
and x i = 0 otherwise. Similarly, I(v) is bounded if and only if F is atomistic.

The first question we address is to know when the core is nonempty. It is easy to see that the classical definitions and result of Bondareva on balancedness still work: core(v) = ∅ if and only if v is balanced, where balanced collections are understood as collections in F . Another result is due to [START_REF] Faigle | Cores of games with restricted cooperation[END_REF], with a different (but equivalent) definition of balancedness. A game v on F is balanced if for all families A 1 , . . . , A k in F and m ∈ N it holds

1 m k i=1 1 A i = 1 N implies 1 m k i=1 v(A i ) ≤ v(N).
In the above, it should be noted that repetitions are allowed in the family and that the length of a family is arbitrary.

Assuming that core(v) is nonempty, one can define its lower envelope v * , which is a game on 2 N : v * (S) := min x∈core(v)

x(S), ∀S ⊆ N.

Note that v * (N) = v(N), and if F = 2 N , we have core(v * ) = core(v).

Remark 7. The lower envelope is an important notion in decision theory (see [START_REF] Walley | Statistical Reasoning with Imprecise Probabilities[END_REF]). In game theory, it is called the Harsanyi mingame [START_REF] Derks | On the Harsanyi payoff vectors and Harsanyi imputations[END_REF].

An important question is to know whether the equality v = v * holds. Such games are called exact. If a game v is exact, by the above mentioned property, it is the smallest game having the core equal to core(v). [START_REF] Faigle | Cores of games with restricted cooperation[END_REF] proved the next result: Theorem 3. A game v is exact if and only if for all families A, A 1 , . . . , A k in F \ {∅} and m, l ∈ N, k i=1

1 A i = m1 N + l1 A implies k i=1 v(A i ) ≤ mv(N) + lv(A).
As above, repetitions are allowed in the family. This is similar to a result of [START_REF] Schmeidler | Cores of exact games I[END_REF], proved when F is a (possibly infinite) family closed under union and complementation: v is exact if and only if for all S ∈ F

v(S) = sup i a i v(S i ) -a|v| s.t. i a i 1 S i -a1 N ≤ 1 S , with a ∈ R + , (a i , S i ) is a finite sequence in R + × F , and |v| := sup{ i a i v(S i ) | (a i , S i ) is a finite sequence in R + × F s.t. i a i 1 S i ≤ 1 N }.
When nonempty, the core is a polyhedron. Therefore it makes sense to speak of its recession cone (proposed under the name of core of the set system F by [START_REF] Derks | On the core of a collection of coalitions[END_REF], hence the notation): core(F ) := {x ∈ R n | x(S) ≥ 0 for all S ∈ F and x(N) = 0}.

A direct application of results of Section 2.2 leads to:

(i) core(v) has rays if and only if core(F ) is a pointed cone different from {0}. Then core(F ) corresponds to the conic part of core(v);

(ii) core(v) has no vertices if and only if core(F ) contains a line;

(iii) core(v) is a polytope if and only if core(F ) = {0}.

Therefore, it remains to study the structure of the recession cone. We introduce

span(F ) := S ⊆ N | 1 S = T ∈F λ T 1 T for some λ T ∈ R .
F is non-degenerate if span(F ) = 2 N3 . Non-degeneracy implies the discerning property (see Section 5.2). The converse holds if F is closed under ∪, ∩ (see Theorem 7). We give two easy sufficient conditions for F to be non-degenerate:

(i) F contains all singletons (obvious from Footnote 3);

(ii) F is regular. Indeed, since any chain has length n, all 1 i 's can be recovered from 1 S j -1 S j-1 , for two consecutive sets S j , S j-1 in a chain. This result is easy to see from Footnote 2 and Section 2.2. Indeed, non-degeneracy is equivalent to the existence of linear combinations of the 1 T 's, T ∈ F , giving all 1 i 's, i ∈ N, and the same linear combinations can be used to express all x i 's, i ∈ N, from the system x(T ) = 0, T ∈ F , thus proving that this system has a unique solution (which is 0). But this is equivalent to say that the recession cone is a pointed cone. We recall that F is balanced if ∃λ S > 0 for all S ∈ F such that 1 N = S∈F λ S 1 S .

Theorem 5. [START_REF] Derks | On the core of a collection of coalitions[END_REF]) core(F ) is a linear subspace if and only if F is balanced.

Therefore, core(F ) = {0} if and only if F is balanced and non-degenerate.

Lastly, considering a game v on F , we introduce the following extension of v to F [START_REF] Faigle | Cores of games with restricted cooperation[END_REF]

ṽ(S) := max i∈I v(F i ), {F i } i∈I is a F -partition of S ,
where by a F -partition we mean a partition whose blocks belong to F . The game ṽ is superadditive, and if ṽ(N) = v(N), then core(v) = core(ṽ), which is easy to show. Remark 8. If F contains all singletons (e.g., a partition system), then F = 2 N , and so ṽ is an extension of v on 2 N : compare with the extension v defined in Section 6.3. Also, ṽ is a partitioning game of Kaneko and Wooders (see Section 5.5). If v is a superadditive game on a partition system, then ṽ = v. In Bilbao (2000, §5.3) it is shown that if F is a partition system containing N and v(N) = v(N) = ṽ(N), then core(v) = core(ṽ).

Set systems closed under ∪, ∩

Let F be a set system closed under ∪, ∩ (such systems are distributive lattices, and correspond to permission structures; see Section 3.4). For each i ∈ N we define

D i := {S ∈ F | S ∋ i} = smallest S in F containing i.
Proposition 3. The set of D i 's coincides with the set of join-irreducible elements of F , i.e.,

{D i } i∈N = J (F ).
Moreover, if the height of F is strictly smaller than n, necessarily we have D i = D j for some i, j (the height equals the number of distinct D i 's).

Proof. Suppose there is some D i which is not a join-irreducible element. Then D i can be written as the supremum of other elements, which are smaller. Since F is closed under ∪, one of these elements must contain i, a contradiction with the definition of D i .

Conversely, take a join-irreducible element S. If S = {i}, we are done. Assume then that |S| > 1. Since it covers only one subset, say S ′ , for any i in S \ S ′ , S is the smallest subset containing i, whence the result.

Finally, since F is a distributive lattice, its height is the number of join-irreducible elements, hence some D i 's must coincide if the height is less than n.

Remark 9. The sets D i 's are introduced in [START_REF] Derks | Hierarchical organization structures and constraints on coalition formation[END_REF]. They are also known in the literature of combinatorial optimization (see Fujishige (2005, Sec. 3.3) and Fujishige (2005, Sec. 7.2 (b.1)) (principal partitions)).

Theorem 6. core(F ) = cone(1 j -1 i | i ∈ N and j ∈ D i ).
If F is not closed under ∪, ∩, then any 1 j -1 i is a ray of core(F ).

Remark 10. This result is due to [START_REF] Derks | Hierarchical organization structures and constraints on coalition formation[END_REF]. It was in fact proved when the system is of the type O(N) in a more precise form by Tomizawa [START_REF] Tomizawa | Theory of hyperspace (XVI)-on the structure of hedrons[END_REF], cited in Fujishige (2005, Th. 3.26)): it says that the extreme rays are those corresponding to j ≻ i in (N, ≤). Note that it could be easily adapted if the lattice is not generated by N, but by a partition of N (see Proposition 1). Another consequence of this result is that when F is closed under ∪, ∩, the core is always unbounded, unless (N, ≤) (or the partition of N endowed with ≤) is an antichain.

The set system F is discerning if all D i 's are different (equivalently, by Proposition 3, if the height of F is n, which is a much simpler condition).

Theorem 7. [START_REF] Derks | Hierarchical organization structures and constraints on coalition formation[END_REF] Consider F to be closed under ∪, ∩. core(F ) is a pointed cone if and only if F is discerning. This result is easy to deduce from previous facts. If the recession cone is pointed, then F is non-degenerate by Theorem 4, which implies the discerning property as mentionned above. If F is discerning, then its height is n, and so it is regular, which implies that it is non-degenerate, and therefore, the recession cone is pointed.

When F is of the type O(N), for any maximal chain C ∈ C(F ), define the marginal vector associated to C like in the classical case, and define the Weber set as the convex hull of all marginal vectors. Theorem 8. Let F be of the type O(N). Then the convex part of the core is included in the Weber set.

Theorem 9. Let F be of the type O(N). Then v is convex if and only if the convex part of the core is equal to the Weber set.

Remark 11. The two last theorems are shown by [START_REF] Grabisch | The restricted core of games on distributive lattices: how to share benefits in a hierarchy[END_REF], but they can deduced from [START_REF] Derks | Hierarchical organization structures and constraints on coalition formation[END_REF], where they are stated for acyclic permission structures. Indeed, from [START_REF] Algaba | Cooperative games on antimatroids[END_REF], we know that these systems are equivalent to distributive lattices of the type O(N) (see Section 3.4). The "only if" part of the latter theorem was already shown by [START_REF] Fujishige | A note on submodular functions on distributive lattices[END_REF].

Lastly, we address a slightly more general case, where closure under union is replaced by weak union-closure. The following development is due to [START_REF] Faigle | Cores of games with restricted cooperation[END_REF]

. A, B ⊆ N is a crossing pair if A, B intersect, A ∪ B = N and A \ B, B \ A are nonempty. Then F is a crossing family if A ∪ B, A ∩ B ∈ F whenever A, B is a crossing pair. v on a crossing family F is convex if for every crossing pair v(A ∪ B) + v(A ∩ B) ≥ v(A) + v(B).
Theorem 10. Suppose F is weakly union-closed and closed under intersection. Then F is closed under union and intersection, and v convex on F implies ṽ convex on F .

Theorem 11. Suppose F is weakly union-closed and closed under intersection, and v on F is convex. Then v is balanced if and only if for all partitions (with nonempty blocks, as usual)

{A 1 , . . . , A k } of N, v(A 1 ) + . . . v(A k ) ≤ v(N).
Now, if the A i 's are only pairwise disjoint, this characterizes complete balancedness (see Section 6).

Distributive lattices generated by a poset on N

Consider F = O(N) for some partial order ≤ on N. Then F is a regular distributive set lattice, closed under union and intersection, and previous results give us the properties of the core. Considering a balanced game v, we have seen that:

(i) core(v) is a pointed polyhedron, since F is non-degenerate (see Section 5.1); (ii) core(v) is unbounded, unless (N, ≤) is an antichain. (iii) core F (v) ⊆ W(v), where core F (v) is the convex part of core(v) (see Theorem 8); (iv) v is convex if and only if core F (v) = W(v) (see Theorem 9).
The following result [START_REF] Grabisch | The bounded core for games with precedence constraints[END_REF] shows that all games can be balanced, provided (N, ≤) is connected (i.e., all players are within a single hierarchy).

Proposition 4. If (N, ≤) is connected, then core(v) = ∅ for any game v on O(N). Conversely, if (N, ≤) is not connected, there exists some game v on O(N) such that core(v) = ∅.

So far we have mainly studied extremal points and rays. Although faces of the core have not drawn the attention of game theorists, they have been deeply studied in combinatorial optimization when F = O(N) (see Fujishige (2005, Ch. 2, §3.3 (d)) for a detailed account). We restrict here to basic facts.

Assuming v is a balanced game, take any x ∈ core(v) and define

F (x) = {S ∈ F | x(S) = v(S)}. Then F (x) is a sublattice of F if v is convex. Indeed, first remark that ∅, N ∈ F (x)
. Now, take S, T ∈ F (x) and let us prove that S ∪ T and S ∩ T belong to F (x). Assuming it is false, we have

x(S) + x(T ) = x(S ∪ T ) + x(S ∩ T ) > v(S ∪ T ) + v(S ∩ T ) ≥ v(S) + v(T ) = x(S) + x(T ), a contradiction. Assuming v is convex, define for any subsystem D ⊆ F F (D) := {x | x(S) = v(S), ∀S ∈ D, x(S) ≥ v(S) otherwise} F • (D) := {x | x(S) = v(S), ∀S ∈ D, x(S) > v(S)

Convex Geometries

The core of games on convex geometries has been studied by [START_REF] Bilbao | The core of games on convex geometries[END_REF].

Theorem 12. Let v be a game on a convex geometry F .

(i) core(v) is either empty or a pointed polyhedron (i.e., having vertices).

(ii) Assume that core(v) = ∅ and that v is nonnegative. Then core(v) is a polytope if and only if F is atomistic if and only if core(v) = core + (v).

Remark 12. (i) is clear from Theorem 4 since a convex geometry is non-degenerate (since n-regular). (ii) was already remarked by [START_REF] Faigle | Cores of games with restricted cooperation[END_REF] (see Theorem 18).

A game v is quasi-convex if convexity holds only for pairs A, B ∈ F such that A ∪ B ∈ F . Marginal vectors are defined as usual, considering all maximal chains in F (all of length n).

Theorem 13. A game v on F is quasi-convex if and only if all marginal vectors belong to the core.

Partition systems

Let F be a partition system, v be a game on F , and v its extension on 2 N (see Section 6.3). If N ∈ F , it is easy to establish that core(v) ⊆ core(v). [START_REF] Kaneko | Cores of partitioning games[END_REF] deal with a weaker definition of partition systems. A partition system only needs to contain all singletons. Then a partitioning game v is a game on 2 N defined from some game v ′ on F by

v(S) = max i∈I v ′ (F i ), {F i } i∈I is a F -partition of S .
Then v is superadditive and core(v) = core(v ′ ) when N ∈ F .

k-regular set systems

The core of games on k-regular set systems has been studied by [START_REF] Xie | The core of games on k-regular set systems[END_REF]. We mentioned in Section 5.1 that a n-regular set system is non-degenerate, hence Theorem 4 applies and the core is a pointed polyhedron, unbounded in general. However, in many cases, F could be degenerate, and in this case the core has no vertices. This is the case for the 2-regular set system given in Figure 7. Let F be a k-regular set system, and a maximal chain C := {∅ = S 0 , S 1 , . . . , S k = N}. Since |S i \ S i-1 | > 1 may occur, the classical definition of a marginal worth vector does not work. Instead, from a given maximal chain, several marginal worth vectors can be derived. Choose an element r i in S i \ S i-1 , i = 1, . . . , k. The marginal worth vector associated to C and r 1 , . . . , r k is defined by

ψ C(r 1 ,...,r k ) = k i=1 (v(S i ) -v(S i-1 ))1 r i .
We have ψ C(r 1 ,...,r k ) (S i ) = v(S i ) for all S i ∈ C. Denote by M(v, F ) the set of all marginal worth vectors, for all maximal chains and possible choices of elements. We define the Weber set as W(v) := conv(M(v, F )).

Theorem 14. Let F be a k-regular lattice closed under union and intersection. If v is convex, then W(v) ⊆ core(v).

Theorem 15. Let F be a n-regular lattice. If v is monotone and convex, then W(v) ⊆ core(v).

The classical inclusion of the convex part of the core into the Weber set does not hold in general, as shown by the following counterexample4 .

Consider the following sets system (regular set lattice but not distributive, since it contains a pentagon, figured by the grey circles), with the values of the game v given into parentheses.

∅ (-1) 1 (-1) 12 123 (0) 23 (0) 2 (-1) 13 (0)
The core is defined by

x 1 ≥ -1 x 2 ≥ -1 x 1 + x 2 ≥ -1 x 1 + x 3 ≥ 0 x 2 + x 3 ≥ 0 x 1 + x 2 + x 3 = 0
The core is bounded and vertices are (0, 0, 0), (-1, 0, +1), (0, -1, +1). The Weber set is generated by the marginal vectors associated to the 4 maximal chains (only 2 differents):

(0, -1, +1), (-1, 0, +1).

Clearly, W(v) ∋ (0, 0, 0).

Remark 13. As noted in Section 6.1, the same phenomenon occurs for the positive core of games on augmenting systems. However, one should be careful that this kind of (negative) result heavily depends on the definition given to the marginal vectors: the framework given in Section 6.2, which is more general than augmenting systems, does not exhibit this drawback.

Coalition structures

Let B be a coalition structure and v on 2 N being zero-normalized (i.e., v({i}) = 0 for all i ∈ N). The core is defined as follows [START_REF] Aumann | Cooperative games with coalition structures[END_REF]:

core(v, B) := {x ∈ R n | x(S) ≥ v(S), ∀S ∈ 2 N , and x(B k ) = v(B k ), k = 1, . . . , m}.
Theorem 16. Let B be a coalition structure and v on 2 N being zero-normalized, and let x ∈ core(v, B). Then

{y ∈ R B k | (y, x |N \B k ) ∈ core(v, B)} = core(B k , v * x , X k ), with core(B k , v * x , X k ) := {y ∈ R B k + | y(B k ) = v * x (B k ), y(S) ≥ v * x (S), ∀S ⊆ B k , }.

Bounded faces of the core

We have seen that in many cases, especially if F = O(N), the core is unbounded. Since infinite payoffs cannot be used in practice, it is necessary to find bounded parts of the core and to select a payoff vector in this part. A simple idea to do this is to impose further restrictions on the definition of the core. One of them is to impose nonnegativity of the payoff vectors: this leads to the positive core, studied in the next section. Another one is to select some inequalities x(S) ≥ v(S), S ∈ F of the core and to turn them into equalities. It is easy to prove that this procedure will eventually lead to a bounded subset of the core. Equalities x(S) = v(S) can be interpreted as additional binding constraints: the members of coalition S must share v(S) among them. On the geometrical side, this is nothing else than defining a face of the core, which has the property to be bounded (see Section 2.2).

A first attempt in this direction was done by [START_REF] Grabisch | The restricted core of games on distributive lattices: how to share benefits in a hierarchy[END_REF] for F = O(N), based on an interpretation of (N, ≤) as a hierarchy. Later, the problem was further elucidated for the case F = O(N) [START_REF] Grabisch | Ensuring the boundedness of the core of games with restricted cooperation[END_REF], and some other cases (regular set systems and weakly-union closed set systems, although much less general results can be obtained in these cases). We give here the main results for the case F = O(N).

The basic idea is to suppress all extremal rays of the recession cone core(F ) (recall that the extremal rays do not depend on v, but only on F ), which are of the form 1 j -1 i for any i, j ∈ N such that j ≺ i (in other words, each link of the Hasse diagram of (N, ≤) corresponds to an extremal ray and vice versa). We say that an extremal ray r ∈ core(F ) is deleted by equality x(S) = 0 in core(F ) if r ∈ core {S} (F ), where

core {S} (F ) := {x ∈ core(F ) | x(S) = 0}.
A first fundamental result is the following.

Proposition 5. Let F = O(N), and suppose that h(N) > 0 (height of (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.

A collection N ⊆ F \ {N} of nonempty sets is said to be normal for F if core N (F ) := {x ∈ core(F ) | x(S) = 0, ∀S ∈ N } reduces to {0}. We call restricted core of v w.r.t. N the set core N (v) = {x ∈ core(v) | x(S) = v(S), ∀S ∈ N }. If nonempty, it corresponds to a bounded face of core(v), and the union of all bounded faces of the core is called the bounded core, studied in [START_REF] Grabisch | The bounded core for games with precedence constraints[END_REF].

A nonempty normal collection is nested if any two sets S, T in the collection satisfy S ⊆ T or T ⊆ S.

We introduce three examples of normal collections. The first one is introduced in [START_REF] Grabisch | Ensuring the boundedness of the core of games with restricted cooperation[END_REF], and we call it the upwards collection. It is obtained as follows: discard all disconnected elements from (N, ≤), then consider M 1 the set of all minimal elements of (N, ≤), and put N 1 :=↓ M 1 , the principal ideal generated by M 1 (see Section 2.1). Then on N ′ := N \ M 1 , perform the same operations (discard disconnected elements, consider M 2 the set of minimal elements, etc.), till reaching the empty set. Then N u := {N 1 , . . . , N q } is a normal collection, minimal in the sense that no subcollection is normal. The second example comes from [START_REF] Grabisch | The restricted core of games on distributive lattices: how to share benefits in a hierarchy[END_REF] and is built as follows. First, elements in (N, ≤) of same height i are put into the level set Q i+1 . Hence, N is partitioned into level sets Q 1 , . . . , Q k , and Q 1 contains all minimal elements of N. Then

N GX := {Q 1 , Q 1 ∪ Q 2 , . . . , Q 1 ∪ • • • ∪ Q k-1 }
is a nested normal collection. Lastly, a nested collection can be built from N u (called the nested closure of N u ):

N ncu := {N 1 , N 1 ∪ N 2 , . . . , N 1 ∪ • • • ∪ N q }
(see Figure 8 for illustration). Given a normal collection N = {S 1 , . . . , S q }, restricted maximal chains are those passing through all sets S 1 , . . . , S q . Marginal vectors induced by restricted maximal chains are called restricted marginal vectors, and the restricted Weber set w.r.t. N , denoted by W N , is the convex hull of all restricted marginal vectors.

Theorem 17. Consider N a nested normal collection on F = O(N). Then for every game v on F , core N (v) ⊆ W N (v). In addition, if v is convex, equality holds.

The converse (core N (v) = W N (v) implies convexity of v) does not hold in general. Note that the theorem shows that core N (v) is nonempty as soon as v is convex and N is nested.

Structure of the positive core

We first address the question of nonemptiness. Adapting the result of Bondareva, we say that a collection B is completely balanced if there exist positive coefficients λ B , B ∈ B such that

B∈B λ B 1 B ≤ 1 N .
Then a game is completely balanced if B∈B λ B v(B) ≤ v(N) holds for every completely balanced collection, and core + (v) = ∅ if and only if v is completely balanced.

An equivalent definition of a completely balanced game is given by [START_REF] Faigle | Cores of games with restricted cooperation[END_REF]. A game v is completely balanced if and only if for all families A 1 , . . . , A k in F and m ∈ N it holds 1 m k i=1

1 A i ≤ 1 N implies 1 m k i=1 v(A i ) ≤ v(N).
Above, F ∋ ∅ is assumed, in order to get the condition v(N) ≥ 0 by considering the family reduced to ∅. If F is closed under intersection and complementation, a nonnegative balanced game is completely balanced.

Remark 14. The positive core is in general much smaller than the core, and could be empty even if the core is nonempty. In particular, if v is not monotone, the positive core is likely to be empty. See also the discussion below on the equality between the core and the positive core.

An important question is to know when the core and the positive core coincide.

Theorem 18. [START_REF] Faigle | Cores of games with restricted cooperation[END_REF] Let v be a nonnegative balanced game on F closed under intersection. Then core(v) = core + (v) if and only if F is atomistic. Moreover, core(v) is unbounded unless core(v) = core + (v).

F atomistic implies core(v) = core + (v) is obvious by nonnegativity of v. Also, if core(v) = core + (v) then F is not atomistic, and for {j} ∈ F , x j can be taken arbitrarily negatively large, hence unboundedness.

The positive core for augmenting systems

This has been studied by [START_REF] Bilbao | The core and the Weber set of games on augmenting systems[END_REF]. Given a (nonnegative) game v on F , we consider its extension v on 2 N :

v(S) := T maximal in F (S) v(T ).
(see Section 6.3). Recall that maximal sets in F (S) are pairwise disjoint.

Since N does not necessarily belong to F , the definition of the core is slightly modified as follows:

core + (v) := {x ∈ R n + | x(S) ≥ v(S) for all S ∈ F and x(N) = v(N)}.
A fundamental (but obvious) property is that core + (v) = core + (v) (see Section 7 for a close result, as well as Remark 15(v) for a more general result), and it is a polytope.

Suppose that N ∈ F (hence it is a regular set system). Then any maximal chain in F corresponds to an ordering on N (compatible orderings or permutations). For a maximal chain C, denote by φ C the corresponding marginal worth vector. Then the Weber set is naturally defined by

W(v) := conv{φ C | C ∈ C(F )}. Define v to be convex if for all S, T ∈ F such that S ∪ T ∈ F , v(S ∪ T ) + F maximal in F (S∩T ) v(F ) ≥ v(S) + v(T )
(this is identical to supermodular games on weakly union-closed systems in Section 6.2).

Theorem 19. [START_REF] Bilbao | The core and the Weber set of games on augmenting systems[END_REF] If v is monotone and convex, then W(v) ⊆ core + (v), and any marginal vector is a vertex of core + (v).

The classical inclusion of the core in the Weber set does not hold in general: a counterexample is given in [START_REF] Bilbao | The core and the Weber set of games on augmenting systems[END_REF] (see also Remark 13).

A game v is superadditive if for all disjoint S, T ∈ F such that

S ∪ T ∈ F , v(S ∪ T ) ≥ v(S) + v(T ).
Theorem 20. [START_REF] Bilbao | The core and the Weber set of games on augmenting systems[END_REF] Let v be a game on F .

(i) If v is superadditive and monotone, then v is superadditive and monotone.

(ii) If v is convex and monotone, then v is convex.

(iii) Suppose v is monotone. Then v is convex if and only if v is convex if and only if core(v) = W(v).

The positive core and Monge extensions

It is possible to get more general results, valid for an arbitrary set system or a weaklyunion closed system, by considering an approach closer to combinatorial optimization, through the so-called Monge algorithm5 . We refer the reader to [START_REF] Faigle | Monge extensions of cooperation and communication structures[END_REF] for details and proofs. Consider an arbitrary set system F , and a vector c ∈ R n , which will be the input vector of the Monge algorithm (MA). The idea of the algorithm is to take at each iteration the largest subset F of F contained in the current set X, and to select in F the first element p corresponding to the smallest component of a vector γ ∈ R n . At initialization, X = N and γ = c, and at each iteration, p is discarded from X, and γ p is subtracted from γ i , for all i ∈ F .

The output of the algorithm is the sequence of all selected subsets F , the sequence of all selected elements p, and a vector y ∈ R F recording at index F the quantity γ p .

We define Γ(y) := v, y . Letting for any input c ∈ R n v(c) := Γ(y), v is an extension of v since it can be proven that v(1

F ) = v(F ) for any F ∈ F . Moreover, core + (v) = {x ∈ R n | c, x ≥ v(c), ∀c ∈ R n }.
The next step is to define marginal vectors, usually defined through permutations on N. The idea here is to take instead the sequence of selected elements p produced by MA, which is not necessarily a permutation, because some elements of N may be absent. Let us denote by Π the set of all possible sequences produced by MA, and consider a sequence π ∈ Π. Then the marginal vector x π associated to π is computed as follows: for each p ∈ π, x π p is the difference between v(F ) (where F is the smallest selected subset containing p) and G v(G), where the sum is running over all maximal subsets of F belonging to the sequence. For each p ∈ π, we put x π p = 0. Clearly, the classical definition is recovered if F is regular, since in this case, the sequence of selected subsets will form a maximal chain.

We define the Weber set as

W(v) := conv{x π | π ∈ Π}.
Then it is proved in [START_REF] Faigle | Monge extensions of cooperation and communication structures[END_REF] that core + (v) ⊆ W(v).

The last step is to relate equality of the Weber set and the core to convexity. This is done through the following definition. A game v on F is convex if v is concave, i.e., it satisfies for all parameter vectors c, d ∈ R N and real scalars 0 < t < 1,

tv(c) + (1 -t)v(d) ≤ v(tc + (1 -t)d). Theorem 21. Assume v is monotone. Then v is convex if and only if core + (v) = W(v).
The above definition of convexity is done through the extension v. However, it is possible to relate it directly to v. A game v on F is strongly monotone if for any F ∈ F and pairwise disjoint feasible sets G 1 , . . . , G f ∈ F (F ) we have

f ℓ=1 v(G ℓ ) ≤ v(F ). For any intersecting F, F ′ ∈ F we put v(F ∩ F ′ ) := {v(G) | G ∈ F (F ∩ F ′ ) maximal} A game v on F is supermodular if for all intersecting F, F ′ ∈ F , we have v(F ∪ F ′ ) + v(F ∩ F ′ ) ≥ v(F ) + (F ′ ).
Theorem 22. A game v is convex if and only if v is strongly monotone and supermodular.

7 Games on communication graphs Recall also from Section 3.5 the characterization of van den Brink, and that these set collections are weakly union-closed.

(ii) A generalization of communication graphs is done through conference structures of Myerson, or equivalently through hypergraphs (see Section 3.5).

A game on the graph G = (N, E) is a TU-game on C E (N) (i.e., it is a game on the collection of feasible coalitions F = C E (N)). From v we define the extended game v G on 2 N as follows (see Section 6.3; called point game by [START_REF] Borm | On the position value for communication situations[END_REF]) This definition was considered, among others, by [START_REF] Demange | Intermediate preferences and stable coalitions structures[END_REF][START_REF] Demange | On group stability in hierarchies and networks[END_REF]. As it is easy to show, core(v) = core(v G ), which proves that when nonempty the core is a polytope.

Remark 17. Note that if the graph is connected, we recover the definition of the previous sections, hence all general properties given in Section 5.1 apply. Concerning the positive core, results in Section 6.2 apply under the same condition. Using again Remark 4 (ii), the above definition of the core amounts to take the intersection of all cores on the subsystems induced by the connected components of G.

We consider below the main families of communication graph, most useful in applications.

Communication line-graphs

Let us assume that the players are ordered according to the natural ordering 1, . . . , n, and consider the set of edges connecting two adjacent players: E 0 = {(i, i + 1), i = 1, . . . , n -1}. Then G = (N, E) is a line-graph if E ⊆ E 0 , i.e., only some adjacent players can communicate. For convenience, we introduce the notation [i, j] := {i, i + 1, . . . , j} for i < j in N.

These line-graphs often arise in applications, e.g., water distribution problem along a river [START_REF] Ambec | Sharing a river[END_REF], and auctions situations [START_REF] Graham | Differential payments within a bidder coalition and the Shapley value[END_REF], and have been studied by [START_REF] Van Den Brink | Component efficient solutions in line-graph games with applications[END_REF]. They show that a sufficient condition for the nonemptiness of the core is linear convexity:

v([i, j]) -v([i + 1, j]) -v([i, j -1]) + v([i + 1, j -1]) ≥ 0 for all [i, j] ∈ C(E) N .
van den Brink (to appear) has characterized communication line-graphs in terms of the associated set system as follows.

Theorem 24. A collection F ⊆ 2 N is the set of connected coalitions of a line-graph if and only if F ∋ ∅, F is normal (i.e., F = N), weakly union-closed, satisfies 2-accessibility (see Remark 3 (ii)) and path union stability.

To explain the last property, we need some definitions. Let ∅ = S ∈ F and i ∈ S. Then i is an extreme player in S if S \ i ∈ F . Now, S is a path in F if it has exactly two extreme players. The name comes from the fact that a path in F corresponds to a path in the graph (although the converse is false). Path union stability means that the union of two nondisjoint paths in F is still a path in F .

Cycle-free communication graphs

A graph is cyle-free if it contains no cycle, in the usual sense of graph theory. [START_REF] Breton | Strongly balanced cooperative games[END_REF] have characterized this property by what they call strong balancedness: the collection F of connected coalitions is strongly balanced if every balanced collection contains a partition of N.

Another characterization is due to van den Brink (to appear).

Theorem 25. A collection F ⊆ 2 N is the set of connected coalitions of a cycle-free graph if and only if F ∋ ∅, F is normal (i.e., F = N), weakly union-closed, satisfies 2-accessibility (see Remark 3 (ii)) and weak path union stability.

Weak path union stability means that path union stability is required only for those pairs of paths having a common extreme player.

An important particular case of cycle-free communication graph is the case of connected graphs. Then the graph is called a tree. Games on trees have been studied by many authors, among them [START_REF] Demange | Intermediate preferences and stable coalitions structures[END_REF][START_REF] Demange | On group stability in hierarchies and networks[END_REF], [START_REF] Herings | The average tree solution for cycle free games[END_REF], [START_REF] Khmelnitskaya | Values for rooted-tree and sink-tree digraph games and sharing a river[END_REF], [START_REF] Baron | Average tree solutions and the distribution of Harsanyi dividends[END_REF][START_REF] Béal | Rooted-tree solutions for tree games[END_REF]. However, most of these works are more concerned with single-valued solution (as the average tree solution of [START_REF] Herings | The average tree solution for cycle free games[END_REF]) than the core (see however Béal et al. (to appear)).

Cycle-complete communication graphs

A communication graph is cycle-complete if for each cycle of the graph, the subgraph induced by the players in that cycle is complete (i.e., each player is connected to every player in the cycle).

van den Nouweland and [START_REF] Van Den Nouweland | On the convexity of communication games[END_REF] have studied this kind of communication graph. They have shown that if the game v is convex (assuming v is defined on 2 N , unlike our assumption), then v G is also convex.

van den Brink (to appear) has characterized cycle-complete communication graphs as follows.

Theorem 26. A collection F ⊆ 2 N is the set of connected coalitions of a cycle-free graph if and only if F ∋ ∅, F is normal (i.e., F = N), weakly union-closed, satisfies 2-accessibility (see Remark 3 (ii)) and the path property.

F has the path property if for every pair of players i, j, there is at most one path having i, j as extremal players. Alternatively, the path property can be replaced by closure under intersection.

Acknowledgment

The author is indebted in particular to Ulrich Faigle, Jean Derks, and René van den Brink for fruitful discussions, and for giving him an incentive to write a survey on this topic.

Figure 1 :

 1 Figure 1: Left: a distributive lattice L. Join-irreducible elements are those in grey. Middle: the poset J (L) of join-irreducible elements. Right: the set O(J (L)) of all downsets of J (L) ordered by inclusion, which is isomorphic to L

Figure 2 :

 2 Figure 2: A set system satisfying one-point extension and accessibility, but which is not k-regular

Figure 3 :

 3 Figure 3: Set lattices and k-regular set systems

Figure 4 :

 4 Figure 4: (i) k-regular but not a lattice; (ii) lattice but not k-regular; (iii) k-regular lattice but not distributive; (iv) distributive lattice but not closed under ∪; (v) closed under ∪, ∩ but not isomorphic to O(N)

Figure 5 :Figure 6 :

 56 Figure 5: Regular set systems and weakly union-closed systems

Theorem 4 .

 4 [START_REF] Derks | On the core of a collection of coalitions[END_REF] core(F ) is a pointed cone if and only if F is non-degenerate.

  otherwise}. Note that F (D) is either empty or a face of the core provided D ∋ N, and that F • (D) is an open face. DefineD := {D ∈ F | D is a sublattice of F containing ∅, N, F • (D) = ∅}.Observe that any such D is necessarily distributive, and therefore is generated by a poset. It is easy to see that D = {F (x) | x ∈ core(v)}. It follows that any face of the core is defined by a distributive sublattice of F . Moreover, the dimension of a face F (D) is |N| -|h(D)|, where h(D) is the height of the lattice D.

Figure 7 :

 7 Figure 7: Example of a degenerate 2-regular set system with 3 players

Figure 8 :

 8 Figure8: (N, ≤) has 9 elements. Level 1 is {1, 2, 3}, level 2 is {4, 5, 6, 9} and level 3 is {7, 8}. The upwards collection is {123, 13456}, its nested closure is {123, 123456}, and the Grabisch-Xie collection is {123, 1234569}.

  ), ∀S ⊆ N.Since a communication graph may contain several connected components, and recalling Remark 4 (ii), a natural adaptation for the definition of the core is as follows:core(v) := {x ∈ R n | x(C) = v(C), ∀C ∈ N/E, and x(S) ≥ v(S), ∀S ∈ C E (N)}.

  Consider a (undirected) graph G = (N, E), where the vertices are players, and E is the set of links. A link between i, j exists if these players can communicate or are friends. Two players are connected if there exists a path between them. A connected coalition is a subset of N where any two players are connected. The set of connected coalitions is denoted by C E (N). Maximal connected coalitions of G are called connected components of G, and they partition N. The set of connected components of G is denoted by N/E. Any coalition S ⊆ N, even if not connected, can be partitioned into maximal connected coalitions (i.e., connected components of the subgraph induced by S). The set of connected components of S is denoted by S/E. This is the framework defined byMyerson (1977a).Remark 16. (i) As said in Section 3.7, set collections induced by communication graphs are exactly augmenting systems containing all singletons. If the graph is connected, then they are regular set systems containing all singletons (the converse is false).

	7.1 General definitions

Some authors use instead the words ideals and filters. This is however incorrect, since in the standard terminology, an ideal is a downset closed under supremum, and a filter is an upset closed under infimum.

In fact, it is simpler to check the following equivalent condition: for all i ∈ N , it exists a linear combination of the 1 T 's, T ∈ F , giving 1 i .

This example was communicated by J. Derks.

The original idea of the Monge algorithm goes back to[START_REF] Monge | Déblai et remblai[END_REF]. Monge studied a geometric transportation problem in which a set of locations s 1 , . . . , s n of mass points has to be matched optimally (in the sense of minimizing the total cost) with another set of locations t 1 , . . . , t n , and proved that optimality was reached if the transportation lines do not cross. This geometric fact can be expressed as follows: if the costs c ij of matching objects s i with t j have the "uncrossing" property:c ij + c kℓ ≥ c max(i,k),max(j,ℓ) + c min(i,k),min(j,ℓ)then the optimal matching is (s 1 , t 1 ), . . . , (s n , t n ). This is also called the "north-west corner rule". Translated into the language of set functions, the uncrossing property is in fact submodularity:v(A) + v(B) ≥ v(A ∪ B) + v(A ∩ B).

Extension of v on 2 N

Let F be weakly union-closed, and v be a game on F . We introduce an extension of v on 2 N as follows:

v(S) =

T maximal in F (S) v(T ), ∀S ⊆ N.

Remark 15. (i) This way of extending a game on 2 N appears in many different works.

For communication graphs, Myerson (1977b) used it for computing v G (S), the extension on 2 N of a game v on G, for any S ⊆ N, decomposing S into its (maximal) connected components (in this context, see also [START_REF] Owen | Values of graph-restricted games[END_REF], [START_REF] Borm | On the position value for communication situations[END_REF], [START_REF] Potters | γ-component additive games[END_REF]). It can be found also in Bilbao (2000, §5.2) with F a partition system, under the name of F -restricted game, and in [START_REF] Bilbao | The core and the Weber set of games on augmenting systems[END_REF]. In general, it is considered in all the literature on communication graphs. This extension has been studied by [START_REF] Faigle | A discrete Choquet integral for ordered systems[END_REF], and arises naturally as the output of the Monge algorithm described in Section 6.2 (see (ii) and (iii) below).

(ii) Even if v is monotone, v need not be monotone. If v is monotone, it is not the smallest extension of v (for this replace by max in the above equation). If F is union-closed, then v is the smallest extension and preserves monotonicity of v [START_REF] Faigle | A discrete Choquet integral for ordered systems[END_REF].

(iii) v is given by the Monge algorithm, i.e., v(S) = v(1 S ) for all S ∈ 2 N .

(iv) The Möbius transform (see Section 3) of v vanishes for all S not in F (easy fact, remarked by [START_REF] Owen | Values of graph-restricted games[END_REF]). More precisely:

, for all S ∈ F 0, otherwise where m v is the Möbius transform of v on F .

(v) For any game v, we always have core + (v) = core + (v). Indeed, the inclusion of core + (v) in core + (v) is obvious. Conversely, assume that x ∈ core + (v) and take any F ∈ F . Then v(F ) = T maximal in F (F ) v(T ). We have x(T ) ≥ v(T ) for all T maximal in F (F ). Therefore, since these T 's are disjoint and x is nonnegative, we find x(F ) ≥ v(F ). Adapting the previous argument, core(v) = core(v) holds provided all singletons belongs to F . Then the maximal sets in F (F ) form a partition of F (F is a partition system).

Faigle and Grabisch (2011) have proved the following.

Theorem 23. Assume F is union-closed, and v is a game on F . Then v is supermodular on F (in the sense of Section 6.2) if and only if v is supermodular on 2 N .