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

Peter Sudh Ölter

On a class of vertices of the core

Keywords: TU games, restricted cooperation, game with precedence constraints, core, vertex JEL Classification: C71

It is known that for supermodular TU-games, the vertices of the core are the marginal vectors, and this result remains true for games where the set of feasible coalitions is a distributive lattice. Such games are induced by a hierarchy (partial order) on players. We propose a larger class of vertices for games on distributive lattices, called min-max vertices, obtained by minimizing or maximizing in a given order the coordinates of a core element. We give a simple formula which does not need to solve an optimization problem to compute these vertices, valid for connected hierarchies and for the general case under some restrictions. We find under which conditions two different orders induce the same vertex for every game, and show that there exist balanced games whose core has vertices which are not min-max vertices if and only if n > 4.

Introduction

In the seminal paper of [START_REF] Shapley | Cores of convex games[END_REF] was undertaken probably the first study of the geometric properties of the core of TU-games. In particular, it was established that the set of marginal vectors coincides with the set of vertices of the core when the game is convex. This paper was the starting point of numerous publications on the core and its variants, studying its geometric structure (vertices, facets, since it is a closed convex polytope) for various classes of games (in particular, the assignment games of [START_REF] Shapley | The assignment game I: The core[END_REF]).

In a parallel way, it was found that the classical view of TU-games, defined as set functions on the power set of the set of players, was too narrow, and the idea of restricted cooperation (i.e., not any coalition can form) germinated in several papers, most notably [START_REF] Aumann | Cooperative games with coalition structures[END_REF]; [START_REF] Myerson | Values of games in partition function form[END_REF]; [START_REF] Owen | Values of games with a priori unions[END_REF] and [START_REF] Faigle | Cores of games with restricted cooperation[END_REF], who coined the term "restricted cooperation" and precisely studied the core of such games. Many algebraic structures were proposed for the set of feasible coalitions, e.g., (distributive) lattices, antimatroids, convex geometries, etc. It turned out that the structure of the core became much more complex to study, in particular due to the fact that the core on such games may become unbounded (see a survey in [START_REF] Grabisch | The core of games on ordered structures and graphs[END_REF]). However, as shown by [START_REF] Derks | Hierarchical organization structures and constraints on coalition formation[END_REF], the main result established in [START_REF] Shapley | Cores of convex games[END_REF] remains true for games on distributive lattices: for supermodular games, the set of marginal vectors still coincides with the set of extreme points of the core.

The question addressed in this paper arises naturally from the last result: What if the game is not supermodular? Is it possible to know all of its vertices in an analytical form? The question has puzzled many researchers, and so far only partial answers have been obtained, and only in the case of classical TU-games, i.e., without restriction on cooperation. Significant contributions have been done in particular by Núñez and[START_REF] Núñez | On extreme points of the core and reduced games[END_REF][START_REF] Tijs | The first steps with Alexia, the average lexicographic value[END_REF]. In the former work, a family of vertices is obtained, which is shown to cover all vertices of the core when the game is almost convex (i.e., satisfying the supermodularity condition except when the grand coalition is involved). Later, [START_REF] Núñez | Characterization of the extreme core allocations of the assignment game[END_REF] have shown that this family of vertices is also exhaustive for assignment games, while [START_REF] Ch | On the set of extreme core allocations for minimal cost spanning tree problem[END_REF] have shown that the same result holds for minimum cost spanning tree games. In the work of Tijs, another family of vertices is proposed, called leximals, which is leading to the concept of lexicore and the Alexia value.

The present paper lies in the continuity of these works, showing that the two previous families have close links, proposing a wider class of vertices (unfortunately, still not exhaustive in all cases), and most importantly, establishing results in the general context of games on distributive lattices. Such a class of games is of considerable interest, because it has a very simple interpretation: the set of feasible coalitions is induced by a hierarchy (partial order) on the set of players, and feasible coalitions correspond to subsets of players where every subordinate of a member must be present. In the absence of hierarchy, the classical case is recovered.

We summarize the main achievements of the paper. We first give a tight upper bound of the number of vertices of the core, using an argument of [START_REF] Derks | On the number of extreme points of the core of a transferable utility game[END_REF]. Then we introduce the family of min-max vertices, obtained by minimizing or maximizing in a given order the coordinates of a core element. Minimization (respectively, maximization) is performed if the considered coordinate (player) is a minimal element (respectively, a maximal element) in the sub-hierarchy formed by the remaining players. We prove that these are indeed vertices of the core (Theorem 2), and that in the case of supermodular games, we recover all marginal vectors (Corollary 1). The case of connected hierarchies reveals to be particularly simple, because min-max vertices take a simple form and can be computed directly without solving an optimization problem (Theorem 5). In the general case, a similar computation can be done provided some conditions are satisfied (Formula (15)). Two different orders may yield the same min-max vertex for every game. We show in Theorem 7 that this arises if and only if one of the orders can be obtained from the other one by a sequence of switches exchanging minimal and maximal elements. Lastly, we investigate the limits of the min-max approach to find vertices, and show that there exist balanced games whose core has vertices which are not min-max vertices if and only if n > 4 (Theorem 8).

The paper is organized as follows. Section 2 introduces the necessary material for games on distributive lattices and cores of such games, which are unbounded in general. We show that the structure of the convex hull of the vertices of the core of games on distributive lattices is more complex than the structure of the core of ordinary games (Proposition 1). Section 3 gives an upper bound of the number of vertices of the core. Section 4 is the main section of the paper, introducing and studying min-max vertices. Section 5 investigates under which condition orders yield identical min-max vertices. Examples illustrating the main results and concepts are given in Section 6, together with a practical summary of how to proceed. The limits of the min-max approach are investigated in Section 7, and the paper finishes with Section 8 detailing the past literature on the topic.

Notation, definitions and preliminaries

A partially ordered set or poset (P, ) is a set P endowed with a partial order , i.e., a reflexive, antisymmetric and transitive binary relation. A poset (P, ) is a lattice if every two elements x, y ∈ P have a supremum and an infimum, denoted respectively by ∨, ∧. The lattice is distributive if ∨, ∧ obey distributivity. As usual, x ≺ y means x y and x = y. We say that x covers y, denoted by y ≺• x, if y ≺ x and there is no z ∈ P such that y ≺ z ≺ x. A chain in (P, ) is a sequence x 0 , . . . , x p such that x 0 ≺ • • • ≺ x p , and its length is p. The height of (P, ) is the length of a longest chain in (P, ).

Throughout the paper we consider posets (N, ), where N ⊆ U is finite, with |N| = n, and U is a set that contains {1, . . . , 5}. The set N can be considered as a set of players, agents, and as expressing precedence constraints or hierarchical relations among players. For this reason, we will often refer to (N, ) as a hierarchy.

Subsets of N are called coalitions, and a coalition S is said to be feasible if i ∈ S and j i imply j ∈ S. In other words, the feasible coalitions are the downsets of the poset (N, ), and we denote by O(N, ) the set of downsets of (N, ). It is well known that (O(N, ), ⊆) is a distributive lattice of height n, whose infimum and supremum are set intersection and union, respectively. By [START_REF] Birkhoff | On the combination of subalgebras[END_REF] Theorem, the converse also holds: any distributive lattice of height n is isomorphic to the set of downsets of some poset of n elements.

A (TU) game with precedence constraints [START_REF] Faigle | The Shapley value for cooperative games under precedence constraints[END_REF]) is a triple (N, , v) where (N, ) is a poset and v : O(N, ) → R satisfies v(∅) = 0. The set O(N, ) of feasible coalitions is denoted by F . Classical TU-games correspond to the case F = 2 N , i.e., the partial order is empty. We denote by Γ the set of games (N, , v), N ⊆ U, with precedence constraints.

We say that (N, ) is connected if the Hasse diagram of (N, ), seen as a graph, is connected in the sense of graph theory, i.e., if for any two distinct i, j ∈ N, there is a sequence of elements i = j 1 , . . . , j m = j in N such that either j ℓ ≺• j ℓ+1 or j ℓ+1 ≺• j ℓ for every ℓ = 1, . . . , m -1. In this case, we speak of a connected hierarchy.

For any x ∈ R N , we use the shorthand x(S) = i∈S x i for any nonempty S ∈ 2 N . The set of feasible payoff vectors and the set of preimputations of a game (N, , v) are respectively defined by

X * (N, , v) = {x ∈ R N : x(N) v(N)}, X(N, , v) = {x ∈ R N : x(N) = v(N)}.
The core of a game (N, , v) is the set defined by

