Alexandre Skoda
email: askoda@univ-paris1.fr

Xavier Venel
email: xvenel@luiss.it

Weighted Average-convexity and Cooperative Games

Keywords: AMS Classification: 91A12, 91A43, 90C27, 05C75 TU-games, convexity, average-convexity, weighted Shapley value, communication

We generalize the notion of convexity and average-convexity to the notion of weighted average-convexity. We show several results on the relation between weighted averageconvexity and cooperative games. First, we prove that if a game is weighted averageconvex, then the corresponding weighted Shapley value is in the core. Second, we exhibit necessary conditions for a communication TU-game to preserve the weighted averageconvexity. Finally, we provide a complete characterization when the underlying graph is a priority decreasing tree.

Introduction

We consider a situation where a set of players N " t1, . . . , nu can cooperate to generate some profit. It is usually assumed that any coalition S Ď N of players is feasible and that the profit generated by the players in S can be freely distributed among them. This kind of situation corresponds to a cooperative game with transferable utility. One of the key question in this framework is to allocate to each player his share of the profit generated by the grand coalition N . Any share of the total worth of N between the n players is called a solution of the game.

Lots of solution concepts have been introduced and they can be divided in two different families: single-valued solutions and set-valued solutions. The best-known singled-valued solution in cooperative game theory is the Shapley value introduced and characterized in Shapley (1953b). The Shapley value allocates to each player its average marginal contribution and is always defined. A typical set valued solution is the core [START_REF] Gillies | Solutions to general non-zero-sum games[END_REF]). The core is the set of allocations that are efficient and coalitionally rational, two particularly desirable properties in the context of cooperative games. An allocation is efficient if it fully distributes the worth of the grand coalition N among the n players. Coalitional rationality requires that for every coalition S the total payoff obtained by S is at least equal to the profit that it can generate by itself. Hence no coalition can have an incentive to leave the grand coalition N . Unfortunately, the core of a game may be empty but some properties of the game can guarantee the non-emptiness of the core and more specifically that the Shapley value lies in the core. [START_REF] Shapley | Cores of convex games[END_REF] introduced the class of convex games. In a convex game, the marginal contribution of a player is an increasing function with respect to the coalition size. [START_REF] Shapley | Cores of convex games[END_REF] showed that if a game is convex, then the Shapley value belongs to the core and therefore the core is non-empty. In fact, the convexity assumption is very strong and can be relaxed to ensure that the Shapley value is a core element. [START_REF] Iñarra | The shapley value and average convex games[END_REF] introduced a weaker notion than convexity, called average-convexity and proved that it is a sufficient condition for the Shapley value to be in the core. In the average convexity, one compares average of marginal contributions instead of comparing directly marginal contributions. More precisely, for any coalition the sum of the marginal contributions of the players belonging to this coalition has to be less or equal to the sum of the marginal contributions of the same players in a larger coalition. Independently, [START_REF] Sprumont | Population monotonic allocation schemes for cooperative games with transferable utility[END_REF] established a result similar to the one of [START_REF] Iñarra | The shapley value and average convex games[END_REF] but in a different framework as he investigated population monotonic allocation schemes (PMAS). In particular, average convexity is also a sufficient condition for the existence of a PMAS.

By definition, the Shapley value is symmetric between the players. But many situations like for example players representing groups of individuals or players having different bargaining powers are naturally asymmetric. Shapley (1953a) extended the notion of Shapley value to weighted Shapley value by considering asymmetric positive weights on the players. Even more general, [START_REF] Kalai | On weighted shapley values[END_REF] introduced the notion of weight system introducing different priorities on the players and provided an axiomatic characterization of the weighted Shapley values. Further results and characterizations of the weighted Shapley values were proven in [START_REF] Hart | Potential, value, and consistency[END_REF]. [START_REF] Monderer | Weighted values and the core[END_REF] proved that if the game is convex, then the weighted Shapley values are in the core (for any weight system). Moreover, they showed that for any game one can obtain all the elements of the core as weighted Shapley values by varying the weight system.

The first aim of this article is to establish given a weight system a weaker sufficient condition than convexity to ensure that the weighted Shapley value belongs to the core. To do so, we introduce the notion of weighted average-convexity generalizing the average-convexity of [START_REF] Iñarra | The shapley value and average convex games[END_REF]. We prove then that it is indeed a sufficient condition.

In many situations, the cooperation of players may be restricted by some communication or social structures. Then, the worths of coalitions have to be modified to take these restrictions into account, leading to the introduction of restricted games. [START_REF] Myerson | Graphs and cooperation in games[END_REF] introduced the class of graph restricted games, also known as communication games. In his framework, one considers an initial game and a communication graph. Players have to be connected in the underlying graph to be able to cooperate. Formally, the value of a coalition in the communication game is the sum of the values in the initial game of connected subcoalitions. The Myerson value of the game and the communication graph is the Shapley value of the communication game. [START_REF] Slikker | Communication situations with asymmetric players[END_REF] extended the Myerson value to weight systems.

A central question is the inheritance of properties from the original game (without the graph structure) to the associated communication game. For a general overview of inheritance of properties for communication games we refer to [START_REF] Slikker | Social and Economic Networks in Cooperative Game Theory[END_REF]. Our focus will be on convexity and its variants. [START_REF] Van Den Nouweland | On the convexity of communication games[END_REF] proved that there is inheritance of convexity if and only if the graph is cycle-complete. [START_REF] Slikker | Average Convexity in Communication Situations[END_REF] showed that there is inheritance of average convexity if and only if connected components of the graph are complete graphs or stars.

We investigate the question of inheritance of weighted average-convexity for communication games. We exhibit necessary conditions on the underlying graph to preserve weighted average-convexity from any game to the associated communication game.

When there is a unique priority, we prove that the conditions given in Slikkers's characterization are also necessary using more general counter-examples taking into account the different weights of the players. In this case we get the same characterization as [START_REF] Slikker | Average Convexity in Communication Situations[END_REF] for inheritance of weighted average convexity.

When there are more than one priority, we provide necessary conditions. The first condition is for each subgraph associated with a priority level to be composed of stars or complete graphs. The second is how two connected components lying in different priority levels are connected. In the third condition, we analyze how several components can interact with each other. Finally, we focus on the case where the graph is a tree and the priorities are decreasing along the tree. We provide a full characterization of the class of priority decreasing trees preserving weighted-average convexity. Informally, such a graph is a succession of stars along a path and with decreasing priorities from one star to another.

By combining these last results with our first one on the weighted Shapley value, we obtain sufficient conditions on the game and on the graph to guarantee that the weighted Myerson value belongs to the core.

The outline of the article is the following. Section 2 provides classical definitions in cooperative game theory, including several equivalent definitions of the Shapley value and sufficient conditions for it to be in the core. In Section 3, we recall the definition of the weighted Shapley value and introduce the notion of weighted average-convexity. We prove that weighted average-convexity is a sufficient condition to ensure that the weighted Shapley value belongs to the core (Theorem 1). In the next sections we investigate the class of graphs ensuring inheritance of weighted average-convexity for communication games. Section 4 pro-vides a complete characterization (Theorem 2) of this class in the case of weight systems with a unique priority. In Section 5, we establish necessary conditions when weight systems have several priorities (Propositions 7,8,and 9). Finally, we provide a complete characterization (Theorem 3) for the class of priority decreasing trees.

TU-games and Classical Shapley Value

TU-Games

A T U -game is defined by a set of players N and a characteristic function v from 2 N to R that satisfies vpHq " 0. An allocation is a vector x P R N that represents the respective payoff of each player. It is said to be efficient if

ÿ iPN x i " vpN q.
and individually rational if every player receives at least the value that he could guarantee alone @i P N, x i ě v ptiuq .

This last property can be extended to coalitions. An allocation is coalitionally rational if for every coalition the sum of payoffs of its members is at least the value of the coalition

@S Ď N, ÿ iPS x i ě v pSq .
The core is the set of efficient and coalitionally rational allocations. Formally,

Cpvq " # x P R N , ÿ iPN x i " vpN q, ÿ iPS x i ě vpSq, @S Ă N + . A player i in N is a null player if vpS Y tiuq " vpSq for every coalition S Ď N ztiu. A game pN, vq is superadditive if, for all A, B P 2 N such that A X B " H, vpA Y Bq ě vpAq `vpBq.
For any given subset H " S Ď N , the unanimity game pN, u S q is defined by

u S pAq " # 1 if A Ě S, 0 otherwise.
Let us consider a game pN, vq. For arbitrary subsets A and B of N , we define the value ∆vpA, Bq :" vpA Y Bq `vpA X Bq ´vpAq ´vpBq.

A game pN, vq is convex if its characteristic function v is supermodular, i.e., ∆vpA, Bq ě 0 for all A, B P 2 N . Shapley (1953b) proved that every cooperative game pN, vq can be written as a unique linear combination of unanimity games, v " ř SĎN λ S pvqu S , where λ H pvq " 0, and for any S " H the coefficients λ S pvq P R are given by λ S pvq " ř T ĎS p´1q s´t vpT q. We refer to these coefficients λ S pvq as the unanimity coefficients1 of v.

Shapley value

The Shapley value of pN, vq is a solution concept. In terms of the unanimity coefficients the Shapley value is given by

Φ i pvq " ÿ SĎN : iPS 1 s λ S pvq,
for all i P N . It is equivalent to say that the Shapley value associated to a game pN, vq is a linear function and that the allocation associated to the unanimity game of set S is

x i " $ & % 1 s , if i P S, 0 otherwise.
Hence, the agents in S share the utility of 1 in equal shares.

Another definition is based on the following story. Consider that all the players are in the room. At every stage, one player is chosen uniformly among the remaining players and leaves the room. When leaving, he obtains as payoff its marginal contribution between when he was present and when he was not anymore. The Shapley value is its expected payoff. Formally, let L be the set of ordered sequences, then define U to be the uniform distribution over L. Then Φ i pvq " E U pvptL ě iuq ´vptL ą iuqq ,

where tL ě iu (resp. tL ą iu) is the set of agents (resp. strictly) after i in the list L, i.e. tj P N, Lpjq ě Lpiqu (resp. tj P N, Lpjq ą Lpiqu).

Let us justify this alternative definition. First, the right-hand side is indeed a linear function of v. Second, let us consider the unanimity game pN, u S q. Given an order L, we define the pivot of S the first occurence of an element of S. Formally, it is the element i of S such that Lpiq is minimal. By definition of u S , the marginal contribution of an agent is equal to 1 if and only if this agent is a pivot. Hence E U pu S ptL ě iuq ´uS ptL ą iuqq " P U pi is pivot of Sq " 1 s

By symmetry of U , the probability for i to be the pivot of S is 1 s giving the result. Shapley (1953b) showed that the Shapley value of a convex game belongs to the core. Looking for a weaker condition insuring that the Shapley value of a game lies in the core, [START_REF] Iñarra | The shapley value and average convex games[END_REF] relaxed the convexity assumption by introducing the notion of average convexity.

Definition 1. The game pN, vq is average convex if for every S Ă T Ď N , ÿ iPS pvpSq ´vpSztiuqq ď ÿ iPS pvpT q ´vpT ztiuqq .

They obtained the following result.

Proposition 1 [START_REF] Iñarra | The shapley value and average convex games[END_REF]; [START_REF] Sprumont | Population monotonic allocation schemes for cooperative games with transferable utility[END_REF] 2 ). If the game is average convex then the Shapley value is in the core.

3 Weighted Shapley Value and weighted convexity

Weighted Shapley Value

