Keywords

1 Introduction

A TU-game (a cooperative game with transferable utility) also referred to as coalitional game describes a situation in which all players can freely interact with each other, i.e. every coalition of players is able to form and cooperate. However, this is not the case in many real world scenarios. A typical situation is when there exists a restriction on the communication possibilities among players, as in the context of social interactions between groups of people, political alliances within parties, economic exchange among firms, research collaborations and so on. In order to represent and study such situations it is necessary to drop the assumption that all coalitions are feasible. Then a natural question arises: how can we model restrictions of the interaction possibilities between players?

A typical way to do so is that of considering a network structure Footnote 1 that describes the interaction possibilities between the players: the nodes of the network are the players of the game and there exists a link between two nodes if the corresponding players are able to interact directly. In this context it is usual to refer to such networks as communication networks, since a typical situation they model is a restriction of communication possibilities between players.

This approach leads to the definition of a so-called communication situation [13] and to the search for solution concepts that take into account the constraints imposed by the underlying network structure. For the class of graph games, a crucial point is to study how the communication constraints influence the allocation rules. There are at least two ways to measure this impact that correspond to two different main streams in the recent literature.

In a first approach, the communication constraints determine how a coalition is evaluated. There is no actual restriction constraint on the set of feasible coalitions, but if a coalition is not connected through the communication graph, its worth is evaluated on the connected components in the induced graph. This approach is investigated in the seminal paper by Myerson [13], who introduces the Myerson value in order to generalize the Shapley value from TU-games to graph games. Jackson and Wolinsky [11] extend Myerson’s model by considering a function assigning values to networks as a basic ingredient. Borm et al. [4] introduce the position value for communication situations. Like the Myerson value, the position value is based on the Shapley value, but it stresses the role of the pairwise connections in generating utility, rather than the role of the players. The value of a pairwise connection is derived as the Shapley value of a game on the set of links of the network and the position value equally divides the value of each link among the pair of players who form it. The position value has been extended in [19] to the setting of network situations introduced in [11] and an axiomatic characterization in this context is given in [21].

In a second approach, the communication constraints determine which coalitions can actually form. The definition of the Shapley value relies on the idea of a one-by-one formation of the grand coalition: its interpretation assumes that the players gather one by one in a room; each player entering the room gets his marginal contribution to the coalition that was already there and all the different orders in which the players enter are equiprobable. To take into account the communication constraints, the orderings of the players that induce disconnected coalitions are ruled out: the formation of the grand coalition requires a communication at any stage. In order to satisfy the communication constraints Demange [5] proposes to model the sequential formation of the grand coalition by a rooted spanning tree of the communication graph. Each rooted spanning tree represents a partial order on the players set such that the arrival of a new player forms a connected coalition. Demange [5] introduces the hierarchical outcome in order to extend the concept of marginal contribution from orderings of the players to rooted spanning trees. This second approach is also studied by Herings et al. [9] who introduce the average tree solution for graph games in which the communication graph is a forest (cycle-free graph). This allocation is the average of the hierarchical outcomes associated with all rooted spanning trees of the forest. Hering et al. [10] and Baron et al. [2] show how an extension of the average tree solution to arbitrary graph games can be seen as another generalization of the Shapley value. In [3], the principle of compensation formulated by Eisenman [6] is generalized from orderings of the players to rooted spanning trees and the compensation solution for graph games is introduced.

Based on the idea that the formation of the grand coalition requires a communication at any stage, our approach is different in spirit with respect to the aforementioned models. We assume indeed a different mechanism of coalition formation which results from subsequent connection of links among players. This idea naturally leads to consider a communication situation where a network between the players is produced by a permutation of links and we suppose that, at each step of the network formation process, the surplus generated by a link is shared between the players involved according to a certain protocol. Taking into account this mechanism, we propose a class of solution concepts where each solution corresponds to a different allocation protocol. In particular, at a certain step when a link between two players forms, it is reasonable to equally share the surplus between the players that are responsible for this connection, i.e. the two nodes incident to the link that is formed. It turns out that the solution obtained by this particular allocation protocol is indeed the position value. Our model thus provides a different interpretation for this well-known solution concept and proposes a family of solution that embraces the basic principles of both the approaches described above, providing a bridge between two different ways of modeling the restriction of communication possibilities between players in a coalitional game.

The paper is structured as follows. In Sect. 2 we introduce basic definitions and notations regarding coalitional games and networks. Section 3 describes the concept of communication situation and related solutions in literature. In Sect. 4 we introduce the notion of allocation protocol and the class of solution concepts that derives. Section 5 presents some preliminary results and in Sect. 6 we give formulas for the position value on specific communication situations. Section 7 concludes the paper.

2 Games and Networks

In this section, we introduce some basic concepts and notations on coalitional games and networks.