C(N, , v) = {x ∈ X(N, , v) : x(S) v(S), ∀S ∈ F }.
A game has a nonempty core if and only if it is balanced [START_REF] Faigle | Cores of games with restricted cooperation[END_REF]. Whenever nonempty, the core is a closed convex pointed polyhedron [START_REF] Derks | Hierarchical organization structures and constraints on coalition formation[END_REF], i.e., it has the following form:

C(N, , v) = conv(ext(C(N, , v))) + C(N, , 0), (1)
where "conv" indicates the convex hull of a set of points, "ext" the extreme points (or vertices) of a convex set, "+" is the Minkovski sum, and C(N, , 0) is the conic part (recession cone) of C(N, , v), obtained by replacing v by the null game. It has the following form [START_REF] Derks | Hierarchical organization structures and constraints on coalition formation[END_REF][START_REF] Tomizawa | Theory of hyperspace (XVI)-on the structure of hedrons[END_REF]:

C(N, , 0) = cone({1 {i} -1 {j} : i, j ∈ N, i ≺• j}), (2)
where "cone" indicates the convex cone containing 0 ∈ R N and the conic combination of a set of points, and, for any S ⊆ N, 1 S ∈ R N is the characteristic function of S. It follows that the core is bounded if and only if is empty.

A game (N, , v) is supermodular if v(S ∪ T ) + v(S ∩ T ) v(S) + v(T )
for every S, T ∈ F . The structure of the core is completely known for supermodular games. Let us denote by Π(F ) the set of total orders π on N, i.e., bijective mappings {1, . . . , n} -→ N, which are compatible with F , i.e., such that the sets ∅ = B π 0 , B π 1 , . . . , B π n = N with B π i = {π(1), . . . , π(i)} form a maximal chain in F (these orders are the linear extensions of ). For any π ∈ Π(F ), we define its associated marginal vector m

π,v ∈ R N by m π,v π(i) = v(B π i ) -v(B π i-1 ), ∀i ∈ {1, . . . , n}.
Theorem 1. [START_REF] Fujishige | A note on submodular functions on distributive lattices[END_REF][START_REF] Derks | Hierarchical organization structures and constraints on coalition formation[END_REF] The game (N, , v) is supermodular if and only if every marginal vector m π,v with π ∈ Π(F ) is a vertex of C(N, , v).

Let S ⊆ N. For any x ∈ R N , x S denotes the vector of R S which is the restriction of x to S. Considering the poset (S, ) with the slight abuse of notation that is now restricted to S, the induced distributive lattice is O(S, ) =: F (S) = {T ∩ S : T ∈ F }.

Consider a game (N, , v) on F , a set ∅ = S ⊆ N and a vector x N \S ∈ R N \S . The reduced game w.r.t. x N \S and S is the game (S, , v S,x N\S ) defined by [START_REF] Davis | The kernel of a cooperative game[END_REF] as follows:

v S,x N\S (T ) =      v(N) -x(N \ S), if T = S 0, if T = ∅ max{v(T ∪ R) -x(R) : R ⊆ N \ S, T ∪ R ∈ F }, if T ∈ F (S) \ {∅, S}.
(3) Note in particular, if S = N \ {j} for some j ∈ N, then v S,x j denotes the coalition function of the reduced game w.r.t. N \ {j} and x j ∈ R {j} . It is useful to note the following transitivity property of reducing:

(v S,x N\S ) T,x S\T = v T,x N\T . ( 4
)
for any T ⊂ S ⊆ N and any x ∈ R N . A solution on Γ ′ ⊆ Γ is a correspondence σ that assigns to each (N, , v) ∈ Γ ′ a subset σ(N, , v) of X * (N, , v). A solution σ satisfies:

(i) The reduced game property (RGP) if for every (N, , v) ∈ Γ ′ , every ∅ = S ⊆ N and every x ∈ σ(N, , v), we have (S, , v S,x N\S ) ∈ Γ ′ and x S ∈ σ(S, , v S,x N\S );

(ii) The reconfirmation property (RCP) if for every (N, , v) ∈ Γ ′ , every ∅ = S ⊆ N and every x ∈ σ(N, , v), the following condition holds: If (S, , v S,x N\S ) ∈ Γ ′ and y S ∈ σ(S, , v S,x N\S ), then (y S , x N \S ) ∈ σ(N, , v).

By Remark 4.2 in [START_REF] Grabisch | The bounded core for games with precedence constraints[END_REF], as in the classical case F = 2 N , the core satisfies RGP and RCP on any Γ ′ ⊆ Γ, with the restriction for the former that Γ ′ is closed under taking reductions w.r.t. core elements.

The following notions are useful [START_REF] Grabisch | Characterizations of solutions for games with precedence constraints[END_REF]. We consider R (N, ) (denoted simply by R if no ambiguity occurs) the partition of N whose blocks are the connected components of (N, ) and define the intermediate game

(R, v R ), with v R : 2 R → R a classical TU-game defined by: v R (T ) = v( T ) (T ⊆ R).
We denote by F 0 the set of feasible coalitions which are not unions of blocks of R, i.e., F 0 ⊆ F and F \ F 0 = { T : T ⊆ R}.

Before entering the main topic, we show that there is interest in studying the core of games with precedence constraints, because the convex part of the core of such games has a richer structure than the core of classical games. Put otherwise, there exist games with precedence constraints such that the convex part of their core does not coincide with any core of a classical game.

Let (N, v) be an exact TU game, i.e., for every subset S of N, there exists a core element such that x(S) = v(S). We then have

v = ext(C(N, v)), (5)
i.e., v(S) = min{x(S) : x ∈ ext(C(N, v))} for all S ⊆ N. We call (N, v) oxytrophic [START_REF] Rosenmüller | Game Theory: Stochastics, Information, Strategies and Cooperation[END_REF] if none of the extreme points of the core is redundant in the representation (5) of v. Let v = {(3, 4, 0, 0), (0, 0, 2, 5)} (Example 3.3 of the aforementioned book). Then it can be checked that ext(C(N, v)) = {(3, 4, 0, 0), (0, 0, 2, 5), (2, 4, 0, 1), (0, 2, 2, 3), (2, 2, 0, 3), (3, 2, 0, 2), (1, 0, 2, 4), (1, 2, 2, 2)} so that (N, v) is not oxytrophic. We now consider (N, ) defined by 1 ≺ 2, 3 ≺ 2, and 3 ≺ 4 (see Figure 1). Proposition 1. There exists a TU game (N, , v) with a connected hierarchy such that the convex hull of the vertices of its core does not coincide with the core of any classical TU game.

3 An upper bound for the number of vertices

Let (N, , v) ∈ Γ, denote F = O(N, ), and introduce κ(F ) = |Π(F )|, Q F = conv{1 S : S ∈ F }, and, for any π ∈ Π(2 N ), Q π = {x ∈ [0, 1] N : x π(1) ≥ • • • ≥ x π(n) }.
Then the interior of the intersection of any two of the Q π is empty, their union is the unit cube, and the volumes of all of them are identical so that we conclude that the volume of

Q π is V (Q π ) = 1 n! . Moreover, we claim that Q F = π∈Π(F ) Q π .
Indeed, it is a well-known fact that each Q π is an n-dimensional simplex, and its vertices are the n + 1 characteristic vectors 1

B π 0 , 1 B π 1 , . . . , 1 B π n . Therefore, we have Q π = conv{1 B π 0 , 1 B π 1 , . . . , 1 B π n }. Since any maximal chain in F is of the form B π 0 , B π 1 , . . . , B π n for some π, we have F = π∈Π(F ) n i=0 B π i ,
which proves the desired result.

Our claim shows that

V (Q F ) = V   π∈Π(F ) Q π   = π∈Π(F ) V (Q π ) = κ(F ) n! .
Now, according to Theorem 4.4 of [START_REF] Derks | On the number of extreme points of the core of a transferable utility game[END_REF], the number of vertices of C(N, , v) is not larger than n!V (Q F ) so that we have deduced the following proposition.

Proposition 2. For any game (N, , v) with precedence constraints, the number of vertices of its core is not larger than the number of linear extensions of (N, ), i.e.,

C(N, , v) has at most |Π (O(N, , v))| vertices.
By Theorem 1, the vertices of the core of a supermodular game are the κ marginal vectors of the game. The upper bound is then attained, provided they are all different (e.g., when the game is strictly supermodular [START_REF] Grabisch | On the restricted cores and the bounded core of games on distributive lattices[END_REF]).

Min-max vertices

This section presents the construction of our proposed family of vertices. We begin by presenting informally the main idea underlying this family.

The main idea