The notion of Shapley value was then extended in Shapley (1953a) and in [START_REF] Kalai | On weighted shapley values[END_REF] to weighted Shapley value. In the first one, the weight of each player is strictly positive whereas in the second one, a player may have a null weight. It is then necessary to define a weight system to describe how the players with a zero weight would share their contributions when only them are present. Formally, a weight system is a pair pω, Σq where ω P R N ``and Σ " pN 1 , ..., N m q is an ordered partition of N . It is called simple if Σ is equal to the singleton N . m will be the size of the partition. Given an element i in N , we define its priority denoted by ppiq as the unique integer such that i P N ppiq . Given a set S, we define the priority of S, denoted by ppSq, as the largest k P t1, ¨¨¨, mu such that N k X S ‰ H. Notice that this coincides with the previous definition if S is a singleton. Moreover, priority is a nondecreasing mapping. We also define S as the elements in S with the highest priority, i.e., S " ti P S, ppiq " ppSqu.

Definition 2. The weighted Shapley value with weight system pω, Σq is the unique function from the set of T U -games to allocation such that • it is linear,

• the allocation of the unanimity game on the set S is defined as follows: for all i P N ,

x i " $ & % ω i ř iPS ω i , if i P S, 0 otherwise.
In the previous definition, it is interesting to distinguish three sets of agents: S, S ´S and N ´S. In the unanimity game with set S,

• agents in N ´S are not contributing to obtain a positive payoff, hence they obtain 0,

• agents in S ´S are contributing to obtain a positive payoff but they have low priority, hence they obtain 0,

• agents in S are contributing to obtain a positive payoff and have the highest priority inside S, hence they share the total value of 1.

It is convenient for the following results to define the relative weight of the agents in the unanimity game on S. Given a set S, one defines for all i P N

ω S i " $ ' ' & ' ' % ω i if i P S,
0 if i P SzS, 0 if i R S.
We also define ω S as the sum for all i P S of ω S i . Notice that it is equal to the sum of the weights of elements in S. Moreover, the unanimity games on S and S lead to the same allocation vector.

Using the decomposition of a game into unanimity games, we obtain that the pω, Σqweighted Shapley value Φ ω of a game pN, vq is defined for all i P N by

Φ ω i pvq " ÿ SĎN : iPS ω S i ω S λ S pvq " ÿ SĎN : iPS ω i ω S λ S pvq.
The interesting case is if i is in S and not in S. It means that the priority of i is too low hence, he does not obtain a contribution.

Similarly to the classical Shapley value, a third interpretation can be given to the weighted Shapley value. Recall that L is the set of ordered sequences on N . Let P be a probability over L, one can define an allocation as follows: let

Ψ P i pvq " E P ´v`t L ě iu ˘´v `tL ą iu ˘¯.
When P is the uniform distribution, one obtains the classical Shapley value.

Let us now define a probability distribution P ω,Σ generating the pω, Σq-weighted Shapley value. We define it by induction:

• Let N be the agents with highest priority in N .

• Then Lp1q is equal to i with probability ω N i {ω N . In particular, it is strictly positive if and only if i has highest priority or equivalently i P N ,

• Given Lp1q fixed, pLp2q, ...., LpN qq are defined following the distribution associated to the projection of pω, Σq to N ztLp1qu.

In particular by construction, if i, j P N such that ppiq ą ppjq then the probability under P of an order L where j appears before i in the order is equal to 0.

Proposition 2. Given N and P ω,Σ , then Ψ P ω,Σ pvq is equal to the pω, Σq-weighted Shapley value Φ ω .

Proof. Proof in Appendix A.

Weighted-convexity

In a similar way than the notion of Shapley value has been extended to weight systems, one can extend the notion of average convexity.

Definition 3. Let pω, Σq be a weight system, we say that the game is pω, Σq-convex if for every S Ă T Ď N , ˜ÿ iPS ω i T pvpT q ´vpT ztiuq ´vpSq `vpSztiuqq ¸ě 0 (1)

In particular, notice that if ppSq ă ppT q, then for every i P S, ω T i " 0 and the corresponding inequality is satisfied by any game. If Σ " tN u and if all weights are equal, then pω, Σq-convexity corresponds to average-convexity. Let us also note that if a game is convex then it is pω, Σq-convex for any weight system pω, Σq.

Remark 1. If the game pN, vq contains null players then we can restrict condition (1) to coalitions S and T excluding null players. We first argue that one can exclude null players from S and then from T . If i P S is a null player then vpT q ´vpT ztiuq ´vpSq `vpSztiuq " 0, hence its contribution is zero. Thus we can assume S without null player. Now, let T 1 be the set of null players in T . By the previous sentence, we know that S Ă T zT 1 . There are two cases:

• if ppT q ą ppT zT 1 q, then w i T " 0 for all i in S. Element of S have a too low priority and the inequality is trivially satisfied and can be forgotten.

• if ppT q " ppT zT 1 q, then one can replace T by T zT 1 .

Results

One obtains the following theorem which extends the result of [START_REF] Iñarra | The shapley value and average convex games[END_REF].

Theorem 1. Let ω P R N ``and Σ be a partition. If the game is pω, Σq-convex then its pω, Σq-weighted Shapley value is in the core.

The first part of the proof is inspired from [START_REF] Sprumont | Population monotonic allocation schemes for cooperative games with transferable utility[END_REF]. Let pN, vq be a given game. For any non-empty coalition T Ď N , we denote by v T the subgame of v induced by T , i.e., v T pSq " vpSq for any S Ď T . Let Φ ω pv T q be the pω, Σq-weighted Shapley value of the subgame v T . Define the vector Ψ ω " pΨ ω iT q iPT,T PPpN q recursively by

Ψ ω iT " ω T i ω T pvpT q ´vpT ztiuqq `ÿ jPT ztiu ω T j ω T Ψ ω iT ztju ,
for all i P T , T P PpN q, and setting Ψ ω iH " 0 for all i P N .

Proposition 3. For all T P PpN q, pΨ ω iT q iPT " Φ ω pv T q.

Proof. Proof in Appendix B.

As a consequence, one obtains the following result.

Proposition 4. Let us denote by Φ ω T the pω, Σq-weighted Shapley value of v T . We have

Φ ω iT " ω T i ω T pvpT q ´vpT ztiuqq `ÿ jPT ztiu ω T j ω T Φ ω iT ztju ,
for all i P T .

Let us now prove the main result.

Proof of Theorem 1. We do a proof by induction. If n " 1, the result is true. Let n ą 1 and assume that for all pω, Σq-convex games of size n ´1, the result is true. Let us consider a pω, Σq-convex game v of size n. We check the condition for Φ ω to be in the core. Let T be a subset of N . By Proposition 3 and by definition of Ψ ω , we get

ÿ iPT Φ ω i pvq " ÿ iPT Ψ ω iN , " ÿ iPT ¨ωN i ω N pvpN q ´vpN ztiuqq `ÿ kPN, k‰i ω N k ω N Ψ ω iN zk ', " 1 ω N ¨ÿ iPT ω N i pvpN q ´vpN ztiuqq `ÿ kPN ω N k ¨ÿ i‰k, iPT Ψ ω iN zk '' . ( 2
)
By Proposition 3, we have Φ ω pv N zk q " pΨ ω iN zk q iPN zk and by the induction assumption, Φ ω pv N zk q belongs to the core of v N zk . We distinguish two cases for the sum ř i‰k, iPT Ψ ω iN zk :

• If k P T , then one sum for all i P T zk and by induction assumption

ÿ i‰k, iPT Ψ ω iN zk ě vpT zkq. (3)
Let us note that ( 3) is satisfied at equality for T " N .

• If k R T , then one sum for all i P T and by induction assumption

ÿ i‰k, iPT Ψ ω iN zk ě vpT q. ( 4
)
If T " N , then ( 2) and ( 3) imply ř iPN Φ ω i pvq " vpN q. Let now T be a strict subset of N . By ( 2),(3), and (4), one obtains

ÿ iPT Φ ω i pvq ě 1 ω N ¨ÿ iPT ω N i pvpN q ´vpN ztiuqq `ÿ kPT ω N k vpT zkq `ÿ kPN, kRT ω N k vpT q '.
Finally, the assumption of pω, Σq-convexity implies

ÿ iPT Φ ω i pvq ě 1 ω N ¨ÿ iPT ω N i pvpT q ´vpT ztiuqq `ÿ kPT ω N k vpT zkq `ÿ kPN, kRT ω N k vpT q '.
We now see that the terms vpT ztiuq are compensated by vpT ztkuq, whereas the terms vpT q are accumulated with a total weight of w N , hence

ÿ iPT Φ ω i pvq ě vpT q.

Link between pω, Σq-convexity and superadditivity

It is well known that average-convexity implies superadditivity [START_REF] Iñarra | The shapley value and average convex games[END_REF]). We prove that pω, Σq-convexity also implies superadditivity when Σ " tN u. We first establish a more general result with possibly different priorities which will be also useful in Section 5.

Proposition 5. Let pN, vq be an pω, Σq-convex game. Let us consider S, T, U Ď N such that S X T " H, U Ď T and for all s P S, ppsq ą ppU q and ppsq ě ppT q then vpS Y T q ´vpT q ě vpS Y U q ´vpU q.

(5)

Proof. The proof is by induction on |S|. If |S| " 1, then we set S " tiu and pω, Σq-convexity applied to

S 1 " tiu Y U Ď T 1 " tiu Y T implies ω T 1 i pvptiu Y T q ´vpT qq ě ω T 1 i pvptiu Y U q ´vpU qq.
By assumption on the priorities, we have ppiq " ppT 1 q hence ω T 1 i ą 0 and one can divide the inequality by ω T 1 i ą 0. We obtain that ( 5) is satisfied for |S| " 1. Let k be a given integer with k ě 1. Let us assume (5) satisfied for any triple S, T, U Ď N such that S X T " H, U Ď T , and for all s P S, ppsq ą ppU q, ppsq ě ppT q, and |S| " k. Let us consider S, T, U Ď N such that S X T " H, U Ď T , and for all s P S, ppsq ą ppU q, ppsq ě ppT q, and |S| " k `1. Let us set w.l.o.g. S " t1, 2, . . . , k `1u. pω, Σq-convexity applied to

S Y U Ď S Y T implies k`1 ÿ i"1 ω T YS i pvpS Y T q ´vppSztiuq Y T qq ě k`1 ÿ i"1 ω T YS i pvpS Y U q ´vppSztiuq Y U qq . (6)
We do not need to consider other element in S Y U since all elements of U have too low priorities. By induction hypothesis, we have vppSztiuq Y T q ´vpT q ě vppSztiuq Y U q ´vpU q, for all i P t1, 2, . . . , k `1u. Multiplying each inequality by ω T YS i and adding them to (6), we get

k`1 ÿ i"1 ω T YS i pvpS Y T q ´vpT qq ě k`1 ÿ i"1 ω T YS i pvpS Y U q ´vpU qq. (7)
This implies (5) and proves the result at the next step of the induction. By the principle of induction, the result is true for every set S.

We obtain as a particular result that the value function v is superadditive if there exists only one partition.

Corollary 1. Let pN, vq be an pω, Σq-convex game such that Σ " tN u, then v is superadditive.

Proof. Let us consider S, T Ď N such that S X T " H. Taking U " H, the conditions of Proposition 5 are satisfied for any pair of sets. We obtain vpS Y T q ´vpT q ě vpSq ´vpHq.

(8)

The game is superadditive.

4 Weighted-convexity and Communication game : The singleton case

We now consider TU-games with a communication graph G " pN, Eq. Let pN, vq be a TUgame. We define its restriction to the communication graph G " pN, Eq as the TU-game with characteristic function

v G pSq " ÿ APC G pSq vpAq,
where C G pSq is the set of all connected components of the induced graph pS, E S q where only nodes in S and edges with both end-nodes in S remained.

Definition 4. Let pω, Σq be a weight system. We say that a graph G " pN, Eq preserves the pω, Σq-convexity if for every game pN, vq that is pω, Σq-convex then the communication game pN, v G q is also pω, Σq-convex.