A coalitional game is a pair (N, v), where N denotes the set of players and \(v: 2^{N} \rightarrow \mathbb{R}\) is the characteristic function, with v(∅) = 0. A group of players S ⊆ N is called coalition and v(S) is called the value or worth of the coalition S. If the set N of players is fixed, we identify a coalitional game (N, v) with the characteristic function v.

We shall denote by \(\mathcal{G}\) the class of all coalitional games and by \(\mathcal{G}^{N}\) the class of all coalitional games with players set N. Clearly, \(\mathcal{G}^{N}\) is a vector space of dimension 2n − 1, where n = | N | . The canonical basis for this vector space is given by the family of canonical games {e S , S ⊆ N}. The game e S is defined as:

$$\displaystyle{e_{S}(T) = \left \{\begin{array}{ll} 1&\mbox{ if $S = T$}\\ 0 &\mbox{ otherwise} \end{array} \forall S \subseteq N,S\neq \emptyset.\right.}$$

It is possible to consider another basis for \(\mathcal{G}^{N}\), the family of the unanimity games {u S , S ⊆ N}, where u S is defined as:

$$\displaystyle{u_{S}(T) = \left \{\begin{array}{ll} 1&\mbox{ if $S \subseteq T$}\\ 0 &\mbox{ otherwise} \end{array} \forall S \subseteq N,S\neq \emptyset.\right.}$$

Every coalitional game v can be written as a linear combination of unanimity games as follows:

$$\displaystyle{ v =\sum _{S\subseteq N,S\neq \emptyset }c_{S}(v)u_{S}, }$$
(1)

where the constants c S , referred to as unanimity coefficients of v, can be inductively defined in the following way: let c {i}(v) = v({i}) and, for S ⊆ N of cardinality s ≥ 2,

$$\displaystyle{ c_{S}(v) = v(S) -\sum _{T \subsetneq S,T\neq \emptyset }c_{T}(v). }$$
(2)

An equivalent formula for the unanimity coefficients is given by:

$$\displaystyle{ c_{S}(v) =\sum _{T\subseteq S}(-1)^{\vert S\vert -\vert T\vert }\:v(T). }$$
(3)

Given a coalitional game, it is usual in many applications to consider as a solution the Shapley value of the game. The Shapley value was introduced by Shapley [16] in the context of cooperative games with transferable utility. The approach followed by Shapley consists of providing a set of properties that a solution for TU-games should satisfy. A formula to compute the Shapley value is the following:

$$\displaystyle{ \varPhi _{i}(v) =\sum _{S\subseteq N\setminus \{i\}}\frac{s!(n - s - 1)!} {n!} \big(v(S \cup \{ i\}) - v(S)\big),\:\forall i \in N, }$$
(4)

where s = | S | is the cardinality of coalition S and n = | N | .

The Shapley value belongs to the broader class of semivalues:

$$\displaystyle{ \varPsi _{i}^{\mathbf{p}}(v) =\sum _{ S\subseteq N\setminus \{i\}}p_{s}^{n}\big(v(S \cup \{ i\}) - v(S)\big)\:\:\forall i \in N, }$$
(5)

where n = | N | , s = | S | and p s n is such that p s n ≥ 0 for all s = 0, 1, …, n − 1, \(\sum _{s=0}^{n-1}\binom{n - 1}{s}p_{s}^{n} = 1\) and represents the probability that a coalition of size s + 1 forms. Furthermore, if p s n > 0 for all s, then the semivalue is called regular semivalue. We shall write p s instead of p s n when there is no ambiguity about the players set. In particular, the Shapley value is a regular semivalue with

$$\displaystyle{ p_{s} = \frac{1} {n\binom{n - 1}{s}}. }$$
(6)

and the Banzhaf index [1] is defined by (5) with \(p_{s} = \frac{1} {2^{n-1}}\).

Another class of regular semivalues is the one of the q-binomial semivalues [14] Ψ q, where

$$\displaystyle{ p_{s} = q^{s}(1 - q)^{n-s-1} }$$
(7)

with q ∈ [0, 1] (by convention, we take 00 = 1 if q = 0 or q = 1). In particular if q = 0 we obtain the dictatorial index Ψ i 0(v) = v({i}), while if q = 1 we get the marginal index Ψ i 1(v) = v(N) − v(N∖{i}). Note that q = 1∕2 gives Ψ 1∕2 = β, the Banzhaf value.

An undirected graph or network Γ is the pair (V, E), where V is a set of nodes and E ⊆ {{ i, j}: i, j ∈ V, i ≠ j} is the set of links between the nodes.

We denote by deg(i) the degree of a node i ∈ V, i.e. the number of links incident to i in Γ. Given a subset S ⊆ V of nodes, we define the induced subgraph Γ S  = (S, E S ), where E S is the set of links {i, j} ∈ E such that i, j ∈ S. Similarly, we denote by Γ A the graph (V A , A) induced by a subset A ⊆ E of links, where V A is the set of nodes incident to at least one link of A.

A path between i and j in a graph Γ is a sequence of distinct nodes (i 0, i 1, ⋯ , i k ) such that i 0 = i, i k  = j and \(\{i_{s},i_{s+1}\} \in E\ \forall s = 0,\ldots,k - 1\). Two nodes i and j are said to be connected in Γ if i = j or if there is a path between them in Γ. We call chain the set of nodes on a path with different endpoints and we denote by s-chain a chain with s nodes. A connected component in Γ is a maximal subset of V with the property that any two nodes of V are connected in Γ. We denote by C Γ the set of connected components in Γ. A graph Γ is said to be connected if there exists a path between every two elements of V. A subset of nodes S ⊆ V (respectively, a set of links A ∈ E) is connected if the induced graph Γ S (respectively, Γ A ) is connected.

A cycle in Γ is a path (i 0, i 1, ⋯ , i k ) such that i 0 = i k . A forest is a graph without cycles. A tree is a forest with only one connected component.

3 Cooperative Games with Restricted Communication: The Position Value

A coalitional game describes a situation in which every coalition of players is able to form and cooperate. If there exists a restriction on the interaction possibilities among players, not all coalitions are feasible. We can represent this situation by introducing a network structure that models the interactions between players. This leads to the definition of a communication situation.

Given a graph Γ and a coalitional game (N, v) we can define the so-called communication situation [13] as the triple (N, v, Γ), where N is the set of players, (N, v) is a coalitional game and Γ is an undirected graph with N as set of vertices. The graph Γ = (N, E) describes the communication possibilities between players: an indirect communication between i and j is possible if there is a path that connects them; if {i, j} ∈ E, then i and j can communicate directly.

Borm et al. [4] introduce a solution concept for a communication situation based on the approach of Meessen [12]: given Γ = (N, E) and A ⊆ E, the link game v L is defined by:

$$\displaystyle{ v^{L}(A) =\sum _{ T\in C_{\varGamma _{A}}}v(T), }$$
(8)

where \(C_{\varGamma _{A}}\) is the set of connected components in Γ A . We denote by \(\mathcal{G}_{L}\) the vector space of all link games on Γ = (N, E), E ⊆ {{ i, j}: i, j ∈ V, i ≠ j}, where N is a fixed set of players. Note that the dimension of \(\mathcal{G}_{L}\) is equal to the number of connected subsets of E; i.e. the cardinality of {A ⊆ E: Γ A  is connected}.

Every link game v L can be written as a linear combination of unanimity link games as follows:

$$\displaystyle{ v^{L} =\sum _{ A\subseteq E}c_{A}(v^{L})u_{ A}, }$$
(9)

where c A are the unanimity coefficients of v L:

$$\displaystyle{ c_{A}(v^{L}) =\sum _{ B\subseteq A}(-1)^{\vert A\vert -\vert B\vert }\:v^{L}(B); }$$
(10)

or equivalently c {l}(v L) = v L({l}) and for A ⊆ E, | A | ≥ 2:

$$\displaystyle{ c_{A}(v^{L}) = v(A) -\sum _{ B\subsetneq A,B\neq \emptyset }c_{B}(v^{L}). }$$
(11)

Given a communication situation (N, v, Γ), the position value π(N, v, Γ) is defined as:

$$\displaystyle{ \pi _{i}(N,v,\varGamma ) = \frac{1} {2}\sum _{a\in A_{i}}\varPhi _{a}(v^{L})\:\forall i \in N, }$$
(12)

where A i  = {{ i, j} ∈ E, j ∈ N} is the set of all links for which player i is an endpoint. Note that, since the players in v L are the elements of E, i.e. the links of Γ, in formula (12) we compute the Shapley value of a link. We shall write π(v) when there is no ambiguity about the underlying network.

We point out here a particular property satisfied by the position value that will be useful for our purpose, namely the superfluous arc property [21]. Given a communication situation (N, v, Γ), with Γ = (N, E), we call superfluous a link a such that \(v^{L}(A \cup \{ a\}) = v^{L}(A)\ \forall A \subseteq E\).

The superfluous arc property states that if a is a superfluous arc, then π(N, v, Γ) = π(N, v, Γ′), where Γ′ = (N, E∖{a}). The property follows directly by formula (12): the links (or arcs) that provide a marginal contribution equal to zero to every coalition of links (not containing the link itself) do not give contribution to the sum in (12), thus the position value does not change if they are removed from the network.

Note that, like the Shapley value, every semivalue Ψ p induces a solution concept ψ p for communication situations given by:

$$\displaystyle{ \psi _{i}^{\mathbf{p}}(N,v,\varGamma ) = \frac{1} {2}\sum _{a\in A_{i}}\varPsi _{a}^{\mathbf{p}}(v^{L}). }$$
(13)

We write ψ(v) when there is no ambiguity about the underlying network. Note that, by definition of semivalue, the superfluous arc property still holds for every solution ψ corresponding to a given semivalue.

See [18, 19, 21] for an axiomatic characterization of the position value for network situations, which generalize the context of communication situations.

4 Coalition Formation and Allocation Protocols

In Sect. 2 we introduced the Shapley value and gave a formula to compute it. Formula (4) has the following interpretation: suppose that the players gather one by one in a room to create the grand coalition. Each player entering the room gets his marginal contribution to the coalition that was already in the room. Assuming that all the different orders in which they enter are equiprobable, one gets the formula, where n! is the number of permutations on a set of n elements.

Let us consider a different mechanism of coalition formation: let us assume that a coalition forms by subsequent formation of links among players. This naturally leads to consider a communication situation, where a network between the players is produced by a permutation of links and all the different orders in which the links form are considered to be equiprobable.

In this scenario, we can imagine that, when a link between two players forms, the players that are connected to each other receive a certain value according to some rule. Let us suppose that, at each step of the network formation process, when a link between two players i and j forms, the value of the coalition S, where S is the connected component containing i and j, reduced by the values of the connected components formed by the players of S at the previous step, is shared between the players involved according to a certain protocol. Then a natural question rises: How to share this value?

Given a communication situation (N, v, Γ), let us consider a possible permutation σ of links. At each step k of the network formation process, when the k-th link a = { i, j} in the sequence determined by σ forms, let us consider the surplus produced by a:

$$\displaystyle{ S_{k}^{\sigma } = v(S) - v(C_{ k-1,\sigma }^{i}) - v(C_{ k-1,\sigma }^{j}) }$$
(14)

where S is the connected component in Γ containing i and j at the step k, and C k−1, σ i and C k−1, σ j are the connected components in Γ at the step k − 1, containing i and j, respectively.

An allocation protocol is a rule that specifies how to divide S k σ between the players in S. Given an allocation protocol r and a communication situation (N, v, Γ), a solution of v, that we shall denote by ϕ r(v), is given by:

$$\displaystyle{ \phi _{i}^{r}(v) = \frac{1} {\vert E\vert !}\sum _{\sigma \in \varSigma _{E}}\sum _{k=0}^{\vert E\vert }f_{ i}^{r}(S_{ k}^{\sigma }),\:\forall i \in N, }$$
(15)

where Σ E is the set of possible orders on the set of links E in Γ and f i r is a function that assigns to each player i ∈ N a fixed amount of the surplus S k σ, depending on the allocation protocol r.

In other words, the solution ϕ r(v) is computed by considering all possible permutations of links, and summing up, for each player i, all the contributions he gets with the allocation procedure r, averaged by the number of permutations over the set of links among the players, with the interpretation discussed at the beginning of this section.

This idea leads to the introduction of a class of solution concepts: different choices of the allocation protocol define different solutions for a communication situation. At a certain step, when a link a = { i, j} forms, it is possible to consider the allocation protocol that equally divides the surplus between players i and j only. The solution obtained by this particular allocation protocol is indeed the position value π defined in (12).

Note that other solution concepts can be achieved by sharing the surplus among the players involved in a different way.

5 Preliminary Results

In this section we present some preliminary results that will be useful in the next sections.

Proposition 1.

Let (N,v,Γ) be a communication situation and v L the corresponding link game. Then c A (v L ) = 0 for any coalition A ⊆ E which is not connected in Γ, where c A (v L ) are the unanimity coefficients of v L .

Proof.

We prove the result by induction on a = | A | .

Suppose a = 2, i.e. A = { l 1, l 2}, l 1, l 2 ∈ E, where l 1 and l 2 belong to two different connected components. From this hypothesis and from (8) and (11) we get

$$\displaystyle\begin{array}{rcl} v^{L}(A)& =& v(\{l_{ 1}\}) + v(\{l_{2}\}) \\ & =& c_{\{l_{1}\}}(v^{L}) + c_{\{ l_{2}\}}(v^{L}){}\end{array}$$
(16)

and

$$\displaystyle\begin{array}{rcl} v^{L}(A)& =& \sum _{ B\subseteq A}c_{B}(v^{L}) \\ & =& c_{\{l_{1}\}}(v^{L}) + c_{\{ l_{2}\}}(v^{L}) + c_{ A}(v^{L}).{}\end{array}$$
(17)

By comparing (16) and (17), we get that c A (v L) = 0.

Let us now consider k ≥ 2 and suppose by inductive hypothesis that \(c_{B}(v^{L}) = 0,\forall B\) such that | B | ≤ k and B is not connected in Γ. We shall prove that \(c_{A}(v^{L}) = 0\ \forall A\) such that A is not connected and | A | = k + 1. Let B 1 ⊂ A be a connected component in Γ, i.e. \(B_{1} \in C_{\varGamma _{A}}\). Then by hypothesis A∖B 1 ≠ ∅. It follows that:

$$\displaystyle{ v^{L}(A) = v^{L}(B_{ 1}) + v^{L}(A\setminus B_{ 1}). }$$
(18)

Moreover it holds:

$$\displaystyle\begin{array}{rcl} v^{L}(A)& =& \sum _{ B\subseteq A}c_{B}(v^{L}) \\ & =& \sum _{B\subseteq B_{1}}c_{B}(v^{L}) +\sum _{ B\subseteq A\setminus B_{1}}c_{B}(v^{L}) +\sum _{ B\subseteq A:A\cap B_{1}\neq \emptyset \wedge B\cap (A\setminus B_{1})\neq \emptyset }c_{B}(v^{L}) \\ & =& v^{L}(B_{ 1}) + v^{L}(A\setminus B_{ 1}) +\sum _{B\subsetneq A:B\cap B_{1}\neq \emptyset \wedge B\cap (A\setminus B_{1})\neq \emptyset }c_{B}(v^{L}) + c_{ A}(v^{L}) \\ & =& v^{L}(B_{ 1}) + v^{L}(A\setminus B_{ 1}) + c_{A}(v^{L}), {}\end{array}$$
(19)

where (19) follows from the inductive hypothesis.

Then, by comparing (18) and (19) we get: c A (v L) = 0, which ends the proof. ⊓ ⊔

Note that an equivalent result has been proved by Van den Nouweland et al. [21] for a value function (i.e. a characteristic function over subsets of links).

Corollary 1.

The family of unanimity games {u A ,A ⊆ E, where A is connected in Γ} is a basis for \(\mathcal{G}_{L}\)

Proof.

From Proposition 1, we get that {u A , A ⊆ E, where A is connected in Γ} is a spanning set for the vector space \(\mathcal{G}_{L}\). Moreover the cardinality of this set is equal to the dimension of \(\mathcal{G}_{L}\). □

Equivalent results hold in the context of graph-restricted games and the proofs can be found, for example, in [8]. Moreover, the previous results hold for a generic value function v that satisfies the component additivity property, i.e. such that \(v(A) =\sum _{T\in C_{\varGamma _{ A}}}v(T)\) for every network Γ over the set of nodes N.

6 The Position Value on Particular Classes of Communication Situations

In general, given a communication situation (N, v, Γ) it is not easy to compute the position value. However, it is so for particular classes of games and graphs. In this section we give formulas to compute the position values on particular classes of communication situations, where the underlying network is described by a tree or a cycle. We assume w.l.o.g throughout our work that \(v(\{i\}) = 0\ \forall i \in N\).

6.1 The Position Value on Trees

Let (N, v, Γ) be a communication situation, where Γ = (N, E) is a tree and | N | = n. Given a node i ∈ N and a coalition S ⊆ N, we define fringe(S) = { j ∈ N∖S such that {i, j} ∈ E for some i ∈ S}. Let f(S): = | fringe(S) | , deg S (i) the degree of i in S, i.e. the number of nodes in S that are directly connected to i in Γ and deg fringe(S)(i) the number of nodes in fringe(S) that are directly connected to i in Γ.

We provide a formula for the position value on e S , with S ⊆ N connected in Γ such that | S | ≥ 2. If S is not connected, it doesn’t make sense to consider the position value of e S , since the associated link game e S L is the null game.

Proposition 2.

Let S ⊆ N connected in Γ, where Γ is a tree and |S|≥ 2. Then the position value on the canonical game e S is given by:

$$\displaystyle{ \pi _{i}(e_{S}) = \left \{\begin{array}{ll} \frac{1} {2} \frac{(s-2)!(f(S)-1)!} {(m-1)!} \:\delta _{i}(s)&\mbox{ if $i \in S$}\\ \\ -\frac{1} {2} \frac{(s-1)!(m-s-1)!} {(m-1)!} & \mbox{ if $i \in fringe(S)$}\\ \\ 0 &\text{otherwise} \end{array} \right. }$$
(20)

where m = s + f(S) and δ i (s) = f(S)deg S (i) − (s − 1)deg fringe(S) (i).

Proof.

We observe that every link not in E S∪fringe(S) is superfluous. Therefore π i (e S ) = 0 for every i ∉ S ∪ fringe(S) and we can reduce the network to (S ∪ fringe(S), E S∪fringe(S)).

Consider i ∈ S. Node i gets a positive contribution (equal to 1∕2) every time a link incident to it is the last one to form inside S and no link outside S already formed. This happens deg S (i) times. Moreover it gets a negative contribution (equal to − 1∕2) when all the links in S already formed and a link incident to i is the first one to form outside S. This happens deg fringe(S)(i) times. Therefore we get

$$\displaystyle{\pi _{i}(e_{S}) = \frac{1} {2}\Big[\frac{(s - 2)!(m - s)!} {(s - 1)!} deg_{S}(i) -\frac{(s - 1)!(m - s - 1)!} {(m - 1)!} deg_{fringe(S)}(i)\Big],}$$

where m = s + f(S) and the expression (20) follows directly.

Consider i ∈ fringe(S). Node i gets a negative contribution when all the links in S already formed and the only link that connects i to S is the first one to form outside S. Therefore we get

$$\displaystyle{\pi _{i}(e_{S}) = -\frac{1} {2} \frac{(s - 1)!(m - s - 1)!} {(m - 1)!}.}$$

□

Note that the formula holds also for S = N, with fringe(N) = ∅, which implies that f(N) = 0. On the other hand, when S = { i}, the associated link game e S L is the null game, as for S not connected.

Let us consider the unanimity games {u S , S ⊆ N}. We also provide a formula for the position value on u S , with S ⊆ N connected in Γ such that | S | ≥ 2.

Proposition 3.

Let S ⊆ N connected in Γ, where Γ is a tree and |S|≥ 2. Then the position value on the unanimity game u S is given by:

$$\displaystyle{ \pi _{i}(u_{S}) = \left \{\begin{array}{ll} \frac{1} {2}deg_{s}(i) \frac{1} {s-1} & \mbox{ if $i \in S$}\\ \\ 0 &\mbox{ otherwise}. \end{array} \right. }$$
(21)

Proof.

We observe that every link not in E S is superfluous. Therefore π i (u S ) = 0 for every i ∉ S and we can reduce the network to (S, E S ).

Consider i ∈ S. Node i gets a positive contribution (equal to 1∕2) every time a link incident to it is the last one to form inside S. This happens deg S (i) times. Therefore we get

$$\displaystyle{\pi _{i}(e_{S}) = \frac{1} {2} \frac{(s - 2)!(m - s)!} {(m - 1)!} deg_{S}(i),}$$

where m = s and the result follows directly. □

Moreover, if S = { j}, easy calculations show that:

$$\displaystyle{\pi _{i}(u_{S}) = \left \{\begin{array}{ll} \frac{1} {2} & \mbox{ if $i = j$} \\ \frac{1} {2f(S)} & \mbox{ if $i \in fringe(\{j\})$} \\ 0 &\mbox{ otherwise}. \end{array} \right.}$$

6.2 The Position Value on Cycles

Let (N, v, Γ) be a communication situation, where Γ = (N, E) is a cycle and | N | = n.

We provide a formula for the position value on e S , where S ⊆ N is a s-chain (i.e. S is connected in Γ) with 2 ≤ s ≤ n − 2. If S is not connected, or S = { i}, it doesn’t make sense to consider the position value of e S , since the associated link game e S L is the null game.

Proposition 4.

Let S ⊆ N be a s-chain in Γ, where Γ is a cycle and 2 ≤ s ≤ n − 2. Then the position value on the canonical game e S is given by:

$$\displaystyle{ \pi _{i}(e_{S}) = \left \{\begin{array}{ll} \frac{1} {2} \frac{(s-2)!(m-s-1)!} {(m-1)!} (m - 2s + 1)&\mbox{ if $i \in S_{e}$}\\ \\ \frac{(s-2)!(m-s)!} {(m-1)!} & \mbox{ if $i \in S_{i}$}\\ \\ -\frac{1} {2} \frac{(s-1)!(m-s-1)!} {(m-1)!} & \mbox{ if $i \in fringe(S)$}\\ \\ 0 &\mbox{ otherwise} \end{array} \right. }$$
(22)

where m = s + f(S), S e is the set of the extremal nodes and S i = S∖S e is the set of the internal nodes.

Proof.

We observe that every link not in E S∪fringe(S) is superfluous. Therefore π i (e S ) = 0 for every i ∉ S ∪ fringe(S) and we can reduce the network to (S ∪ fringe(S), E S∪fringe(S)).

Consider i ∈ S. We shall distinguish between the internal and extremal nodes of the chain S. Let i ∈ S e the set of endpoints in Γ S . Node i gets a positive contribution when the link incident to it in the chain is the last one to form inside S and no link outside S already formed. Moreover it gets a negative contribution when all the links in S already formed and the link incident to i in fringe(S) is the first one to form outside S. Therefore we get

$$\displaystyle{\pi _{i}(e_{S}) = \frac{1} {2}\Big[\frac{(s - 2)!(m - s)!} {(m - 1)!} -\frac{(s - 1)!(m - s - 1)!} {(m - 1)!} \Big],}$$

where m = s + f(S) and the expression (22) follows directly.

Let i ∈ S i  = S ∖ S e . Node i gets a positive contribution when one of the two links incident to it in S is the last one to form inside S. Therefore we get

$$\displaystyle{\pi _{i}(e_{S}) = 2\Big[\frac{1} {2} \frac{(s - 2)!(m - s)!} {(m - 1)!} \Big].}$$

Consider i ∈ fringe(S). Node i gets a negative contribution when all the links in S already formed and the only link that connects i to S is the first one to form outside S. Therefore we get

$$\displaystyle{\pi _{i}(e_{S}) = -\frac{1} {2} \frac{(s - 1)!(m - s - 1)!} {(m - 1)!}.}$$

□

On the other hand, if S = N∖{j}, the following proposition holds:

Proposition 5.

Let S ⊆ N be a s-chain in Γ, where Γ is a cycle and s = n − 1. Then the position value on the canonical game e S is given by:

$$\displaystyle{ \pi _{i}(e_{S}) = \left \{\begin{array}{ll} \frac{4-n} {2n(n-1)(n-2)} & \mbox{ if $i \in S_{e}$}\\ \\ \frac{2} {n(n-1)(n-2)} & \mbox{ if $i \in S_{i}$}\\ \\ - \frac{1} {n(n-1)} & \mbox{ if $i \in fringe(S)$}\\ \end{array} \right. }$$
(23)

where S e is the set of the extremal nodes and S i = S∖S e is the set of the internal nodes.

Proof.

Using the same argument of the previous proof, formulas for i ∈ S are derived by noting that there is no superfluous link and m = n. Moreover, the only node i ∈ fringe(S) gets twice the contribution he gets in the previous case since it is directly connected to S by its incident links. □

Note that if S = N, there is no superfluous link and by symmetry \(\pi _{i}(e_{S}) = \frac{1} {n}\), for all i ∈ N.

We provide a formula for the position value on u S , with S ⊆ N an s-chain. If 2 ≤ | S | ≤ n − 1, the following proposition holds:

Proposition 6.

Let S ⊆ N be a s-chain in Γ, where Γ is a cycle and 2 ≤ s ≤ n − 1. Then the position value on the unanimity game u S is given by:

$$\displaystyle{\pi _{i}(u_{S}) = \left \{\begin{array}{ll} \frac{1} {2}\big[\frac{(n-s+1)} {n(s-1)} + (2s - 3) \frac{1} {n(n-1)}\big] &\mbox{ if $i \in S_{e}$}\\ \\ \frac{1} {2}\big[2\frac{(n-s+1)} {n(s-1)} + 2(s - 2) \frac{1} {n(n-1)}\big]&\mbox{ if $i \in S_{i}$}\\ \\ (s - 1) \frac{1} {n(n-1)} & \mbox{ if $i\notin S$} \end{array} \right.}$$

where S e is the set of the extremal nodes, i.e. the endpoints in Γ S , and S i = S∖S e is the set of the internal nodes.

Proof.

We observe that there is no superfluous link. Consider i ∈ S e . Node i gets a positive contribution (equal to 1∕2) every time the link incident to it in the chain is the last one to form inside S (no matter which links already formed outside S).

Moreover it gets a positive contribution when the link incident to it outside the chain is the last one to form in E ∖{a}, where a is the link incident to i in the chain S and every time one of the two links incident to i is the last one to form in E ∖{b}, where b is one of the links in the chain S not incident to i. Note that the first case happens \(\sum _{k=0}^{n-s}{n - s + 1\choose k}\) times; the second one only occurs once and the last case happens 2(s − 2) times. This yields the following formula for i ∈ S e :

$$\displaystyle{\pi _{i}(u_{S}) = \frac{1} {2}\left [\sum _{k=0}^{n-s}{n - s + 1\choose k}\frac{(s - 2 + k)!(n - s - k + 1)!} {n!} + (2s - 3) \frac{1} {n(n - 1)}\right ].}$$

Consider i ∈ S i . Node i gets a positive contribution (equal to 1∕2) every time one of the two links incident to it in the chain is the last one to form inside S (no matter which links already formed outside S). Moreover it gets a positive contribution whenever one of the two links incident to it is the last one to form in E ∖{a}, where a is other link incident to i in the chain S and every time one of the two links incident to i is the last one to form in E ∖{b}, where b is one of the links in the chain S not incident to i. Note that the first case happens \(2\sum _{k=0}^{n-s}{n - s + 1\choose k}\) times; the second one only occurs twice and the last case happens 2(s − 3) times.

Consider i ∉ S. Node i gets a positive contribution (equal to 1∕2) every time one of the two links incident to it is the last one to form in E ∖{a}, where a is one of the links in the chain S. This happens 2(s − 1) times. It follows that:

$$\displaystyle{\pi _{i}(u_{S}) = \left \{\begin{array}{ll} \frac{1} {2}\big[\sum _{k=0}^{n-s}{n - s + 1\choose k}\frac{(s-2+k)!(n-s-k+1)!} {n!} + (2s - 3) \frac{1} {n(n-1)}\big] &\mbox{ if $i \in S_{e}$}\\ \\ \frac{1} {2}\big[2\sum _{k=0}^{n-s}{n - s + 1\choose k}\frac{(s-2+k)!(n-s-k+1)!} {n!} + 2(s - 2) \frac{1} {n(n-1)}\big]&\mbox{ if $i \in S_{i}$}\\ \\ (s - 1) \frac{1} {n(n-1)} & \mbox{ if $i\notin S$} \end{array} \right.}$$

This formula can be simplified by using Lemma (1) (see Appendix):

$$\displaystyle\begin{array}{rcl} & & \sum _{k=0}^{n-s}{n - s + 1\choose k}\frac{(s - 2 + k)!(n - s - k + 1)!} {n!} \\ & & \qquad = \frac{1} {n}\sum _{k=0}^{n-s}{n - s\choose k} \frac{n - s + 1} {n - s - k + 1} \frac{(s - 2 + k)!(n - s - k + 1)!} {(n - 1)!} \\ & & \qquad = \frac{n - s + 1} {n} \sum _{k=0}^{n-s}{n - s\choose k}\frac{(s - 2 + k)!(n - s - k)!} {(n - 1)!} \\ & & \qquad = \frac{(n - s + 1)} {n(s - 1)}, {}\end{array}$$
(24)

where (24) follows from identity (27). This ends the proof. ⊓ ⊔

Note that if S = N, all players are symmetric and \(\pi _{i}(u_{S}) = \frac{1} {n}\). On the other hand, if S = { j}, the position value is very easy to compute. In fact, the links a = { i, j} and b = { j, k} are symmetric players in the link game, while all the remaining links are superfluous. This implies that \(\varPhi _{a} =\varPhi _{b} = \frac{1} {2}\) and \(\varPhi _{c} = 0\ \forall c \in E\setminus \{a,b\}\).

$$\displaystyle{\pi _{i}(u_{S}) = \left \{\begin{array}{ll} 1/2&\mbox{ if $i = j$} \\ 1/4&\mbox{ if $i\neq j,\{i,j\} \in E$} \\ 0 &\mbox{ otherwise}. \end{array} \right.}$$

6.3 The Position Value for a Generic Coalitional Game

In the last two sections we provided formulas for the position value on particular classes of games. We shall use those formulas and the results of Sect. 5 to derive an expression that shows the relation between the position value for a generic game and the position value of unanimity games.

Proposition 7.

Let (N,v,Γ) be a communication situation. Then the position value for i ∈ N is given by

$$\displaystyle{ \pi _{i}(v) =\sum _{A\subseteq E\text{ connected}}c_{A}(v^{L})\pi _{ i}(w), }$$
(25)

where w is such that w L = u A .

Proof.

By definition of position value and by Corollary 1 we get that:

$$\displaystyle\begin{array}{rcl} \pi _{i}(v)& =& \frac{1} {2}\sum _{a\in A_{i}}\varPhi _{a}(v^{L}) = \frac{1} {2}\sum _{a\in A_{i}}\sum _{A\subseteq E\text{ connected}}c_{A}(v^{L})\varPhi _{ a}(u_{A}) {}\\ & =& \sum _{A\subseteq E\text{ connected}}c_{A}(v^{L})\pi _{ i}(w) {}\\ \end{array}$$

where w is such that w L = u A . □

This result implies that, in order to compute the position value of a generic game, we have to consider the position value on those games whose corresponding link game is a unanimity game on a connected subset of links.

However, when Γ is a tree, the formula (25) can be simplified and a direct relation between the position value for a generic game and the position value of unanimity games can be obtained.

Corollary 2.

Let (N,v,Γ) be a communication situation, where Γ is a tree. Then the position value for i ∈ N is given by

$$\displaystyle{ \pi _{i}(v) =\sum _{S\subseteq N\text{ connected}}c_{E_{S}}(v^{L})\pi _{ i}(u_{S}). }$$
(26)

Proof.

Consider A ⊆ E connected in Γ. Let S be the set of nodes in Γ A . This definition of S induces a bijection between the set {w: w L = u A , A connected in Γ} and the set {u S : S ⊆ N, S connected in Γ}. Therefore the result follows directly. □

However, the computation of the position value for a generic game remains difficult even if the underlying graph is a tree. Indeed, deriving the position value using formula (26) requires listing all subtrees of a tree (the problem has been extensively addresses in the literature, see, for example, [7, 15, 20] without) and computing the corresponding unanimity coefficients.

7 Conclusions

In this paper we proposed a family of solution concepts for communication situations that embraces the principles of the two main approaches existing in the related literature. We also provided a different interpretation of the position value, as the solution concept arising from a particular symmetric allocation protocol, which prescribes how to share the surplus generated by a link among the players involved in the network formation process. Moreover, we provide an expression for the position value of a game when the underlying network is a tree, which relates its computation to the one for unanimity games.

The computation of the position value and its complexity remains an open problem, which has not been studied in the literature and deserves, in our opinion, further investigation. Another interesting direction for future research is to provide a characterization of the family of solution concepts we introduced, based on some reasonable properties that an allocation protocol should satisfy. Moreover, it would be interesting to investigate the relationship between different allocation protocols and known solution concepts, besides the position value.