Consider a balanced game (N, , v) and select some element i ∈ N. If i is minimal in (N, ), then {i} is a feasible coalition, so that any core element x satisfies x i v({i}). Hence x i is bounded from below by v({i}). If i is a maximal element in (N, ), then N \ {i} is a feasible coalition, therefore any core element x satisfies

x i = x(N) -x(N \ {i}) v(N) -v(N \ {i}),
which provides an upper bound for x i . Suppose now that i is neither maximal nor minimal. Then there exist j, k ∈ N such that j ≺ • i ≺ • k. By (2), 1 {j} -1 {i} and 1 {i} -1 {k} are both extremal rays of the recession cone, so that x i is neither bounded from below nor from above.

Consider then a minimal or maximal element i in (N, ), and fix x i to be accordingly the lower or upper bound. Supposing some core element has value x i on the ith coordinate, by the reconfirmation property of the core, it suffices to find x N \{i} in the core of the reduced game v N \{i},x i (which is nonempty by the reduced game property) to ensure that x = (x i , x N \{i} ) is a core element.

The basic algorithm is then the following:

(i) Choose some order π on the players such that π(i) is either minimal or maximal in the poset ({π(i), . . . , π(n)}, ) for every i = 1, . . . , n;

(ii) Starting from player π(1), do successively for i = 1, . . . , n:

(a) Set x π(i) to its lower or upper bound depending whether i is minimal or maximal.

(b) Eliminate player π(i) and update the game by taking the reduced game over {π(i + 1), . . . , π(n)}.

Note that the algorithm will end up with a core element if at each step there exists a core element with coordinate attaining the lower or upper bound. Hence, the key point of this procedure will be to find valid bounds for core elements.

Min-max vertices

We formalize and develop the previous ideas. Let (N, , v) be a game with precedence constraints, S ⊆ N, and x S ∈ R S . We say that x S is core extendable

(w.r.t. (N, , v)) if there exists z ∈ C(N, , v) such that z S = x S .
Lemma 1. Let (N, , v) be a game with precedence constraints and i ∈ N.

(i) Let n 2. Then x i ∈ R {i} is core extendable if and only if (a) x i v({i}) if i is a minimal element of (N, ), (b) x i v(N) -v(N \ {i}) if i is a maximal element of (N, ), and (c) (N \ {i}, , v N \{i},x i ) is balanced.
(ii) Assume that (N, , v) is balanced. The set {x i : x ∈ C(N, , v)} is convex and bounded (a) from below if and only if i is a minimal element of (N, );

(b) from above if and only if i is a maximal element of (N, ).

(iii) Let S, T ⊆ N such that S ∩T = ∅ and S = N. Then x S∪T ∈ R S∪T is core extendable if and only if x S is core extendable and x T is core extendable w.r.t. the reduced game (N \ S, , v N \S,x S ).

Proof.

(i) Suppose x ∈ C(N, , v). By RGP, x N \{i} ∈ C(N \ {i}, , v N \{i},x i ) so that (c) is satisfied. Moreover, if i is minimal, then {i} ∈ F := O(N, ) implying (a). Similarly, if i is maximal, then N \ {i} ∈ F . Hence, x(N \ {i}) = v(N) -x i v(N \ {i}) so that (b) follows. For the if-part, assume that x i satisfies (a) -(c). Then there exists x N \{i} ∈ C(N \ {i}, , v N \{i},x i ) and it suffices to prove that x ∈ C(N, , v). Let S ∈ F . If S = N \ {i} and S ∩ (N \ {i}) = ∅, then x(S \ {i}) v N \{i},x i (S \ {i}) by (c), which implies x(S) v(S).
In particular, (c) also implies x ∈ X(N, , v). If S = {i}, then i is minimal and x(S) v(S) by (a), and if S = N \ {i}, then i is maximal and x(S) v(S) by (b).

(ii) This is an immediate consequence of ( 1) and ( 2).

(iii) Let (N \ S, , v N \S,x S ) = (N ′ , , v ′ ). Now, if x S∪T is core extendable, then obviously x S is, and there exists z ∈ C(N, , v) such that z S∪T = x S∪T . By RGP,

z N ′ ∈ C(N ′ , , v ′ ) so that z T = x T is core extendable w.r.t. (N ′ , , v ′ ). Conversely, if x S is core extendable and x T is core extendable w.r.t. (N ′ , , v ′ ), then there exist y ∈ C(N, , v) and y ′ N ′ ∈ C(N ′ , , v ′ ) such that y S = x S and y ′ T = x T . Let x = (x S , x N ′ ) ∈ R N be defined by x N ′ = y ′ N ′ . Then x(N) = v(N)
and, hence, it suffices to show that x(P ) v(P ) for each P ∈ O(N, ). If P ∩(N \S) = ∅ and S ∪P = N, then, by (3), v(P ) -

x(P ) v ′ (P ∩ N ′ ) -y ′ (P ∩ N ′ ) 0 because y ′ ∈ C(N ′ , , v ′ ). If P ⊆ S, then v(P ) -x(P ) = v(P ) -x S (P ) 0 because x S is core extendable. Finally, if N \ S ⊆ P , then x(P ) = x(N \ S) + y(P ∩ S) = y(P ) v(P ) because y(N) = x(N) = v(N) and y ∈ C(N, , v) so that the proof is finished.
For any total order π on N, we define

A π i = {π(i), . . . , π(n)} = N \ B π i-1
for i = 1, . . . , n. A total order π on N is admissible if π(i) is either a minimal or a maximal element in the poset (A π i , ) for all i = 1, . . . , n. Note that any linear extension of (N, ) is an admissible order.

A decision vector is any vector in {-1, 1} N . Given an admissible order π and a decision vector d, we say that (π, d) is a consistent pair if the following conditions are satisfied for i = 1, . . . , n:

d i = -1 =⇒ π(i) is minimal in the poset (A π i , ); (6) d i = 1 =⇒ π(i) is maximal in the poset (A π i , ). (7)
Actually, d is only useful for breaking ties, i.e., when π(i) happens to be both minimal and maximal in (A π i , ). Note that this situation never happens when (A π i , ) is connected, unless i = n.

Assume (N, , v) is balanced. For any consistent pair (π, d), recursively define the vector x = x π,d,v ∈ R N as follows:

x π(i) = d i • max z π(i) d i : z ∈ C(A π i , , v A π i ,x B π i-1
) for all i = 1, . . . , n.

Theorem 2. Let (N, , v) be a balanced game, π be an admissible order of N, and d a decision vector. If (π, d) is consistent, then the vector x π,d,v given by ( 8) is well-defined, and it is a vertex of C(N, , v).

Proof.

For i = 1, . . . , n denote (A i , , v i ) = (A π i , , v A π i ,x B π i-1
) and x π(i) = x π,d,v π(i) . Claim 1: For each i = 1, . . . , n, (A i , , v i ) is balanced, and x π(i) is well-defined. We show Claim 1 by induction on i. As (A 1 , , v 1 ) = (N, , v), part (ii) of Lemma 1 shows our claim for i = 1. Assume now that Claim 1 is valid for some i < n. Then x π(i) is core extendable w.r.t. (A i , , v i ) so that, by RGP, A i+1 , , (v i ) A i+1 ,x π(i) is balanced. However, by the transitivity of reducing (4), (v i ) A i+1 ,x π(i) = v i+1 so that Claim 1 is shown for i + 1 by Lemma 1 (ii).

Claim 2: For each i = 1, . . . , n, x B π i is core extendable. Note that x B π 1 = x π(1) so that Claim 1 implies that Claim 2 is valid for i = 1. Proceeding by induction we assume now that x B π i is core extendable for some i < n. By Claim 1, x π(i+1) is core extendable w.r.t. (A i+1 , , v i+1 ) so that, by Lemma 1 (iii) applied to S = B π i and T = {π(i + 1)}, x B π i+1 is core extendable. Note that, by Claim 2 applied to i = n, we have x ∈ C(N, , v). Hence, it remains to show that x is a vertex of the core. Let y, z ∈ C(N, v), y = x and 0 λ < 1 such that x = λy + (1λ)z. Let i ∈ {1, . . . , n} be minimal such that y π(i) = x π(i) . Hence, z B π i-1 = x B π i-1 as well. By Lemma 1 (iii) applied to S = B π i-1 and T = {π(i)}, y π(i) and z π(i) are core extendable w.r.t. (A i , , v i ). By (8), y π(i) < x π(i) d i and z π(i) x π(i) d i , hence z = x and λ = 0 which finishes the proof.

Remark 1. (i) We see that by Claim 1 of the proof, each reduced game (

A π i , , v A π i ,x B π i-1
) is balanced. It follows that the above theorem can be applied to any such reduced game, and by the transitivity of reducing (4), we obtain that x π,d,v