We want to investigate what type of graph preserves the pω, Σq-convexity as a function of ω and Σ. [START_REF] Slikker | Average Convexity in Communication Situations[END_REF] shows that a connected communication graph preserves average convexity if and only if it is a complete graph or a star. If the graph is not connected, the condition becomes for each connected component to be a complete graph or a star. In our formalism, it corresponds to the case where Σ " tN u and ω is a constant vector. In order to prove this result, he shows that a graph G preserving average convexity has to satisfy the following conditions:

1. G has to be cycle-complete and, 2. G cannot contain the following subgraphs: a 4-path and a 3-pan.

The formal definitions of these notions are the following.

Definition 5. We say that a cycle C " tv 1 , e 1 , v 2 , e 2 , . . . , v m , e m , v 1 u in a graph G " pN, Eq is complete (resp. non-complete) if the subset tv 1 , v 2 , . . . v m u Ď N of nodes of C induces a complete (resp. non-complete) subgraph in G. A graph G " pN, Eq is cycle-complete if any cycle C in G is complete.
Definition 6. A graph G " pN, Eq admits a 4-path subgraph if there exist i, j, k, l P N such that

• ti, ju, tj, ku, tk, lu P E

• any other link between ti, j, k, lu is absent:

A graph G " pN, Eq admits a 3-pan subgraph if there exists i, j, k, l P N such that • ti, ju, tj, ku, tk, iu P E and tl, iu P E

• any other link between ti, j, k, lu is absent:

Notice that in both cases, j and k have degree 2 in the subgraph induced by ti, j, k, lu.

A 4-path and a 3-pan are represented in Figures 1a and1b respectively. Let us start with the simple case where Σ is a singleton, i.e., Σ " tN u. Then all players have the same priority and we will prove that we obtain the same characterization as Slikker (1998) for inheritance of average convexity. Let us note that, as all players have the same priority, we have ω i T " ω i for any player i P T Ď N throughout this section. Hence, the difference with [START_REF] Slikker | Average Convexity in Communication Situations[END_REF] is the non homogeneity of the weights. Figure 1 Theorem 2. Let G " pN, Eq be a connected graph and let pω, Σq be a weight system with Σ " tN u. Then the following properties are equivalent.

1. G preserves pω, Σq-convexity.

(a) G is cycle-complete.

(b) There is no restricted subgraph that is a 4-path or a 3-pan.

3. G is a complete graph or a star.

The equivalence between Conditions 2 and 3 in Theorem 2 was already established in [START_REF] Slikker | Average Convexity in Communication Situations[END_REF].

Remark 2. In fact, it is enough to establish the necessity of Condition 2a (resp. Condition 2b) in Theorem 2 for a graph that is exactly a non-complete cycle (resp. a 4-path or a 3-pan). For a graph containing one of these graphs as subgraph, one can consider a game where only agents involved in the specific subgraph contribute to the utility and all remaining agents are null players. By Remark 1, such a game is pω, Σq-convex if its restriction to players in the non-complete cycle (resp. 4-path or 3-pan) is pω, Σq-convex.

Let us establish three intermediate results before proving Theorem 2: a counter-example if the graph is not cycle-complete, a counter-example if the graph is a 3-pan (or a 4-path) and a proposition for stars.

Example 1 (Weighted Non-complete cycle). Let C " t1, e 1 , 2, e 2 , . . . , m, e m , 1u be a noncomplete cycle in G and let l ˚be a node of C. Let j and k be the neighbors of l ˚in C and let us assume tj, ku R E. We consider the convex game pN, vq defined by vpSq " |S| ´1 for all S Ď N , S " H. As pN, vq is convex, it is also pω, Σq-convex for any weight system pω, Σq. Let us consider S " tj, l ˚, ku and T " V pCq as represented in Figure 2. We get

ÿ iPS ω i pv G pSq ´vG pSztiuqq " ω j `2ω l ˚`ω k ą ω j `ωl ˚`ω k " ÿ iPS ω i pv G pT q ´vG pT ztiuqq.
This contradicts pω, Σq-convexity of the communication game pN, v G q.

13 Documents de travail du Centre d'Economie de la Sorbonne 2022.16

j 1 l m k Figure 2: Non-complete cycle C, tj, ku R E.
As a Corollary of this example, one recovers the necessity for the graph to be cyclecomplete. Indeed, if the graph is not cycle-complete, one can consider the smallest cycle that is not complete. By minimality, there exists three nodes l ˚, j and k such that j and k are neighbors of l ˚in C and tj, ku R E. We choose the previous formulation since it will be closer to the general result with priorities. The second counter-example shows that a graph preserving pω, Σq-convexity cannot contain a 3-pan subgraph. Our example is different and much more general than the one given by [START_REF] Slikker | Average Convexity in Communication Situations[END_REF] for average convexity since it needs to take into account the different weights. We present the counter-example here and highlights only that the communication game is not weighted average convex. This counter-example will be also used later in a more general version when agents have different priorities. Checking all the inequalities to establish pω, Σq-convexity of the game will be done in the Appendix in the general case with priorities.

Moreover, we show thereafter that the game considered in this example also gives a contradiction to inheritance of pω, Σq-convexity if the graph contains a 4-path.

Example 2 (3-pan). Let us assume that there are only 4 nodes denoted by t1, 2, 3, 4u. The graph G is a 3-pan such that 4 has degree 2 as represented in Figure 3. We assume that all 4 1 2 3

Figure 3 nodes have the same priority. Let us prove that there is no conservation of pω, Σq-convexity.

We represent in Figure 4 the lattices of coalitions of t1, 2, 3, 4u ordered by inclusion for pN, vq and pN, v G q with the corresponding values. Let us state a few facts.

H 0 1 0 2 0 3 0 4 0 12 0 13 0 14 X 23 0 24 0 34 Y 123 0 124 X 134 XỲ ´1 234 Z N Θ (a) pN, vq. H 0 1 0 2 0 3 0 4 0 12 0 13 0 14 X 23 0 24 0 34 0 123 0 124 X 134 X 234 Z N Θ (b) pN, v G q.
Figure 4

The game pN, vq is not convex but is pω, Σq-convex A detailed proof for the general case with priorities is provided in Appendix C. The communication game pN, v G q on the 3-pan is not pω, Σq-convex:

Let us insist on the the coalitions whose value changed compared to the original game pN, vq

• the value of t3, 4u changes from Y to 0 hence loosing Y ,

• the value of t1, 3, 4u changes from X `Y ´1 to X hence loosing Y ´1.

The key element is to notice that the value of t1, 3, 4u is loosing less than the value of t3, 4u which allows for a contradiction to pω, Σq-convexity. Let us prove that pN, v G q is not pω, Σq-convex. We consider S " t2, 3, 4u and T " N :

ÿ iPS ω i pv G pSq ´vG pSziqq " pω 2 `ω3 `ω4 qZ, (9)
whereas ÿ iPS ω i pv G pT q ´vG pT ziqq " ω 2 pΘ ´Xq `ω3 pΘ ´Xq `ω4 pΘ ´0q, " pω 2 `ω3 `ω4 qZ ´ω2 ´ω3 `ω4 pX ´1q.

By definition of X, we have either ´ω2 `ω4 pX ´1q " 0 or ´ω3 `ω4 pX ´1q " 0. As ω 2 ą 0 and ω 3 ą 0, we get in both cases ÿ iPS ω i pv G pT q ´vG pT ziqq ă ÿ iPS ω i pv G pSq ´vG pSziqq, a contradiction to pω, Σq-convexity.

Remark 3. Although Example 2 is designed for a 3-pan, it is also valid for a 4-path. Let us consider the 4-path corresponding to t1, 4, 2, 3u as represented in Figure 5. In this case,

1 4 2 3
Figure 5: 4-path t1, 4, 2, 3u.

the communication game is equal to the previous game v G associated with the 3-pan. Indeed, starting from a game pN, vq, the only differences between the communication games associated with the specified 3-pan and 4-path are potentially the values of t1, 2, 3u and t1, 2u. In the 3-pan, it is equal to the value vpt1, 2, 3u (resp. vpt1, 2u) whereas in the 4-path it is equal to vpt1uq `vpt2, 3uq (resp. vpt1uq `vpt2uq). By construction, these values are all equal to 0 in Example 2, hence it is also a counter-example to inheritance of pω, Σq-convexity for a 4-path.

Remark 4. In order to obtain a counter-example for another 3-pan or 4-path, one exchange the role of the players.

Finally, [START_REF] Slikker | Average Convexity in Communication Situations[END_REF] established that there is always inheritance of average-convexity if the underlying graph is a star. It can be easily seen that this result is more generally valid for pω, Σq-convexity if Σ " tN u. Proposition 6. A star graph preserves pω, Σq-convexity for any weight system pω, Σq with Σ " tN u.

We omit the proof of Proposition 6 as the result can be straightforwardly obtained from the proof given in Slikker (1998)3 replacing average convexity by pω, Σq-convexity.

We can now prove Theorem 2.

Proof of Theorem 2. 3 ñ 1 Let us consider a graph G " pN, Eq corresponding to a star or a complete graph and let pN, vq be an pω, Σq-convex game. If G is complete then v G " v and pN, v G q is pω, Σq-convex. If G is a star, then pN, v G q is also pω, Σq-convex by Proposition 6. 1 ñ 2 By the previous examples, a graph preserving pω, Σq-convexity has to be cyclecomplete and it cannot contain any 4-path or 3-pan.

2 ñ 3 Following Slikker (1998)4 , we know that the only connected cycle-complete graphs that do not contain any 4-path or 3-pan are the star and the complete graphs.

As the characterization given in Theorem 2 is the same established by [START_REF] Slikker | Average Convexity in Communication Situations[END_REF] for inheritance of average convexity, we get that the class of graphs preserving pω, Σq-convexity is equal to the class of graphs preserving average convexity when Σ " tN u .

Corollary 2. Let G " pN, Eq be a connected graph. The following properties are equivalent:

1. G preserves average convexity.

2. G preserves pω, Σq-convexity for any weight system with Σ " tN u.

Weighted convexity and Communication game: The case with several priorities

The situation with several priorities is much more complex. We will see that the previous conditions are also necessary in the presence of priorities but only for specific subgraphs of G.

In particular, whereas in Slikker (1998) all nodes have the same behavior, it is not the case anymore and we will need to precise the role of each node in each configuration. We will start by presenting examples similar to Examples 1 and 2 where priorities are now taken into account. Then, we deduce from these examples some necessary conditions on the structure of the graphs. Finally, we provide a complete characterization in the special case of tree graphs satisfying the additional condition that the priorities are inducing a hierarchy in the trees.

Examples with priorities

Cycles and Chords

The first example focuses on cycles. We show that the neighbors of a node with maximal priority in any cycle have to be linked.

Example 3 (Weighted Non-complete cycle with priorities). Let C " t1, e 1 , 2, e 2 , . . . , m, e m , 1u be a non-complete cycle in G and let l ˚be a node of C satisfying ppl ˚q " ppV pCqq.

Let j and k be the neighbors of l ˚in C and let us assume tj, ku R E. We consider the convex game pN, vq defined by vpSq " |S| ´1 for all S Ď N , S " H. As pN, vq is convex, it is also pω, Σq-convex for any weight system pω, Σq. Let us consider S " tj, l ˚, ku and T " V pCq as represented in Figure 6. We get

ÿ iPS ω T i pv G pSq ´vG pSztiuqq " ω T j `2ω T l ˚`ω T k ą ω T j `ωT l ˚`ω T k " ÿ iPS ω T i pv G pT q ´vG pT ztiuqq.
This contradicts pω, Σq-convexity of the communication game pN, v G q as ppl ˚q " ppT q.

3-pan

The aim of this section is to exhibit a counter-example for the 3-pan as depicted in Figure 3 under the following condition on the priorities:

pp2q ě maxppp1q, pp4qq ě pp3q. (11)
The counter-example is the following.

