Khaled Maafa

Lhouari Nourine

Mohammed Said

Algorithms for computing the Shapley value of cooperative games on lattices

Keywords:

whether they are published or not. The documents may come

Introduction

The Shapley value [START_REF] Shapley | A value for n-person games[END_REF] is one of the most popular solution concepts in the theory of cooperative games. It reflects the intuitive notion of fairness in the division of the output generated by a coalition of players. The Shapley value has been used in a wide range of applications such as clustering [START_REF] Garg | Novel biobjective clustering (bigc) based on cooperative game theory[END_REF], congestion games [START_REF] Kollias | Restoring pure equilibria to weighted congestion games[END_REF] and network centrality [START_REF] Michalak | Efficient computation of the shapley value for game-theoretic network centrality[END_REF]. Thus, the challenging task of computing the Shapley value has been one of the main concerns of researchers and practitioners in cooperative games. Most of the effort that has been prodigated to solve this issue deals with classical cooperative games i.e games where the set of feasible coalitions is the boolean lattice. In practice, however, not all the coalitions are feasible. For example, the feasible coalitions may be determined by linguistic or geographical factors. The solution concepts of classical cooperative games have to be redefined to take into account the restriction of the coalitional possibilities. Much effort has been done in this direction (see for example the survey in [START_REF] Grabisch | The core of games on ordered structures and graphs[END_REF] and the references therein). In the framework of restricted cooperation, the Shapley value was defined for cooperative games with precedence constraints by Faigle and Kern [START_REF] Faigle | The shapley value for cooperative games under precedence constraints[END_REF], and for cooperative games on convex geometries by Bilbao and Edelman [START_REF] Bilbao | The shapley value on convex geometries[END_REF]. Recently, Faigle et al [START_REF] Faigle | Games on concept lattices: Shapley value and core[END_REF] have extended the definition of the Shapley value to cooperative games on concept lattices and therefore for general lattices. The algorithmic aspects of solution concepts of games with restricted cooperation have not yet been sufficiently developed to permit their use in applications. The focus in this paper is on these algorithmic aspects. We address the issue of computing the Shapley value of a cooperative game on a lattice of sets closed under intersection, given by an implicational system Σ. From logic point of view, Σ is a Horn CNF, and the models of Σ are the characteristic vectors of the feasible coalitions [START_REF] Bertet | The multiple facets of the canonical direct unit implicational basis[END_REF][START_REF] Wild | The joy of implications, aka pure horn formulas: Mainly a survey[END_REF]. The classical situation, where all the subsets of N are feasible, occurs exactly when the implicational system is empty.

The complexity of computing the Shapley value of a game depends on how the input is given. Faigle and Kern [START_REF] Faigle | The shapley value for cooperative games under precedence constraints[END_REF] have shown that if the game is given by an oracle then the computation of the Shapley value is already exponential in the classical case. They have also shown that, for games with restricted cooperation, computing the Shapley value is #P -hard even for elementary games given explicitly. Their reduction is based on counting the number of linear extensions of a poset, or minimal interval extensions when considering the concept lattice.

The paper is structured as follows. In Section 2, we relate our work to previous contributions and introduce the model of cooperative games on implicational systems. In Section 3, we define the problem of computing the Shapley value, decompose it into two sub-problems and discuss its difficulty. In Section 4, we give two algorithms for computing the Shapley value of cooperative games on implicational systems and discuss their complexity. In Section 5, we study the case where the lattice of feasible coalitions is isomorphic to a product of chains. We then show that when the chains are all of the same fixed length, we can compute in polynomial time the Shapley value of weighted graph games.

Preliminaries and related work

An implicational system on a set N is a binary relation

Σ ⊆ 2 N × N . An implication (A, i) ∈ Σ is denoted by A → i. Definition 1. Let Σ = {A 1 → a 1 , ..., A m → a m }
be an implicational system on N and X ⊆ N . The Σ-closure of X, denoted X Σ , is the smallest set containing X and satisfying:

∀1 ≤ j ≤ m, A j ⊆ X Σ ⇒ a j ∈ X Σ .
The set F Σ = {X Σ , X ⊆ N } is a closure system (closed under intersection and containing N ). The elements of F Σ are referred to as Σ-closed sets. When ordered by inclusion, F Σ is a lattice denoted by L Σ = (F Σ , ⊆). We will assume that ∅ ∈ F Σ , that is, ∀i ∈ N, ∅ → i ∈ Σ. Notice that we can remove from Σ every implication A → i with i ∈ A, without changing the lattice of feasible coalitions. Therefore, we will consider only implications A → i with i ∈ A. Figure 1 shows the lattice L Σ corresponding to the implicational system Σ = {2 → 1, 4 → 3, 6 → 5} on N = {1, ..., 6}. We define a cooperative game on an implicational system as a game with restricted cooperation where the feasible coalitions are the closed sets of the given implicational system. More formally: Definition 2. A cooperative game on an implicational system is a triplet (N, Σ, v) where:

a) N is a finite set of players; b) Σ is an implicational system on N ; c) v is a mapping from F Σ to R such that: v(∅) = 0.
The mapping v assigns to every feasible coalition F ∈ F Σ its worth, that is, the gain that the members of F can achieve by themselves, regardless of how the players not in F will act.

The notion of a conjuctive permission structure, introduced by Gilles et al [START_REF] Gilles | Games with permission structures: The conjunctive approach[END_REF] to model situations where a player may need the permission of another player to participate in the cooperative effort, can be translated to our framework, by restricting Σ as follows: i → j ∈ Σ ⇔ i needs the permission of j to cooperate.

The autonomous coalitions in [START_REF] Gilles | Games with permission structures: The conjunctive approach[END_REF] will then be the Σ-closed sets in our framework. The idea of a conjunctive permission structure can even be generalized in our framework to include the case where a subset A of players needs the presence of a player i in order to put its cooperative possibilities into action. The player i acts then as a catalyst to the cooperation of the players in A. This is simply achieved by setting A → i ∈ Σ. Note however the difference between games with a permission structure as defined in [START_REF] Gilles | Games with permission structures: The conjunctive approach[END_REF] and our games on implicational systems which are games with restricted cooperation in the sense that only feasible coalitions can form. In [START_REF] Gilles | Games with permission structures: The conjunctive approach[END_REF] all coalitions can form but only their feasible part is able to generate worth. See [START_REF] Faigle | The shapley value for cooperative games under precedence constraints[END_REF] for more details on this point.

Many structural properties of the lattice L Σ can be deduced directly from the form of the implicational system Σ. For instance we have the following proposition

Proposition 1. If |A| = 1 for all (A → i) ∈ Σ, then L Σ is a distributive lattice. Proof: Assume that |A| = 1 for all (A → i) ∈ Σ, then Σ induces a permission structure S on N , defined by S(i) = {j ∈ N | (j → i) ∈ Σ}. L Σ is
then the collection of autonomous coalitions derived by the conjunctive approach from the permission structure S, and hence, is a distributive lattice. (See Definition 2.1 and Proposition 2.2 in [START_REF] Derks | Hierarchical organization structures and constraints on coalition formation[END_REF]).

Note that the converse statement is not valid as shown in the following example:

N = {1, 2, 3, 4, 5}, Σ = {1 → 2, 3 → 4, 5 → 2, 5 → 4, 24 → 5}.
The lattice L Σ , depicted in figure 2, is distributive despite the fact that 24 → 5 ∈ Σ Our work goes in the same line as those of Faigle and Kern [START_REF] Faigle | The shapley value for cooperative games under precedence constraints[END_REF], Bilbao and Edelman [START_REF] Bilbao | The shapley value on convex geometries[END_REF] and Faigle et al [START_REF] Faigle | Games on concept lattices: Shapley value and core[END_REF]. Cooperative games with precedence constraints, introduced in [START_REF] Faigle | The shapley value for cooperative games under precedence constraints[END_REF], correspond in our framework to the case |A| = 1 for all (A → i) ∈ Σ. We consider cooperative games on closure systems as in [START_REF] Faigle | Games on concept lattices: Shapley value and core[END_REF], with the difference that the feasible coalitions in our model are given by an implicational system Σ on a set of players N , instead of a context as in [START_REF] Faigle | Games on concept lattices: Shapley value and core[END_REF]. We can shift from our representation to the representation of [START_REF] Faigle | Games on concept lattices: Shapley value and core[END_REF], in the following way: Let Σ be an implicational system. Consider the context K = (G, M, I) defined by

G = N , M = {F ∈ F Σ | ∀F 1 , F 2 ∈ F Σ , F = F 1 ∩F 2 } and I = {(i, F ) ∈ G×M | i ∈ F }. The concept lattice of K is isomorphic to L Σ .
It is worth noticing, that these two representations are incomparable. Indeed, the size of an implicational system Σ can be exponential in the size of the associated context and vice-versa. For example, if we define the feasible coalitions to be the cliques of a graph G = (N, E) then we need |N | 2 implications in our representation, whereas the size of a representation by a context is exponential. On the other side one may need an exponential number of implications to represent the concepts of a context of polynomial size [START_REF] Mannila | On the complexity of inferring functional dependencies[END_REF]. It might be noteworthy that sometimes the exponential blow-up can be avoided if auxiliary elements in N are allowed, as shown in [START_REF] Rudolph | Succinctness and tractability of closure operator representations[END_REF].

Position of the problem

Let (N, Σ, v) be a cooperative game on an implicational system. Let Ch be the set of maximal chains of the lattice L Σ = (F Σ , ⊆). For a maximal chain c ∈ Ch and i ∈ N , we denote by F (c, i) the last coalition in c that doesn't contain the player i, and by F + (c, i) the first coalition in c that contains the player i.

The coalition F + (c, i) always covers the coalition F (c, i) in the lattice L Σ , that is, there is no coalition F in L Σ such that F (c, i) F F + (c, i).
The Shapley value of (N, Σ, v), as defined in [START_REF] Faigle | Games on concept lattices: Shapley value and core[END_REF], is the vector ϕ(v) = (ϕ i (v)) i∈N , where

ϕ i (v) = 1 |Ch| c∈Ch v(F + (c, i)) -v(F (c, i)) |F + (c, i) \ F (c, i)| . (1)
In this paper, we consider the following problem:

Shapley value

Input: A cooperative game (N, Σ, v).

Output: ϕ(v). 3 shows the set A 5 for Σ = {2 → 1, 4 → 3, 6 → 5} on N = {1, ..., 6}. For a maximal chain c, the coalition F (c, 5) is linked to the coalition F + (c, 5) by a dotted line. The elements of A 5 can be identified with the dotted lines. For any F ∈ F Σ , we denote by Ch ↓ (F ) (resp. Ch ↑ (F )) the number of maximal chains of the sublattice [∅, F ] (resp. [F, N ]). In Figure 3, we have Ch ↓ (135) = 6 and Ch ↑ (135) = 6. With this notation, equation (1) becomes

Define the set

A i = {(F, F ) ∈ F 2 Σ | ∃c ∈ Ch : F = F (c, i) and F = F + (c, i)} . Figure
ϕ i (v) = 1 Ch ↓ (N ) (F,F )∈A i Ch ↓ (F ) • Ch ↑ (F ) |F \ F | (v(F ) -v(F )) . (2)
In view of the last expression, we can decompose the problem Shapley value into two sub-problems, MarginSets and NChains: MarginSets Input: An implicational system Σ on the set of players N and i ∈ N . Output: Enumerate the set A i .

NChains

Input: An implicational system Σ on the set of players N and F ∈ F Σ .

Output: Ch ↓ (F ).

There exist output polynomial time algorithms to enumerate the set A i for any given implicational system Σ [START_REF] Bordat | Calcul pratique du treillis de galois d'une correspondance[END_REF][START_REF] Kuznetsov | Algorithms for the construction of concept lattices and their diagram graphs[END_REF][START_REF] Nourine | A fast algorithm for building lattices[END_REF], but the size of A i may be exponential e.g. for Σ = ∅, we have

|A i | = 2 |N |-1 .
For general cooperative games, when the function v is given by an oracle, any algorithm that solves Shapley value will list all the pairs in A i . For particular games, one can obtain a partition of the set A i of polynomial size, where the elements of each equivalence class have the same behaviour. This idea will be developed in Section 5.

The problem NChains consists in counting the number of maximal chains in the lattice associated to the implicational system Σ F = {X → x | X ∪ {x} ⊆ F } on the set of players F . Notice that Ch ↑ (F ) is obtained by solving the problem NChains with the arguments F = N and Σ = Σ ∪ {∅ → j | j ∈ F }. Brightwell and Winkler [START_REF] Brightwell | Counting linear extensions[END_REF] have shown that the problem NChains is #P -Hard even for closure systems closed under union, i.e. distributive lattices.

The next proposition is a rewriting of results in [START_REF] Faigle | The shapley value for cooperative games under precedence constraints[END_REF] we therefore omit its proof.

Proposition 2. [START_REF] Faigle | The shapley value for cooperative games under precedence constraints[END_REF] Assume that we have an oracle solving NChains. Then an algorithm that solves Shapley value will execute a call for the oracle for each (F,

F ) ∈ A i , i ∈ N .
Thus, solving Shapley value is at least as hard as solving NChains. In other words, the complexity of NChains is a lower bound for the complexity of Shapley value even for elementary games.

In order to solve efficiently the problem Shapley value, we must be able to solve the problem NChains efficiently. This is, however, not sufficient. It may happen that we can solve NChains efficiently and yet the problem Shapley value remains hard. This is due to the interaction between the two sub-problems NChains and MarginSets. In the next section, we give two algorithms for solving the problem Shapley value. The first one enumerates the maximal chains of L Σ . The second one computes the lattice L Σ , and then computes the Shapley value. In Section 5, we address the case where the lattice L Σ is isomorphic to a product of chains.

Two algorithms for computing the Shapley value

In the following, we describe two algorithms for computing the Shapley value for any cooperative game (N, Σ, v).

Enumeration of the maximal chains of L Σ

We will generate the maximal chains of the lattice L Σ in a classical backtracking manner, i.e. given a partial chain C = (∅ = F 0 , . . . , F j ), for each feasible set F covering F j we will enumerate all the maximal chains having (∅ = F 0 , . . . , F j , F ) as a prefix, starting from C = (∅). Whenever F = N , then a maximal chain is obtained and thus we compute the marginal contribution of each player in N with respect to this maximal chain.

For a family E of sets, We denote by M in ⊆ (E) the set of minimal elements of E with respect to set inclusion. Lemma 1 shows how to compute a feasible coalition covering another in the lattice L Σ . This lemma is not new, it can be found in earlier papers dealing with the construction of the Galois or concept lattice of a context. See for example [START_REF] Bordat | Calcul pratique du treillis de galois d'une correspondance[END_REF]. Our contribution is to show how to compute a covering coalition using Σ as an input.

Lemma 1. F covers F in L Σ iff F ∈ M in ⊆ {(F ∪ {i}) Σ , i ∈ N \ F }.
Proof: Suppose F covers F and let j ∈ F \F . Then F ⊂ (F ∪{j}) Σ = F otherwise F does not cover F . Now suppose there exists i ∈ N \F such that F ⊂ (F ∪{i}) Σ ⊂ (F ∪{j}) Σ = F . This contradicts the fact that F covers F , and thus