A π i is a vertex of C(A π i , , v A π i ,x B π i-1
) for any i = 1, . . . , n.

(ii) Another remarkable property of x = x π,d,v is the following:

x π(i) = d i • max z π(i) d i : z ∈ C(N, , v), z B π i-1 = x B π i-1 for all i = 1, . . . , n. (9) Indeed, letting (A i , , v i ) = (A π i , , v A π i ,x B π i-1
) and

B i = B π i , z ∈ C(A i , , v i ) is equivalent to z(A i ) = v i (A i ) = v(N) -x B i-1 and z(S) v i (S) for every S ∈ F (A i ). The second assertion is equivalent to z(S) v(S ∪ R) -x(R) for every S ∈ F (A i ) and every R ∈ F (B i ). Therefore z ∈ C(A i , , v i ) is equivalent to z ∈ C(N, , v), z B i = x B i .
Based on this result, we call min-max vertex of C(N, , v) any vector x π,d,v where (π, d) is a consistent pair. The computation of min-max vertices depends then if we are able to find an explicit expression for the bounds of core elements. We will show that in two important particular cases studied in Sections 4.3 and 4.4, this computation is easy and corresponds to what we call hereafter the induced vector.

Given a consistent pair (π, d) (recall that π is an admissible order), and a game (N, , v), we define the induced vector y π,d,v ∈ R N recursively on i = 1, . . . , n with

v i = v A π i ,y π,d,v B π i-1
as follows:

y π,d,v π(i) = v i ({π(i)}), if d i = -1, v i (A π i ) -v i (A π i+1 ), if d i = 1, (i = 1, . . . , n). ( 10
)
Note that the induced vector corresponds to the intuitive bounds given in our informal presentation in Section 4.1. Contrarily to x π,d,v , it is not always a core element, however the following result holds.

Theorem 3. Let (π, d) be a consistent pair and (N, , v) be a game. Then

(i) Each game (A π i , , v A π i ,y π,d,v B π i-1
) is balanced for i = 1, . . . , n if and only if y π,d,v is a core element;

(ii) y π,d,v is a core element if and only if y π,d,v = x π,d,v , i.e., it is a min-max vertex.

Proof. We fix (π, d) and v and denote for simplicity d,v .

A i = A π i , v i = v A π i ,y π,d,v B π i-1 and y = y π,d,v , x = x π,
(i) We show the "only if" part. By definition of y π(1) , the assumption of balancedness and Lemma 1 (i), y π(1) is core extendable. Proceeding by induction, suppose that y B π i is core extendable for some i < n. Then, by Lemma 1 (iii), y B π i+1 is core extendable iff y B π i is and y π(i+1) is core extendable w.r.t. v i+1 . Now, the last assertion holds by Lemma 1 (i), by definition of y π(i+1) and the assumption of balancedness.

Conversely, we show by induction that y

A i ∈ C(A i , , v i ).
The property is trivially true for i = 1. Assume it is true for some i < n and let us prove it for i + 1. We have

v i+1 (A i+1 ) = v(N) -y(B π i ) = y(A i+1
) since y is a core element. Now, for any S ∈ F (A i+1 ), we have

v i+1 (S) = v(S ∪ T ) -y(T ) y(S ∪ T ) -y(T ) = y(S)
for some adequate T ⊆ B π i , which proves the claim.

(ii) We have only to show the "only if" part. By definition of x and since y is a core element, we have dy π(1) dx π(1) . On the other hand, since x is a core element, it satisfies 1) is maximal, so that in any case y π(1) = x π(1) . Proceeding by induction, suppose that y B π i = x B π i for some i < n. We know from (i) that y A i+1 ∈ C(A i+1 , , v i+1 ). Hence, we deduce that dy π(i+1) dx π(i+1) , and equality holds because x π(i+1) is core-extendable w.r.t. v i+1 .