Example 4 (3-pan). Let us assume that there are only 4 nodes denoted by t1, 2, 3, 4u. The graph is a 3-pan such that 4 has degree 2 as represented in Figure 7. We assume pp2q ě pp4q, pp4q ě pp1q and pp4q ě pp3q. Let us prove that there is no conservation of pω, Σq-convexity. Let us define

X " max ˆ1 `ω2 ω 4 , 1 `ω3 ω 4 ˙, Y " 1 `ω1 ω 4 , Z " X `2Y `p1 ´αp q " ω 1 ω 2 `ω3 `ω4 X ´ω1 ω 4  , Θ " Z `X ´1,
where Figure 8

α p " # 1 if pp2q " pp4q ą pp3q, 0 otherwise.
The communication game pN, v G q on the 3-pan is not pω, Σq-convex: Let us insist on the coalitions whose value changed compared to the original game pN, vq

• the value of t3, 4u changes from Y to 0 hence loosing Y ,

• the value of t1, 3, 4u changes from X `Y ´1 to X hence loosing Y ´1.

The key element is to notice that the value of t1, 3, 4u is loosing less than the value of t3, 4u which allows for a contradiction to pω, Σq-convexity. Let us consider S " t2, 3, 4u and T " N :

ÿ iPS ω T i pv G pSq ´vG pSziqq " ω T 2 pZ ´0q `ωT 3 pZ ´αp Y q `ωT 4 pZ ´0q, (12)
Let us first assume pp4q ă ppN q. Then we have ω T 4 " 0 and get a contradiction as pp2q " ppN q. Let us now assume pp4q " ppN q. By assumption and as α p " 0, we also have pp3q " ppN q. Then, by definition of X, we get either ´ωT 2 `ωT 4 pX ´1q " ´ω2 `ω4 pX ´1q " 0 or ´ωT 3 `ωT 4 pX ´1q " ´ω3 `ω4 pX ´1q " 0. In both cases we still obtain a contradiction.

By symmetry of 1 and 4, interverting 1 and 4 in Example 4, we also get a contradiction if maxppp1q, pp4qq " pp1q. Thus we have a contradiction on the 3-pan for any weight system satisfying (11).

Remark 5. Example 4 can be extended to the 4-path if α p " 0 but not if α p " 1. Let us consider the 4-path corresponding to t1, 4, 2, 3u as represented in Figure 9. Starting from a game pN, vq, the only differences between the communication games associated with the specified 3-pan and 4-path are the values of t1, 2, 3u and t1, 2u. In the 4-path, the value of coalition t1, 2, 3u (resp. t1, 2u) is equal to vpt1uq `vpt2, 3uq " 0 (resp. vpt1uq `vpt2uq " 0). ( 12) is not modified and ( 13) becomes

ÿ iPS ω T i pv G pT q ´vG pT ziqq " ω T 2 pΘ ´Xq `ωT 3 pΘ ´X ´αp pY ´1qq `ωT 4 pΘ ´0q " ω T 2 pZ ´1q `ωT 3 pZ ´αp Y ´p1 ´αp qq `ωT 4 pZ `X ´1q. ( 16
)
If α p " 0, then ( 12) and ( 16) are equivalent to ( 14) and ( 15) and we get the same contradiction as before. If α p " 1, then we would need ω 2 ą ω 4 pX ´1q to get a contradiction. This is not possible as X ě 1 `ω2 ω 4 by definition.

4-path

The aim of this section is to exhibit a counter-example for the 4-path as represented in Figure 9 under the following condition on the priorities:

1 4 2 3
Figure 9: 4-path t1, 4, 2, 3u.

minppp2q, pp4qq ě maxppp1q, pp3qq.

Depending on the precise order of priorities, several counter-examples are necessary.

• Assume that pp2q ą pp4q ě maxppp1q, pp3qq.

By Remark 5 and as α p " 0, Example 4 provides a counter-example.

• Assume that pp2q " pp4q " maxppp1q, pp3qq.

We have two cases that are similar up to permutation of the roles. If pp3q ě pp1q, then Example 4 still provides a counterexample by Remark 5 and as α p " 0. If pp1q ą pp3q, one can intervert at the same time the role of 2 and 4 and the role of 1 and 3 to obtain a counterexample.

• Finally, assume that pp2q " pp4q ą maxppp1q, pp3qq.

One needs a new counter-example. Example 5 will be our counter-example.

By symmetry of 2 and 4, one obtains a counterexample for any weight system satisfying (17).

Example 5. We consider the following game pN, vq and the communication game pN, v G q induced by pN, vq and the communication structure given by G.

vpSq " 4u, t1, 2, 4u, t1, 3, 4u, t2, 3, 4u, N u, 0 otherwise.

$ & % 1 if S P tt1, 4u, t3, 4u, t1, 2, 4u, t1, 3, 4u, t2, 3, 4u, N u, 0 otherwise. v G pSq " $ & % 1 if S P tt1,
We represent in Figure 10 the lattices of coalitions of t1, 2, 3, 4u ordered by inclusion for pN, vq and pN, v G q with the corresponding values. Figure 10

We establish the following facts under the assumption that pp2q " pp4q ą maxppp1q, pp3qq. The game pN, vq is not convex but pω, Σq-convex: See the proof in Appendix D. The communication game pN, v G q is not pω, Σq-convex:

Let us insist on the coalitions whose value changed compared to the original game pN, vq

• the value of t3, 4u changes from 1 to 0,

• the value of t1, 2, 3u (resp. t1, 3, 4u) becomes equal to the value of t2, 3u (resp. t1, 4u) and therefore stays equal to 0 (resp. 1).

Let us prove that pN, v G q is not pω, Σq-convex. We consider S " t2, 3, 4u and T " N :

ÿ iPS ω T i pv G pSq ´vG pSziqq " ω T 2 `ωT 3 `ωT 4 , whereas ÿ iPS ω T i pv G pT q ´vG pT ziqq " ω T 2 p1 ´1q `ωT 3 p1 ´1q `ωT 4 p1 ´0q " ω T 4 .
As pp2q " ppN q ą pp3q, we have ω T 3 " 0 but ω T 2 " 0 implying a contradiction to pω, Σqconvexity of pN, v G q.

Necessary conditions

We now establish several necessary conditions based on the previous counter-examples and the result for the singleton partition. Example 3 implies directly the following result.

Lemma 1. Let pω, Σq be a weight system and let G " pN, Eq be a graph preserving pω, Σqconvexity. Let C be a cycle in G and let j be a node of C. Let i and k be neighbors of j in C. If ppjq " ppV pCqq then ti, ku P E. Remark 6. Let us note that if all nodes in C have the same priority then Lemma 1 implies cycle-completeness of C.

Based on the previous section on singleton partition, a necessary condition is for each level of priority to be composed of disjoint complete subgraphs or stars.

Proposition 7. If a graph pN, Eq preserves the pω, Σq-convexity, given a priority k, the set of players of priority k corresponds to a collection of disconnected star/complete subgraphs.

The proof relies on showing that there exists no non-complete cycle, no 3-pan, and no 4-path but not directly in the original graph but in a family of graphs constructed by taking into account the different priorities.

Proof. Fix a priority k and N k the set of players in layer k. If the connected components of G k are not complete graphs or stars, then G k contains a subgraph Gk corresponding to a non-complete cycle or a 4-path or a 3-pan. We can consider one of the games defined in Examples 1 or 2 and extend it to N by taking all remaining players as null players. By Remark 1, the resulting game is pω, Σq-convex. As all nodes of Gk belong to the same layer, we still get a contradiction to pω, Σq-convexity of the communication game as in the case of a single partition.

Remark 7. Let us insist that when restricting to the set of players in layer k, one can loose the connectivity. Hence a priori the set of players of priority k may be composed of several stars and/or complete subgraphs.

Moreover the connection between two such components in different layers depends on the type of the component of larger priority.

Proposition 8. Let pω, Σq be a weight system and pN, Eq be a graph preserving the pω, Σqconvexity. If a player s of priority k is connected to a player a in a layer with higher priority then one of the following statements is satisfied • a is part of a complete component K in the graph restricted to its priority and s is then connected to each node of K,

• a is the center of a star S in the graph restricted to its priority and s cannot be linked to any leaf of S if |V pSq| ě 3.

Remark 8. Connected component with one or two nodes play special roles. Indeed a connected component of size one is at the same time a star with no leaf and a complete component. Similarly, a connected component of size two is at the same time a star centered on one of the two nodes, a star centered on the second one and a complete component.

Proof. Let s be a player of priority k connected to a player a of priority k 1 ą k. Let C a be the connected component of G k 1 containing a. By Proposition 7, it is necessarily a star or a complete component. We can assume that C a contains at least three nodes otherwise Proposition 8 is trivially satisfied. By contradiction, let us assume that a is not the center of a star and not part of a complete component. Then C a is a star and a is a leaf of this star. Let c be the center of C a and let b " a be another leaf. Then ts, a, c, bu corresponds to a path in G (but not necessarily a 4-path as some more edges between nodes s, a, c, b could exist). As C a is a star, there is no edge linking a and b. We now distinguish several cases:

• Let us assume s non-connected to b. If s is not connected (resp. connected) to c then ts, a, c, bu corresponds to a 4-path (resp. 3-pan) as represented in Figure 11a (resp.

Figure 11b) and one can use Example 4 to get a contradiction (s playing the role of 1).

• Let us now assume s connected to b. If s is not connected (resp. connected) to c, then we have a non-complete cycle as represented in Figure 12a (resp. Figure 12b) and Example 3 gives a contradiction considering c as the key node with high priority.

Let us now turn to the case where C a is a complete component. • Assume that there is exactly one node in C a that is not linked to s denoted by t. Let b be a node of C a different from a and t as represented in Figure 13a. Then ts, a, t, b, su corresponds to a non-complete cycle (as ts, tu R E) and Example 3 gives a contradiction with a as the key node with high priority. • Assume that there exist at least two nodes b and c in C a that are not linked to s as represented in Figure 13b. Then ts, a, b, cu corresponds to a 3-pan where s has degree 1, and Example 4 gives a contradiction where s plays the role of 3 with a strictly lower priority.

We now investigate how the presence of other layers impact what happens on a layer of priority k. We establish that if a graph preserves pω, Σq-convexity, then there are important restrictions on connected components simultaneously linked to a connected component lying in a higher layer.

Proposition 9. Let pω, Σq be a weight system with at least two priority levels and let G " pN, Eq be a graph preserving pω, Σq-convexity. Let k, k 1 , k 2 be priority levels with

k ď k 1 ă k 2 . Let C 1 (resp. C 2 ) be a connected component of G k (resp. G k 1 ) linked to a connected component C of G k 2 .
Then the following statements are satisfied:

1. There exists a node i in C such that C 1 and C 2 are both linked to i. (e) There is no path linking C 1 to C 2 that does not pass through c.

3. If there exists a link between C 1 and C 2 , then we have k ă k 1 and there exists a node j 1 (resp. j 2 ) in C 1 (resp. C 2 ) such that ti, j 1 , j 2 , iu is a triangle. Moreover, any component C 3 linked to C belonging to a layer with priority l ď k 1 is linked to j 1 and j 2 and we necessarily have l R tk, k 1 u.

Proof. Let us consider C 1 and C 2 linked to C. 1 Let us assume that C 1 and C 2 are not linked to a common node in C. Then, by Proposition 8, C is necessarily a star of size 2. Let i 1 , i 2 be the two distinct nodes of C and let j 1 (resp. j 2 ) be a node in C 1 (resp. C 2 ) such that ti 1 , j 1 u P E (resp. ti 2 , j 2 u P E) as represented in Figure 14. tj 1 , i 2 u and tj 2 , i 1 u cannot exist otherwise C 1 and C 2 would be