F ∈ M in ⊆ {(F ∪ {i}) Σ , i ∈ N \ F }. Conversely suppose F ∈ M in ⊆ {(F ∪ {i}) Σ , i ∈ N \ F }, with F = (F ∪ {j}) Σ , j ∈ N \ F and F does not cover F . Let F ⊂ F " ⊂ F and i ∈ F " \ F . Then F ⊂ F " = (F ∪ {i}) Σ ⊂ F = (F ∪ {j}) Σ which contradicts the fact that (F ∪ {j}) Σ is minimal. Algorithm 1 Shapley -M ain(N, Σ, v). Data: A restricted cooperative game (N, Σ, v) Result: (ϕ i ) i∈N begin for i ← 1 to n do ϕ i ← 0 end Shapley(∅, C = (∅)); end Algorithm 2 Shapley((A, C)).
Result: Proof: Algorithm 1 enumerates maximal chains recursively, and at each node A of the execution tree, it computes the feasible coalitions covering A in the lattice using Lemma 1. For each leaf, the algorithm computes the marginal contributions associated to the corresponding maximal chain (see Line 1 of Algorithm 2).

(ϕ i ) i∈N begin if A = N then {Let C = (∅ = F 0 , . . . , F k = N )} 1 for j ← 1 to k do for i ∈ F j \ F j-1 do ϕ i ← ϕ i + v(F j )-v(F j-1 ) |F j \F j-1 | end end end else S = ∅; for i ∈ N \ A do 2 S = S ∪ {(A ∪ {i}) Σ }; end 3 for F ∈ M in ⊆ (S)
The complexity of Algorithm 2 is strongly related to the complexity of Line 2. Wild [START_REF] Wild | Computations with finite closure systems and implications[END_REF] gives an algorithm for computing the closure of a set using an implicational system in O(|N | 2 .|Σ|). Thus, the complexity for outputting a maximal chain is bounded by O(|N | 3 .|Σ|), since the length of a chain is at most |N |.

Building the lattice L Σ

The strategy here is first to compute the feasible coalitions lattice, and then compute the Shapley value. There are several algorithms for computing the lattice [START_REF] Baixeries | Yet a faster algorithm for building the hasse diagram of a concept lattice[END_REF][START_REF] Bordat | Calcul pratique du treillis de galois d'une correspondance[END_REF][START_REF] Nourine | A fast algorithm for building lattices[END_REF] that are already implemented in several platforms (e.g. Galicia or concepts explorer).

Algorithm 3 Procedure Shapley2(N, Σ, v). Data: A restricted cooperative game (N, Σ, v) Result: (ϕ i ) i∈N begin 1
Compute the covering graph of the lattice L Σ = (F Σ , ⊆);

2
For each F ∈ F Σ , compute Ch ↓ (F ) and Ch ↑ (F ); Proof: The complexity of the computation of the lattice based on an implicational system can be easily derived from the complexity of algorithms in [START_REF] Baixeries | Yet a faster algorithm for building the hasse diagram of a concept lattice[END_REF][START_REF] Bordat | Calcul pratique du treillis de galois d'une correspondance[END_REF][START_REF] Nourine | A fast algorithm for building lattices[END_REF] and can be bounded by

3 for (F, F ) ∈ F Σ such that F covers F do for i ∈ F \ F do ϕ i ← ϕ i + v(F )-v(F )
O(|N | 3 .|Σ|.|F Σ |). The computation of Ch ↓ (F ) for every F ∈ F Σ can be done in O(|N |.|F Σ |)
using a breadth first search (BFS) of the covering graph of the lattice L Σ starting from the bottom. The same argument applies to computing Ch ↑ (F ) starting from the top of the lattice. The line 3 is simple search of the covering graph of the lattice L Σ , and for each edge the computation time is constant. Thus, the total complexity is bounded by the computation of the lattice (line 1).

Notice that whenever the time complexity of Algorithm 1 is polynomial then Algorithm 3 is also polynomial, since |Ch| ≥ |F Σ | N .

Weighted graph games on a product of chains

In this section, we restrict our attention to implicational systems which yield a collection of feasible coalitions isomorphic to a product of chains. This situation occurs, for example, in the model of multi-choice games introduced by Hsiao and Raghavan [START_REF] Hsiao | Shapley value for multichoice cooperative games, I[END_REF] and further studied in [START_REF] Nouweland | Cores and related solution concepts for multi-choice games[END_REF]. The problem NChains can then be solved efficiently. The sets A i , i ∈ N , will be partitioned into equivalence classes in such a way that we need only to consider one element of each class in the computation of the Shapley value. If the number of classes is polynomial, the Shapley value may be computed in polynomial time for specific classes of games.

Let C 1 , . . . , C m be disjoint finite sets. Assume that for each t in {1, . . . , m}, C t is totally ordered by t . We thus have m disjoint totally ordered sets (C 1 , 1 ), . . . (C m , m ). The size of a chain is defined as the number of its elements and the length of a chain is defined as its size minus one. Without loss of generality, we can assume that all the chains have the same size l, and hence, the same length l -1. See remark 2 at the end of the paper for the case where the chains are not of the same length. We associate with the partial order P the implicational system Σ on N defined by

Σ = {i → j | i, j ∈ N, j i} . (3)
An ideal of P is a subset I of P such that j ∈ I and i j implies i ∈ I. Clearly L Σ = (F Σ , ⊆) is the lattice of ideals of P .

The product of the chains

(C 1 , 1 ), . . . (C m m ) is the partial order (C 1 × C 2 × • • • × C m , prod ) , where (x 1 , x 2 , • • • , x m ) prod (y 1 , y 2 , • • • , y m ) ⇔ x t t y t ∀t ∈ {1, 2, • • • , m} . (4)
To see that the lattice L Σ = (F Σ , ⊆) is isomorphic to a product of chains, observe that any F ∈ L Σ is uniquely determined by the set

max(F ) = {i ∈ F | i j ∀j ∈ F }.
Indeed, we have

F = {i ∈ N | ∃j ∈ max(F ) : i j}. F ∈ L Σ can thus be identified with the m-tuple (i 1 , i 2 , • • • , i m ) where, for t = 1, 2, • • • m, i t is the unique player in max(F ) ∩ C t if max(F ) ∩ C t = ∅
, and i t = r t with r t is an imaginary player appended at the bottom of the chain (C t , t ), if max(F ) ∩ C t = ∅. Letting (C t , t ) be the obtained chain after appending the player r t at the bottom of (C t , t ), the lattice

L Σ = (F Σ , ⊆) is isomorphic to the product of chains (C 1 ×C 2 ו • •×C m , prod ).
This fact is illustrated in the following example.

Example 1. Consider the three chains C 1 : 1 1 2, C 2 : 3 2 4 , C 3 : 5 3 6. The Hasse diagram of the partial order P is depicted in figure 4a. In figure 4b, we have added an imaginary player at the bottom of each chain of P . The implicational system associated with P is Σ = {2 → 1, 4 → 3, 6 → 5}. We have n = 6, m = 3, l = 2. The lattice L Σ is depicted in figure 5a and is isomorphic to the product of chains (a) The partial order P . (r 1 ,r 2 ,r 3 ) For F ∈ F Σ , let P |F denote the restriction of the partial order P to the elements of F . For i ∈ N , let h(i) = |{i} Σ | -1, i.e. the number of players preceding i in the order P . The fact that L Σ is the lattice of ideals of P enables us to give an alternative formulation for the sets A i , i ∈ N , where