x π(1) v({π(1)}) if π(1) is minimal, or x π(1) v(N) -v(N \ {π(1)}) if π(

The case of supermodular games

For any i ∈ {1, . . . , n} denote T π,d i = {π(j) : j ∈ {1, . . . , i -1}, d j = -1}.

Theorem 4. Let (N, , v) be supermodular and let (π, d) be a consistent pair. Then

v A π i ,y π,d,v B π i-1 (S) = v(S ∪ T π,d i ) -v(T π,d i )
for all i ∈ {1, . . . , n} and S ∈ O(A π i , ).

Proof. Let y = y π,d,v , and, for any i ∈ {1, . . . , n},

A i = A π i , T i = T π,d i , and v i = v A i ,y B π i-1
. We proceed by induction on i. If i = 1, then A i = N, T i = ∅, and v i = v so that the proof is finished. Assume that the theorem is correct for i = k -1 and some k = 2, . . . , n. Now, if i = k, we distinguish two cases:

1. d i-1 = 1: Then T i = T i-1 so that, by the inductive hypothesis,

y π(i-1) = v i-1 (A i-1 ) -v i-1 (A i ) = v(A i-1 ∪ T i ) -v(A i ∪ T i )
which in turn implies, using (4) and the inductive hypothesis again,

v i (A i ) = v i-1 (A i-1 ) -y π(i-1) = v(A i ∪ T i ) -v(T i ).
Let S ∈ O(A i , ) \ {A i , ∅}. Two subcases may occur: If S ∪ {π(i -1)} / ∈ O(A i-1 , ), then, by definition of the reduced game, v i (S) = v i-1 (S) = v(S ∪ T i )v(T i ), where the last equation results from the inductive hypothesis because

T i = T i-1 . If S ∪ {π(i -1)} ∈ O(A i-1 , ), then v i (S) = max{v i-1 (S), v i-1 (S ∪ {π(i -1)}) -y π(i-1) }. By the inductive hypothesis, v i-1 (S) = v(S ∪ T i ) -v(T i ) and v i-1 (S ∪ {π(i -1)}) -y π(i-1) = v(S ∪ {π(i -1)} ∪ T i ) + v(A i ∪ T i ) -v(T i ) -v(A i-1 ∪ T i ). By supermodularity, v(S ∪ {π(i -1)} ∪ T i ) + v(A i ∪ T i ) v(S ∪ T i ) + v(A i-1 ∪ T i )
hence we get v i (S) = v i-1 (S), so that the proof is finished in this case.

2.

d i-1 = -1: Then T i = T i-1 ∪ {π(i -1)} so that S ∪ {π(i -1)} ∪ T i-1 = S ∪ T i for all S ∈ O(A i , ).
Hence, proceeding as in Case 1, we find that

y π(i-1) = v i-1 ({π(i -1)}) = v(T i ) -v(T i-1 ) and v i (A i ) = v i-1 (A i-1 ) -y π(i-1) = v(A i ∪ T i ) -v(T i ). Now, let S ∈ O(A i , ) \ {A i , ∅}. As π(i -1) is minimal in (A i-1 , ), S ∪ {π(i -1)} ∈ O(A i-1 , ) so that v i (S) = max{v i-1 (S), v i-1 (S ∪ {π(i -1)}) -y π(i-1) } = max{v(S ∪ T i-1 ) -v(T i-1 ), v(S ∪ T i ) -v(T i )} = v(S ∪ T i ) -v(T i ),
where the second equation follows from the inductive hypothesis and the last equation follows from supermodularity.

The foregoing theorem shows that all the reduced games (

A π i , , v A π i ,y π,d,v B π i-1
) of a supermodular game (N, , v) are themselves supermodular, hence balanced. It follows by Theorem 3 that y = y π,d,v = x π,d,v if (N, , v) is supermodular. Therefore, by Theorem 1, there must be a total order π ′ which is a linear extension of O(N, , v) such that y coincides with the associated marginal vector, i.e., y = m π ′ ,v . We now define such an order π ′ that we call induced order (of the consistent pair (π, d)), denoted π d . The order π d first orders the players π(i) with d i = -1 according to the order π and afterwards orders the players π(j) with d j = 1 according to the reverse order of π.1 Hence B π d k is the set of the k first players π(i) with d i = -1 if there are at least k players of this type, and otherwise B π d k consists of all players i with d i = -1 and the last players π(j) with d j = 1 that are needed to get k players in total. Therefore, B π d 0 , . . . , B π d n is a maximal chain in O(N, ) and Theorem 4 implies the following result (see Figure 2 for an illustration of the above definitions).

Corollary 1. Let (N, , v) be supermodular, let (π, d) be a consistent pair, and let π d be the total order induced by (π, d). Then π d is a linear extension of O(N, , v) and Proof. By Theorem 4,

m π d ,v = y π,d,v = x π,d,v = x π d ,(-1,...,-1),v .
y π,d,v π(i) = v(T π,d i ∪ {π(i)}) -v(T π,d i ) , if d i = -1, v(A π i ∪ T π,d i ) -v(A π i+1 ∪ T π,d i ) , if d i = 1. ( 11
)
A careful inspection of the definition of π d and of (11

) shows that m π d ,v = y π,d,v .
Hence, for supermodular games, already those consistent pairs (π, d) that satisfy di = -1 for all i = 1, . . . , n define all the marginal vectors.

The case of connected hierarchies

By Lemma 3.2 of [START_REF] Grabisch | The bounded core for games with precedence constraints[END_REF], any game that has a connected hierarchy is balanced. Hence, part (c) of Lemma 1 (i) is vacuously satisfied whenever also (N \ {i}, ) is connected so that we obtain for any connected poset (N, ) with |N| = n 2: (i) If i is minimal in (N, ) and (N \ {i}, ) is connected, then

min{x i : x ∈ C(N, , v)} = v({i}) (12)
(ii) If i is maximal in (N, ) and (N \ {i}, ) is connected, then

max{x i : x ∈ C(N, , v)} = v(N) -v(N \ {i}). ( 13
)
This motivates the following definition. An order π on a connected hierarchy (N, ) is simple if for every i = 2, . . . , n -1, (A π i , ) is connected (Note that a simple order may not be admissible: take, e.g., (N, ) given by 1

≺• 2 ≺• 3, 1 ≺• 4 ≺• 3; then 2143 is simple but not admissible).
Thus, if (π, d) is consistent and (A π i , ) remains connected for all i = 1, . . . , n, the coordinates of x := x π,d,v are given by

x π(i) = v ′ ({π(i)}) , if d i = -1, v ′ (A π i ) -v ′ (A π i+1 ) , if d i = 1, ( 14
)
where

v ′ = v A π i ,x B π i-1
. Therefore, we have x π,d,v = y π,d,v . We have shown:

Theorem 5. Let (N, , v) be a game with (N, ) a connected hierarchy. Then for any consistent pair (π, d) where π is a simple order, the induced vector y π,d,v is the min-max vertex x π,d,v .

It is well known from graph theory that for any connected graph, there exists a node such that its removal does not disconnect the graph (see, e.g., (Diestel, 2005, Prop. 1.4.1)). It follows that for every (N, ), a simple order always exists. This result can be used to show the following lemma.

Lemma 2. Any poset (N, ) has a total order that is simple and admissible.

Proof. We may assume that (N, ) is connected and that |N| = n 2. It suffices to show that there exists i ∈ N such that (a) i is minimal or maximal and (b) (N \ {i}, ) is connected. We proceed by induction on n. If n = 2, then each element of N has the desired properties. If our statement is true for n < t for some t 3, and if, now, n = t, then select any vertex ℓ ∈ N such that with S = N \ {ℓ}, (S, ) is connected. (As mentioned, such a vertex always exists.) We may assume that ℓ is neither maximal nor minimal. By the inductive hypothesis there exists a minimal or maximal element k of (S, ) such that (S \ {k}, ) is connected. If k ≺ ℓ, then k is minimal in (N, ), and if ℓ ≺ k, then k must be maximal in (N, ). If neither k ≺ ℓ nor ℓ ≺ k, then k remains maximal or minimal in (N, ). Hence, k is maximal or minimal in (N, ) in any case so that we may conclude that k has the desired properties.

The general case

We consider here that (N, ) is not necessarily connected, nor that the game under consideration is supermodular.

Let (N, , v) be a game with precedence constraints (not necessarily balanced). Let R (N, ) = R be the partition of N into connected components, and consider the intermediate game (R, v R ) as defined in Section 2. For y ∈ X(R, v R ) denote

C y (N, , v) = {x ∈ X(N, , v) : x(S) v(S) ∀S ∈ F 0 , x(R) = y R ∀R ∈ R},
where F 0 is the set of downsets that are not unions of connected components. We say that C y (N, , v) is the core of (N, , v) w.r.t. y. Remark 2. Let (R, v R ) be the intermediate game of the game (N, , v) with precedence constraints and y ∈ X(R, v R ).

(i) If (N, ) is connected, then C y (N, , v) = C(N, , v).
(ii) By Proposition 2.4 of [START_REF] Grabisch | Characterizations of solutions for games with precedence constraints[END_REF], C y (N, , v) = ∅.

(iii) Define the auxiliary game (N, , v y ) with precedence constraints by

v y (S) = y(T ) , if S = T for some T ⊆ R, v(S) , if S ∈ F 0 . Then C(N, , v y ) = C y (N, , v). Indeed, if x ∈ C(N, , v y ), then x(N) = v y (R) = v(N) and x(R) y R for all R ∈ R so that x(R) = y R and, hence, x ∈ C y (N, , v).
Moreover, it is straightforward to verify the other inclusion.

We now generalize (14) to allow computing x π,d,v y under certain additional assumptions by first proving a statement that follows from (i) of Lemma 1 for the auxiliary game. To this end we say that x S ∈ R S is y-core extendable if it is core extendable w.r.t. (N, , v y ).

Lemma 3. Let (N, , v) be a game with precedence constraints and with intermediate game

(R, v R ), y ∈ X(R, v R ), and i ∈ R ∈ R with |R| 2 such that (R \ {i}, ) is connected. Then x i ∈ R {i} is y-core extendable if and only if (i) x i max S⊆R\{R} v({i} ∪ S)-y(S) =: a N, ,v i,y if i is a minimal element of (R, ) and (ii) x i min S⊆R\{R} y(S ∪ {R}) -v((R \ {i}) ∪ S) =: a N, ,v i,y
if i is a maximal element of (R, ).

Proof. Let x i be y-core extendable. Then there exists

x ∈ C y (N, , v). Let S ⊆ R \ {R}. Then, if i is minimal in (R, ), x i + y(S) = x ({i} ∪ S) v ({i} ∪ S) so that (i) must be satisfied. Now, if i is maximal, y(S ∪ {R}) -x i = x ((R \ {i}) ∪ S) v ((R \ {i}) ∪ S) which implies (ii).
To show the if-part let x i satisfy (i) and (ii).

As (R \ {i}, ) is connected, R ′ := R N \{i}, = (R \ {R}) ∪ {R \ {i}}. Let y ′ ∈ R R ′ be given by y ′ S = y S , if S ∈ R \ {R}, y R -x i , if S = R \ {i}. Let v 1 = (v y ) N \{i},x i and v 2 = v N \{i},x i y ′
. In view of parts (ii) and (iii) of Remark 2 and of part (i) of Lemma 1 it suffices to prove that v 1 (T ) = v 2 (T ) for all T ∈ F ′ = O(N \{i}, ). As v 1 (∅) = 0 = v 2 (∅), we may assume that T = ∅. If T is not a union of connected components of (N \ {i}, ), then T ∪ {i} is not a union of connected components of (N, ) because |R| = 1. Hence, v 1 (T ) = v 2 (T ) in this case. Hence, we assume that

T = S ′ for some S ′ ⊆ R ′ . If T ∪ {i} / ∈ F , then v 1 (T ) = y(S ′ ) = y ′ (S ′ ) = v 2 (T )
. Hence, we may assume that T ∪ {i} ∈ F . If R \ {i} / ∈ S ′ , then T ∪ {i} is not a union of elements of R so that i is a minimal element. Therefore, v(T ∪ {i})x i y(S ′ ) by (i) so that v 1 (T ) = y(S ′ ) = y ′ (S ′ ) = v 2 (T ) in this case. Therefore we consider the case R \ {i} ∈ S ′ now. If T / ∈ F , then v 1 (T ) = y ′ (S ′ ) = v 2 (T ) by definition of the reduced game. If T ∈ F , then i is maximal. By (ii), , v). Indeed, take any x ∈ C(N, , v). For any S ∈ F 0 , x(S) v(S) by definition, and if S = T for some