i 1 i 2 j 1 j 2 k 2 k 1 k Figure 14: k ď k 1 ă k 2 .
linked to a common node in C. If tj 1 , j 2 u R E, then tj 1 , i 1 , i 2 , j 2 u corresponds to a 4-path where i 1 and i 2 have highest priority and Example 5 gives a contradiction to inheritance of pω, Σq-convexity. If tj 1 , j 2 u P E, then tj 1 , i 1 , i 2 , j 2 u corresponds to a 4-cycle where i 1 and i 2 have highest priority and Example 3 implies tj 1 , i 2 u P E and tj 2 , i 1 u P E, a contradiction.

2 We assume that there is no link between C 1 and C 2 . 2a By contradiction, let us assume that C 2 is not a singleton. Let i be a node in C and j 1 (resp. j 2 ) be a node in C 1 (resp. C 2 ) such that ti, j 1 u P E (resp. ti, j 2 u P E). As |V pC 2 q| ě 2, there exists a node l 2 " j 2 in C 2 such that tj 2 , l 2 u P E. If ti, l 2 u R E (resp. ti, l 2 u P E), then there exists a 4-path (resp. 3-pan) as represented in Figure 15a (resp. Figure 15b) with ppiq ą ppj 2 q " ppl 2 q ě ppj 1 q. Then Example 4 gives a contradiction to inheritance of

i j 1 j 2 l 2 k 2 k 1 k (a) ti, l 2 u R E. i j 1 j 2 l 2 k 2 k 1 k (b) ti, l 2 u P E. Figure 15: k ď k 1 ă k 2 .
pω, Σq-convexity. Thus C 2 is a singleton.

2b Let us prove that C is necessarily a star and that C 2 is linked only to the center of C. Let us first consider |V pCq| " 2. Let us set V pCq " ti 1 , i 2 u. By Statement 1, we can assume w.l.o.g. that j 1 and j 2 are both linked to i 1 . If j 1 is linked (resp. non linked) to i 2 and j 2 non linked (resp. linked) to i 2 as represented in Figure 16a (resp. Figure 16b) then ti 1 , j 2 , i 2 , j 1 u corresponds to a 3-pan and Example 4 gives a contradiction. If j 1 and j 2 are linked to i 2 as represented in Figure 16c then ti 1 , j 2 , i 2 , j 1 , i 1 u corresponds to a non-complete cycle and

i 1 i 2 j 1 j 2 k 2 k 1 k (a) tj 1 , i 2 u P E. i 1 i 2 j 1 j 2 k 2 k 1 k (b) tj 2 , i 2 u P E. i 1 i 2 j 1 j 2 k 2 k 1 k (c) tj 1 , i 2 u P E and tj 2 , i 2 u P E. Figure 16: k ď k 1 ă k 2 , C 2 singleton, C 2 " tj 2 u.
Example 3 gives a contradiction. By considering that C is a star with center c " i 1 , we get the result. Let us now consider |V pCq| ě 3. Let us assume that C is a complete component. By Proposition 8, j 1 and j 2 are linked to all nodes of C. Let i 1 and i 2 be two nodes of C. Then ti 1 , i 2 , j 1 , j 2 u corresponds to a non-complete cycle as in Figure 16c and Example 3 still gives a contradiction. Finally, Proposition 8 implies that C is a star and that j 2 is only linked to its center c.

2c Let us now prove that C 1 is linked to C only at its center c. If |V pCq| ě 3, then Proposition 8 implies the result. Let us assume |V pCq| " 2 and let i 2 " c be the leaf node of C. If j 1 is linked to i 2 , then the situation is equivalent to the one represented in Figure 16a setting i 1 " c and we get the same contradiction as before. Let us assume |V pC 1 q| ě 2 and let us consider j 3 P V pC 1 q with j 3 " j 1 . Let us assume j 3 linked to i 2 as represented in Figure 17. As C 1 is connected, there exists a path P linking j 1 to j 3 . Then P Y tj 3 , i 2 , c, j

1 u i 2 c j 3 j 1 j 2 k 2 k 1 k Figure 17: k ď k 1 ă k 2 , C 2 singleton, C 2 " tj 2 u.
corresponds to a cycle. As ppcq " k 2 , Example 3 implies tj 1 , i 2 u P E, a contradiction.

2d Let us now prove that C 2 cannot be linked to components in lower layers. By contradiction, let C 3 be a connected component in a layer with priority lower than k 1 linked to C 2 . Let j 3 be a node in C 3 such that tj 2 , j 3 u P E. Let us first assume tc, j 3 u R E. If tj 1 , j 3 u P E (resp. tj 1 , j 3 u R E), then tj 1 , c, j 2 , j 3 u corresponds to a non-complete cycle (resp. a 4-path) as represented in Figure 18a (resp. Figure 18b) where c has highest priority and Example 3 (resp. Example 4) gives a contradiction. Let us now assume tc, j 3 u P E. Then we have either a non-complete cycle or a 3-pan and we get contradictions as in the previous case.

c j 1 j 2 j 3 k 2 k 1 k l (a) tj 1 , j 3 u P E. c j 1 j 2 j 3 k 2 k 1 k l (b) tj 1 , j 3 u R E.
2e By contradiction let us assume the existence of a path linking C 1 to C 2 and that does not pass through c. Then we can select a shortest path P linking j 1 to j 2 and not containing c. Then T " P Y tj 1 , c, j 2 u corresponds to a cycle. If ppcq " ppT q, then Example 3 implies tj 1 , j 2 u P E, a contradiction. Otherwise, let i 1 be a node of P satisfying ppi 1 q " ppT q. Let us note that we necessarily have i 1 R tj 1 , j 2 u as ppj 1 q " k ď k 1 " ppj 2 q ă k 2 " ppcq. Then Example 3 implies the existence of an edge linking the neighbors of i 1 in the path P . This contradicts the minimality of P .

3 Let us now assume the existence of a link between C 1 and C 2 . We necessarily have k ă k 1 . Let us consider i P C and j 1 P C 1 (resp. j 2 P C 2 ) with ti, j 1 u P E (resp. ti, j 2 u P E). Let us assume tj 1 , j 2 u R E. By the existence of a link between C 1 and C 2 , there exists a path P linking j 1 to j 2 and passing only through C 1 and C 2 as represented in Figure 19a. Example 3 applied with the cycle formed by ti, j 1 u Y P Y tj 2 , iu implies tj 1 , j 2 u P E, a contradiction. Therefore, we necessarily have tj 1 , j 2 u P E.

Let us assume C linked to a component C 3 different from C 1 and C 2 . Let us assume that

i j 2 j 1 k 2 k 1 k (a) tj 1 , j 2 u R E. i j 2 j 1 j 3 k 2 k 1 k l (b) tj 1 , j 2 u P E, l ď k 1 . i j 2 j 1 j 3 k 2 k 1 k l (c) tj 1 , j 2 u P E, l ď k 1 . Figure 19: k ă k 1 ă k 2 .
C 3 belongs to a layer with priority l ď k 1 . Let j 3 be a node of C 3 linked to i as represented in Figure 19b with l " k. If tj 2 , j 3 u R E, then Example 4 gives a contradiction. Thus we necessarily have tj 2 , j 3 u P E as represented in Figure 19c. Then ti, j 1 , j 2 , j 3 , iu is a cycle where i has highest priority and Example 3 implies tj 1 , j 3 u P E.

As a direct consequence of Proposition 9, we get the following result.

Lemma 2. Let pω, Σq be a weight system with at least two priority levels and let G " pN, Eq be a graph preserving pω, Σq-convexity. Let k, k 1 be priority levels with k ă k 1 . Let C 1 and C 2 be connected components of G k linked to a connected component C of G k 1 . Then C is a star and C 1 and C 2 are necessarily singletons linked only to the center of the star. Moreover, C 1 and C 2 cannot be linked to connected components of a lower layer.

Necessary and sufficient conditions for Priority-decreasing trees.

We now investigate a special type of graphs.

Definition 7. Let pω, Σq be a weight system. We say that a graph G " pN, Eq is an pω, Σqpriority-decreasing tree if

• G is cycle-free,

• There exists a root r such that the priorities are decreasing for the tree-order generated from r.

We give in Figure 20 examples of pω, Σq-priority-decreasing trees. The following theorem provides a characterization of priority-decreasing trees preserving pω, Σq-convexity.

Theorem 3. Let pω, Σq be a weight system and G " pN, Eq be an pω, Σq-priority-decreasing tree. We denote the priorities by 1 to k from low to high priority. The following statements are equivalent:

1. G preserves pω, Σq-convexity. 2. There exist m ě 1 and a strictly decreasing subsequence of priorities pk l q 1ďlďm such that:

(a) k 1 " k, (b) For all l with 1 ď l ď m, the graph restricted to the set of nodes with priority between k l and k l`1 `1 is a star denoted pN l , E l q (setting k m`1 " 0), (c) The center of pN l , E l q denoted c l has priority k l , (d) If m ě 2, then for all l with 1 ď l ď m ´1 there is exactly one edge e l linking pN l , E l q to pN l`1 , E l`1 q, and e l connects a node of priority k l`1 in N l`1 to c l .

Let us observe that the graph given in Figure 20a preserves pω, Σq-convexity as it satisfies Condition 2 with m " 2. Then pN 1 , E 1 q (resp. pN 2 , E 2 q) corresponds to the star induced by t1, 2, 3, 4, 5u (resp. t6, 7, 8, 9u). It can be easily seen that the graphs given in Figures 20b and20c do not satisfy Condition 2 and therefore dot not preserve pω, Σq-convexity.

Proof. We start by establishing that (2) is a necessary condition to preserve pω, Σq-convexity. In a second step, we will prove that it is sufficient. Necessary condition: We first define the subsequence of priorities by induction. 1. Let k 1 " k be the maximal priority in G " pN, Eq.

2. Let Ñ1 be the set of nodes with priority k 1 and Ñ 1 1 the set of neighbors of all elements in Ñ1 . If Ñ 1

1 " H, then define k 2 to be the minimum priority in Ñ 1 1 .

3. For every l with l ě 2, let Ñl be the set of nodes with priority k l and Ñ 1 l the set of neighbors of all elements in Ñl with priority less than k l . If Ñ 1 l " H, then define k l`1 to be the minimum priority in Ñ 1 l .

Let us now show that G has to satisfy the precise structure described in Condition 2. Set m " 1. We first consider the nodes at level k 1 . Under the assumption of decreasing order, they form a connected component. For each node n in Ñ 1 1 , we define its sublevel component Cpnq as the connected component containing n in the restricted graph G ppnq (containing only nodes having the same priority as n). By Statements 1 and 2 in Proposition 9 and as G is cycle-free, Ñ1 forms a star S 1 and each sublevel component Cpnq is linked to S 1 only at its center c 1 by the unique edge tn, c 1 u. Moreover, each Cpnq with priority between k 2 `1 and k 1 is a leaf node in G. We distinguish depending on the number of sublevel components having priority k 2 :

• If there are at least 2 such components, then they are necessarily leaf nodes by Lemma 2.

Therefore G is a star network as represented in Figure 21a and it ends the proof as Condition 2 is satisfied taking m " 1.

c 1 n n 1 n 2 k 1 k 2 k 2
(a) If ppn 1 q " ppn 2 q " k 2 then Cpn 1 q and Cpn 2 q are singletons. • Otherwise, we increase m by 1. Under the assumption of decreasing order, we know that the priority of nodes in N ztc 1 u connected to the unique sublevel component of priority k 2 have a lower priority than k 2 . It follows that we had all nodes with higher priority. The graph restricted to the set of nodes with priority between k 1 and k 2 `1 is a star denoted pN 1 , E 1 q with center c 1 . By construction, c 1 has priority k 1 and there exists a unique link between c 1 and a node with priority k 2 as represented in Figure 21b.

c 1 n n 1 k 1 k 2 (b) Cpn 1 q unique component with priority k 2 .
In the second case, one can repeat the argument in the restricted graph of nodes with priority lower than k 2 . Sufficient condition: We now prove that such a graph preserves the pω, Σq-convexity. The proof follows the lines of [START_REF] Slikker | Average Convexity in Communication Situations[END_REF]. We need to check that if the original game is pω, Σqconvex then Equation (1) remains true for the communication game for any pair of subsets S and T such that S Ă T .

If ppSq ă ppT q, then for every i P S, ω T i " 0 and Equation ( 1) is trivially true. We can now turn to the case where ppSq " ppT q " k. Equation (1) can be rewritten as Let l be the highest index in t1, . . . , mu such that T intersects the star pN l , E l q with center c l .

We have k l`1 ă k ď k l . We distinguish several cases depending if c l is in S and/or T .