(C 1 , 1 )×(C 2 , 2 )×(C 3 , 3 ) depicted in figure 5b.
(1,r 2 ,r 3 ) (r 1 ,3,r 3 ) (r 1 ,r 2 ,5) (2,r 2 ,r 3 ) (1,3,r 3 ) (r 1 ,4,r 3 ) (1,r 2 ,5) (r 1 ,3,5) (r 1 ,r 2 ,6) (2,3,r 3 ) (1,4,r 3 ) (2,
(b) (C 1 , 1 ) × (C 2 , 2 ) × (C 3 , 3 ).
A i = {(F 1 , F 2 ) ∈ F 2 Σ | ∃c ∈ Ch : F 1 = F (c, i) and F 2 = F + (c, i)}.
Proposition 5. Let i ∈ N and Σ defined as in [START_REF] Bilbao | The shapley value on convex geometries[END_REF]. Then the elements of A i are exactly the pairs

(F ∪ {i} Σ \ {i}, F ∪ {i} Σ ) where F ∈ F Σ with F ∩ C(i) = ∅.
Proof: As L Σ is the lattice of ideals of the order P , we know [28, p 291] that the coalitions that cover a coalition F ∈ L Σ are just the coalitions F ∪ {j} where j is minimal in

P \ F . Thus for (F 1 , F 2 ) ∈ A i we have F 2 = F 1 ∪ {i} since F 2 covers F 1 and i ∈ F 2 \ F 1 . Since F 1 = F 2 \ {i} is an ideal of P , we necessarily have i ∈ max(F 2 ). Thus F 2 = F ∪ {i} Σ where F is an ideal of P , hence F ∈ F Σ , with F ∩ C(i) = ∅. Consequently, (F 1 , F 2 ) = (F ∪ {i} Σ \ {i}, F ∪ {i} Σ ). Conversely, if (F 1 , F 2 ) = (F ∪ {i} Σ \ {i}, F ∪ {i} Σ ) with F ∈ F Σ and F ∩ C(i) = ∅ then F 2 covers F 1 since i is minimal in P \ F 1 . In addition i ∈ F 2 \ F 1 , then we can build a maximal chain c in L Σ such that F 1 = F (c, i) and F 2 = F + (c, i). Hence (F 1 , F 2 ) ∈ A i .
In view of the last proposition, the elements (F ∪ {i} Σ \ {i}, F ∪ {i} Σ ) ∈ A i can be identified with those of the set:

Ãi = {F ∈ F Σ | F ∩ C(i) = ∅}.
We define an equivalence relation R i on Ãi as follows:

F 1 R i F 2 ⇔ P |F 1 is isomorphic to P |F 2 .
Let Q i be the quotient set of Ãi modulo R i . We will denote the class of F ∈ Ãi by F . Observe that all the elements of an equivalence class modulo R i have the same cardinal, since

P |F 1 isomorphic to P |F 2 implies |F 1 | = |F 2 |,
D k = {(x 0 , . . . , x l ) ∈ N l+1 , such that l t=0 x t = m -1, l t=0 t • x t = k}.
We recall that m is the number of the disjoint chains in the order P and l is their common size. In the rest of this paper, we denote the set Proof: Let F ∈ Q i and P |F the associated suborder of P . We will show that ψ(F ) ∈ E.

By construction, we have l t=1

x t ≤ m -1, so we have

x 0 = m -1 - l t=1 x t ∈ N.
We have

l t=0 t•x t = |F | and, as F ∈ Ãi , 0 ≤ |F | ≤ n-l. Thus, ψ(F ) ∈ D k with k = l t=0 t•x t .
Now we will show that ψ is a bijection.

ψ is injective: Suppose ψ(F 1 ) = ψ(F 2 ) then P |F 1 is isomorphic to P |F 2 hence F 1 = F 2 . ψ is surjective: Let x = (x 0 , ..., x l ) ∈ D k , i.e. l t=0 x t = m -1 and k = l t=0 t • x t . For each j ∈ [1,
l], take x j chains of size j. Define the poset P X as the parallel sum of all the defined chains. Since the number of chains in P X is at most m -1 and the size of each chain is bounded by l, then P X is isomorphic to a suborder

P |F of P with F ∩ C(i) = ∅. Thus ψ(F ) = x.
D 0 = {(2, 0, 0)}, D 1 = {(1, 1, 0)}, D 2 = {(0, 2, 0), (1, 0, 1)}, D 3 = {(0, 1, 1)}, D 4 = {(0, 0, 2)}.
And: 1, 1, 0), (0, 2, 0), (1, 0, 1), (0, 1, 1), (0, 0, 2)}.