v 1 (T ) = y((S ′ \ {R \ {i}}) ∪ {R}) -x i = y(S ′ \ {R \ {i}}) + y ′ R\{i} = y ′ (S ′ ) = v 2 (T ). Theorem 6. If y is a vertex of C(R, v R ) then every min-max vertex of C y (N, , v) is a vertex of C(N, , v). Proof. Observe first that if y ∈ C(R, v R ), then C y (N, , v) ⊆ C(N,
T ⊆ R, x( T ) = R∈T y R v R (T ) = v( T ). Suppose in addition that y is a vertex of C(R, v R ), and consider a min-max vertex x of C y (N, , v). Moreover, let x ′ , x ′′ ∈ C(N, , v) such that x = x ′ +x ′′ 2 . For any R ∈ R, y R = x(R) = x ′ (R) + x ′′ (R) 2 . Putting x ′ (R) = y ′ R and x ′′ (R) = y ′′ R , we get y R = y ′ R +y ′′ R 2
. This being valid for any R ∈ R, it follows that x ′ , x ′′ ∈ C(N, , v) implies that y ′ , y ′′ ∈ C(R, v R ) so that y = y ′ = y ′′ by the extremality of y.

Hence x ′ (R) = x ′′ (R) = x(R) for every R ∈ R so that x ′ , x ′′ ∈ C(N, , v y ). As x is a vertex of C(N, , v y ), Theorem 2 implies x = x ′ = x ′′ .
Combining Lemma 3 and Theorem 6, we can now give an explicit expression of x π,d,v . Specifically, for a consistent pair (π, d) with π being simple2 and admissible, the min-max vertex is given by, assuming π(i) ∈ R ∈ R, d,v π(j) for all R ∈ R, and y is a vertex of C(R, v R ).

x π,d,v π(i) =    max S⊆R\{R} v A π i ,x π,d,v {π(1),...,π(i-1)} {π(i)} ∪ S -y ′ (S) , if d i = -1 min S⊆R\{R} y ′ (S ∪ {R}) -v A π i ,x π,d,v {π(1),...,π(i-1)} (A π i+1 ∩ R) ∪ S , if d i = 1, ( 15
) for i = 1, . . . , n, where y ′ R = y R -i-1 j=1 1 R (π(j))x π,

Equivalent consistent pairs of permutations and decisions

We begin by a simple observation. If (π, d) is a consistent pair w.r.t. (N, ) and d ′ differs from d only inasmuch as d ′ n = -d n , then (π, d ′ ) is also consistent, and x π,d,v = x π,d ′ ,v for any game (N, , v). Indeed, π(n) is the unique player of A π n so that π(n) is both maximal and minimal in (A π n , ). Moreover,

x π,d,v N \{π(n)} = x π,d ′ ,v N \{π(n)} by definition so that x π,d,v π(n) = x π,d ′ ,v π(n)
by Pareto optimality of the core. For this reason, we call this operation an irrelevant switch.

We say that two consistent pairs (π, d) and (π ′ , d ′ ) are equivalent if, for any balanced game (N, , v), the corresponding min-max vertices coincide, i.e., x π,d,v = x π ′ ,d ′ ,v . We show in this section that equivalent consistent pairs necessarily arise from irrelevant switches and a sequence of "neighbor" pairs. Let (π, d) and (π ′ , d ′ ) be consistent pairs w.r.t. (N, ). We say that (π, d) and (π ′ , d ′ ) are neighbors if there exists k ∈ {1, . . . , n -1} such that

π,d,v = x π ′ ,d ′ ,v . Proof. Let k ∈ {1, . . . , n -1} such that π(i) = π ′ (i) for i = k, k + 1. We may assume that d k = 1 (i.e., d ′ k+1 = -d ′ k = -d k+1 = 1). Denote x = x π,d,v and x ′ = x π ′ ,d ′ ,v . Then x B π k-1 = x ′ B π ′ k-1 because B π k-1 = B π ′ k-1 . Let j = π(k) and ℓ = π(k + 1
). Then by using ( 9)

x j = max{y j : y ∈ C(N, , v), y B π k-1 = x B π k-1 }, x ℓ = min{y ℓ : y ∈ C(N, v), y B π k-1 = x B π k-1 , y j = x j }, x ′ j = max{y j : y ∈ C(N, v), y B π k-1 = x B π k-1 , y ℓ = x ′ ℓ }, and x ′ ℓ = min{y ℓ : y ∈ C(N, , v), y B π k-1 = x B π k-1 }. C(A π k , , v ′ ), x(P ), x(A π k+2 \ P ) 2 -x ℓ . We conclude that 2 = x(N) -x(B π k ) = x(A π k+1 ) = x ℓ + x(P ) + x(A π k+2 \ P ) 4 -x ℓ , i.e., x ℓ 2. Therefore x ℓ = 2. As x π(k) = max{y π(k) : y A π k ∈ C(A π k , , v ′ )}, x π(k+1) = min{y π(k+1) : y A π k ∈ C(A π k , , v ′ ), y π(k) = x π(k) }, x ′ π(k+1) = min{y π(k+1) : y A π k ∈ C(A π k , , v ′ )}, and x ′ π(k) = max{y π(k) : y A π k ∈ C(A π k , , v ′ ), y π(k+1) = x ′ π(k+1) }, we conclude that x π(k) x ′ π(k) and x π(k+1) x ′ π(k+1) . Moreover, x π(k) = x ′ π(k) if and only if x π(k+1) = x ′ π(k+1) . Therefore, it suffices to find y A π k ∈ C(A π k , , v ′ ) such that y ℓ < 2. Put y ℓ = 1, y j = 2, y i = 1 |P | for i ∈ P , y i = 1 |Q| for i ∈ Q, and y i = 0 for i ∈ A π k+2 \ (P ∪ Q) and observe that y A π k ∈ C(A π k , , v ′ ).
Theorem 7. Let (N, ) be a poset and (π, d) and (π ′ , d ′ ) be consistent pairs. Then the following statements are equivalent:

(i) The pairs (π, d) and (π ′ , d ′ ) are equivalent.

(ii) There is a sequence (π 1 , d 1 ), . . . , (π t , d t ) of consistent pairs such that (π 1 , d 1 ) = (π, d), (π t , d t ) = (π ′ , d ′ ), and for any ℓ ∈ {1, . . . , t-1}, either (π ℓ , d ℓ ) and (π ℓ+1 , d ℓ+1 ) are neighbors or they only differ by an irrelevant switch.

Proof. One direction follows from Proposition 3. For the other direction assume, on the contrary, that (π, d) and (π ′ , d ′ ) are not equivalent, but that x π,d,v = x π ′ ,d ′ ,v for any balanced game (N, , v). Let |N| = n be minimal under this condition. Then (π(1), d 1 ) = (π ′ (1), d ′ 1 ) because otherwise consider the pairs (π, d) and (π ′ , d′ ) defined by π(i) = π(i + 1), π′ (i) = π ′ (i + 1), di = d i+1 , and d′ i = d ′ i+1 for all i ∈ {1, . . . , n -1} on (N \ {π(1)}, ) and observe that these pairs are not equivalent but induce the same vertices of the core for any balanced game (N \ {π(1)}, , v) contradicting the minimality assumption on n.

By Corollary 1, π d = π ′d ′ . We conclude that π(1) = π ′ (1) and

d 1 = d ′ 1 , (18)
say d ′ 1 = 1 = -d 1 .
We also assume that d n = 1. Let j = π ′ (1) and k = min{i ∈ {2, . . . , n} : d) and we may replace (π, d) by (π ′′ , d ′′ ). Proceeding recursively, we decrease k in each step until we finally obtain that (A π k+2 , ) is disconnected. Indeed, if we reach k = 1 and A π k+2 were still connected, then (π ′′ , d ′′ ) is equivalent to (π, d) and satisfies π ′′ (1) = π ′ (1) which is impossible by (18). By Lemma 4 there exists a balanced (N, , v) d,v j and the desired contradiction has been obtained.

d i = 1} -1. Again, as π d = π ′d ′ , π(k + 1) = j. Let ℓ = π(k). If (A π k+2 , ) is connected, then (π ′′ , d ′′ ) is equivalent to (π,
∈ G such that x π ′′ ,d ′′ ,v j > x π,d,v j . Now, x π ′′ ,d ′′ ,v j = max{y j : y ∈ C(N, , v), y B π ′′ k-1 = x π ′′ ,d ′′ ,v B π ′′ k-1 } and x π ′ ,d ′ ,v j = max{y j : y ∈ C(N, , v)} so that x π ′ ,d ′ ,v j x π ′′ ,d ′′ ,v j > x π,
In view of Theorem 7, for any arbitrary balanced game we may not ignore any equivalence class of consistent pairs in order to compute all min-max vertices of the core. However, there might be more equivalence classes than possible vertices according to Proposition 2. E.g., in the traditional case, i.e., if = ∅ and |N| = n 3, then there are precisely 2 n-3 n! equivalence classes of consistent pairs. Indeed, if (π, d) and (π ′ , d ′ ) are neighbors, then the k where π and π ′ differ first must satisfy that (A π k+2 , ) is connected, hence k n -2. Therefore, for any equivalent consistent pairs (π, d) and (π ′ , d ′ ), we have (π(i), d i ) = (π ′ (i), d ′ i ) for all i = 1, . . . , n -3. Moreover, it is straightforward to check that for any consistent pair (π, d) there exists an equivalent consistent pair (π

′ , d ′ ) such that d ′ n-2 = d ′ n-1 = d ′ n = -1.
Hence, the 2 n-3 n! pairs (π, d), where π is an order and d is a decision vector such that d n-2 = d n-1 = d n = -1, are representatives of all pairwise distinct equivalence classes in the traditional case.

The following example shows that consistent pairs which are not equivalent may or may not induce different min-max vertices.

Example 1. We consider n = 4 and the hierarchy shown below. The consistent pairs (π, d) and (π ′ , d ′ ) given by π = 1234, d = (-1, -1, -1, -1) and π ′ = 4321, d ′ = (1, 1, 1, 1) are in different equivalence classes. However, the induced orders π d = 1234 and π ′d ′ = 1234 are the same. Hence, if the game is strictly supermodular, they induce the same vertex, namely m 1234,v . Otherwise, the induced min-max vertices may be different: take, e.g., the game (N, , v) defined by v(12) = 1 and v(S) = 0 otherwise. Then it can be checked that

x π,d,v = (0, 1, 0, -1), x π ′ ,d ′ ,v = (1, 0, -1, 0).

♦

Remark 3. It is easy to check that for every connected hierarchy with n = 3, each equivalence class of consistent pairs contains some simple admissible order. This shows that for computing all min-max vertices for balanced 3-person games with connected hierarchies we can restrict to simple admissible orders. However, for n > 3, this property fails to be true in general. Consider, e.g., the "N" example (Figure 1). Then {(3214, (-1, 1, 1, 1)), (3214, (-1, 1, 1, -1)), (3241, (-1, 1, -1, 1)), (3241, (-1, 1, -1, -1))} is an equivalence class which does not contain any simple order.

Examples and summary of the results

We begin by illustrating the computation of the min-max vertices when the hierarchy is connected.

Example 2. We consider n = 4 and the connected hierarchy (N, ) given in Figure 1 (the "N" example).

Let us consider a strictly supermodular game (N, , v). Every order is admissible and the simple orders are 1234, 1243, 1423, 1432, 4321, 4312, 4123 and 4132. The linear extensions (which yield all extreme points of the core) are 1324, 1342, 3124, 3142, and 3412. Taking order 1234 and using strict supermodularity, we compute the min-max vertex x = x π,v (the decision vector d is irrelevant here), which by Theorem 5, is equal to y π,v (note that by Pareto optimality, it is not necessary to compute the last coordinate). Omitting braces and commas for denoting sets, we find:

x 1 = v(1) x 2 = v 234,x (234) -v 234,x (34) = v(N) -v(1) -max(v(34), v(134) -v(1)) = v(N) -v(134) x 3 = v 34,x (3) = max(v(3), v(13) -x 1 , v(123) -x 1 -x 2 ) = max(v(3), v(13) -v(1), v(123) -v(N) + v(134) -v(1)) = v(13) -v(1).
This yields x = m 1342,v , the marginal vector associated with the order 1342. Similarly, we find:

x 1243,v = x 1234,v = m 1342,v x 1423,v = x 1432,v = x 4123,v = x 4132,v = m 1324,v x 4321,v = x 4312,v = m 3124,v .

♦

The example illustrates Corollary 1 and Proposition 3 as well. Indeed, for π = 1234 we have d = (-1, 1, -1, 1) and the induced order π d is 1342. Moreover, all orders 1423, 1432, 4123 and 4132 are neighbors.

We now illustrate Theorem 3, showing that nonsimple admissible orders may produce min-max vertices as well.

Example 3 (Example 2 ctd). With the "N" hierarchy let us take the game defined by

v(1) = 0, v(3) = -2, v(13) = v(34) = v(123) = 2, v(134) = 4, v(N) = 5.
which is neither super-nor submodular. The vertices of the core are (0, 0, 2, 3), (0, 1, 2, 2), (2, 1, 0, 2) and (3, 0, -1, 3). It can be checked that they can be recovered by the following orders (respectively): 1423, 1234, 2431 and 4321, among which the last but one is not simple.

In addition, note that the marginal vectors are: (0, 1, 2, 2), (0, 0, 2, 3), (4, 1, -2, 2, ), (4, 0, -2, 3) and (2, 1, -2, 4). Only the two first ones are vertices and two of the vertices are not marginal vectors.

We have three equivalence classes of simple admissible orders, whose lexicographically minimal members are 1234, 1423, and 4312. ♦ 7 Limits of the min-max approach

The following example shows that there exists a game v that possesses a vertex x of its core with the following property: for any i ∈ N, there exist core elements y, z with y i < x i < z i . It shows that it is not possible in general to find all vertices of the core by taking arbitrary orders and maximizing or minimizing within the core the payoff of the first player, then of the second, etc.

Example 5. Let N = {1, . . . , 5}, S = {{1, 2, 3}, {2, 3}, {2, 4}, {3, 4}, N}, and let (N, ) be a poset that such that S ⊆ O(N, ), e.g., the classical case = ∅ or the connected poset given below. Let (N, , v) be a game that satisfies v(S) = 0 for all S ∈ S ∪ {∅} and v(T ) ≤ -3 for all T ∈ O(N, ) \ (S ∪ {∅}). Moreover, let x = (0, 0, 0, 0, 0). Then x(S) = v(S) for all S ∈ S so that x is a vertex of the core. Moreover,

z 1 = (1, -1, 1, 1, -2) z 2 = (0, 1, -1, 1, -1) z 3 = (-2, 1, 1, -1, 1)
are core elements which satisfy

z 3 1 < x 1 < z 1 1 z 1 2 < x 2 < z 2 2 z 2 3 < x 3 < z 1 3 z 3 4 < x 4 < z 1 4 z 1 5 < x 5 < z 3 5 ,
so that the desired property is satisfied. ♦

The following result shows that no such situation arises with less than 5 players.

Lemma 5. Let (N, v) be a balanced game on 2 N . For n 4, no vertex x of the core has the above property, i.e., α i < x i < β i with α i , β i core extendable.

Proof. The result can be easily checked geometrically for n = 2 and n = 3. Let us prove it for n = 4. Assume x is a core vertex satisfying the above property. Then x must satisfy v({i}) < x i < v(N)v(N \ {i}) ∀i ∈ N, which implies that x is determined by x(N) = v(N) and x(S) = v(S) for at least 3 subsets of N among 12, 13, 14, 23, 24, 34. Let us select 12, 23 and 34. Then by x(N) = v(N), we find x 1 = v(N)-x 2 -x 3 -x 4 . Injecting in x(12) = v(12), we find -x 3 -x 4 = v(12)-v(N), which is not linearly independent with x(34) = v(34). Therefore, this selection does not define a vertex. Up to permutations, it can be checked that the remaining possibilities are of the type 12,13,23,and 12,23,24. Consider type 12,13,23. Observe that this yields

x 1 + x 2 + x 3 = 1 2 v(12) + v(13) + v(23) ,
and therefore x 4 = v(N) -1 2 v(12) + v(13) + v(23) . Then no core element z can be s.t. z 4 > x 4 , for, in this case we would have z 1 + z 2 + z 3 < 1 2 v(12) + v(13) + v( 23) , invalidating one of the inequalities z( 12) v( 12), z(13) v(13) or z( 23) v( 23).

Lastly, consider type 12, 23, 24. Let us solve the system x(12) = v(12), x(23) = v(23), x(24) = v(24), x(N) = v(N). We obtain:

x 1 = 1 2 v(N) + v(12) -v(23) -v(24)
x 2 = 1 2 v(N) + v(12) + v(23) + v( 24)

x 3 = 1 2 v(N) -v(12) + v(23) -v(24) x 4 = 1 2 v(N) -v(12) -v(23) + v(24) .
Let us show that no core element z satisfies z 2 < x 2 , which suffices to invalidate the above property. Assume, on the contrary, that z is a core element satisfying z 2 = x 2ε for some ε > 0. By x(12) = v(12) z(12) we deduce z 1 x 1 + ε. Similarly, we have x(23) = v(23) z(23) and x(24) = v(24) z(24), implying z 3 x 3 + ε and z 4 x 4 + ε, respectively. We conclude that z(N) >= x(N) + 2ε > v(N), which is a contradiction.

From Lemma 5 and Example 5, we immediately deduce the following result.

Theorem 8. For any balanced game (N, , v), every vertex of the core is a min-max vertex if and only if n 4.

Proof. The "only if" part comes from Example 5. As for the "if" part, observe that Lemma 5 remains valid for any hierarchy (N, ), because the only difference is that some of the subsets 12, 13, 14, 23, 24, 34 may be unfeasible, thus limiting the choice of 3 subsets to satisfy equality. Now, take any vertex x of the core of a balanced game (N, , v). For n 4, we know by Lemma 5 that at least one of the coordinates is equal to the minimum or maximum over the core, say x 1 . Then, since x N \{1} is a vertex of the core of the reduced game v N \{1},x 1 , it follows that it has also a coordinate which is the minimum or maximum over the core. Finally, x is a min-max vertex.

Figure 1 :

 1 Figure 1: Example of a hierarchy with 4 players, referred to as the "N" example

Figure 2 :

 2 Figure 2: A hierarchy with 5 players. Consider π = 13524 and d = (-1, -1, 1, 1, -1). Then π d = 13452, and the maximal chain B π d 0 , . . . , B π d n is ∅, 1, 13, 134, 1345, N.

  (i) π(i) = π ′ (i) and d i = d ′ i for all i ∈ {1, . . . , n} \ {k, k + 1}, (ii) π(k) = π ′ (k + 1) and d k = d ′ k+1 = -d k+1 = -d ′ k , and (iii) (A π k+2 ,) is connected (where A π n+1 = ∅ and ∅ is assumed to be connected). Proposition 3. Let (N, , v) ∈ Γ be balanced and (π, d) and (π ′ , d ′ ) be consistent w.r.t. (N, ). If (π, d) and (π ′ , d ′ ) are neighbors, then x

Formally, π d is defined as follows. Let α(d) = |{i ∈ {1, . . . , n} : d i = -1}| and i ∈ {1, . . . , n}. For i α(d) there exists a unique j 1 ∈ {1, . . . , n} such that d j1 = -1 and |{j ∈ {1, . . . , j 1 } : d j = -1}| = i. Define π d (i) = π(j 1 ). If i > α(d), then there exists a unique j

∈ {1, . . . , n} such that d j2 = 1 and |{j ∈ {j 2 , . . . , n} : d j = 1}| = iα(d). In this case put π d (i) = j 2 .

In the sense that no connected component gets disconnected.

Therefore, x j x ′ j and x ℓ x ′ ℓ . Moreover,

x j = max{y j : y ∈ C(N, , v), y B π k-1 = x B π k-1 , y ℓ = x ℓ } and x ′ ℓ = min{y ℓ : y ∈ C(N, , v), y B π k-1 = x B π k-1 , y j = x ′ j } so that x j = x ′ j if and only if

), then x ′ j x j , i.e., x ′ j = x j so that it suffices to show that (x j , x ′ ℓ ) is core extendable. To this end we assume that k < n -1 because otherwise x j = x ′ j and