• If c l R S and c l R T as represented in Figure 22a, then c l c l`1 pN l , E l q pN l`1 , E l`1 q T S (a) c l R S and c l R T . c l c l`1 pN l , E l q pN l`1 , E l`1 q T S (b) c l R S and c l P T .

Figure 22: ppc l q " k l and ppc l`1 q " k l`1 . v G pSq " ÿ iPS, k l`1 ăppiqďk l vptiuq `vG pS ďk l`1 q.

where S ďk l`1 is the set of elements in S with priority lower than k l`1 . Notice that we do not explicit the remaining value since it depends on the connectivity and it is unnecessary. It follows that v G pSq ´vG pSztiuq " vptiuq, @i P S with ppiq " k.

At T , one obtains the same computation and therefore for every i P S with ppiq " k v G pSq ´vG pSztiuq " vptiuq " v G pT q ´vG pT ztiuq, and ( 18) is satisfied by considering the weighted sum.

• If c l R S but c l P T as represented in Figure 22b, then ( 19) is still satisfied and we necessarily have k " k l . Let tT 1 , . . . , T m u with m ě 1 be the connected components of T . As c l P T , we can assume w.l.o.g. c l P T 1 . Then, we have ppT 1 q " k l and ppT j q ă k l for all j with 2 ď j ď m. We get ÿ iPS, ppiq"k l w T i pv G pT q ´vG pT ztiuqq " ÿ iPSXT 1 , ppiq"k l w T 1 i pv G pT q ´vG pT ztiuqq.

Let us note that any i in T 1 ztc l u with ppiq " k l is necessarily a leaf in pN l , E l q. As v G pT q " ř n j"1 vpT j q and as c l R S, (20) implies ÿ iPS, ppiq"k l w T i pv G pT q ´vG pT ztiuqq " ÿ iPSXT 1 , ppiq"k l w T 1 i pvpT 1 q ´vpT 1 ztiuqq.

Moreover, by (19) and as ω T i " ω T 1 i for all i P S, we have ÿ iPS, ppiq"k l ω T i `vG pSq ´vG pSztiuq ˘" ÿ iPSXT 1 , ppiq"k l ω T 1 i vptiuq.

pω, Σq-convexity of v applied with tiu Ď T 1 and ppiq " k l gives w T 1 i pvpT 1 q ´vpT 1 ztiuqq ě w T 1 i pvptiuq ´vpHqq " w T 1 i vptiuq.

Then, using ( 21) and ( 22), we get that ( 18) is satisfied.

• If c l P S and c l P T , the computation is more complex. As c l P T , we necessarily have k " k l . We first focus on the case where S is composed of a single component. Any i P S with ppiq " k l belongs to the star pN l , E l q and therefore satisfies v G pSq ´vG pSztiuq "

$ & % vpSq ´vpSztiuq if i P Sztc l u, vpSq ´řjPN l XS vptjuq ´vpS X N c l q if i " c l .

It follows that one can replace all the increments by the first formula except when i is the center. One obtains ÿ iPS, ppiq"k l ω T i pv G pSq ´vG pSztiuqq " ÿ iPS, ppiq"k l ω T i pvpSq ´vpSztiuqq `ωT c l ˜vpSztc l uq jPN l XS vptjuq ´vpS 1 q ¸, (23)

where S 1 :" S X N c l . Similarly, one obtains for T ÿ iPS, ppiq"k l ω T i pv G pT q ´vG pT ztiuqq " ÿ iPS, ppiq"k l ω T i pvpT q ´vpT ztiuqq `ωT c l ˜vpT ztc l uq ´ÿ jPN l XT vptjuq ´vpT 1 q ¸, (24)

where T 1 :" T X N c l . Let us note that all elements in T 1 have a priority less than k l`1 and all elements in N l have a priority strictly greater than k l`1 . Let S 1 be the set of elements in pS X N l qztc l u with lowest priority. Let T 1 be the set of elements j in ppT zSq X N l qztc l u satisfying ppjq ď ppS 1 q (T 1 may be empty). Let t 1 , . . . , t m be the elements in T 1 ordered by increasing priorities. Then, pω, Σq-convexity of v applied successively to t k Ă T 1 Y Ť k j"1 t j with k P t1, . . . , mu gives vpT 1 Y T 1 q ´vpT 1 q ě ÿ jPT 1 vptjuq.

(25)

Proposition 5 applied to S 1 and S 1 Ă T 1 Y T 1 gives vpS 1 Y T 1 Y T 1 q ´vpT 1 Y T 1 q ě vpS 1 Y S 1 q ´vpS 1 q.

(26)

Proof of Proposition 3. If t " 1, then the result is satisfied. Let us consider T P PpN q with t ą 1 and i P T . We assume Ψ ω S " Φ ω pv S q for all S P PpN q with s " t ´1. We get Ψ ω iT " ω T i ω T pvpT q ´vpT ztiuqq `ÿ jPT ztiu ω T j ω T Φ ω i pv T ztju q " ω T i ω T pvpT q ´vpT ztiuqq `ÿ jPT ztiu ω T C Proof of Counter-example 3-pan (Example 4)

We show that Example 4 described page 18 provides a counter-example if pp2q ě pp4q, pp4q ě pp1q and pp4q ě pp3q.

The game pN, vq is not convex:

The marginal contribution of player 1 is strictly smaller to t3, 4u than to t4u.

vpt1, 4uq ´vpt4uq " X ´0 " X, vpt1, 3, 4uq ´vpt3, 4uq " pX `Y ´1q ´Y " X ´1.

The game pN, vq is pω, Σq-convex:

We need to check the inequalities for any pair of non-empty sets S and T such that S Ă T .

• Let us first notice that the function v is monotonic since pY ´1q ě 0, pX ´1q ě 0 and Θ ě Z ě Y . Hence if S has value 0, we have ÿ iPS ω T i pvpSq ´vpSziqq " 0 ´0 " 0.

(42)

Since the function v is monotonic, each marginal contribution has to be positive, hence the pω, Σq-convexity inequality is satisfied for any T containing S. (42) is satisfied if S is a singleton, and if S is equal to t1, 2u, t1, 3u, or t2, 3u.

Figure 6 :

 6 Figure 6: Non-complete cycle C, tj, ku R E, ppl ˚q " ppV pCqq.

  Figure 7

  pN, v G q.

  pN, v G q.

  ts, cu R E and ts, bu R E. ts, bu R E.

Figure 11 :

 11 Figure 11: k ă k 1 .

Figure 12 :

 12 Figure 12: k ă k 1 .

  ts, cu R E and ts, bu R E.

Figure 13 :

 13 Figure 13: k ă k 1 .

2.

  If there is no link between C 1 and C 2 then (a) C 2 is a singleton. (b) C is a star and C 2 is linked to C only at its center c. (c) C 1 is linked to C only at its center c. (d) C 2 cannot be linked to connected components of a lower layer.

Figure 18 :

 18 Figure 18: k ď k 1 ă k 2 , l ă k, and tc, j 3 u R E.

Figure 20 :

 20 Figure 20: pω, Σq-priority-decreasing trees with root 3.

Figure 21 :

 21 Figure 21: k 2 ă ppnq ă k 1 .

ÿ

  iPS, ppiq"k ω T i `vG pSq ´vG pSztiuq ˘ď ÿ iPS, ppiq"k ω T i `vG pT q ´vG pT ztiuq ˘. (18)

Documents de travail du Centre d'Economie de la Sorbonne 2022.16

Documents de travail du Centre d'Economie de la Sorbonne 2022.16

Documents de travail du Centre d'Economie de la Sorbonne 2022.16

The λS's are also called Harsanyi dividends in cooperative game theory[START_REF] Harsanyi | A simplified bargaining model for the n-person cooperative game[END_REF].5 Documents de travail du Centre d'Economie de la Sorbonne

2022.16

[START_REF] Sprumont | Population monotonic allocation schemes for cooperative games with transferable utility[END_REF] established the same result. Average convex games are called quasiconvex in Sprumont's work.

Documents de travail du Centre d'Economie de la Sorbonne 2022.16

Documents de travail du Centre d'Economie de la Sorbonne 2022.16

Theorem 3.2 in[START_REF] Slikker | Average Convexity in Communication Situations[END_REF].

Lemmas 3.1 and 3.2 in[START_REF] Slikker | Average Convexity in Communication Situations[END_REF].

We consider the following game pN, vq and the communication game pN, v G q induced by pN, vq and the communication structure given by G.

vpSq "

Define

Θ " Z `X ´1.

We consider the following game pN, vq and the communication game pN, v G q induced by pN, vq and the communication structure given by G.

Let us note that this game corresponds exactly to the game given in Example 2 if α p " 0. We represent in Figure 8 the lattices of coalitions of t1, 2, 3, 4u ordered by inclusion for pN, vq and pN, v G q with the corresponding values. Let us establish a few facts. The game pN, vq is not convex but is pω, Σq-convex A detailed proof for the general case with priorities is provided in Appendix C.

(25) and ( 26) imply

Let now S 2 be the set of elements in pS X N l qzpS 1 Y tc l uq with lowest priority. Let T 2 be the set of elements j in ppT zSq X N l qzpT 1 Y tc l uq satisfying ppjq ď ppS 2 q. By definition any element j in T 2 also satisfies ppjq ą ppS 1 q. By the same reasoning as before, we get using successively the pω, Σq-convexity of v

and by Proposition 5 applied to S 2 and

(27), ( 28) and ( 29) imply

Repeating the reasoning, we finally get vpT ztc l uq ´ÿ jPT XN l vptjuq ´vpT 1 q ě vpSztc l uq ´ÿ jPSXN l vptjuq ´vpS 1 q.

(31) pω, Σq-convexity of v applied with S Ă T gives ÿ iPS, ppiq"k l ω T i pvpSq ´vpSztiuqq ď ÿ iPS, ppiq"k l ω T i pvpT q ´vpT ztiuqq .

Finally, ( 23), ( 24), (31), and (32) imply (18).

Let us now show the general case. Let tS 1 , ..., S n u (resp. tT 1 , ..., T m u) with n ě 2 (resp. m ě 1) be the partition of S (resp. T ) into connected components. As c l P S, we can assume w.l.o.g. c l P S 1 Ď T 1 . Then, we have ppS 1 q " ppT 1 q " k l and ppS j q ă k l (resp. ppT j q ă k l ) for all j with 2 ď j ď n (resp. 2 ď j ď m). We get

As v G pSq " ř n j"1 v G pS j q and as ω T i " ω T 1 i for every i in S 1 , (33) implies ÿ iPS, ppiq"k l w T i pv G pSq ´vG pSztiuq "

Similarly we have

We have reduced the problem to the previous situation and therefore established the pω, Σq-convexity for any pair of sets.

By combining the results of Section 3 and 5.3, we obtain sufficient conditions on the game and on the graph to guarantee that the weighted Myerson value belongs to the core.

A Proof of Proposition 2

Proof. Let us check that this definition is indeed coherent with the first definition of the weighted Shapley value.

Since it is defined through the expectation of v under the probability distribution P ω,Σ , it is clearly a linear mapping of v.

Fix the unanimity game on the set S, then

• A player not in S will never have a positive marginal contribution, hence his value is 0.