E = 4 k=0 D k = {(2, 0, 0), (
The set D 2 contains two codes which correspond to two equivalence classes modulo R 5 . These two classes contain coalitions of size k = 2. The class associated with the code (0, 2, 0) contains feasible coalitions that are built by taking exactly one player from two distinct chains not containing the player 5. The only such coalition is {1, 3}. The class associated with the code (1, 0, 1) contains feasible coalitions that are built by discarding one chain (the 1 in the first position), never taking only one player from a chain (the zero in the second position), and taking two players in a given chain, that doesn't contain the player 5. The feasible coalitions that satisfy this pattern are {1, 2} and {3, 4}. Indeed we have {1, 2} R 5 {3, 4}. We can see also that {1, 2, 3} R 5 {1, 4, 3} and the two coalitions share the code (0, 1, 1) ∈ D 3 .

Let x ∈ E and denote by A x

i the equivalence class ψ -1 (x), where ψ is the bijection defined in proposition 6. By Proposition 5, we have |F \ F | = 1 for all (F, F ) ∈ A i . Thus, equation ( 2) can be rewritten as:

ϕ i (v) = 1 Ch ↓ (N ) n-l k=0 x∈D k F ∈A x i Ch ↓ (F ∪{i} Σ \{i})•Ch ↑ (F ∪{i} Σ )• v(F ∪ {i} Σ ) -v(F ∪ {i} Σ \ {i}) . (5)
The following lemma states that Ch ↓ (F ∪ {i} Σ \ {i}) • Ch ↑ (F ∪ {i} Σ ) depends only on the class of F . Lemma 2. Let all the chains in P have the same length and x ∈ E. Then for all F 1 , F 2 ∈ A x i , we have:

Ch ↓ (F 1 ∪ {i} Σ \ {i}) • Ch ↑ (F 1 ∪ {i} Σ ) = Ch ↓ (F 2 ∪ {i} Σ \ {i}) • Ch ↑ (F 2 ∪ {i} Σ ).
Proof:

Let x ∈ E and F 1 , F 2 ∈ A x i .
Recall that for any F ∈ F Σ , Ch ↓ (F ) is the number of linear extensions of P |F and Ch ↑ (F ) is the number of linear extensions of P |N \F .

Since P |F 1 is isomorphic to P |F 2 , then P |F 1 ∪{i} Σ \{i} is isomorphic to P |F 2 ∪{i} Σ \{i} . Therefore, we have:

Ch ↓ (F 1 ∪ {i} Σ \ {i}) = Ch ↓ (F 2 ∪ {i} Σ \ {i}).
On the other hand, since all the chains are of the same length, then

P |N \[F 1 ∪{i} Σ \{i}] is isomorphic to P |N \[F 2 ∪{i} Σ \{i}]
. Therefore, we also have:

Ch ↑ (F 1 ∪ {i} Σ \ {i}) = Ch ↑ (F 2 ∪ {i} Σ \ {i}).
Hence, we have:

Ch ↓ (F 1 ∪ {i} Σ \ {i}) • Ch ↑ (F 1 ∪ {i} Σ ) = Ch ↓ (F 2 ∪ {i} Σ \ {i}) • Ch ↑ (F 2 ∪ {i} Σ ).
Thus, we can associate with each class A x i the nonnegative integer

α x = Ch ↓ (F ∪ {i} Σ \ {i}) • Ch ↑ (F ∪ {i} Σ )
with F being any coalition in A x i . The following lemma gives a formula for α x .

Lemma 3. Let x ∈ E and k = l t=0 t • x t . We have

α x = (k + h(i))! • (n -k -h(i) -1)! h(i)! • (l -h(i) -1)! • l t=0 [t! • (l -t)!] xt . Proof: Let x ∈ E with k = l t=0 t • x t and F ∈ A x i . Let F = F ∪ {i} Σ \ {i} and p j = |F ∩ C j |, j = 1, . . . m
, where C j is a chain of P . Ch ↓ (F ) is the number of linear extensions of P |F which is the parallel sum of disjoint chains of sizes p j j = 1, . . . m. Thus, we have [START_REF] Möhring | Computationally tractable classes of ordered sets[END_REF]:

Ch ↓ (F ) = |F |! m j=1 p j ! .
In the same way, we obtain:

Ch ↑ (F ∪ {i} Σ )) = Ch ↑ (F ∪ {i}) = (n-|F |-1)!•(l-h(i)) m j=1 (l-p j )! . It follows that Ch ↓ (F ) • Ch ↑ (F ∪ {i}) = |F |!•(n-|F |-1)!•(l-h(i)) m j=1 p j !•(l-p j )! .
For t = 0, 1 . . . , l, t = h(i), the number of chains C j such that p j = t is x t . The number of chains C j such that p j = h(i) is x h(i) + 1. Thus,

Ch ↓ (F ) • Ch ↑ (F ∪ {i} = |F |! • (n -|F | -1)! • (l -h(i)) l t=0 [t! • (l -t)!] xt • h(i)! • (l -h(i))! .
Finally, observing that |F | = k + h(i), we get:

α x = (k+h(i))!•(n-k-h(i)-1)! l t=0 [t!•(l-t)!] x t •h(i)!•(l-h(i)-1)!
. Now we can rewrite equation ( 5) using α x as follows:

ϕ i (v) = 1 Ch ↓ (N ) n-l k=0 x∈D k α x • F ∈A x i v(F ∪ {i} Σ ) -v(F ∪ {i} Σ \ {i}) . (6)
In order to compute ϕ i (v) using ( 6), we need to enumerate, for k = 0, . . . , n -l, all the elements of D k . Now, we describe a backtracking algorithm to enumerate all the encodings x = (x 0 , ..., x l ) ∈ N l+1 in D k . At a depth j, we suppose that all the entries x l , ..., x j-1 have already been filled. The remaining values m = m -1 -l t=j-1

x t and k = k - l t=j-1 t • x t
will be decomposed on x 0 , ..., x j if k ≤ j.m , otherwise there is no possible completion of the vector x. Whenever k = 0 the only solution is to put all the remaining chains in x 0 . The first call to Algorithm 4 is Gen-Class(l, k, m -1) with 0 ≤ k ≤ l.(m -1).

Algorithm 4 Gen-Class(j, k, m). begin if k = 0 then x 0 = m; Output x; end else

1 for i = k j to 0 do x j = i; k = k -i.j; m = m -i; if k ≤ (j -1).m then Gen-Class(j -1, k , m ); end end end end Proposition 7. Let k be an integer in [0, n -l]. Algorithm 4 generates all the vectors in D k in O(k.l.|D k |) using polynomial space.
Proof: First, we will show by induction on the integer j ∈ [1, l], that all the vectors x = (x 0 , . . . , x l ) generated by Gen-Class(j, k, m-1) satisfy x t = m -1.

Suppose now that every vector x, generated by Gen-Class(j , k , m ), where 1 ≤ j < j, is correct. The call Gen-Class(j, k, m -1) will do the following affectations:

x j = i, k = k -ij, m = m -1 -i
and then call Gen-Class(j -1, k , m ). By the induction hypothesis, any output x of Gen-Class(j -1, k , m ) satisfies:

j-1 t=0 tx t = k and j-1 t=0 x t = m .
Thus, we have

j t=0 tx t = k + jx j = k -ij + ji = k and j t=0 x t = m + x j = m -1 -i + i = m -1.
Thus, for all j ∈ [1, l], the vectors x generated by Gen-Class(j, k, m -1) satisfy x t = m -1 that is,

x ∈ D k . Now, we will show that if a = (a 0 , . . . , a l ) ∈ D k , then a is generated by Algorithm 4 with the input (l, k, m -1). First, note that, the values of x l generated by the algorithm are the integers between 0 and k l . Since a ∈ D k , we have k = Therefore a l ≤ k l and the element a l will be generated by the algorithm. Next, suppose that the partial solution (a j+1 , . . . a l ) has already been generated. Then Algorithm 4 will be called with the arguments (j, Observe however, that even if we can enumerate efficiently all the elements of D k for k = 0, . . . n -l, and we have a formula for each α x , computing the Shapley value using Equation ( 6) remains hard for general v. Indeed, if v is given by an oracle, we must execute at least |A x i | calls to the oracle in order to compute v(F ∪ {i} Σ ) -v(F ∪ {i} Σ \ {i}) for each F ∈ A x i . In the following, we will consider particular games on a product of chains for which the computation can be carried efficiently.

The model of weighted graph games captures the interactions between pairs of players. This is done by considering an undirected graph G = (N, E) with an integer weight v ij for each edge {i, j} ∈ E. A positive v ij means that there are synergies between the two players, and a negative one that the presence of both players in a coalition will decrease its worth, because of, for instance, a conflict between i and j. We define a cooperative game (N, Σ, v) by:

v(S) = {i,j}⊆S v ij ∀S ∈ F Σ .
When Σ = ∅, we recover the classical weighted graph games studied by Deng and Papadimitriou [START_REF] Deng | On the complexity of cooperative solution concepts[END_REF] who gave a simple formula for computing the Shapley value of these games. We will show that the computation of the Shapley value remains easy when the lattice of feasible coalitions is isomorphic to a product of chains with the same fixed length. Proposition 9. Let (N, Σ, v) be a weighted graph game and i ∈ N . We have,

ϕ i (v) = 1 Ch ↓ (N ) n-l k=0 x∈D k j =i β x ij • α x • v ij , where β x ij = |{F ∈ A x i | j ∈ F ∪ {i} Σ }|.
Proof: Let i ∈ N and F ∈ A i . We have

v(F ∪ {i} Σ ) -v(F ∪ {i} Σ \ {i}) = j∈F ∪{i} Σ \{i} v ij .
Thus, [START_REF] Bubley | Faster random generation of linear extensions[END_REF] becomes

ϕ i (v) = 1 Ch ↓ (N ) n-l k=0 x∈D k F ∈A x i α x • j∈F ∪{i} Σ \{i} v ij ,
which can be rewritten as:

ϕ i (v) = 1 Ch ↓ (N ) n-l k=0 x∈D k j =i F ∈A x i , j∈F ∪{i} Σ α x • v ij
Finally, we obtain:

ϕ i (v) = 1 Ch ↓ (N ) n-l k=0 x∈D k j =i β x ij • α x • v ij Example 3. (Example 1
continued) Let i = 5, j = 1 and x = (0, 1, 1). We have A x i = {{1, 2, 3}, {1, 4, 3}} and β x ij = 2 since the two coalitions in A x i contain the player 1.

The next proposition gives a formula for β x ij :

Lemma 4. Let i = j ∈ N and x ∈ E. Then

β x ij =                                    0, if j → i, (m -1)! l t=0 x t ! , if i → j, (m -2)! l t=0 x t ! • l t=h(j)+1
x t , otherwise.

Proof: Recall that the number of partitions of a set X, with |X| = n to parts X 0 , . . . , X l , such that |X t | = x t , with l t=0

x t = n is given by the multinomial coefficient [7, p. 27]:

n x 0 , . . . , x l = n! l t=0 x t ! . (7)
We will distinguish 3 cases according to whether i and j are comparable in P or not.

1. j → i, i.e. i is below j in a chain. Then, j ∈ F ∪ {i} Σ for any F ∈ A x i , hence β x ij = 0.

2. i → j, i.e. j is below i in a chain. Then, j ∈ F ∪ {i} Σ for all F ∈ A x i . Hence, we have:

β x ij = |A x i | = m -1 x 0 , . . . , x l = (m -1)! l t=0 x t ! .
3. i j and j i, i.e. i and j are not in the same chain. Let θ j be the height of the maximal element of F ∈ A x i which is in the same chain as j. For a given θ j , the choice of F amounts at partitioning the m -2 chains not containing neither i nor j, to sets X 0 , . . . , X l with |X t | = x t , where

x t = x t -1 if t = θ j + 1 x t otherwise. (8)
Since θ j can take all the integer values in the interval [h(j), l -1], we have:

β x ij = h(j)≤θ j ≤l-1 m -2 x 0 , . . . , x l , where m -2 x 0 , . . . , x l = (m-2)! l t=0 x t ! = (m-2)!•x θ j +1 l t=0 xt! . Therefore, β x ij = h(j)≤θ j ≤l-1 (m-2)!•x θ j +1 l t=0 xt! = (m-2)! l t=0 xt! • h(j)≤θ j ≤l-1 x θ j +1
We can rewrite the last equation as:

β x ij = (m-2)! l t=0 xt! • l t=h(j)+1
x t .

Theorem 1. The Shapley value ϕ i of a player i in a weighted graph game on a product of m chains with the same length l -1 can be computed in O(n l+3 ), where n is the number of players. For fixed l, it can be computed in polynomial time.

Proof:

Let P be the sum of m disjoint chains of length l -1 and i ∈ N , where N is the set of all the elements of the m chains. Let |N | = n. From Proposition 9, the Shapley value can be computed using the formula:

ϕ i (v) = 1 Ch ↓ (N ) n-l k=0 x∈D k j =i β x ij • α x • v ij , where β x ij = |{F ∈ A x i | j ∈ F ∪ {i} Σ }|.
According to [START_REF] Möhring | Computationally tractable classes of ordered sets[END_REF], the number of linear extensions Ch

↓ (N ) of P is Ch ↓ (N ) = n! (l!) m , thus Ch ↓ (N ) can be computed in O(n + m) = O(n) since n ≤ m. From Proposition 7, the equivalence classes in D k can be generated in O(k.l.|D k |) for k ∈ [0, n -1]. Proposition 8
shows that the number of equivalence classes in D k is bounded by O(k l ). Using Lemma 3 and Lemma 4, for each each equivalence class in D k corresponding to A x i , we compute both α x and β x ij in O(n). Thus the total complexity is bounded by O(n l+3 ). When l is fixed, then O(n l+3 ) is a polynomial and therefore the total time complexity is bounded by a polynomial. Remark 1. When Theorem 1 is restricted to classical graph games, i.e. m = n and l = 1, we obtain the complexity O(n 4 ) which is larger than O(n), the complexity obtained in [START_REF] Deng | On the complexity of cooperative solution concepts[END_REF] for each player. Indeed, for a classical graph game, the lattice is boolean and has several properties that cannot be exploited for the general case. The difficult in our case is the number of equivalence classes and how to compute them, whereas, for the boolean lattice, there are n -1 classes and this fact leads to a simplification of the formula.

Remark 2. If the chains are not of the same length, we define the relation R i as follows:

F 1 R i F 2 ⇔ P |F 1 ∼ = P |F 2 and P |N \F 1 ∼ = P |N \F 2 . ( 9
)
Each class modulo R i will be coded by two l-tuples of nonnegative integers, where l is the maximal size of the chains. Ch ↓ (F ∪ {i} Σ \ {i}) • Ch ↑ (F ∪ {i} Σ ) will be constant within each class and the number of classes corresponding to a cardinality k of the class elements will be bounded by a polynomial in k for constant l.

Concluding remarks

We have addressed in this paper the issue of computing the Shapley value of a cooperative game on a lattice given by an implicational system. The structural properties of the lattice L Σ of feasible coalitions play an important role in the design of efficient algorithms. Indeed, efficient algorithms for the computation of the Shapley value are likely to exist only on lattices for which the computation of the number of maximal chains traversing any element of the lattice can be done efficiently, since this computation is a prerequisite for the computation of the Shapley value. A lattice isomorphic to a product of chains is one such structure treated in this paper. There exist distributive lattices for which Nchains can be solved efficiently. For example, the lattices of ideals of series-parallel orders [START_REF] Möhring | Computationally tractable classes of ordered sets[END_REF], or N -free orders with activity bounded by a constant [START_REF] Felsner | Linear extensions of N-free orders[END_REF]. An interesting issue to be addressed, would be whether the Shapley value can be computed efficiently for weighted graph games on these lattices.

When no efficient algorithm for computing the Shapley value is likely to exist, approximation becomes in order. When the lattice of feasible coalitions is distributive, approximating the number of maximal chains traversing an element of the lattice, amounts to approximate the number of linear extensions of a partial order. Methods have been proposed to deal with this issue, [START_REF] Brightwell | Counting linear extensions[END_REF][START_REF] Ewacha | Approximating the number of linear extensions[END_REF][START_REF] Bubley | Faster random generation of linear extensions[END_REF]. One may think also of reducing the number of coalitions considered in computing the Shapley value, following an idea used in [START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF] in searching for an optimal coalition structure. Of course, the quality of the approximation, will depend on the choice of the coalitions taken into consideration.

As presented in this paper, the model of cooperative games on implicational systems generalizes the notion of a conjunctive permission structure. We think that this model can be extended to involve disjunctive permission structures, and many other constraints on coalition formation, by allowing for implications with "negated" players. For example the implication 1 2 3 → 4 will mean that the absence of players 1, 2 and 3 in a coalition will result in the absence of player 4, and the implication 1 2 3 → 4 will mean that the presence of player 2 in a coalition where the players 1 and 3 are absent, will entail the presence of player 4.

Another issue is the study of the algorithmic aspects of other solution concepts for cooperative games on lattices such as the core.

Figure 1 :

 1 Figure 1: The lattice LΣ corresponding to Σ = {2 → 1, 4 → 3, 6 → 5} on N = {1, ..., 6}.

Figure 2 :

 2 Figure 2: The lattice LΣ corresponding to Σ = {1 → 2, 3 → 4, 5 → 2, 5 → 4, 24 → 5} on N = {1, ..., 5}.

Figure 3 :

 3 Figure 3: The dotted lines correspond to the elements of A5.

  do Shapley(F, C + F ); end end end Proposition 3. Algorithm 1 computes the Shapley value in O(|N | 3 .|Σ|.|Ch|) time complexity using polynomial space.

4 .

 4 Algorithm 3 computes the Shapley value in O(|N | 3 .|Σ|.|F Σ |) time and space complexity.

Let N = m t=1 C

 t=1 t and |N | = n. We define the partial order P = (N, ), called the parallel sum of the chains (C 1 , 1 ), . . . (C m m ), by ∀i, j ∈ N : i j ⇔ ∃t ∈ {1, . . . , m} : i t j .

3 (

 3 b) The chains (C t , t ), t = 1, 2, 3.

Figure 4 :

 4 Figure 4: Adding imaginary players at the bottom of each chain of P .

Figure 5 :

 5 Figure 5: The lattice LΣ is isomorphic to the product (C 1 , 1) × (C 2 , 2) × (C 3 , 3).

  and that this common cardinal is an integer in [0, n -l]. The next proposition gives an encoding of the class F , with |F | = k, by a vector of integers in the set:

Proposition 6 .

 6 Let i ∈ N . The sets Q i and E = n-l k=0 D k are in bijection by the mapping ψ : Q i → E, F → ψ(F ) = (x 0 , . . . , x l ) where x t is the number of chains of size t in P |F for 1 ≤ t ≤ l, and x 0 = m -1 -l t=1 x t . Furthermore, we have ψ(F ) ∈ D k with k = |F |.

Example 2 .

 2 (Example 1 continued) For i = 5, as 5 ∈ C 3 , the elements of Ã5 are the feasible coalitions F ∈ F Σ such that F ∩ C 3 = ∅, that is, 5 ∈ F and 6 ∈ F : Ã5 = {∅, {1}, {3}, {1, 3}, {1, 2}, {1, 2, 3}, {3, 4}, {1, 3, 4}, {1, 2, 3, 4}}; The size of an element of Ã5 is between 0 and n -l = 6 -2 = 4. The sets D k for k ∈ [0, 4] are:

  to D k . For j = 1, the algorithm generates a unique vector x with x 0 = m -1 -k and x 1 = k and all other entires are null, which satisfies j t=0 tx t = k and j t=0

x t = m - 1 .

 1 For j = l, we obtain l t=0 tx t = k and l t=0

tProposition 8 .

 8 • a t , m -1 -l t=j+1 a t ). The values x j generated by the algorithm are the integers between 0 and solution (a j , a j+1 , . . . a l ) will be generated. Once the sequence (a 1 , . . . , a l ) generated, the algorithm will generate a 0 by a 0 = m -1 -l t=1 a t . Thus the solution a will be generated by the algorithm.Each call of the algorithm will cost O(k) (see Line 1), and the depth of the execution tree is bounded by l the size of the vector. Thus the total cost of the algorithm is bounded by O(k.l.|D k |), since each call has a leaf which is a solution. The space used by the algorithm corresponds to a chain from the root to a leaf and is bounded by O(l). We have|D k | ∈ O(k l ).Proof: The elements of D k correspond to the leaves of the search tree of Algorithm 4. The depth of the tree is l and its branching factor is bounded by O(k). Thus |D k | ∈ O(k l ).

Email addresses: maafa.khaled@gmail.com (Khaled MAAFA), nourine@isima.fr (Lhouari NOURINE), radjefms@gmail.com (Mohammed Said RADJEF) Preprint submitted to ElsevierDecember 25, 2017

Acknowledgment: The authors wish to thank anonymous referees for their suggestions which have greatly improved the presentation of the paper. This work has been funded by the CMEP Tassili 15MDU944-2015-2018 and the ANR project Graphen 2015-2019. The first author has received a scholarship from the Algerian Ministry of Higher Education and Scientific Research.

Appendix A. Computing the Shapley value using the Harsanyi dividends

We explore the use of Harsanyi dividends and their recurrence formula in the computation of the Shapley value.

Following [START_REF] Faigle | The shapley value for cooperative games under precedence constraints[END_REF], we define for all T ∈ F Σ , T = ∅, the T -simple game u T : F Σ → R: by

When F Σ = 2 N , u T is known as the T -unanimity game.

The family {u T , T ∈ F Σ \ ∅} is a basis of the vector space of all cooperative games defined on F Σ . Hence, each game v : F Σ → R can be expressed uniquely as a linear combination of the games

In view of the definition of the simple games u T , the last equation becomes

The real coefficient ∆ v T is called the Harsanyi dividend of the coalition T in the game v.

Letting ∆ v ∅ = 0, Equation (A.3) yields the following recurrence formula for the dividends

Using this recurrence formula to compute the dividends ∆ v T is not efficient from the algorithmic point of view, since, to compute ∆ v T , we have to compute all the ∆ v S 's, where S ⊂ T is a feasible coalition.

We now turn to the evaluation of the Shapley value ϕ i (u T ) of the player i ∈ N in the simple game u T . Let us recall the definition of the hierarchical strength h T (i) of player i in the feasible coalition T [START_REF] Faigle | The shapley value for cooperative games under precedence constraints[END_REF]. A feasible ranking of the players in N is a linear extension of the order P . i ∈ T is T -maximal in the ranking π, if i is maximal in the linear order induced by π on T . Let R(N ) be the set of all feasible rankings of N . The hierarchical strength h T (i) of player i in the feasible coalition T is then defined by:

Then, the Shapley value of i ∈ N in the game u T is given by [START_REF] Faigle | The shapley value for cooperative games under precedence constraints[END_REF]:

Using Lemma 4 in [START_REF] Faigle | The shapley value for cooperative games under precedence constraints[END_REF], which states that h T (i) = 0 if and only if i ∈ max(T ), we obtain:

Then, by the linearity of the Shapley value and Equation (A.1), we have:

In the case studied in Section 5, (F Σ , ⊆) is the lattice of ideals of a partial order P . Then, an explicit expression of the dividend ∆ v T can be obtained from Equation (A.3), using the Möbius inversion formula [START_REF] Stanley | Enumerative Combinatorics[END_REF]:

where µ is the Möbius function of the lattice (F Σ , ⊆). As (F Σ , ⊆) is the lattice of ideals of the partial order P , we know [START_REF] Stanley | Enumerative Combinatorics[END_REF] that

The condition S ⊆ T and T \ S is an antichain of P is equivalent to S = T \ E, where E is a subset of max(T ). We thus obtain the following expression for the dividend ∆ v T :

The Shapley value of player i ϕ i (v), given by Equation (A.5), becomes then

Again, the direct use of Equation (A.8) to compute the Shapley value is not efficient from the computational point of view. Indeed, we have to generate all the coalitions T ∈ F Σ with i ∈ max(T ) and all the subsets E of max T .


Jean-Baptiste Trystram
email: jbtrystram@redhat.com

Toward Software Updates in IoT Environments: Why Existing P2P Systems are not Enough

Keywords: CCS CONCEPTS, Networks → Peer-to-peer protocols, Sensor networks, Peerto-peer networks, Mobile ad hoc networks, • Computer systems organization

The number of connected devices around us is growing, and their embedded software is increasing in complexity. Applications need to be managed and updated throughout their life-cycle. Modern software orchestrators and management systems are mostly centralised and expensive to scale to very large systems. We propose a decentralised approach to distribute software updates to Internet of Things (IoT) devices using Peer-to-Peer (P2P) transfers. We seek to improve the efficiency of software update propagation by adapting system behaviour to IoT constraints, such as device heterogeneity, unreliable network connectivity and applications specifics.

INTRODUCTION

The IoT landscape will include billions 1 of devices deployed in various environments such as smart industries and cities, connected cars and healthcare. As these devices get new features, they will run increasingly complex software. Like all software, it needs to be patched for feature improvements and security fixes. A large number of these devices puts a strain on the traditionally centralised software deployment schemes as modern networks cannot cope with intensive M2M usage [START_REF] Cherkaoui | LTE-A Random Access Channel Capacity Evaluation for M2M Communications[END_REF]. Additionally, centralised techniques are designed for static environments while IoT devices have unpredictable network connectivity and heterogeneous hardware. P2P systems handle these constraints but usually deal only with 1 Gartner's forecast for IoT, Feb. 2017. http://www.gartner.com/newsroom/id/3598917 Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). scalability and resiliency issues, so we propose to extend these techniques to take account of energy usage and IoT application-specific requirements.

RELATED WORK

Service discovery in distributed systems has been widely studied [START_REF] Meshkova | A survey on resource discovery mechanisms, peer-to-peer and service discovery frameworks[END_REF][START_REF] Sailhan | Scalable Service Discovery for MANET[END_REF]. Such techniques locate a given service or file within the system but do not offer ways to access them. Moreover, some do not scale to large and disconnected networks. For example, Distributed Hash Table (DHT) requires connectivity with the node storing the desired entry [START_REF] Meshkova | A survey on resource discovery mechanisms, peer-to-peer and service discovery frameworks[END_REF]. Additionally, there is no support for versioning: services or files cannot co-exist with different versions; they are treated as unrelated.

Software management systems are designed to handle versioning and large systems, but they are mostly centralised, thus requiring a permanent connection with the orchestrator. De-centralised flavours do exist, but still, rely on a central server to coordinate peers [START_REF] Arcangeli | Automatic deployment of distributed software systems: Definitions and state of the art[END_REF].

Today's software distribution mechanisms are almost exclusively based on a client-server model. P2P software distribution exists but is mainly focused on offloading work from the central server [START_REF] Abiteboul | Large Scale P2P Distribution of Open-Source Software[END_REF]. Peer locality [START_REF] Gkantsidis | Planet scale software updates[END_REF] reduces inter-ISP data traffic but relies on a central service.

Ad-hoc networks are a conducive environment for P2P applications [START_REF] Ding | Peer-to-peer File-sharing over Mobile Ad hoc Networks[END_REF][START_REF] Goel | Efficient Peer-to-Peer Data Dissemination in Mobile Ad-Hoc Networks[END_REF]. While MANETs share similar constraints to IoT (mobility, energy limits, unstable connectivity) the scale is different. Indeed, MANET networks are fairly small, and all the nodes are regularly connected.

Lastly, the network usage related to software updates is nonnegligible [START_REF] Orehek | Updates in IoT are more than just one iota[END_REF]. Modern centralised mobile infrastructures cannot scale to a large amount of data per user [START_REF] Rivano | Wireless Access Networks for Smart Cities[END_REF] nor to a vast number of devices [START_REF] Cherkaoui | LTE-A Random Access Channel Capacity Evaluation for M2M Communications[END_REF].

INTENDED APPROACH

In this section, we lay down the key features of a new software update dissemination system that fit IoT constraints and adapts to applications specifics. First, we describe how a device discovers available content. We then argue how constraints imply the need of downloading from multiple sources. Next, we introduce piece selection strategies and their impact on the system's efficiency. Security aspects are then discussed, and how metrics collection improves reliability.

Content discovery. A large number of unpredictable devices implies that a fully connected graph is not realistic. Thus, a DHT or a tracker-based system is not efficient. We assume nodes will spontaneously initiate ad-hoc connections with their neighbours when possible. To make use of these connections, devices need to Middleware Doct Symposium 17, December 11-15, 2017, Las Vegas, NV, USA Jean-Baptiste Trystram know whether they have a shared interest in certain resources (e.g. software updates).

Announce-based protocols have proven reliable in networks with inconsistent connectivity (e.g. vehicular networks), providing efficient epidemic or gossip-style dissemination [START_REF] Das | SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol[END_REF]. Using this announcement, devices can exchange details about the software they run and share, together with, their associated versions. Devices can initiate transfer of packages included in announcements received.

Multiple parts download. Spontaneous connections between mobile devices may be too short to exchange a full package between two devices. To cope with this issue, files can be divided into small chunks. Block usage allows to resume an interrupted download, or get the remaining parts of the file from other peers.

Piece selection strategy. The main challenge is to design a piece selection algorithm that efficiently distributes files throughout the network. There are several block selection approaches to improve file dissemination. BitTorrent chooses blocks randomly or picks the rarest first. Specific strategies could make use of the dynamic properties of devices, such as mobility and social interactions. Social patterns help to predict how devices will meet [START_REF] Vaz De Melo | RECAST: Telling apart social and random relationships in dynamic networks[END_REF]. Adding the last devices met in the announcement message facilitate this approach.

Application dependencies require consideration, as updating some software may be impossible without up-to-date dependencies. In this case, dependencies must be downloaded first. The announcement protocol should express such constraints. This is critical for low memory devices: they may not be able to hold all of the update packages in memory alongside the running application. It may be necessary to process updates as they download them, in which case the downloading order cannot be random.

Security. To avoid a malicious device tampering with the data before sharing it, cryptographic signatures can be used. As a central server is not always reachable, downloads should contain a hash of the pieces, signed with the publisher's keys (as in Android and iOS applications).

Application-centric. A non content-agnostic protocol would provide improved features. The addition of metadata along packages allow to adjust convergence and consistency accordingly (e.g. a critical security fix needs a faster deployment). Such metadata could also host statistics on application deployment results in a distributed manner. Devices may use feedbacks from their peers to avoid installation errors or rollback to previous versions.

Accomplished work

Initial work has been done modifying the PeerSim2 simulator to reproduce a more realistic IoT scenario. We added dynamic properties to the simulation engine: nodes mobility, free-riders, network bandwidth heterogeneity and limited energy. Nodes only pick peers within a given range when creating the neighbour table. The next step is to include an advanced mobility model; at the time of writing, we use a simple random walk.

EVALUATION

Several mobility data sets can be used to test our solution with realistic data. The TAPAS Cologne3 project logged vehicular traffic within the city of Cologne for 24h. The San Francisco cab data set4 contains mobility trace of 500 cabs for 30 days. Those provide data representative of mobility patterns that we will use to measure how quickly an update propagates.

The primary performance metric being considered is the network volume overhead: how much more network data is exchanged compared to a simpler client-server download. The overhead for a single device will be measured from which the overhead for the full network will be extrapolated. Values will be compared to a standard P2P file sharing system like BitTorrent. These metrics should be reported to the time needed to get the update on every device. Additionally, a Markov model can describe the system behaviour in its stationary state. This approach and have been used previously with accurate results [START_REF] Qiu | Modeling and performance analysis of BitTorrent-like peer-to-peer networks[END_REF][START_REF] Zou | A File-Centric Model for Peer-to-Peer File Sharing Systems[END_REF].

CONCLUSION

P2P dissemination of software updates in IoT systems will lower infrastructure load while increasing efficiency and reliability in cases where strong consistency and quick convergence is not needed. The update process should also satisfy IoT constraints: after the download, a safe installation is critical. A reliable rollback system will prevent the device from entering a blocking state, as manual intervention may be costly or impossible for some devices.

Middleware Doct Symposium 17, December 11-15, 2017, Las Vegas, NV, USA © 2017 Copyright held by the owner/author(s). ACM ISBN 978-1-4503-5199-7/17/12. https://doi.org/10.1145/3152688.3152694

http://peersim.sourceforge.net

http://sumo.dlr.de/wiki/Data/Scenarios/TAPASCologne

http://crawdad.org/epfl/mobility/20090224

ACKNOWLEDGMENTS

I want to thank my advisers Julien Ponge, Frédéric Le Mouël, David Ingham and Mark Little for their guidance and support during this first year of PhD. This work is supported by Red Hat Inc.