Games on concept lattices: Shapley value and core

Games on concept lattices: Shapley value and core Ulrich FAIGLE1, Michel GRABISCH2⋆, Andres JIM´ ENEZ-LOSADA3, and Manuel ORD ´ O˜ NEZ3 1Mathematisches Institut, Universit¨at zu K¨oln, Weyertal 80, 50931 K¨oln, Germany. [email protected] 2Paris School of Economics, University of Paris I, 106-112, Bd. de l’Hˆopital, 75013 Paris, France. [email protected] 3University of Seville, Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n, 41092 Sevilla, Spain. {ajlosada,mordonez}@us.es Abstract. We introduce cooperative TU-games on concept lattices, where a concept is a pair (S, S′) with Sbeing a subset of players or objects, and S′a subset of attributes. Any such game induces a game on the set of players/objects, which appears to be a TU-game whose collection of feasible coalitions is a lattice closed under intersection, and a game on the set of attributes. We propose a Shapley value for each type of game, axiomatize it, and investigate the geometrical properties of the core (nonemptiness, boundedness, pointedness, extremal rays). Keywords: cooperative game, restricted cooperation, concept lattice, core, Shapley value 1 Introduction Cooperative games with transferable utility (TU-games) have been widely studied and used in many domains of applications. Nbeing a set of players, or more generally, a set of abstract objects, a TU-game v: 2N→ ∅ assigns to every coalition or group S⊆Na number representing its “worth” (monetary value: benefit created by the cooperation of the members of S, or cost saved by the common usage of a service by the members of S, power, importance, etc.). Once the function vis determined, the main concern of cooperative game theory is to provide a rational scheme for distributing the total worth v(N) of the cooperation among the members of N(or determining individual power/importance degrees, if v(N) is not interpreted as a monetary value). The until now most popular methods to achieve this are the Shapley value [19] and the core [14]. The Shapley value yields a single distribution vector, satisfying a set of four natural axioms (Pareto optimality, symmetry, linearity, null player property), while the core is a set of distribution vectors that are Pareto optimal and satisfy coalitional rationality (i.e., a coalition receives at least equal its own worth). While the Shapley value always exists for any game, the core is a convex polyhedron, but may be empty. In many situations, however, not all subsets of Ncan be realized as coalitions or are feasible, which means that the mapping vis defined on a subcollection Fof 2Nonly. ⋆Corresponding author. Tel (33) 14407-8285, Fax (33) 14407-8301. The corresponding author thanks the Agence Nationale de la Recherche for financial support under contract ANR-13-BSHS1-0010. Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 Such games are said to have restricted cooperation [9]. Fhas been studied under many structural assumptions, such as distributive lattices (closed under union and intersection) [12], convex geometries [3, 4], antimatroids [2], union-stable systems [1] (a.k.a. weakly union-closed systems [11, 10]), etc. In this case, the study of the geometric properties of the core is challenging since the core may become unbounded or have no vertices (see a survey in [15]). Also the Shapley value has to be redefined, and its axiomatization may become difficult. In most of the cases, the structural assumptions on Fare not clearly motivated or are too restrictive. The aim of this paper is to study a structure for Fwhich is both very general (a lattice of sets closed under intersection), and produced in a natural way, through a set of attributes possessed by the players or objects in N. In short, our framework is based on concept lattices [5, 6, 16], a notion which has lead to the now quite active field of formal concept analysis [13]. Mbeing a set of attributes, a concept is a pair (S, S′) with S⊆Nand S′⊆Msuch that S′is the set of those attributes that are satisfied by all members of S. A remarkable result is that any (finite) lattice is isomorphic to a concept lattice, and that the lattice of extents (i.e., the lattice of concepts (S, S′) limited to the first arguments S) is a set lattice closed under intersection, and moreover any such lattice arises that way. We define a game von the lattice of concepts, dividing it into a game vNon the lattice of extents (which corresponds to a game with restricted cooperation (v, F) where Fis a lattice closed under intersection), and a game vMon the lattice of intents (which corresponds to a game on the set of attributes). For both types of games, we propose a Shapley value with its axiomatization. Moreover, we investigate in details the properties of the core. Our results can be seen to generalize many results of the literature on games with restricted cooperation. The paper is organized as follows. Section 2 introduces the main notions needed in the paper: cooperative games, concept lattices and games on concept lattices. Section 3 proposes a definition for the Shapley value, which is a natural generalization of those values presented by Faigle and Kern [12], and Bilbao and Edelman [4], together with its axiomatization. Section 4 studies the properties of the core: nonemptiness, boundedness, pointedness, and extremal rays. Some interesting properties of balanced collections are also presented. 2 Framework 2.1 Cooperative games Let N={1,...,n}be a finite set of players. A cooperative (TU) game (or game for short) on Nis a mapping v: 2N→Rsuch that v(∅) = 0. Any subset S⊆Nis called acoalition. The quantity v(S) represents the “worth” of the coalition, that is, depending on the application context, the benefit realized (or cost saved, etc.) by cooperation of the members of S. We consider the general case where the cooperation is restricted, i.e., where the set Fof all feasible coalitions might be a proper subset of 2N. We denote the corresponding game with restricted cooperation as a pair (F, v), or simply vif there is no ambiguity. Let us consider a cooperative game (F, v) with N∈ F. A payoff vector is a vector x∈Rn. For any S⊆N, we denote by x(S) = Pi∈Sxithe total payoff given by xto 2 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 the coalition S. The payoff xis efficient if x(N) = v(N). The core of a cooperative game is the set of efficient payoff vectors such that no coalition can achieve a better payoff by itself: core(F, v) = {x∈Rn|x(S)≥v(S)∀S∈ F,and x(N) = v(N)}. Note that core(F, v) is a convex closed bounded polyhedron when F= 2N. In other cases, the core may be unbounded or non pointed, and its study becomes difficult (see [9] and a survey in [15]). We recall from the theory of polyhedra that a polyhedron defined by a set of inequalities Ax ≥bis the Minkowski sum of its convex part and its conic part (the so-called recession cone), the latter being determined by the inequalities Ax ≥0, and being therefore independent of the righthand side b. So the recession cone of core(F, v) is the polyhedron core(F,0), which does not depend on v. A collection B ⊆ F of nonempty sets is said to be balanced if there exist positive weights λS, S ∈ B such that X S∈B,S∋i λS= 1 ∀i∈N. A game (F, v) is said to be balanced if v(N)≥PS∈B λSv(S) holds for every balanced collection Bwith weight system (λS)S∈B. It is well-known that the core of vis nonempty if and only if vis balanced [9]. 2.2 Concept lattices We begin by recalling that a lattice is a partially ordered set (poset) (L, ) such that for any two elements x, y ∈L, a supremum x∨yand an infimum x∧yexists. If no ambiguity occurs, the lattice is simply denoted by L. The dual partial order ∂is defined by x∂y if and only if yx. The dual of the lattice (L, ) is the poset (L, ∂), denoted by L∂if no ambiguity occurs. Acontext (see, e.g., [5, 6, 13, 16]) is a triple C= (N, M, I), where Nis a finite nonempty set of objects, Mis a finite set of attributes, and I:N×M→ {0,1}is a binary relation defined by I(i, a) = 1 if object i∈Nsatisfies attribute a∈M, and 0 otherwise. The binary relation can be represented as a matrix or table called the incidence matrix (table). Let C= (N, M, I) be a context. The intent of a subset of objects S⊆Nis defined as the set of attributes satisfied by all objects in S: S′ C={a∈M|I(i, a) = 1,∀i∈S}. Dually, the extent of any set of attributes A⊆Mis defined as the set of objects satisfying all attributes in A: A′ C={i∈N|I(i, a) = 1,∀a∈A}. To avoid a heavy notation, we write simply S′, A′for the intent of Sand the extent of A, when the meaning is clear. A basic property of the extents and intents is the relation (S′)′⊇S, (A′)′⊇A∀S⊆N, A ⊆M. (1) Aconcept in Cis a pair (S, A) with S⊆Nand A⊆Msuch that S=A′and A=S′. Equivalently, a concept is a maximal rectangle of “1” in the incidence matrix, or it is (N, ∅) if N′=∅, or (∅, M) if M′=∅. 3 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 We denote by LCthe set of all concepts in C, and endow it with a partial order ≤ defined by (S, A)≤(T, B) if S⊆T (equivalently, if B⊇A). Then (LC,≤) is a lattice, called the concept lattice, with supremum and infimum given by (S, A)∧(T, B) = ((S∩T),(S∩T)′) (S, A)∨(T, B) = ((A∩B)′,(A∩B)). The top and bottom elements of this lattice are (N, N′) and (M′, M) respectively. It is important to note that any finite lattice is isomorphic to a concept lattice. Given a context Cand its concept lattice LC, the lattice of extents (LN C,⊆) is defined by the set LN C={S⊆N|(S, S′)∈LC}. Similarly, we define the lattice of intents (LM C,⊆) as the set LM C={A⊆M|(A′, A)∈LC}. Clearly, the lattices LC, LN C,(LM C)∂are isomorphic. Example 1. Consider N={1,2,3,4},M={a, b, c}, and the incidence table given in Figure 1. The lattices LC,LN Cand LM Care shown on the right of the table. For ease of notation, sets like {2,4}and {b, c}are denoted by 24 and bc. a b c 1× × 2× × 3× 4×(∅, abc) (13, a) (24, c) (12, b) (1, ab) (2, bc) (1234,∅) ∅ 13 24 12 1 2 1234 abc a c b ab bc ∅ Fig. 1. From left to right: The incidence table of a context, its concept lattice, the lattices of extents, and the lattice of intents 2.3 Games on concept lattices We consider a context C= (N, M, I), the lattice of concepts LC, the lattice of extents LN Cand the lattice of intents LM C. We assume that no attribute is superfluous, i.e., the top element of LCis (N, ∅) (no attribute is satisfied by all objects), however, the bottom element (M′, M) may be with M′6=∅(there are objects satisfying all attributes). To each concept (A, A′)∈LC, we assign a number v(A, A′)∈R(its meaning could be benefit, cost, evaluation, certainty degree of occurrence, etc.). We call the pair (C, v) acooperative game on concepts or concept game for short, and impose the restriction v(∅, M) = 0 whenever (∅, M)∈LC. We denote by CCG the set of all concept games. 4 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 We derive from vtwo mappings vN:LN C→Rand vM:LM C→Rdefined by vN(S) = v(S, S′)−v(M′, M) (S∈LN C) vM(A) = v(N, ∅)−v(A′, A) (A∈LM C). Note that vN(M′) = 0 and vM(∅) = 0 holds, i.e., these set functions vanish at the bottom of their respective lattices, and could thus be considered as cooperative games. Also, if vis monotone nondecreasing, then so are vNand vM(because A⊆Bimplies A′⊇B′) (and similarly for monotone nonincreasing). We call vNand vMthe game on extents and the game on intents, respectively. Example 2. An immediate application of the above framework in cooperative game theory is: Nis the set of players, and Mis the set of attributes of players. Attributes can be thought of as any kind of property, or simply, as membership cards of any association, club, party, etc., that the players may possess. Now a coalition is feasible iff it corresponds to the extent of a concept. Indeed, if S⊆Nis not an extent in LN C, then it is not stable in the sense that the players of Shave common attributes S′, but other players also satisfy these attributes in S′, so they have an incentive to join S. Example 3. Games on concepts can model the interplay between sellers and markets. Consider N={1,2,3,4,5,6}where agent 1 has the patent of a product in a market, and the remaining agents are sellers who want to sell the product in this market. The market is divided into three submarkets M={α, β, γ}, but there are restrictions on which agent can sell in which market: only sellers 4, 5, 6 can sell in market α, only 2, 4, 6 can sell in β, and only 3 and 5 can sell in γ. In addition, we suppose that agent 1 is not a seller. We define a context C= (N, M, I) to represent this situation with the relation Idefined by I(i, a) = 1 if icannot sell in submarket a. Figure 2 gives the incidence table and concept lattice1of C. Let us define a concept game as follows. We make the assumption that α β γ 1× × × 2× × 3× × 4× 5× 6×(1, αβγ) (1246, γ) (135, β)(123, α) (12, αγ) (13, αβ) (123456,∅) Fig. 2. The incidence table of C(left) and its concept lattice (right) 1) Profits obtained by a coalition of sellers depend on the submarkets where they can develop their activity, but 2) Sellers cannot ban others from these submarkets if they are the relation Imakes them eligible. By a pair (S, A)∈N×M, we represent a situation where Sis a set of agents and Ais a set of submarkets where they cannot sell. However, 1Note that this lattice is isomorphic to the one of Example 1, although the incidence tables are completely different. 5 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 not every pair (S, A) is admissible. Indeed, the agents in Scannot sell in the submarkets of S′, thus A⊇S′. Moreover, a seller has no interest to be in a situation which reduces his sale domain, thus A⊆S′, and therefore A=S′. By (1), this yields A′= (S′)′⊇S. Now, 2) implies that A′=S, so finally (S, A) must be a context. We may take for vthe following values (omitting braces and commas): v(1, M) = 6, v(13, αβ) = 16. v(12, αγ) = 20 v(123, α) = 32, v(135, β) = 28, v(1246, γ) = 30, v(N, ∅) = 60. The value v(1, M) represents the fixed payoff obtained by the patent owner if the product is sold. 2.4 Set lattices and concept lattices We investigate in this section the relation between concept lattices and set lattices on N, i.e., sublattices of (2N,⊆) (see, e.g., [16]). We begin by recalling some useful notions about finite lattices and posets. For x, y in a poset (P, ), we say that xis covered by y, or ycovers x, denoted by x≺· y, if xy, and xzyimplies x=zor z=y. For xy in (P, ), a maximal chain from xto yis a sequence of elements x=x0, x1,...,xp=y such that x0≺· x1≺· · · · ≺· xp. Its length is p. The height of a lattice is the length of a longest maximal chain. Given a poset (P, ), x∈Pis a join-irreducible element if it covers exactly one element. Dually, xis a meet-irreducible element if it is covered by exactly one element. We denote respectively by J(P, ) and M(P, ) the sets of join-irreducible and meetirreducible elements. A subset Q⊆Pof a poset is a downset if x∈Qand y∈Psuch that yximply y∈Q. The set of all downsets of (P, ) is denoted by O(P, ). A lattice is distributive if ∨,∧obey the algebraic distributivity law. A fundamental result due to Birkhoff says that a finite lattice (L, ) is isomorphic to (O(J(L),),⊆) if and only if the lattice is distributive. This means that a distributive lattice can be reconstructed from its join-irreducible elements. The same statement with meet-irreducible elements holds as well, because Lis distributive if and only if (J(L),) is isomorphic to (M(L),). An application in game theory of the result of Birkhoff is the following: consider a set Nof players endowed with a partial order . Then the set of downsets O(N, ) forms a collection F ⊆ 2Ncontaining Nand ∅, which is a distributive (set) lattice when ordered by inclusion, with supremum and infimum being union and intersection. Conversely, any collection F ⊆ 2Nof height ncontaining N, ∅and closed under union and intersection arises that way (see Faigle and Kern [12]). Aclosure system on Nis a collection Fof subsets of Nwhich is closed under intersection and contains N, while a dual closure system is a collection closed under union and containing the empty set. Endowing a closure system (or a dual closure system) with inclusion order ⊆, we obtain a poset with remarkable properties: (i) Any lattice is isomorphic to a closure system, and to a dual closure system; (ii) The lattice of extents of a context is a closure system, while the collection of complement sets of the lattice of intents, i.e., {A∈2M|Ac∈LM C}, is a dual closure system. As a consequence, the lattices of extents and of intents are closed under intersection; 6 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 (iii) Conversely, any closure system Fon Nis the lattice of extents of some context. Specifically, the simplest context is C= (N, M, I), with Mthe set of meet-irreducible elements of F, and I(i, j) = 1 iff i∈j, with i∈Nand j∈M. Example 4. Take N={1,2,3,4,5,6,7}and the closure system represented on Figure 3 (left). Its meet-irreducible elements are (in red): 12357, 1237, 2467, 17, which we denote a, b, c, d, respectively. The corresponding table is given in the middle, and the context lattice on the right of the figure. 7 17 (d)27 1237 (b) 2467 (c) 12357 (a) 1234567 a b c d 1× × × 2××× 3× × 4× 5× 6× 7×××× (7, abcd) (17, abd) (27, abc) (1237, ab) (2467, c) (12357, a) (1234567,∅) Fig. 3. From left to right: a closure system (meet-irreducible elements in red), the corresponding table and context lattice We observe on the example that lines 4 and 6 are duplicate, line 7 is full, and line 3 is the intersection of lines 1 and 2. On the closure system, this corresponds respectively to the fact that 4 and 6 are always together in a concept, 7 is always present, and 3 is present whenever 1 and 2 are present. These situations are captured under the notion of macro-player and companion player (assuming Nis the set of players). Definition 1. Let Fbe a closure system on N. A subset K⊆N,|K|>1, is a macroplayer in Fif either K⊆Sor K∩S=∅for every nonempty S∈ F (equivalently, no S∈ F “separates” K, i.e., S∩K6=∅and K\S6=∅). Definition 2. Let Fbe a closure system on N. A player i∈Nis a companion player of S,S⊆N\i, if S∪i∈ F, and for all T∈ F, T∋iif and only if S⊆T. It is clear from the definition that macro-players arise as identical lines in the table, while a companion iof Scorresponds to the situation where line iis the intersection of the lines in S. The following properties are noteworthy: (i) If K, K′are maximal (w.r.t. inclusion) macro-players, then K∩K′=∅. (ii) If M′(bottom of F) is nonempty, then M′is a macro-player when |M′|>1, and a companion player when |M′|= 1 (companion of ∅). (iii) When M′=∅, atoms which are not singletons are macro-players, but the converse is false. More precisely, a macro-player Kis an atom if and only if K∈ F. (iv) If iis a companion of {j}, then {i, j}is a macro-player. (v) If iand jare companion of the same S, then {i, j}is a macro-player. 7 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 Consider a closure system Fon Nwith |N|=n, and consider J(F) the set of its join-irreducible elements. The following is important to note. (i) Suppose |J (F)|< n. Then there exist either companion players or macro-players. Indeed, each join-irreducible element corresponds to a line in the incidence table, and each additional line must not create a new maximal rectangle with new attributes. We have n=|J (L)|+ p X i=1 |Ki| − p+c where K1,...,Kpare the maximal macro-players and cis the number of companion players which do not belong to some macro-player (see Ex. 4). (ii) Suppose |J (F)|=n. In this case, Fis an irreducible closure system since there is no redundant line in the incidence table. Moreover, F ⊆ O(J(F)) where “missing” sets (i.e., those not in O(J(F))) are necessarily unions of sets in F, since taking the closure under union of Fwould give O(J(F)). Example 5 (Example 4 continued). Let us make the closure system of Example 4 irredundant by suppressing the superfluous elements 3, 6 and 7, so as to have n=|J (F)|= 4. This gives the closure system represented on Figure 4 (solid lines), to which we give a slightly different shape, in order to make it apparent as a sublattice of O(J(F)) (additional links in red dotted lines). The two missing sets are 15 and 124 (in red). ∅ 1 2 12 24 125 1245 15 124 a b c d 1× × × 2××× 4× 5× Fig. 4. Irredundant version of Figure 3 Let Lbe any lattice, with N={1,2,...}the set of its join-irreducible elements, and M={a,b,c,...}the set of its meet-irreducible elements. The irreducible closure system associated to Lis the set lattice C(L) on Ndefined by C(L) = {J(x)|x∈L},with J(x) = {i∈N|i≤x}. Its bottom element is ∅. The irreducible dual closure system associated to Lis the set lattice O(L) on Mdefined by O(L) = {M(x)|x∈L},with M(x) = {j∈M|j6≥ x}. Its top element is M. The irreducible concept lattice associated to Lis given by the context C= (N, M, I) with I(i, j) = 1 iff i≤j. Then LN C=C(L) and LM C={A⊆M|Ac∈O(L)}. 8 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 Example 6. Take the lattice on Figure 5 (left), its join-irreducible elements are in red, the meet-irreducible elements are in blue. The irreducible closure and dual closure systems (ordered by ⊆) are depicted in the middle and on the right of the figure. By comparing with Example 1, one can see the above identity. 3a4 c b 1 2 ∅ 13 2412 1 2 1234 ∅ bc ab ac c a abc Fig. 5. From left to right: a lattice (in red: join-irreducible elements, in blue: meet-irreducible elements), and the corresponding irreducible closure and dual closure systems 3 The Shapley value Given a game (C, v) on a context, we define the extent Shapley value and the intent Shapley value as the Shapley value for the games on extents and on intents respectively. We begin with the extent Shapley value. 3.1 The extent Shapley value We consider the lattice of extents LN Cof a context Cand the game vNdefined on it. Consider the set CH(C) of all maximal chains from the bottom M′to the top Nin LN C(equivalently, in LC), and denote its cardinality by ch(C). Consider a given maximal chain C∈CH(C), letting C=M′=S0⊂S1· · · ⊂ Sk=N, and a player i. Denote by Ti Cand Si Crespectively, the last set in the sequence which does not contain i, and the first set containing i. The extent Shapley value of (C, v), denoted by Φex(C, v), is defined to be the Shapley value Φ(vN) of the game on extents, given by Φex(C, v) = Φi(vN) =        1 ch(C)X C∈CH(C) 1 |Si C\Ti C|vN(Si C)−vN(Ti C),if i6∈ M′ vN(M′) |M′|,otherwise. (2) This definition is a natural generalization of the values introduced by Faigle and Kern [12], and Bilbao and Edelman [4]. We formulate properties to axiomatize the extent Shapley value. Let Fbe any value over the set of concept games. 9 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 We obtain core(vN) =                x1≥10 x2≥20 x1+x2≥40 x1+x3≥50 x2+x4≥40 x1+x2+x3+x4= 100 ,core∗(vM) =                yc≥10 ya≥20 yb+yc≥50 ya+yc≥40 ya+yb≥40 ya+yb+yc= 100 which are not empty since x= (20,20,30,30) ∈core(vN) and y= (30,30,40) ∈ core∗(vM). An important consequence of the above facts, we find that the study of the extent and intent cores amounts to the study of the core of games on closure systems (closed under intersection) and on dual closure systems (closed under union). In what follows we study in depth the structure of the extent core, especially its conic part. Results on the intent core will be obtained by duality. In the whole section, Fdenotes any collection of sets. 4.1 Nonemptiness We ask when the cores are nonempty. As said in Section 2.1, the core of a game on a subcollection Fof 2Nis nonempty if and only if the game is balanced in the usual sense. Hence, core(vN) is nonempty if and only if vNis balanced, and core∗(vM) is nonempty if and only if vMis balanced. The case M′6=∅deserves some attention, because then core(vN) is never empty. Indeed, it is not difficult to see that the only balanced collection in LN Cis {N}, whence any game on the lattice of extents is balanced. There is no such conclusion for core∗(vM) because N′=∅. There seems to be no clear relation between the nonemptiness of the extent and intent cores. One could be empty while the other is not, or both could be empty or nonempty. The following example illustrates this. Example 10 (Example 9 continued). Let us take the concept lattice of Examples 9 and 1, but without specific values for v. The minimal balanced collections for LN Care {1234} and {13,24}, while those for LM Care {abc},{bc, ac, ab},{c, ab}and {bc, a}. Hence, by Bondareva-Shapley theorem, the extent core is nonempty if and only v(13) + v(24) ≤v(1234) while the intent core is nonempty if and only if 1 2v(13) + 1 2v(12) + 1 2v(24) ≤v(1234) v(1) + v(24) ≤v(1234) v(2) + v(13) ≤v(1234). The nonemptiness of one the core does not imply the nonemptiness of the other one, unless some conditions on vare satisfied. For example, the nonemptiness of the intent core implies the nonemptiness of the extent core if v(12) ≤v(1234), or if v(1)+v(2) ≤v(1234). 16 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 4.2 Pointedness and boundedness of the extent core We assume that core(vN) is nonempty. The aim of this section is to study the question whether the core is unbounded and whether it contains a line, in which case it is not pointed (i.e., it has no vertices). The general condition to be pointed is that the system of linear equations x(S) = 0,∀S∈ F has 0 as its unique solution (in which case we say that, following Derks and Reijnierse [8], Fis nondegenerate). It is easy to see that Fis degenerate if there exists a macro-player Kin F, because Fcontains the hyperplane x(K) = 0. A remarkable result with closure systems is that the converse is also true. Theorem 4. A closure system is nondegenerate if and only if it contains no macroplayer. Proof. The “only if” part is obvious since the presence of a macro-player implies degeneracy. Suppose that Fis a closure system on Nwith bottom element M′, which has no macro-player. We prove by induction on n=|N|that it is nondegenerate. The assertion is easily checked for n= 1, with the two possible closure systems {∅,{1}} and {{1}}. Suppose the assertion holds till some value n−1 and let us prove it for n. Claim: there exists i∈Nsuch that {i} ∈ F. Proof of the claim: Since Fhas no macro-player, we know that its bottom M′ is either ∅or some singleton. In the latter case, the claim is proved. Suppose then that M′=∅. Then necessarily, every atom is a singleton. Indeed, suppose per contra that S is an atom, with |S|>1. Since Sis not a macro-player, there exists T∈ F separating S, i.e., j∈T6∋ kfor some j, k ∈S. Since Fis closed under intersection, it follows that S∩T∈ F and ∅ 6=S∩T(S, a contradiction with the fact that Sis an atom.  Consider then F−i={S⊆N\i|Sor S∪i∈ F} on N\i, the collection of sets obtained from Fby removing iin every set. Note that ∅ ∈ F−i. We prove that F−iis a closure system without macro-players. -F−i∋N\i: clear since N∈ F. -F−iis closed under intersection: take S, S′∈ F−i. Then three cases arise. If S, S′∈ F, then S∩S′∈ F and i6∈ S∩S′, hence S∩S′∈ F−i. If S∈ F and S′∪i∈ F, then i6∈ S∩(S′∪i)∈ F, and therefore S∩(S′∪i) = S∩S′∈ F−i. Lastly, if S∪i, S′∪i∈ F, then i∈(S∪i)∩(S′∪i)∈ F, therefore ((S∪i)∩(S′∪i)) \i=S∩S′∈ F−i. -F−ihas no macro-player: suppose K⊆N\iis a macro-player in F−i. Take S∈ F−i. Then either S∩K=∅or S⊇K. If S∈ F, then S∩K=∅or S⊇Kremains true. If S∪i∈ F, then (S∪i)∩K=∅or S∪i⊇Kis true because K6∋ i. Hence Kis a macro-player in F, a contradiction. Then F−iis a closure system without macro-player on N\i, and by the induction hypothesis, F−iis nondegenerate, i.e., the system of equations x(S)=0, S ∈ F−ihas a unique solution x= 0. Finally, observe that the system x(S) = 0, S ∈ F differs from the previous one only by the adjunction of xiin some lines. Since {i} ∈ F, the line xi= 0 makes the two systems equivalent. Therefore, Fis nondegenerate. ⊓⊔ 17 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 The next example shows that this result does not extend to arbitrary collections of sets. Example 11. Take n= 5 and the collection Fshown below. ∅ 12 123 12345 24 Fis not closed under intersection but has no macro-player. However it is degenerate (rank is 4 and (1,−1,0,1,−1) is a vector of the null space). This being established, we turn to the question whether the core is unbounded or not. The following result is useful [8]. Theorem 5. The recession cone of a game on a collection of sets Fis a linear subspace if and only if F \ {∅, N}is a balanced collection. Corollary 1. The core is bounded (equiv., the recession cone reduces to {0}) if and only if Fis nondegenerate and F \ {∅, N}is balanced. The situation is summarized by the following table. M′=∅ |M′|= 1 |M′|>1 pointed if Fhas no macro-player if Fhas no macro-player no bounded if Fbalanced and no macro-player no no Table 1. Boundedness and pointedness of the extent core 4.3 Some results on balanced collections For any collection B ⊆ 2N\ {∅}, its closure by intersection denoted by Bis formed by all sets of B, plus the intersection of any family of sets of B, provided the intersection is nonempty2. Note that (·) is a closure operator, in the sense that B=B,B ⊆ B, and B ⊆ B′implies B ⊆ B′. Theorem 6. Suppose Bis a balanced collection on N. Then B, its closure by intersection, is balanced. 2Be careful that this does not mean that Bis closed under intersection, since Bdoes not contain the empty set, despite that it may contain disjoint sets. 18 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 Proof. We prove the result by induction on |N|. The result is trivially true when |N|= 1. Suppose that the property holds for all Nof size at most n, and let us prove it for |N|=n+ 1. Suppose that there exists a macro-player K, and let [k] be a (new) player replacing K. Then by considering N′= (N\K)∪ {[k]}, we can define a balanced collection from Bon N′, and since |N′|< n, the result is proved by the induction hypothesis. We can therefore consider in the rest of the proof that no macro-player exists. This implies in particular that |B| >1 and that there is no set S∈ B,|S|>1 which is disjoint from every other set. Suppose first that B ∋ Ssuch that S∩T=∅for all T∈ B,T6=S, with |S|= 1. Then observe that B \ {S}is a balanced collection over N\S. By induction hypothesis, B \ {S}is balanced, and since B=B \ {S} ∪ {S}, the result is proved in this case. Suppose on the contrary that for every S∈ B,Sintersects some T∈ B. We claim that the collection B∩={S∩T|S, T ∈ B, S 6=T}is balanced. Since the union of balanced collections is balanced (see, e.g., Owen [17]), it follows that B ∪ B∩is balanced over N. Applying the same procedure over B ∪B∩yields another balanced collection, and continuing like this eventually leads to B, proving that it is balanced. Proof of the claim: Take (λS)S∈B any system of balancing weights for B. For each i∈N, consider the subcollection Bi={S1,...Sk}of Bof sets containing i. Observe that Bi6=∅since Bis balanced, and k > 1. Indeed, k= 1 yields λS1= 1. By assumption, there exists T∈ B intersecting S1, therefore there exists j6=i,j∈T∩S1, and PT′∋jλT′= 1 forces λT= 0, which is impossible. For each Biwe construct the collection of pairwise intersections Bi ∩={Sj∩Sℓ| Sj, Sℓ∈ Bi, Sj6=Sℓ}, with the following weights: λi S=X Sj,Sℓ∈Bi Sj6=Sℓ Sj∩Sℓ=S λSj+λSℓ k−1,for every S∈ Bi ∩. By construction, each λi Sis positive, and we have X S∈Bi ∩ λi S=1 k−1 k X j=1 k X ℓ=j+1 (λSj+λSℓ) = k X j=1 λSj= 1. Clearly, B∩=Si∈NBi ∩, however some sets may be present in two different Bi ∩, possibly with different weights. The last step consists in defining a unique weight for each S∈ B∩, while keeping the normalization condition. Observe that if Sappears in, say, Bi ∩and Bj ∩, then S⊇ {i, j}. Since there is no macro-player, {i} ∈ Bi ∩, and {j} ∈ Bj ∩. Define λ′ S= min(λi S, λj S), and assuming that λi S< λj S, define λ′ {j}=λj {j}+ (λj S−λi S). Observe that λ′ S>0, λ′ {j}>0. Putting for the other sets λ′ T=λi Tfor some i, the system of weights (λ′ S)S∈B∩satisfies PT∋iλ′ T= 1 for all i∈N.⊓⊔ 19 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 Lemma 1. Suppose Bis a balanced collection on N. Then Bcontains all singletons in Nif and only if Bhas no macro-player3. Proof. ⇒) Clear. ⇐) Suppose Bhas no macro-player and for some i∈N,{i} 6∈ B. Then TB∈B,B∋iB= S∋i, with |S|>1. Since Sis not a macro-player, there must exist T∈ B such that T6∋ iand T∩S6=∅. Take j∈T∩S, and consider a balancing system (λB)B∈B for B. Then 1 = X B∈B,B∋i λB<X B∈B,B∋i λB+λT≤X B∈B,B∋j λB= 1, a contradiction. ⊓⊔ Note that ⇒) holds also if Bis not balanced. An immediate consequence is: Corollary 2. If Bis a balanced collection on N, then Bcontains all macro-players in B and all singletons in Nnot contained in macro-players. Proof. If there is no macro-player, just apply Lemma 1. Otherwise, replace each macroplayer by a single player and apply Lemma 1. ⊓⊔ Remark 1. (i) If Bis minimal balanced and contains no macro-player, then B 6=B. This is clear from Lemma 1 and from the fact that a minimal balanced collection has at most nsets. (ii) One may wonder if a dual version of Theorem 6 exists, i.e.: if Bis balanced and B=B, then its opening B◦(i.e., removing all sets being intersection of others) is balanced. This is not true as shown by the following example: take N={1,2,3,4}and the balanced collection B={12,23,2,134,14,34}(λS=1 3can be taken for any S∈ B). Its closure is B={12,23,2,134,14,34,1,3,14,4} and is balanced by Theorem 6. Now its opening is (B)◦={12,23,134,14,34}, but this is not a balanced collection, as it can be checked. (iii) Observe that in general B1∪ B2⊆ B1∪ B2with possibly strict inclusion (e.g., take B1={1,23}and B2={12,3}). It is not sure whether one can obtain any closed balanced collection as a union of the closure of minimal balanced collections. We come to our final result. Theorem 7. Assume M′=∅. Then the core of any balanced game is bounded if and only if Fhas no macro-player and F \ {∅, N}arises as the closure under intersection of the union of some minimal balanced collections on N, i.e., F \ {∅, N}=SBi. Proof. ⇐) Since the union of balanced collections is balanced, by Theorem 6, F \ {∅, N} is balanced. Since no macro-player exists, by Lemma 1, Fcontains all singletons, and is therefore nondegenerate. Hence core(0) = {0}by Corollary 1. ⇒) core(0) = {0}iff Fis non-degenerate and F \{∅, N}is balanced. Since Fis closed under intersection, it follows that F \ {∅, N}is the closure of some balanced collection B, with F \ {∅, N} ⊇ B ⊇ (F \ {∅, N})◦. Since Bis the union of some minimal balanced collections, F \{∅, N}has the required form. Finally, nondegeneracy implies that Fdoes not contain any macro-player. 3We mean: there is no macro-player in B. Note that Kcould be a macro-player in Bbut not in F. 20 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 The theorem as well as Remark 1 (iii) gives us a means to derive any set system Fclosed under intersection such that F \ {∅, N}is balanced. It suffices to generate all minimal balanced collections, except {N}(see Peleg [18] for the description of an algorithm doing this), and build all possible unions of them, then take their closure under intersection. This gives F \ {∅, N}. 4.4 Extremal rays of the extent core We recall the classical result which holds for the case F=O(N, ) (distributive lattice), where O(·) indicates the set of downsets of some poset. Lemma 2. ([7, 20]) If F=O(N, ), the extremal rays of core(0) are 1i−1j, for i≺· j in (N, ). Let F=LN Cbe a closure system on N, with bottom element M′. We deal for simplicity with the case where there is no macro-player nor companion player in F(irreducible closure system). In this case M′=∅and |J (F)|=n, therefore J(F) can be assimilated to N. We write (N, ) for the poset on Nisomorphic to (J(F),⊆). Theorem 8. Suppose that Fis an irreducible closure system. Then 1i−1jis a ray of core(F,0) for every i≺· jin the poset (N, ), not necessarily extremal. Moreover, core(F,0) = core(O(N, ),0) if and only if any S∈ O(N, )\ F can be written as a union of disjoint sets in F. Proof. 1. Let (N, ) be the poset of join-irreducible elements of F. Then O(N, ) is a distributive lattice and by Lemma 2, core(O(N, ),0) is generated by the rays 1i−1j, for i≺· jin the poset (N, ). Observe that Fis obtained from O(N, ) by removing some subsets, therefore core(F,0) ⊇core(O(N, ),0). Hence any extremal ray of the latter remains a ray in the former, although not necessarily extremal. 2. To prove the second assertion, equality of the recession cones amounts to show that the “missing” inequalities in core(F,0) are implied by the present ones. 2.1. If S∈ O(N)\ F can be written as a disjoint union of sets in F, say S1,...,Sk, then clearly x(S)≥0 is implied by x(S1)≥0,...,x(Sk)≥0. 2.2. Conversely, suppose that x(T)≥v(T) with T∈ O(N)\F is implied by the other inequalities. It means that there exist λS≥0, S∈ F \ {N}, and λN∈Rsuch that X S∈F,S6=N,T λS1S+λN1N= 1T.(3) 2.2.1. Suppose first that for all λS>0, we have S⊆T, and λN= 0. Then we have found a subcollection B={S∈ F :λS>0}in {S∈ F :S⊆T}=: F(T) which is a balanced collection over T. Since Fis closed under intersection, F(T) contains B. By Lemma 1 and Corollary 2, it follows that B(and hence F) contains all macro-players of Band all singletons in T. Therefore, we have found a decomposition of Tinto disjoint sets of F. 2.2.2. Suppose on the contrary that no set of coefficients λS,S∈ F satisfy (3) with the condition given in 2.2.1. (i.e., no balanced collection over Texists in F), but (3) can be satisfied provided λS>0 for some S6⊂ T. Then there exist j6∈ Tinduced by 21 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 the combination, i.e., PS∈F,S6=NλS1Shas a positive component for j. It follows that necessarily λN<0, and we may put w.l.o.g. λN=−1. In order to have (3) satisfied, we must have X S∈F,S6=N λS1S= 1N\T+ 2 ·1T. This means that we must find a collection Bin Fsuch that {S\T:S∈ B} is a balanced collection over N\T, and {S∩T:S∈ B} is a balanced collection over Twith the same coefficients, and we must find also a balanced collection B′⊆ F(T) over T. But the latter does not exist by assumption. ⊓⊔ The above condition is easily violated as shown in the next example. Example 12. Consider n= 5 and F ⊂ O(N, ) depicted on Figure 8 together with (N, ) (join-irreducible sets in red). Observe that F \O(N) = {1234}, and that it is not possible 1 2 3 4 5 ∅ 1 3 13 34 123 134 1235 12345 Fig. 8. A lattice (right) with the poset of its join-irreducible elements (left) to write 1234 as a union of the two atoms 1 and 3. Hence core(F,0) 6= core(O(N),0). This can be verified as r= (0,0,1,−1,0), which is extremal in core(O(N),0), is no more an extremal ray of core(F,0). We can see this in two ways. First, the set of equalities satisfied by ris x1= 0 x3+x4= 0 x1+x3+x4= 0 x1+x2+x3+x4+x5= 0 Observe that the 3d equality is implied by the two first, hence the system determines a 2-dim space, not a ray. Also, it can be checked in the same way that r1= (0,−1,1,−1,1) and r2= (0,1,0,0,−1) are extremal rays, and that r=r1+r2. 4.5 Properties of the intent core Similar results for the intent core can be obtained easily from the previous results by duality. 22 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 Pointedness and boundedness As explained above, and since core∗(vM) = core(vM), all reduces to the study of the system of linear equations y(S) = 0,∀S∈LM C. Since y(S) + y(M\S) = y(M) = 0 for any S∈LM C, the above system is equivalent to y(S) = 0,∀S∈LM C. Since LM Cis closed under intersection, all previous results apply directly. Since N′=∅, the situation is simpler than with the extent core, and we find: (i) The intent core is pointed if and only if LM Chas no macro-attribute (defined similarly as a macro-player); (ii) The intent core is bounded if LM Cis balanced and has no macro-attribute. Extremal rays We can proceed similarly. The recession cone of the intent core is given by the system y(S)≥0,∀S∈LM C(4) y(M) = 0. Since y(M) = 0, proceeding as above, the system is equivalent to y(S)≤0,∀S∈LM C(5) y(M) = 0. Again, since LM Cis a closure system, we can benefit from previous results. First, we have the following lemma, similar to Lemma 2. Lemma 3. Suppose that (LM C,⊆)is a distributive lattice, and denote by (M, )the poset of its join-irreducible elements. Then the extremal rays of core∗(vM)are 1b−1a, for any a≺· bin (M, ). Proof. Recall that the intent core is equal to core(LM C, vM), hence the recession cone of the intent core is simply core(LM C,0), given by (4). It is equivalent to the system (5), hence core(LM C,0) = −core(LM C,0). Since LM Cis a distributive lattice, it is generated by (M, ). It follows from Lemma 2 that extremal rays of core(LM C,0) are of the form 1a−1b, with a≺· b. Since core(LM C,0) = −core(LM C,0), the result follows. As a consequence, and since LM Cis a closure system, we obtain by application of Theorem 8 the main result of this section: Theorem 9. Suppose that LM Cis irreducible. Then 1b−1ais a ray of core∗(0) (recession cone of the intent core) for every a≺· bin the poset (M, ), not necessarily extremal. Moreover, core∗(0) = core(O(M, ∂),0) if and only if any S∈ O(M, ∂)\LM Ccan be written as the intersection of sets in LM Cwhose union covers M. Note that the poset (M, ∂) is isomorphic to the poset of meet-irreducible elements of the concept lattice LC. We formulate the same result in terms of the core of games on dual closure systems. 23 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70 Corollary 3. Let Fbe a dual closure system on M, and (M, )the poset of its joinirreducible elements. Then 1a−1bis a ray of core(F,0) for every a≺· bin (M, ), not necessarily extremal. Moreover, core(F,0) = core(O(M, ),0) if and only if any S∈ O(M, )\ F can be written as the intersection of sets in Fwhose union covers M. Acknowledgement This research was motivated by Prof. Mario Bilbao’s pioneering investigations of cooperative games on lattices. References 1. E. Algaba, J. M. Bilbao, P. Borm, and J. J. L´opez. The position value for union stable systems. Math. Meth. Oper. Res., 52:221–236, 2000. 2. E. Algaba, J. M. Bilbao, R. van den Brink, and A. Jim´enez-Losada. Cooperative games on antimatroids. Discrete Mathematics, 282:1–15, 2004. 3. J. M. Bilbao, E. Lebr´on, and N. Jim´enez. The core of games on convex geometries. European Journal of Operational Research, 119:365–372, 1999. 4. J.M. Bilbao and P.H. Edelman. The Shapley value on convex geometries. Discrete Applied Mathematics, 103:33–40, 2000. 5. N. Caspard, B. Leclerc, and B. Monjardet. Finite ordered sets — Concepts, results and uses. Number 144 in Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 2012. 6. B. A. Davey and H. A. Priestley. Introduction to Lattices and Orders. Cambridge University Press, 1990. 7. J. Derks and R. Gilles. Hierarchical organization structures and constraints on coalition formation. Int. J. of Game Theory, 24:147–163, 1995. 8. J.J.M. Derks and H. Reijnierse. On the core of a collection of coalitions. Int. J. of Game Theory, 27:451–459, 1998. 9. U. Faigle. Cores of games with restricted cooperation. ZOR – Methods and Models of Operations Research, 33:405–422, 1989. 10. U. Faigle and M. Grabisch. A discrete Choquet integral for ordered systems. Fuzzy Sets and Systems, 168:3–17, 2011. DOI 10.1016/j.fss.2010.10.003. 11. U. Faigle, M. Grabisch, and M. Heyne. Monge extensions of cooperation and communication structures. European Journal of Operational Research, 206:104–110, 2010. 10.1016/j.ejor.2010.01.043. 12. U. Faigle and W. Kern. The Shapley value for cooperative games under precedence constraints. Int. J. of Game Theory, 21:249–266, 1992. 13. B. Ganter and R. Wille. Formal Concept Analysis: Mathematical Foundations. Springer Verlag, 1999. 14. D. Gillies. Some theorems on n-person games. PhD thesis, Princeton, New Jersey, 1953. 15. M. Grabisch. The core of games on ordered structures and graphs. Annals of Operations Research, 204:33–64, 2013. doi: 10.1007/s10479-012-1265-4. 16. B. Monjardet. The presence of lattice theory in discrete problems of mathematical social sciences. Why. Math. Soc. Sci., 46:103–144, 2003. 17. G. Owen. Game Theory. Academic Press, 3d edition, 1995. 18. B. Peleg. An inductive method for constructing minimal balanced collections of finite sets. Naval Research Logistics Quarterly, 12, 1965. 19. L. S. Shapley. A value for n-person games. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games, Vol. II, number 28 in Annals of Mathematics Studies, pages 307–317. Princeton University Press, 1953. 20. N. Tomizawa. Theory of hyperspace (XVI)—on the structure of hedrons. Papers of the Technical Group on Circuits and Systems CAS82-172, Inst. of Electronics and Communications Engineers of Japan, 1983. In Japanese. 24 Documents de Travail du Centre d'Economie de la Sorbonne - 2014.70