• A player i in S only has a positive marginal contribution, if S Ď tL ě iu and i is the pivotal element, hence the first element of S in L. What is the probability of this event? If i is not in S, then this probability is 0, hence he obtains 0. If i is in S, then its probability is exactly ω S i {ω S . The key argument is that the probability of the first element of S to appear to be i conditionally on the fact that an element of S is picked at the current stage is exactly equal to ω i pSq ωpSq . Let i P S. For any t P t1, . . . , nu, we set L ďt " tLpuq, u ď tu. Formally, we have

By assumption T Ă N ´S, hence N ´T is a superset of S and therefore ppN ´T q is greater or equal to ppSq. We distinguish two different cases,

if ppN ´T q ą ppSq, then P ´Lptq P S, @u ă t, Lpuq R S ¯" 0, since any element of S has still a too low priority.

if ppN ´T q " ppSq, then for every i P S, ω N ´T i " ω i whereas for i P S ´S, one has ω N ´T i " 0. Hence,

B Proof of Proposition 3

We first establish a formula for the pω, Σq-weighted Shapley value in terms of the marginal contributions.

Lemma 3. The pω, Σq-weighted Shapley value can be defined as follows

γ N,w S,i pvpSq ´vpSztiuqq where γ N,w S,i "

for all S Ď N with S " H.

Proof. By definition, we have

We get

For any pair S, T occurring in (36) we have i P T Ď S and thus ppiq ď ppT q ď ppSq. As ω S i " ω i (resp. ω S i " 0) for all i P S with ppiq " ppSq (resp. ppiq " ppSq), we get the result.

36 Documents de travail du Centre d'Economie de la Sorbonne 2022.16

Let Φ ω pv T q be the pω, Σq-weighted Shapley value of the subgame v T . We have

Define the vector Ψ ω " pΨ ω iT q iPT,T PPpN q recursively by Ψ ω iT "

for all i P T , T P PpN q and setting Ψ ω iH " 0 for all i P N . We recall Proposition 3.

Proposition 3. For all T P PpN q, pΨ ω iT q iPT " Φ ω pv T q. In order to prove Proposition 3, we first establish the following lemma.

Lemma 4. For all S, T P PpN q with H " S Ă T , and for all i P S

Proof. Let us consider S Ă T Ď N and i P S. We have

If ppT q " ppSq, then any R Ă T with ppRq " ppSq satisfies ω T R " 0 and ( 38) is equivalent to

If ppT q " ppSq, then any R Ď T with R Ě S satisfies ppRq " ppSq and ω R " ω T R and ( 38) is equivalent to

Finally, as ř t´s´1 k"0 C k t´s p´1q k " p1 ´1q t´s ´p´1q t´s , (39) implies the result.

• If S is equal to t1, 4u, then

There are 3 possible cases for T : t1, 2, 4u, t1, 3, 4u and N .

-Assume T " t1, 2, 4u,

If α p " 1, then by definition of Y and as pp4q ě pp1q, we have ω T 4 Y ´pω T 1 `ωT 4 q ě 0 and the pω, Σq-convexity inequality is satisfied. If α p " 0, the inequality is satisfied and tight.

-Assume T " t1, 3, 4u,

Then we can conclude as in the previous case with α p " 1.

-Let us consider T " N , then ÿ iPS ω T i pvpT q ´vpT ziqq " ω T 1 pΘ ´Zq `ωT 4 pΘ ´αp pX ´1qq, " ω T 1 pX ´1q `ωT 4 pZ `p1 ´αp qpX ´1qq.

If α p " 1, we get

As pp4q " ppN q, we have ω T 4 Y ´ωT 1 " ω 4 `ω1 ´ωT 1 ě 0 and the inequality is satisfied. If α p " 0, we have

If pp4q ă ppN q then by assumption we also have pp1q ă ppN q and the pω, Σqconvexity inequality is trivially satisfied. Otherwise, we have ω T 4 Y ´ωT 1 " ω 4 ὼ1 ´ωT 1 ě 0 and the inequality is also satisfied.

39

Documents de travail du Centre d'Economie de la Sorbonne 2022.16

• If S is equal to t2, 4u, then

There are 3 possible cases for T : t1, 2, 4u, t2, 3, 4u and N .

-Let us assume that T " t1, 2, 4u,

If α p " 0, then the inequality is obviously satisfied. If α p " 1, then pp2q " pp4q and we have ω 4 X ´ω2 ´ω4 ě 0 by definition of X.

-Let us assume T " t2, 3, 4u, ÿ iPS ω T i pvpT q ´vpT ziqq " ω T 2 pZ ´Y q `ωT 4 pZ ´0q.

If α p " 0, then the inequality is obviously satisfied. If α p " 1, then Z " X `2Y and the inequality is satisfied.

-Finally, let T " N , then ÿ iPS ω T i pvpT q ´vpT ziqq " ω T 2 pΘ ´X ´Y `1q `ωT 4 pΘ ´αp pX ´1qq, " ω T 2 pZ ´Y q `ωT 4 pZ `p1 ´αp qpX ´1qq.

If α p " 0, then the inequality is obviously satisfied. If α p " 1, then Z " X `2Y and the inequality is also satisfied.

• If S is equal to t3, 4u, then

There are 3 possible cases for T : t1, 3, 4u, t2, 3, 4u and N .

-Let us assume that T " t1, 3, 4u,

The last inequality is by definition of X and as pp4q " ppt1, 3, 4uq. Therefore the pω, Σq-convexity inequality is satisfied. and ÿ iPS ω T i pvpT q ´vpT ziqq " ω T 1 pΘ ´Zq `ωT 3 pΘ ´X ´αp pY ´1qq `ωT 4 pΘ ´αp pX ´1qq, " ω T 1 pX ´1q `ωT 3 pZ ´1 ´αp pY ´1qq `ωT 4 pZ `p1 ´αp qpX ´1qq.

If α p " 0, then the inequality is satisfied as Z ě Y . If α p " 1, then Z " X `2Y and the inequality is also satisfied.

• Finally, let S " t2, 3, 4u and T " N , ÿ iPS ω T i pvpSq ´vpSziqq " ω T 2 pZ ´Y q `ωT 3 pZ ´αp Y q `ωT 4 pZ ´0q, and ÿ iPS ω T i pvpT q ´vpT ziqq " ω T 2 pΘ ´pX `Y ´1qq `ωT 3 pΘ ´pX `αp pY ´1qqq

`ωT 4 pΘ ´αp pX ´1qq " ω T 2 pZ ´Y q `ωT 3 pZ ´αp Y q `ωT 4 pZ ´0q ´ωT 3 p1 ´αp q `ωT 4 p1 ´αp qpX ´1q.

If α p " 1, then the inequality is tight. Let us assume α p " 0. If pp4q ă ppN q then by assumption we also have pp3q ă ppN q and the inequality is trivially satisfied. If pp4q " ppN q, then we also have pp3q " ppN q as α p " 0 and by definition of X we get ´ωT 3 p1 ´αp q `ωT 4 p1 ´αp qpX ´1q " ´ω3 `ω4 pX ´1q ě 0 and the inequality is satisfied.

D Proof of Counter-example 4-path with strict inequality (Example 5)

We show that Example 5 described page 22 provides a counter-example if pp2q " pp4q ą maxppp1q, pp3qq.

The game pN, vq is not convex:

The marginal contribution of player 1 is strictly smaller to t3, 4u than to t4u.

vpt1, 4uq ´vpt4uq " 1 ´0 " 1, vpt1, 3, 4uq ´vpt3, 4uq " 1 ´1 " 0.

The game pN, vq is pω, Σq-convex:

We need to check the inequalities for any pair of non-empty sets S and T such that S Ă T .

42 Documents de travail du Centre d'Economie de la Sorbonne 2022.16

• Let us first notice that the function v is monotonic. Hence if S has value 0, we have

Since the function v is monotonic, each marginal contribution is positive and the pω, Σqconvexity inequality is satisfied for any T containing S. (43) is satisfied if S is a singleton, and if S is equal to t1, 2u, t1, 3u, t2, 3u, t2, 4u, or t1, 2, 3u.

• If S is equal to t1, 4u, then

There are 3 possible cases for T : t1, 2, 4u, t1, 3, 4u and N . In any case, we have ÿ iPS ω T i pvpT q ´vpT ziqq " ω T 4 p1 ´0q `ωT 1 p1 ´1q " ω T 4 .

As pp4q ą pp1q, we have ω T 1 " 0 and the pω, Σq-convexity inequality is satisfied.

• If S is equal to t3, 4u, then

There are 3 possible cases for T : t1, 3, 4u, t2, 3, 4u and N . In any case we have ÿ iPS ω T i pvpT q ´vpT ziqq " ω T 4 p1 ´0q `ωT 3 p1 ´1q " ω T 4 .

As pp4q ą pp3q, we have ω T 3 " 0 and the inequality is satisfied.

• Let S " t1, 2, 4u and T " N , then ÿ iPS ω T i pvpSq ´vpSziqq " ω T 1 p1 ´1q `ωT 2 p1 ´1q `ωT 4 p1 ´0q, and ÿ iPS ω T i pvpT q ´vpT ziqq " ω T 1 p1 ´1q `ωT 2 p1 ´1q `ωT 4 p1 ´0q, and the inequality is satisfied.

• Let S " t1, 3, 4u and T " N ÿ iPS ω T i pvpSq ´vpSziqq " ω T 1 p1 ´1q `ωT 3 p1 ´1q `ωT 4 p1 ´0q, and ÿ iPS ω T i pvpT q ´vpT ziqq " ω T 1 p1 ´1q `ωT 3 p1 ´1q `ωT 4 p1 ´0q.

Hence the inequality is satisfied.


Camille Jalier

Didier Lattard

Gilles Sassatelli
email: sassatelli@lirmm.fr

A Flexible Modeling and Simulation Framework for Design Space Exploration

Applications like 4G baseband modem require single-chip implementation to meet the integration and the power consumption requirements. These applications involve a high computation performance with real-time constraints, low power consumption and low cost. The concept of MPSoC is well suited to this problem. It makes it possible to adjust the architecture, by allocating the computational power where it is needed to fit the application needs. This often implies that the software has to be developed at the same time the platform is refined. Algorithm designers need accurate performance estimation to guide their decisions and system architects need to provide a design with enough calculation capacity and flexibility.

Based on the methodology used for the design of the 4G FAUST chipset, this paper presents a modeling and simulation framework for Design Space Exploration (DSE) which enables a rapid evaluation of the application-to-platform adequation. The key element of this work is a simple and flexible way of modeling application and architecture. Our SystemC-based simulation environment can support a broad range of architecture components (ASIC, DSP, NoC, bus, shared or distributed memory, ...) and application features (control flow, data exchange, interrupts, data-dependent processing, dynamic reconfiguration). Application and architecture models are separated to allow independent design space exploration. The simulation basically executes the algorithms on the architecture and monitors dynamic behavior such as communication transfers, resource conflicts, starvation, dynamic reconfiguration, etc.

I. INTRODUCTION

The increasing complexity of telecommunication algorithms in mobile terminals, requires high computational performance and low power consumption. The algorithms proposed for 4G applications are adaptive so the System On Chip (SoC) requires enough flexibility/reconfigurability to support multiple modulation schemes, Multiple Input Mutiple Output (MIMO) transmissions, etc. The implementation of such algorithms on the FAUST platform [START_REF] Durand | FAUST: on-chip distributed SoC architecture for 4G baseband modem chipset[END_REF] has proved the efficiency of MPSoC to provide an attractive solution. This development has stressed the need for exploration tools to help the designer in the platform implementation choices:

• Processing resources: ASIC, ASIP, DSP, RISC • Communication media: bus, point-to-point, Network-on-Chip (NoC)

• Memory topology: shared, distributed, FIFO • Application: task partitioning, communication protocol, scheduling, mapping

The implementation of a baseband application onto a reconfigurable Multiple Processor SoC (MPSoC) adds stages in the design flow:

• Mapping and scheduling of the algorithm functionality onto each processing resources to exploit parallelism.

• Optimization of data transfer and scheduling to reduce time-overhead.