, and

. In view of Lemma 1 (i) and (iii) with S = {ℓ} and T = {j}, and since we know that x ′ ℓ is core extendable w.r.t. w, it suffices to show that (a

Since x j is core extendable w.r.t. u, by Lemma 1,

Hence, by ( 16) and ( 17),

as well so that (b) has been verified. We now show that (iii) in the definition of neighbors is crucial for Proposition 3.

Lemma 4. Let (π, d) and (π ′ , d ′ ) be consistent pairs w.r.t. the poset (N, ) that satisfy (i) and (ii) of the definition of neighbors for some k ∈ {1, . . . , n -1} such that (A π k+2 , ) is not connected. If

Proof. Note that k n -2, and denote j = π(k) and ℓ = π(k + 1). Choose two distinct connected components P and Q of (A π k+2 , ) and define, for any S ∈ O(N, ),

. We claim that x j = 3 and

Lastly, we illustrate the general case, using (15). We will see that in general not all vertices can be recovered. We define the following game:

which is neither super-nor submodular. The vertices of (N, , v) are found to be (0, 0, 2, 5), (2, 0, 0, 5), (2, 5, 0, 0), (0, 6, 2, -1) and (1, 6, 1, -1). The intermediate game is convex, therefore the vertices of its core are the marginal vectors (0, 7), (7, 0).

We immediately observe that the vertices (2, 0, 0, 5) and (0, 6, 2, -1) cannot be found by our procedure since thay do not satisfy x(R) = y R for R ∈ R. It can be checked that the three other vertices (0, 0, 2, 5), (2, 5, 0, 0) and (1, 6, 1, -1) can be recovered by the orders 1234 with y = (0, 7), 1234 with y = (7, 0), and 4321 with y = (7, 0), respectively. We detail the second one, omitting superscripts.

We computed x 2 in two different ways since 2 is both minimal and maximal in (234, ). Note that anyhow x 2 = y 12 -x 1 = 6, so that the above calculation is in fact not necessary. For 3 and 4, since 34 is connected we are back to the expression in (10). ♦

We summarize the situation:

(i) If (N, ) is connected, using simple admissible orders produce min-max vertices of the core using (10). Unless n 3, not all min-max vertices can be found in general (see Remark 3), other min-max vertices may be obtained by taking admissible nonsimple orders and (10) (see Theorem 3).

(ii) The general case for (N, ) is addressed by Lemma 3 and Theorem 6. Min-max vertices are computed via (15). Again, in general, not all of them can be found by this formula.

(iii) The general case needs the knowledge of the vertices of the core of the intermediate game v R , which is a classical game on the Boolean lattice 2 R . Observe that for classical games, only Theorems 2 and 3 can be used. Theorem 1 guarantees that we get all vertices for supermodular games.

(iv) Theorem 7 shows that it is enough to compute the min-max vertices for one member of each equivalence class of consistent pairs.

Related literature

The basic idea of min-max vertices as well as the form of the induced vector (10) have their roots in the past literature, although limited to the classical case F = 2 N . Perhaps the first occurrence of the idea of systematically taking the minimum or maximum over single coordinates of core elements goes back to the paper of [START_REF] Derks | On the number of extreme points of the core of a transferable utility game[END_REF], while the induced vector y π,d,v (10) in the particular case where π(i) is always considered as a maximal element is due to [START_REF] Núñez | On extreme points of the core and reduced games[END_REF]. In the latter reference, it is proved that if the game (N, v) is almost convex, i.e., it satisfies the supermodularity inequality for all S, T such that S ∪ T = N, then all vertices of the core are induced vectors y π,d,v with d = (1, 1, . . . , 1). In [START_REF] Núñez | Characterization of the extreme core allocations of the assignment game[END_REF], it is shown that the class of assignment games, although in general not almost convex, satisfies also the property that all vertices of the core are induced vectors. Later, [START_REF] Izquierdo | A simple procedure to obtain the extreme core allocations of an assignment market[END_REF] give a very simple way of computing these vertices for assignment games, just by using the assignment matrix. Another class of games was proved to satisfy the same property, namely, minimal cost spanning tree problems [START_REF] Ch | On the set of extreme core allocations for minimal cost spanning tree problem[END_REF].

It seems that the min-max allocation x π,d,v under the form (9), limited to the case F = 2 N and d = (1, 1, . . . , 1), has been first proposed by [START_REF] Tijs | The first steps with Alexia, the average lexicographic value[END_REF] -see also later publications of [START_REF] Funaki | Leximals, the lexicore and the average lexicographic value[END_REF]; [START_REF] Tijs | An average lexicographic value for cooperative games[END_REF]-, under the name of leximal (later called lexinal ), in order to define the Alexia value, and it was already remarked that these vectors are indeed vertices of the core (the convex hull of all such vectors is called the lexicore, and the barycenter of it is precisely the Alexia value). Based on the work of Tijs et al., a systematic study of lexicographic allocations is done in [START_REF] Núñez | Lexicographic allocations and extreme core payoffs: the case of assignment games[END_REF]. There, the so-called lemacols and lemicols are our min-max vertices with d = (1, . . . , 1) and d = (-1, . . . , -1), respectively. Also, the lemiral is introduced, which corresponds to the lemacol taken over the unbounded core (without the constraint x(N) = v(N)). It is proved there that a marginal vector is in the core if and only if it equals the corresponding lemiral, and a lemiral is in the core if and only if it equals the corresponding lemicol.

To the best of our knowledge, there is no publication on the vertices of the core considering games on distributive lattices (except, of course, the supermodular case), nor on min-max vertices considering an arbitrary combination of minimum and maximum over coordinates using a decision vector d.

Acknowledgment

The first author thanks the Agence Nationale de la Recherche for financial support under contract ANR-13-BSHS1-0010 (DynaMITE). The second author was supported by the Spanish Ministerio de Economa y Competitividad under project ECO2015-66803-P and by the Danish Council for Independent Research/Social Sciences under the FINQ project (Grant ID: DFF-1327-00097).