• Optimization of resource allocation to minimize the chip.

• Performance evaluation of the application on the architecture to guarantee the real-time constraints. In order to address these issues, we propose a SystemCbased simulation framework. This framework incorporates both application and architecture aspects of the MPSoC to enable a behavioral approach. The performance is extracted through a simulation of the application behavior onto the platform. Because the application and the architecture are abstracted, it is possible to significantly speed up and ease the exploration process, to perform dynamic performance analysis and to quickly change parameters without rewriting models. In this context, this framework is useful to perform an early Design Space Exploration (DSE) and/or to provide an early execution platform for the software development. This tool might allow a faster verification of the second generation FAUST platform. The rest of this paper is organized as follows. The importance of the DSE in the design flow and the related works are discussed in section II. Section III describes the application and architecture abstraction models. Section IV describes the DSE environment.

II. SYSTEM LEVEL DESIGN

A. Framework Overview

In baseband modems, the algorithm choices widely influence the MPSoC design. In the traditional top down approach, the designer starts with an informal specification and develops a reference model of the telecom standard using a high-level language such as Matlab or C++. At this functional level of abstraction, the algorithm is developed independently from the architecture. This modeling approach is used by software designers to study different algorithms under complexity and precision aspects [START_REF] Kempf | A modular Simulation Framework for Spatial and Temporal Task Mapping onto Multi-Processor SoC Platforms[END_REF].

As shown in Fig. 1, in the next step of the design flow, this description is refined into an abstract platform. The platform is composed of modules, each of them executes a part of the application. They represent future hardware or software components (RISC, DSP, ASIC, etc). The transition between a functional view to a platform view is complex [START_REF] Magarshack | System-on-chip Beyond the Nanometer Wall[END_REF]. This implies deciding Hardware/Software partitioning, defining the architecture components and finally perform the algorithm mapping. Each architectural decision affects the global performance and the application behavior considering processing time, memory latency, data-transfer latency, possible parallel processing, resource sharing, etc. Flexible frameworks, that can model easily a broad range of platform and quickly estimate resulting performance, are required to perform an efficient DSE and converge to a satisfying solution. The exploration process at high level allows very efficient system optimizations. Our modeling and simulation framework simplifies and accelerates this process and is well suited for high complexity systems such as complex 4G baseband chipsets. Once both algorithm and platform specifications are decided, every component is refined into either Register Transfer Level (RTL) model or embedded C code. The used approach is incremental for verification purposes: every low-level cycleaccurate RTL hardware component is simulated within the platform model for ensuring proper behavior.

Platform Level

B. Related work

Several methodologies and tools have been introduced to help the designer to model and simulate an application onto an architecture. The most relevant are mentioned in this paper.

Syndex [START_REF] Grandpierre | From algorithm and architecture specification to automatic generation of distributed real-time executives: a seamless flow of graphs transformations[END_REF] is a system level CAD software tool in which applications and architectures are modeled with independent graphs. In this approach, the application model is well separated from the architecture model to ensure an easy exploration of each aspect. However the application graph is limited to a Data-dependence Graph, in this case it is impossible to capture data-dependent processing or synchronization by interrupts.

ArchAn [START_REF] Chatelain | Verification Strategy for Integration 3G Baseband SoC[END_REF] is an architectural simulation environment in which applications are modeled in a task modeling language and the abstract architecture is modeled at the cycle-accurate level. In this approach, the task modeling language includes details of the underlying architecture. Algorithms and architectural details are combined, the exploration becomes more difficult.

Artemis [START_REF] Pimentel | Exploring embedded-systems architectures with Artemis[END_REF] is a modeling and simulation environment to explore the design space of heterogeneous embedded-systems architectures. This tool allows to model the architecture at multiple level of abstraction using generic building blocks provided in a library. Regarding application modeling, Artemis uses the Kahn Process Network (KPN) computational model. The KPN semantic forbids the use of interrupts, some dynamic behavior, such as run-time mapping, cannot be simply modeled.

III. APPLICATIONS AND ARCHITECTURES ABSTRACTION MODELS

A. Application abstraction models

In this work, the used approach considers the telecom algorithm (OFDM demodulation, MIMO decoding, channel decoding, etc) and also all the additional mechanisms (synchronization between resources, requests for memory space, etc) as part of the application. All these mechanisms are not defined in the telecom standard but they are mandatory to complete the platform model and they significantly influence the execution behavior, they are time-consuming. One of the motivations of this work is to keep the architecture and the application well separated so that exploration is facilitated; i.e. any functionality can be mapped to either in software (on a RISC) or in hardware (ASIC) without any expensive rewriting phase.

An application is modeled with tasks and buffers. The functionality is divided into a set of tasks. Each task may or may not contain the C++ code of the algorithm, but some specific annotations are required in order to indicate:

• communications with external tasks or buffers (data or control information)

• complexity of the data processing • control flow (loop, conditions, ...) These three types of annotation capture the interactions between the application and the system [START_REF] Waseem | Abstract Application Modeling for System Design Space Exploration[END_REF]. Data transfers between tasks are memorized in buffers. All communications can be represented as edges. The possibility for tasks to exchange some control information offers a great flexibility. The processing algorithm can be conditioned by a control event. Fig. 2 illustrates the proposed approach on a simple example that exhibits both data and control interactions among tasks. Five steps are used for describing task 3 behavior. The first one A synchronizes the execution on a control message START sent by the task 5. Steps B , D and E respectively model the reading, processing and writing operations of the task.

Step C is the C++ code of the interleaving algorithm used in 4G transmissions. This piece of code is not timeconsuming for simulation though, it can be omitted. Finally, the complexity of the algorithm is modeled in the step D .

B. Architecture abstraction models

The platform architecture, which is the physical support for execution, is modeled with the same high-level abstraction approach as the application. To meet the well-known power, performance and cost constraints, architectures are often heterogeneous with multiple differentiated processors, complex memory hierarchy and hardware accelerators [START_REF] Lattard | A Reconfigurable Baseband Platform Based on an Asynchronous Network-on-Chip[END_REF]. Modeling that kind of SoC involves flexible and high-level models. In the literature, two approaches are often used. Either models, like Random Access Machine [START_REF] Tiskin | The bulk synchronous parallel random access machine[END_REF], are employed to evaluate computing complexity but they intentionally neglect the underlying architecture details. Or low level models, like Instruction Set Simulator (ISS) or HDL descriptions, are employed but they do not allow rapid design space exploration as rewriting code is often required, they are too over-detailed.

Our approach is based on abstract models that can describe very complex and different MPSoC implementations without rewriting code. For enabling this, a set of abstract entities that can cover current platform such as FAUST and future HW/SW MPSoC are required. In the previous section III-A, the application is modeled with tasks, buffers and edges. The abstract models for the architecture are directly inspired from the application view. Three different types of abstract entities are used to describe the architecture:

• a processor model that schedules several tasks (calculate requests)

• a memory model that manages several buffers (read, write requests)

• a communication media model that manages several simultaneous communications (edges) The abstract model for each entity is written in SystemC and is composed of a resource manager (scheduler [START_REF] Paul | Schedulers as Model-Based Design Elements in Programmable Heterogeneous Multiprocessors[END_REF]) to allow the concurrent execution of multiple application elements and a communication manager which resolves exchanges between entities. The platform architecture is specified in an XML file that describes the numbers of entities, their types and the interconnections. Each instantiated entity has its own parameters that can be tuned to predict the high level characteristics of the future physical module.

As shown in the Fig. 3, the Processor model is an abstract model used for modeling any type of processing element (DSP, CPU, ASIC). At this stage, the partitioning between hardware and software is not defined and the architecture description is independent of the application model.

C. Mapping

We have separately modeled the functionality and the architecture with independent or orthogonal models. To complete the platform description, we consider the spatial and temporal mapping. Each part of the application such as tasks (resp. buffers and edges) is placed on a Processor (resp. Memory and Communication) entity. When several tasks (resp. buffers and edges) are mapped onto a Processor (resp. Memory and Communication) module, the arbitration is done by the resource manager considering a scheduling policy. The mapping is described in an XML file to be easily changed. During this phase, the designer can efficiently distribute the application to exploit the parallelism or to share resources.

IV. DSE FRAMEWORK

Our framework follows the well-know y-chart principle [START_REF] Lieverse | A Methodology for Architecture Exploration of Heterogeneous Signal Processing Systems[END_REF], where a set of application models is merged with a set of architecture models in a dedicating mapping step. The platform is modeled in an orthogonal way. This mechanism is the key to enhance the flexibility during design space exploration. In our approach, we can independently explore:

• application: task partitioning, communication protocol (message passing, shared memory, etc.), synchronization model (data, interrupt, etc.), etc.

• architecture: performance for computing resources, communication topology, memory topology, number of resources, etc.

• mapping: resource allocation (to optimize performance, chip area, etc.), scheduling policy, etc. The exploration process starts by modeling the application with tasks, buffers and edges. Then a first platform architecture is modeled with Processor models, Memory models and Communication Media models. Based on the application graph and the architecture view, the mapping consists of allocating resources for each part of the application. Using our models, the framework automatically generates a SystemC platform including the application, the architecture and the mapping.

Based on the SystemC simulation engine (Fig. 4), the application is executed on the architecture and the execution behavior is captured. All the relevant characteristics for performance estimation can then be easily extracted: application throughput, maximum latency, utilization rate of resources, transient effects, etc.

According to the estimated performance, the designer can change the architecture and/or the algorithm architect can modify the application. This exploration process, to converge to a suitable solution, is incremental but do not need to rewrite code, only to modify XML files and/or change parameters. The designer is responsible for setting these parameters with relevant values according to his background and the technology. The predicted performance results are tightly linked to the parameters of the architectures entities. As all models are unified in the same framework, the algorithm architect and the designer can interact easily and work independently. In our approach, the modeling phase and the exploration is done manually by the designer relying on his skills and experience. This framework nevertheless offers an accelerated exploration process based on:

• Three parameterizable models (XML & SystemC) for architecture modeling (no code rewriting)

• XML-based description files to quickly parameterize and interconnect modules

• Automatic generation of a platform SystemC View • Extraction of execution parameters on log files At the end of the exploration, the designer has refined:the application into an embedded platform software regarding communication protocols, synchronizations, etc. -the architecture together with the topology/communication architecture and the associated parameters. -the mapping.

The hardware/software partitioning is performed according to the calculation capacity and flexibility of each unit. The designer can then easily provide detailed specifications for deriving a hardware or a software implementation. The programmer can work on an embedded and optimized code according to the target CPU and the designer can describe each hardware unit at Register Transfer Level.

As we have chosen SystemC, we can use Co-Simulation tools to plug each hardware unit, described in HDL languages, in place of our high-level model to perform a platform simulation.

V. CONCLUSION We propose a system level simulation framework for early investigation of MPSoC platform architectures considering a specific application. The major contributions of this paper are firstly a set of flexible high level models based on XML/SystemC descriptions and secondly an orthogonal way of modeling the application, the architecture and the mapping based on a separation between the functionality and the execution support. In this context, the algorithm is modeled in an embedded manner with explicit communication protocol, processing complexity, interrupts, etc. Here the use of high-level parameterizable models enables a rapid exploration process without rewriting code. With our modeling framework, dynamic or data-dependent behavior can be easily captured.

The major advantage of our modeling approach is the combination of a quick exploration flow and an extended modeling capacity.

Based on our experience on the FAUST chip , our future work will focus on the verification of the second generation platform. This design implements more flexible components to guarantee an efficient reconfiguration. On the longer term, this framework will serve as a basis to explore homogeneous architectures in the perspective of a completely reconfigurable telecom system.

Fig. 1 .

 1 Fig. 1. Simplified Design Flow

Fig. 3 .

 3 Fig. 3. A model based on Processor (Proc), Memory (Mem) and Communication (Com) entities.

Fig. 4 .

 4 Fig. 4. A Detailed View of our Exploration Process