A connection-based analysis of networks using the position value: a computational approach

Expert Systems With Applications 251 (2024) 124096 Available online 29 April 2024 0957-4174/© 2024 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/bync/4.0/). Contents lists available at ScienceDirect Expert Systems With Applications journal homepage: www.elsevier.com/locate/eswa A connection-based analysis of networks using the position value: a computational approach Encarnación Algabaa, Alejandro Saavedra-Nievesb,∗ aDepartamento de Matemática Aplicada II and IMUS, Universidad de Sevilla, Spain bCITMAga, Departamento de Estatística, Análise Matemática e Optimización, Universidade de Santiago de Compostela, Spain ARTICLE INFO Keywords: Game theory Position value Communication situation Networks Ranking ABSTRACT In this paper, we introduce the position value as a centrality measure to evaluate the relevance of the edges and players in a network, with the additional advantage that this value integrates the degree measure of each player in it. In fact, in the real world, it is particularly important to consider the natural influence of connections of a player in a network. Its applications were very limited in real-world situations due to the high computational complexity of exactly obtaining this value. With the aim of solving this problem we provide a method, based on sampling theory, to estimate the position value, which is analyzed in terms of the theoretical properties of the resulting estimator. Moreover, we establish specific statistical results for bounding the absolute error in this approximation. It is important to emphasize that this approach allows for obtaining rankings not only of the nodes but also of the edges of the network. To illustrate the advantages and interest of the proposed methodology, as well as the variety of problems that can be analyzed in this framework, we applied it in three very different settings, the suburban train network of Madrid in the year 2000, the Spanish national team in a match against Portugal, and the Zerkani network responsible for the terrorist attacks of Paris (2015) and Brussels (2016). 1. Introduction In this paper, we focus on the position value for communication situations as a centrality measure, solving by sampling methods the computational problems involved with it, and showing the advantages and variety of settings in which it can be applied. This value was introduced in Meesen (1988) and later studied by Borm et al. (1992), who provided a characterization of it for cycle-free communication situations. In Algaba et al. (2000), this value was generalized and characterized for a special class of union stable systems which extends the subclass of cycle-free communication situations and, in Algaba et al. (2004), its connection with hypergraphs was established. Slikker (2005) provided a first characterization of the position value for the whole class of communication situations. New characterizations of the position value as a special solution of the class of Harsanyi solutions in the settings of communication situations and union stable systems are obtained, respectively, in van den Brink et al. (2011) and Algaba et al. (2015). Recently, Manuel et al. (2023) have provided a characterization of the position value from a marginality properties-based approach. Also, relationships, in these contexts, between the Myerson value (Myerson,1977) and the position value can be found in Gómez et al. (2004), Casajus (2007) and Algaba et al. (2012). ∗Corresponding author. E-mail addresses: [email protected] (E. Algaba), [email protected] (A. Saavedra-Nieves). The literature about the position value shows interesting features about this value, specifically, in a communication situation, the position value gives a measure of the importance of a node in a graph, assessing firstly the relevance of the communication links between players, which is of big interest when applying to real data in network structures defined by an undirected graph. However, its exact computation is a very complicated computational task. In fact, the position value is defined from the Shapley value applied to the transferable utility game (TU game) defined on the set of edges that connect the different nodes, focusing on the role of the edges in the network. Nevertheless, for certain class of TU games and/or graphs some efficient algorithms have been introduced for computing certain values based on the Shapley value, for instance, Fernández et al. (2002) proposed polynomial time algorithms for computing the Myerson value (Myerson,1977), for weighted voting games restricted by a tree. Likewise, algorithms by means of the Harsanyi dividends for the Myerson value can be found in Algaba et al. (2007). Aadithya et al. (2010), Michalak et al. (2013), and Szczepanski et al. (2012,2016) also gave polynomial time algorithms for computing the Shapley value and the so-called value betweenness centrality, for certain graphs, respectively. In the general framework of TU games, a common problem that has https://doi.org/10.1016/j.eswa.2024.124096 Received 29 August 2023; Received in revised form 17 April 2024; Accepted 21 April 2024 Expert Systems With Applications 251 (2024) 124096 2 E. Algaba and A. Saavedra-Nieves already been tackled was the computational drawbacks of using known solution concepts as allocation procedures in large-scale real-world problems. Namely, the study of the Shapley value (Shapley,1953) and the Banzhaf value (Banzhaf,1964), as well as their extensions the Owen value (Owen,1977) and the Banzhaf-Owen value (Owen,1982), respectively, to contexts with a priori unions, have been already dealt with. Specifically, sampling techniques were considered for the approximation of the Shapley value (Castro et al.,2009) and the Banzhaf value (Bachrach et al.,2010), and their extensions when assuming an a priori unions structure, such as the Owen value (Saavedra-Nieves et al.,2018) and the Banzhaf-Owen value (Saavedra-Nieves & FiestrasJaneiro,2021). More recently, Saavedra-Nieves (2023) used stratified sampling for the approximation of the Owen value and the BanzhafOwen value. For other families of games, such as games with externalities, their solutions have been also approximated (Saavedra-Nieves & Fiestras-Janeiro,2022). However, to the best of our knowledge, the problem of studying the position value in communication situations from a computational point of view, and apply it as centrality measure to provide simultaneously rankings of both nodes and edges of a network defined by a graph, has not been addressed so far. Along the last decades, social network analysis has focused on the identification of those key members within an internal organization, often without full knowledge of the numerous connections between these elements. For instance, in sports, the interactions of players of a team can be also described as a complex network (see Buldú et al., 2019). Similarly, from a socio-economic perspective, this approach allows us to quantify the relative importance of transfer stops in public transport systems (see Hadas et al.,2017). Terrorist networks are a case of networks, in which members use violence, receiving much attention because of the massive attacks in Western World along recent years. Examples include the 9/11 attacks in 2001, or the attacks carried out by the Zerkani network of Paris in 2015 and Brussels in 2016, among others. Koschade (2006), Sparrow (1991), Klerks (2001), Farley (2003), Guzman et al. (2014), and McGuire et al. (2015) are examples that use the conventional social network perspective to identify essential agents within this kind of organizational structure. However, recent works in graph analysis have incorporated a link-based perspective, for instance, for the detection of communities. We refer to Li et al. (2022), that use likelihood optimization; or Song et al. (2022) and Li et al. (2023), who consider a non-cooperative game scheme for the same purpose. In network analysis described by a graph, Lindelauf et al. (2013) and Husslage et al. (2015) are the first in considering information about the communication between the members of the network. In fact, the heterogeneity of edges and nodes is incorporated for the first time through transferable utility games (TU games), in which cooperation of individuals is a vital aspect. An overall ranking of the nodes of the network, according to its importance, can be determined using solutions for TU games. For example, Hamers et al. (2019) rank the members of the Zerkani network using the Shapley value. Recently, Algaba, Prieto, Saavedra-Nieves, and Hamers (2023) and Algaba, Prieto, and Saavedra-Nieves (2023) assume the existence of an a priori union system modeling the affinities in the cooperation of agents, and Saavedra-Nieves and Casas-Méndez (2023) use games with externalities for this same purpose. Unlike of the perspective analyzed in all these works, the link-based perspective in graph analysis has not been still considered, in practice, as basis for a ranking of the members of a network under cooperation. In this paper, we want to focus on the importance of a certain node in a network according to its position in it, namely, through of the relevance of the communication links between players. With this aim, we firstly analyze the position value for communication situations (cf. Borm et al.,1992) as a centrality measure for networks from a quantitative approach. This value offers additional advantages in comparison with all centrality measures proposed until now, even compared to those based on classical solution concepts for TU games considered so far. The position value, following the cooperative approach in the literature, is the unique solution concept that includes not only information related to the nodes, but also to the number of links incident on them and their strength. On one hand, the position value captures the topology of the network, independently of the initial TU game. On the other hand, it allows for providing a ranking not only of the influence of the nodes but also, it can be obtained a ranking of the strength of the connections among players, achieving a much more complete information and overview of the network than with the classical measures in social network analysis and the ones based on TU games. To illustrate and motivate it, we provide a first application to the suburban train network of Madrid in the year 2000, establishing the main stations and the most robust railway segments. However, many other networked situations can be represented by means of communication situations in which connections between network members and their individual weights have a strong influence on the study of the effectiveness of coalitions at different cooperation scenarios. A major drawback of considering the position value lies in the fact of that, due to the computational complexity involved, its exact calculation has so far been limited to academic examples with few nodes and edges not being possible to apply it for real world examples, in general. Thus, inspired by the sampling techniques that were considered for the Shapley value estimation (Castro et al.,2009), we propose a specific approximation methodology based on simple random sampling with replacement to estimate the position value for large-scale communication situations. In this context, we specifically analyze the problem of bounding the estimation error by providing some useful theoretical results. Moreover, to illustrate the applicability and relevance of the position value, we center on three very different scenarios that reflect the wide range of real situations in which its use is justified. First, we motivate its introduction as centrality measure in the setting of the suburban train network of Madrid in the year 2000. Second, we classify the players as well as the best performances of pairs of players corresponding to the Spanish national team in a match against Portugal. Third, we rank the members providing additionally the stronger connections between terrorists of the Zerkani network supporting the attacks of Paris and Brussels in 2015 and 2016, respectively. Finally, a comparison between the position value and the most well-known centrality measures in the literature, related to this value, is made, showing the interest and utility of this approach. This paper is structured as follows. Section 2briefly presents the position value and those notions required for the understanding of the paper. Section 3introduces the position value as a new connectionbased ranking mechanism of nodes and edges corresponding to a communication situation, motivating it with an application to the suburban train network of Madrid corresponding to the year 2000. The computational problems arising from its exact calculation in those situations with a large enough number of links in the network are addressed in Section 4from a sampling perspective. Section 5illustrates the performance of proposal of ranking on two different scenarios: we classify both the players and pairs of players of the Spanish national team in a match against Portugal, and we rank the terrorists and pairs of terrorists of the Zerkani network. Finally, taking account the nature of the position value and with the aim of showing the feasibility of our approach, the results are compared to those obtained for the main centrality measures related to the graph or the own definition of the position value. Hence, the position value is analyzed versus the main classical centrality measures in the literature as well as the Myerson value (Myerson,1977), defined also from Shapley value (Shapley, 1953) of a TU game whose cooperation among the players is restricted by the connection of the nodes in the graph. Finally, Section 6 concludes. 2. Preliminaries In this section, we formally present some theoretical terminology on cooperative game theory and communication situations, focusing on solution concepts such as the Shapley value (cf. Shapley,1953) and the position value (cf. Meesen,1988). Expert Systems With Applications 251 (2024) 124096 3 E. Algaba and A. Saavedra-Nieves 2.1. On transferable utility games and the Shapley value Atransferable utility game, or TU game, is a pair (𝑁, 𝑣), where 𝑁= {1,2,…, 𝑛}is the set of players, called usually the grand coalition, and 𝑣is a map that assigns a real value 𝑣(𝑆)to each coalition 𝑆 ⊆ 𝑁 such that 𝑣(∅) = 0. The set of all cooperative games with player set 𝑁is denoted by 𝑁. For each 𝑇 ⊆ 𝑁, with 𝑇≠∅, the unanimity game (𝑁, 𝑢𝑇)is given by 𝑢𝑇(𝑆) = 1, if 𝑇 ⊆ 𝑆, and 𝑢𝑇(𝑆) = 0, otherwise. It is wellknown that the unanimity games form a basis for the vector space 𝑁. For every 𝑣∈𝑁, it holds that 𝑣=∑𝑇 ⊆𝑁 𝑇≠∅ 𝛥𝑣(𝑇)𝑢𝑇, where 𝛥𝑣(𝑇) = ∑𝑆⊆𝑇 (−1)|𝑇|−|𝑆|𝑣(𝑆)are the Harsanyi dividends,Harsanyi (1959). A payoff vector 𝑧= (𝑧𝑖)𝑖∈𝑁∈R𝑛is a vector where 𝑧𝑖represents the payoff associated to player 𝑖by its collaboration in a given TU game (𝑁, 𝑣). In general, a solution concept (in short a solution) is a map 𝜙∶𝑁→R𝑛that assigns to each TU game (𝑁, 𝑣)a payoff vector. One of the most appealing and well-known solution concepts for cooperative games is the Shapley value, introduced by Shapley (Shapley, 1953). Formally, the Shapley value for each (𝑁, 𝑣) ∈ 𝑁assigns to each 𝑖∈𝑁, 𝑆ℎ𝑖(𝑁, 𝑣) = 1 |𝛱(𝑁)|∑ 𝜎∈𝛱(𝑁) 𝑚𝜎 𝑣(𝑖),(1) with 𝛱(𝑁)being the set of all permutations of 𝑁, and 𝑚𝜎 𝑣(𝑖)the marginal contribution of player 𝑖in a given 𝜎∈𝛱(𝑁). Formally, it is defined as 𝑚𝜎 𝑣(𝑖) = 𝑣(𝑃𝜎 𝑖∪{𝑖})−𝑣(𝑃𝜎 𝑖), being 𝑃𝜎 𝑖the set of predecessors of 𝑖in 𝜎, i.e., 𝑃𝜎 𝑖= {𝑘∈𝑁∶𝜎(𝑘)< 𝜎(𝑖)}. Then, the Shapley value for (𝑁, 𝑣)is interpreted, for each player 𝑖of 𝑁, as the expected value of 𝑖’s marginal contributions over the set of all possible orders of 𝑁. The popularity, attractiveness and versatility of this value is highlighted, in a wide collection of theoretical and applied results on it, in Algaba et al. (2019a). In fact, the Shapley value not only continue being so appealing as when it was first introduced in 1953 but its interest has even increased enormously in the last years, due not only to the fairness properties that this value satisfy, see Algaba et al. (2019b), but also to the numerous solution concepts derived from it. In our opinion the magic and strength of the Shapley value is its endurance and at the same time its flexibility over time. It has been and keeps being analyzed from many different perspectives. For instance, for networked coalition structures when the TU game is focused on the edges of the graph, see Meesen (1988), the original idea behind the Shapley value, planed in 1953, on how assess the venture of playing a game remains as important as ever and the solution provided by Shapley solves the problem in a successful and desirable way, giving way to the position value (cf. Meesen,1988 and Borm et al.,1992). 2.2. On communication situations and the position value Acommunication situation is denoted by (𝑁, 𝑣, 𝐿), being (𝑁, 𝑣)a TU game and (𝑁, 𝐿)an undirected graph without parallel edges nor loops connecting the members of 𝑁. Notice that the set of nodes 𝑁in the graph (𝑁, 𝐿)coincide with the set of players in the TU game (𝑁, 𝑣). Therefore, the set of edges 𝐿describes all relationships between pairs of players. A relationship between players 𝑖and 𝑗is denoted by 𝑖𝑗, with 𝑖𝑗 ∈𝐿. For a coalition 𝑆 ⊆ 𝑁, the subgraph (𝑆, 𝐿𝑆), where 𝐿𝑆= {𝑖𝑗 ∈ 𝐿∶𝑖, 𝑗 ∈𝑆}, consists of the players in 𝑆and their edges in 𝐿𝑆. A coalition 𝑆 ⊆ 𝑁 is a connected coalition, if the subgraph (𝑆, 𝐿𝑆) is connected, otherwise, 𝑆is called disconnected. Clearly, the set of maximal connected coalitions of 𝑁determines a partition on 𝑁, called the components of 𝑁, this set will be denoted as 𝐶𝐿(𝑁). Thus, the resulting partition for coalition 𝑆induced by the subgraph (𝑆, 𝐿𝑆)is denoted by 𝐶𝐿(𝑆). Given (𝑁, 𝑣, 𝐿)a communication situation, Myerson (1977) defined a new game1as 𝑣𝐿(𝑆) = ∑ 𝑇∈𝐶𝐿(𝑆) 𝑣(𝑇),(2) with 𝑣𝐿(∅) = 0. In fact, the value 𝑣𝐿(𝑆)can be interpreted as the worth of the cooperation on the components of 𝑆under the communication edges in 𝐿𝑆. Notice that (𝑁, 𝑣𝐿)focuses on the economic possibilities of the players in the game. By contrast, an alternative type of TU game can be introduced centering in the economic possibilities of the edges, and taking the edges as players. Formally, the link game,(𝐿, 𝑟𝐿)2associated with a communication situation (𝑁, 𝑣, 𝐿)is given, for every non-empty coalition of links 𝐴⊆𝐿by 𝑟𝐿(𝐴) = 𝑣𝐴(𝑁),(3) and such that 𝑟𝐿(∅) = 0. The link game (𝐿, 𝑟𝐿)assigns to each possible coalition of links 𝐴⊆𝐿the worth of the cooperation of 𝑁specified by (𝑁, 𝑣𝐴), by considering only those links in 𝐴on the network.3 A solution concept on the class of communication situations is given by a function 𝛾that assigns a payoff vector 𝛾(𝑁, 𝑣, 𝐿) ∈ R𝑛, to each communication situation (𝑁, 𝑣, 𝐿). The position value 𝜋(𝑁, 𝑣, 𝐿) was introduced in Meesen (1988) and, later, studied in Borm et al. (1992). For every communication situation (𝑁, 𝑣, 𝐿), the position value is defined from the Shapley value of the link game by 𝜋𝑖(𝑁, 𝑣, 𝐿) = ∑ 𝑖𝑗∈𝐿𝑖 1 2𝑆ℎ𝑖𝑗 (𝐿, 𝑟𝐿),for all 𝑖∈𝑁, (4) where 𝐿𝑖= {𝑖𝑗 ∈𝐿∶𝑗∈𝑁}denotes the set of edges with 𝑖as an endpoint, and 𝑆ℎ𝑖𝑗 (𝐿, 𝑟𝐿)is the allocation provided for edge 𝑖𝑗 by the Shapley value for the link game (𝐿, 𝑟𝐿). Then, the position value assigns to each player 𝑖of 𝑁in the communication situation half as much as the Shapley value of the link game assigns to each of the incident edges in 𝑖. However, given a collection of individual weights {𝑤𝑗}𝑗∈𝑁, for each player 𝑗∈𝑁, with 𝑤𝑗>0, a weighted version of the position value can be naturally established. Thus, the weighted position value 𝜋𝜔(𝑁, 𝑣, 𝐿) is specified, for every communication situation (𝑁, 𝑣, 𝐿)and for every 𝑖∈𝑁, by 𝜋𝜔 𝑖(𝑁, 𝑣, 𝐿) = ∑ 𝑖𝑗∈𝐿𝑖 𝑤𝑖 𝑤𝑖+𝑤𝑗 𝑆ℎ𝑖𝑗 (𝐿, 𝑟𝐿).(5) Notice that if all individual weights 𝑤𝑗, for each player 𝑗, are equal, then the weighted position value is equal to the position value. Example 2.1 illustrates the obtaining of the position value on a small network defined by a graph. Example 2.1. Let (𝑁, 𝐿)be the graph with the topology of nodes and links in Fig. 1. Thus, we have 𝑁= {1,2,3,4} and 𝐿= {𝑎, 𝑏, 𝑐, 𝑑}. The weights associated with each of the players are detailed in Table 1. Fig. 1. Graph of the network (𝑁, 𝐿). Now, let (𝑁, 𝑣, 𝐿)be the communication situation, where the TU game (𝑁, 𝑣)is specified in Table 2 for every connected coalition 𝑆 ⊆ 𝑁. Using (2), we display the associated TU game (𝑁, 𝑣𝐿)in Table 3. 1The Shapley value of this game, i.e. 𝑆ℎ(𝑁, 𝑣𝐿), is called the Myerson value (Myerson,1977). 2If coalition 𝑁and TU game 𝑣are fixed, we will denote the link game as 𝑟𝐿, if only coalition 𝑁is fixed, we will write it as 𝑟𝐿 𝑣𝐿.. 3Both games 𝑣𝐿and 𝑟𝐿have been considered in Algaba, Bilbao, Borm, and López (2001) and Algaba et al. (2000), respectively, for union stable systems, which generalize communication situations. Expert Systems With Applications 251 (2024) 124096 4 E. Algaba and A. Saavedra-Nieves Table 1 List of weights for the nodes in (𝑁, 𝐿). Agent 𝑖 𝑤𝑖 1 2 2 1 3 2 4 3 Table 2 The TU game (𝑁, 𝑣)for connected coalitions. 𝑆{1} {2} {3} {4} {1,2} {1,3} 𝑣(𝑆)2 1 2 3 3 8 𝑆{2,3} {3,4} {1,2,3} {1,3,4} {2,3,4} 𝑁 𝑣(𝑆)3 15 10 21 18 24 Table 3 The TU game (𝑁, 𝑣𝐿). 𝑆∅ {1} {2} {3} {4} {1,2} {1,3} {1,4} 𝑣𝐿(𝑆)0 2 1 2 3 3 8 5 𝑆{2,3} {2,4} {3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} 𝑁 𝑣𝐿(𝑆)3 4 15 10 6 21 18 24 From its characteristic function, we can obtain the link game (𝐿, 𝑟𝐿) defined in (3). For each coalition of edges 𝐴 ⊆ 𝐿, its associated characteristic function can be found in Table 4. Table 4 The TU game (𝐿, 𝑟𝐿). 𝐴∅ {𝑎} {𝑏} {𝑐} {𝑑} {𝑎, 𝑏} {𝑎, 𝑐} {𝑎, 𝑑} 𝑟𝐿(𝐴)0 8 8 12 18 13 13 18 𝐴{𝑏, 𝑐} {𝑏, 𝑑} {𝑐, 𝑑} {𝑎, 𝑏, 𝑐} {𝑎, 𝑏, 𝑑} {𝑎, 𝑐, 𝑑} {𝑏, 𝑐, 𝑑} {𝑎, 𝑏, 𝑐, 𝑑} 𝑟𝐿(𝐴)13 20 22 13 24 24 24 24 Once the link game is determined, the position value can be computed for the communication situation (𝑁, 𝑣, 𝐿). For this purpose, we firstly obtain the Shapley value of the considered link game, which gives us a measure of the relevance of the edges of the graph. That is, 𝑆ℎ(𝐿, 𝑟𝐿) = (2.750,3.083,4.750,12.417). In view of these results, we can conclude that the stronger relation is given between players 3 and 4, as this component of the Shapley value associated with the link is the largest. Next, we illustrate the obtaining of the position value and the weighted position value for Agent 1, i.e., 𝜋1(𝑁, 𝑣, 𝐿)and 𝜋𝜔 1(𝑁, 𝑣, 𝐿). Using the formulas given in (4) and (5), as links 𝑎and 𝑐are adjacent on node 1 in the network considered, we have that •𝜋1(𝑁, 𝑣, 𝐿) = 1 2⋅𝑆ℎ𝑎(𝐿, 𝑟𝐿) + 1 2⋅𝑆ℎ𝑐(𝐿, 𝑟𝐿) = 1 2⋅2.750 + 1 2⋅3.083 = 3.750, and •𝜋𝜔 1(𝑁, 𝑣, 𝐿) = 𝑤1 𝑤1+𝑤2 ⋅𝑆ℎ𝑎(𝐿, 𝑟𝐿) + 𝑤1 𝑤1+𝑤3 ⋅𝑆ℎ𝑐(𝐿, 𝑟𝐿) = 2 2+1 ⋅2.750+ 2 2+2 ⋅4.750 = 4.208. Similarly, the other components of 𝜋(𝑁, 𝑣, 𝐿)and 𝜋𝜔(𝑁, 𝑣, 𝐿)can be easily obtained. Their numerical results are shown in Table 5. The fact that edge 𝑑receives the largest amount of the worth of the cooperation leads to players 3 and 4 receiving the largest allocations through the position value, although player 3 gets much more than others by the allocations received from the other edges adjacent to it in the graph, which underline the influence of the position of a node in a graph in relation with the degree measure of it. 3. A connection-based approach for network analysis As mentioned, in a communication situation, (𝑁, 𝑣, 𝐿), the players in the TU game (𝑁, 𝑣)are represented by the nodes of the graph (𝑁, 𝐿) and the links describe the interactions between each pair of players. Classical network measures, such as degree, betweenness, or closeness Table 5 The position value 𝜋(𝑁, 𝑣, 𝐿)and the weighted position value 𝜋𝜔(𝑁, 𝑣, 𝐿). Player 1 2 3 4 𝜋(𝑁, 𝑣, 𝐿)3.750 2.917 10.125 6.208 𝜋𝜔(𝑁, 𝑣, 𝐿)4.208 1.944 9.397 7.450 centrality (see, for furthers details, Koschade,2006), provide initial methodologies for ranking their members. However, these lines of research only consider the structure of the network under study, without considering the possibilities of cooperation among its members. Lindelauf et al. (2013)orHusslage et al. (2015) solve this drawback by using cooperative game theory to include the heterogeneity of edges and nodes in the graph. In fact, this information is valued through transferable utility games (or TU games). From now on, we will center our study on two well-known TU games considered in the literature as representatives of a network defined by the graph (𝑁, 𝐿). As mentioned in preliminaries, any TU game can be expressed as a linear combination of unanimity games through the coefficients of Harsanyi, see Harsanyi (1959). Specifically, first, we consider the communication situation (𝑁, 𝑢𝑁, 𝐿)derived from considering the unanimity game on the grand coalition. In this case, following Myerson (1977), the TU game (𝑁, 𝑢𝐿 𝑁)is obtained, which will be called grand coalition connectivity game and denoted by (𝑁, 𝑣𝑔𝑐𝑐𝑜𝑛𝑛), from now on. It assigns for each 𝑆 ⊆ 𝑁 the worth of the cooperation according to the following expression: 𝑣𝑔𝑐𝑐𝑜𝑛𝑛(𝑆) = {1,if 𝑆=𝑁and connected, 0,otherwise. (6) In particular, it assigns a worth equal to 1 when the grand coalition 𝑁 is formed, which means that all agents are connected in the graph, or equivalently that the grand coalition is connected. The other coalitions receive a value equal to zero. The grand coalition connectivity game (𝑁, 𝑣𝑔𝑐𝑐𝑜𝑛𝑛)underlines the relevance of the cooperation, agreement or communication of all agents. In other words, the key is the connectivity of the total network under coordination of its members. Moreover, other important aspect about this TU game is that it does not contain any other information about the influence of the nodes or edges in the graph under study. Second, we consider the additive weighted connectivity TU game (awconn) (𝑁, 𝑣𝑎𝑤𝑐𝑜𝑛𝑛), with respect to (𝑁, 𝐿), following Myerson (1977) and Husslage et al. (2015). In order to define this game, a non-negative function 𝑓is defined, depending on coalition 𝑆, to quantify the effectiveness of any coalition in graph (𝑁, 𝐿)according to the influence of the players in it, represented by a set of weights on 𝑁, i.e., ={𝑤𝑗}𝑗∈𝑁 with 𝑤𝑗≥0, and the relational strength between them in the network, given by a set of weights on the edges 𝐿, i.e., = {𝑘𝑙ℎ}𝑙ℎ∈𝐿with 𝑘𝑙ℎ ≥0. An example of effectiveness function 𝑓is the one considered in Husslage et al. (2015), that is defined, for each non-empty connected coalition 𝑆 ⊆ 𝑁 in a given graph (𝑁, 𝐿), as 𝑓(𝑆, ,) = ⎧ ⎪ ⎨ ⎪ ⎩(∑𝑗∈𝑆𝑤𝑗)⋅max𝑙ℎ∈𝐿𝑆𝑘𝑙ℎ,if |𝑆|>1, 𝑤𝑖,if 𝑆= {𝑖},with 𝑖∈𝑁. (7) This framework includes information about relationships between individuals as well as personal information about individuals. More specifically, for each possible connected coalition 𝑆with more than one player, this map specifies the sum of the individual weights of the members of 𝑆multiplied by the maximum weight over the set of edges connecting the subgraph induced by 𝑆. In the case of the unitary coalitions the value is its own worth and for the empty coalition, it will assign the value 0. Expert Systems With Applications 251 (2024) 124096 5 E. Algaba and A. Saavedra-Nieves Fig. 2. Flowchart for the implementation of rankings of nodes and links based on the position value. Given the communication situation (𝑁, 𝑓, 𝐿), following Myerson (1977), the additive weighted connectivity game (𝑁, 𝑣𝑎𝑤𝑐𝑜𝑛𝑛), is given for each 𝑆 ⊆ 𝑁, by the following expression: 𝑣𝑎𝑤𝑐𝑜𝑛𝑛(𝑆) = ∑ 𝑇∈𝐶𝐿(𝑆) 𝑓(𝑇 , ,).(8) Notice that the additive weighted connectivity game assigns to any connected coalition 𝑆the worth of its effectiveness prescribed by the function 𝑓considered. In the case of a disconnected coalition 𝑆, it assigns the aggregated effectiveness of all its maximal connected subsets (or components) in the subgraph induced by 𝑆. By contrast, with the approach provided by the TU game (𝑁, 𝑣𝑎𝑤𝑐𝑜𝑛𝑛), we want to emphasize the worth of the cooperation of each coalition of players, that itself depends on the connectivity of the coalition and, therefore, on the strength of the relations given between players. The definition of this TU game is consistent and has been extensively utilized for analyzing networks derived from graphs (Myerson,1977), as well as in more general networks with communication properties (Algaba, Bilbao, & López,2001). Furthermore, it has also been applied to networks with both communication and hierarchical features, as discussed in Algaba et al. (2018). Note that unlike of the grand coalition connectivity game, the additive weighted connectivity game is considering implicitly the features of the network in it, which will have implications when applying the Shapley or the position values on them. It is important to stress that unlike the classical game theory solutions, our proposal additionally integrates the degree measure and, moreover, it allows for obtaining rankings not only of the nodes of a graph but also of the edges or relations between individuals in a graph. In what follows, we focus on establishing a centrality node measure based on the capabilities of influence of links of the any network defined by the graph (𝑁, 𝐿). Clearly, the number of links incident on each node (the degree) and the strength of these connections will mark the real influence of each node on the graph as a whole through the link game (𝐿, 𝑟𝐿)associated. The flowchart of the steps of the position value-based procedure to rank the nodes and the links of a graph are summarized in Fig. 2. For this purpose, the consideration of the additive weighted connectivity link game (𝐿, 𝑟𝐿 𝑣𝑎𝑤𝑐𝑜𝑛𝑛 )obtained from the expression in (3) by using (𝑁, 𝑣𝑎𝑤𝑐𝑜𝑛𝑛), and the grand coalition connectivity link game (𝐿, 𝑟𝐿 𝑣𝑔𝑐𝑐𝑜𝑛𝑛 ), associated to the TU game (𝑁, 𝑣𝑔𝑐𝑐𝑜𝑛𝑛)when applying the expression in (3), as well as the computation of the position value, are required. Now, Example 3.1 illustrates the usage of the position value as a mechanism of ranking the nodes and links of a real transportation network. Example 3.1. Let (𝑁, 𝐿)be the graph specified in Fig. 3. It specifies the topology of the nodes, representing the main stations of the suburban trains in Madrid in the year 2000, and of the links, detailing the lines that connect them. Thus, we have that |𝑁|= 18 and |𝐿|= 19. Each station is weighted 1, except for the intermodal train stations of Atocha Fig. 3. Graph of the suburban train network (𝑁, 𝐿)of Madrid in the year 2000. and Chamartín, which are weighted 2, according to the volume of their passengers. Each link has a weight equal to the number of train lines passing through it and that are shown in different colors in the figure. Now, let (𝑁, 𝑢𝑁, 𝐿)and (𝑁, 𝑓, 𝐿)4be the communication situations above-defined, which induce the TU games (𝑁, 𝑣𝑔𝑐𝑐𝑜𝑛𝑛)and (𝑁, 𝑣𝑎𝑤𝑐𝑜𝑛𝑛), respectively. The last one is obtained by using the effectiveness function in (7). From their characteristic functions, we can obtain the grand coalition connectivity link game (𝐿, 𝑟𝐿 𝑣𝑔𝑐𝑐𝑜𝑛𝑛 )and the additive weighted connectivity link game (𝐿, 𝑟𝐿 𝑣𝑎𝑤𝑐𝑜𝑛𝑛 ), for each coalition of edges 𝐴⊆𝐿. Using the TU games (𝐿, 𝑟𝐿 𝑣𝑔𝑐𝑐𝑜𝑛𝑛 )and (𝐿, 𝑟𝐿 𝑣𝑎𝑤𝑐𝑜𝑛𝑛 ), several rankings can be obtained derived from the computation of the position value. For 4From now on, when dealing with the communication situations (𝑁, 𝑢𝑁, 𝐿) and (𝑁, 𝑓, 𝐿), we will denote 𝜋(𝑁, 𝑣𝑔𝑐𝑐𝑜𝑛𝑛, 𝐿)and 𝜋(𝑁, 𝑣𝑎𝑤𝑐𝑜𝑛𝑛, 𝐿)instead of 𝜋(𝑁, 𝑢𝑁, 𝐿)and 𝜋(𝑁, 𝑓, 𝐿), to make clear the games used in the link game. Expert Systems With Applications 251 (2024) 124096 6 E. Algaba and A. Saavedra-Nieves Table 6 Shapley value for the link games (𝐿, 𝑟𝐿 𝑣𝑔𝑐𝑐𝑜𝑛𝑛 )and (𝐿, 𝑟𝐿 𝑣𝑎𝑤𝑐𝑜𝑛𝑛 ). Pair of stations 𝑆ℎ(𝐿, 𝑟𝐿 𝑣𝑔𝑐𝑐𝑜𝑛𝑛 )𝑆ℎ(𝐿, 𝑟𝐿 𝑣𝑎𝑤𝑐𝑜𝑛𝑛 )Pair of stations 𝑆ℎ(𝐿, 𝑟𝐿 𝑣𝑔𝑐𝑐𝑜𝑛𝑛 )𝑆ℎ(𝐿, 𝑟𝐿 𝑣𝑎𝑤𝑐𝑜𝑛𝑛 ) El Escorial-Villalba 0.08256 (1–11) 2.41850 (18) Atocha-Alcalá de Hen. 0.08256 (1–11) 6.76259 (4) Villalba-Cercedilla 0.08256 (1–11) 3.43730 (13) Atocha-Vill. Bajo 0.01066 (16) 7.28532 (3) Cercedilla-Cotos 0.08256 (1–11) 2.07143 (19) Atocha-Móstoles 0.08256 (1–11) 3.60263 (11) Villalba-El Tejar 0.08256 (1–11) 7.30238 (2) Méndez Álvaro-Vill. Alto 0.01066 (17) 4.17460 (8) El Tejar-Príncipe Pío 0.01393 (12) 4.15913 (9) Vill. Bajo-Vill. Alto 0.01066 (18) 3.51508 (12) El Tejar-Chamartín 0.01393 (13) 4.83091 (7) Vill. Alto-Fuenlabrada 0.08256 (1–11) 2.71573 (16) Chamartín-Tres Cantos 0.08256 (1–11) 3.92208 (10) Vill. Alto-Parla 0.08256 (1–11) 2.71573 (17) Príncipe Pío-Méndez Álvaro 0.01393 (14) 5.12817 (6) Vill. Bajo-Aranjuez 0.08256 (1–11) 2.86454 (14) Méndez Álvaro-Atocha 0.00413 (19) 6.37539 (5) Alcalá de Hen.-Guadalajara 0.08256 (1–11) 2.71930 (15) Chamartín-Atocha 0.01393 (15) 23.9992 (1) Table 7 Position value for the nodes of the graph (𝑁, 𝐿). Station 𝜋(𝑁, 𝑣𝑔𝑐𝑐𝑜𝑛𝑛, 𝐿)𝜋𝜔(𝑁, 𝑣𝑔𝑐𝑐𝑜𝑛𝑛 , 𝐿)𝜋(𝑁, 𝑣𝑎𝑤𝑐𝑜𝑛𝑛 , 𝐿)𝜋𝜔(𝑁, 𝑣𝑎𝑤𝑐𝑜𝑛𝑛, 𝐿) El Escorial 0.04128 (9) 0.04128 (9) 1.20925 (17) 1.20925 (15) Villalba 0.12384 (1) 0.12384 (2) 6.57909 (6) 6.57909 (5) Cercedilla 0.08256 (4) 0.08256 (4) 2.75436 (10) 2.75436 (10) Cotos 0.04128 (10) 0.04128 (10) 1.03571 (18) 1.03571 (17) El Tejar 0.05521 (6) 0.05289 (7) 8.14621 (3) 7.34106 (3) Chamartín 0.05521 (7) 0.07129 (5) 16.3761 (2) 17.8349 (2) Tres Cantos 0.04128 (11) 0.02752 (15) 1.96104 (11) 1.30736 (14) Príncipe Pío 0.01393 (18) 0.01393 (17) 4.64365 (9) 4.64365 (8) Atocha 0.09692 (2) 0.12691 (1) 24.0126 (1) 28.0169 (1) Méndez Álvaro 0.01436 (17) 0.01367 (18) 7.83908 (4) 6.77652 (4) Villaverde Bajo 0.05194 (8) 0.05017 (8) 6.83246 (5) 5.61825 (7) Villaverde Alto 0.09322 (3) 0.09322 (3) 6.56057 (7) 6.56057 (6) Móstoles 0.04128 (12) 0.02752 (16) 1.80132 (12) 1.20088 (16) Fuenlabrada 0.04128 (13) 0.04128 (11) 1.35786 (15) 1.35786 (12) Parla 0.04128 (14) 0.04128 (12) 1.35786 (16) 1.35786 (13) Aranjuez 0.04128 (15) 0.04128 (13) 1.43227 (13) 1.43227 (11) Alcalá de Henares 0.08256 (5) 0.06880 (6) 4.74094 (8) 3.61385 (9) Guadalajara 0.04128 (16) 0.04128 (14) 1.35965 (14) 1.35965 (12) this purpose, we firstly obtain the Shapley value of the two considered link games, which gives us a ranking of the edges of the graph according to their relevance (see Table 6). When considering (𝐿, 𝑟𝐿 𝑣𝑔𝑐𝑐𝑜𝑛𝑛 ), there are several edges that can be qualified as key to the connectivity of the network, as there are ties in the maximum allocations that the Shapley value specifies. However, the edge that contributes the least to the connectivity of the entire network is Méndez Álvaro-Atocha. On the other hand, under the consideration of (𝐿, 𝑟𝐿 𝑣𝑎𝑤𝑐𝑜𝑛𝑛 ), the link that contributes most to the network is the one that connects the two most important stations in the city, Atocha and Chamartín. The link that has the least contribution to the network under this approach is the one between Cotos and Cercedilla stations. Table A.1 in Appendix A of the Online resource section (ORS) gives the overall rankings. The position value and the weighted position value are obtained for the main stations of the suburban train network under the TU games considered. These results are shown in Table 7. Thus, such allocations prescribe different rankings for the nodes of the graph. For each station, we indicate in brackets its position in the associated ranking. Atocha occupies the first position in the rankings, except for the case of 𝜋(𝑁, 𝑣𝑔𝑐𝑐𝑜𝑛𝑛, 𝐿)that assigns it position 2 of the ranking. Although Chamartín station is ranked second when using 𝑣𝑎𝑤𝑐𝑜𝑛𝑛, it drops several positions in the rankings based on 𝑣𝑔𝑐𝑐𝑜𝑛𝑛. As for the least influential stations, 𝑣𝑔𝑐𝑐𝑜𝑛𝑛 assigns to the centrally located stations of Mendez Álvaro and Príncipe Pío the last two positions. Conversely, the two least relevant stations according to 𝑣𝑎𝑤𝑐𝑜𝑛𝑛 are stations on the outskirts of the central area of the city. The overall rankings are detailed in Table A.2 of Appendix A in the ORS. The previous example illustrates the computation of rankings based on the position value in a ‘‘small’’ scheme. However, the exact computation of the position value becomes a challenging task when the number of links in the graph significantly increases. Notice that similar problems arise for the exact computation of the Shapley value in those contexts with a large number of players (see, for example, Fernández-García & Puerto-Albandoz,2006 or Castro et al.,2009), for which sampling techniques provide an approximated solution as an alternative. 4. Estimating the position value As mentioned, the main drawback concerning the (weighted) position value is computational, since its complexity exponentially increases with the number of players and the number of links connecting them. However, up to the authors’ knowledge, the task of obtaining a procedure for the approximation of the position value has not been explored yet, in spite of the importance of taking into account the connections in real networks. Let (𝑁, 𝑟𝐿)be the link game associated with a given communication situation (𝑁, 𝑣, 𝐿). Notice that the (weighted) position value can be obtained in terms of the Shapley value for the associated link game. Hence, its own definition justifies a proposal for its estimation, based on the ideas used by Fernández-García and Puerto-Albandoz (2006) and Castro et al. (2009) for the Shapley value approximation by using sampling techniques. The steps of that sampling procedure for the estimation of the weighted position value are illustrated below: 1. The sampling population corresponds to all orders of the set of links 𝐿, i.e., 𝛱(𝐿). 2. The vector of unknown parameters to be estimated is 𝜋𝜔= (𝜋𝜔 𝑖)𝑖∈𝑁, with 𝜋𝜔 𝑖being 𝜋𝜔 𝑖(𝑁, 𝑣, 𝐿), for all 𝑖∈𝑁. 3. The feature to analyze is the vector (𝑚𝜎 𝑟𝐿(𝑎))𝑎∈𝐿= (𝑟𝐿(𝑃𝜎 𝑎∪{𝑎})−𝑟𝐿(𝑃𝜎 𝑎))𝑎∈𝐿, for each sampling unit 𝜎∈𝛱(𝐿). 4. Each permutation 𝜎∈𝛱(𝐿)is equally likely. 5. The average of the marginal contribution vectors over a sample of permutations of 𝐿is the estimation of the Shapley value for Expert Systems With Applications 251 (2024) 124096 7 E. Algaba and A. Saavedra-Nieves the link game (𝐿, 𝑟𝐿), i.e.,  𝑆ℎ = (  𝑆ℎ𝑎)𝑎∈𝐿, such that  𝑆ℎ𝑎(𝐿, 𝑟𝐿) = 1 𝓁∑ 𝜎∈ 𝑚𝜎 𝑟𝐿(𝑎), for all 𝑎∈𝐿, where 𝓁is the sample size. 6. The estimator for the weighted position value 𝜋𝜔(𝑁, 𝑣, 𝐿)is 𝜋𝜔= (𝜋𝜔 𝑖)𝑖∈𝑁, where 𝜋𝜔 𝑖(𝑁, 𝑣, 𝐿) = ∑ 𝑖𝑗∈𝐿𝑖 𝑤𝑖 𝑤𝑖+𝑤𝑗  𝑆ℎ𝑖𝑗 (𝐿, 𝑟𝐿),for all 𝑖∈𝑁. (9) Upon applying this procedure, the resulting vector 𝜋𝜔= ( 𝜋𝜔 1,…, 𝜋𝜔 𝑛) corresponds to the estimation of the weighted position value for all players involved in the communication situation (𝑁, 𝑣, 𝐿). First, we examine the statistical properties of the estimator given in Eq. (9). Consider a fixed player 𝑖∈𝑁. Thus, 𝜋𝜔 𝑖is an unbiased estimator since it holds that E(𝜋𝜔 𝑖) = E(∑ 𝑖𝑗∈𝐿𝑖 𝑤𝑖 𝑤𝑖+𝑤𝑗  𝑆ℎ𝑖𝑗 (𝐿, 𝑟𝐿)) =∑ 𝑖𝑗∈𝐿𝑖 𝑤𝑖 𝑤𝑖+𝑤𝑗 E( 𝑆ℎ𝑖𝑗 (𝐿, 𝑟𝐿)) =∑ 𝑖𝑗∈𝐿𝑖 𝑤𝑖 𝑤𝑖+𝑤𝑗 𝑆ℎ𝑖𝑗 (𝐿, 𝑟𝐿) =𝜋𝜔 𝑖. (10) These equalities are satisfied due to the unbiased nature of the Shapley value estimator for a TU game, obtained when using simple random sampling with replacement (cf. Castro et al.,2009). Similarly, the consistency of the estimator 𝜋𝜔is also ensured. Over a sample of permutations in 𝐿, given by , the estimator 𝜋𝜔 𝑖 for the weighted position value of player 𝑖in (9) admits an alternative formulation, for every 𝑖∈𝑁, that we detail below. Thus, we have that 𝜋𝜔 𝑖(𝑁, 𝑣, 𝐿) = ∑ 𝑖𝑗∈𝐿𝑖 𝑤𝑖 𝑤𝑖+𝑤𝑗  𝑆ℎ𝑖𝑗 (𝐿, 𝑟𝐿) = ∑ 𝑖𝑗∈𝐿𝑖 𝑤𝑖 𝑤𝑖+𝑤𝑗(1 𝓁∑ 𝜎∈ 𝑚𝜎 𝑟𝐿(𝑖𝑗)) =1 𝓁(∑ 𝑖𝑗∈𝐿𝑖∑ 𝜎∈ 𝑤𝑖 𝑤𝑖+𝑤𝑗 𝑚𝜎 𝑟𝐿(𝑖𝑗)) =1 𝓁∑ 𝜎∈(∑ 𝑖𝑗∈𝐿𝑖 𝑤𝑖 𝑤𝑖+𝑤𝑗 𝑚𝜎 𝑟𝐿(𝑖𝑗)) =1 𝓁∑ 𝜎∈ 𝑥(𝜎)𝑖, (11) being 𝑥(𝜎)𝑖=∑ 𝑖𝑗∈𝐿𝑖 𝑤𝑖 𝑤𝑖+𝑤𝑗 𝑚𝜎 𝑟𝐿(𝑖𝑗), for all 𝑖∈𝑁. A fundamental issue in problems of solution approximating for TU games lies in bounding the estimation error, which refers to the difference between the approximated value and the exact value. Since it is often impractical to measure this error directly, a probabilistic bound is typically provided instead. Roughly speaking, the approximation of the weighted position value for player 𝑖is at a distance greater than 𝜀 of the real value with a probability 𝛼as maximum. Formally, it means P(|𝜋𝜔 𝑖−𝜋𝜔 𝑖|≥𝜀)≤𝛼, with 𝜀 > 0and 𝛼∈ (0,1]. Therefore, as the sampling size enlarges, the estimated weighted position value tends to be a more accurate approximation of the real one. Given the relevance of selecting an appropriate sampling size, we provide valuable results for effectively bounding such error. In order to accomplish this, we have thoroughly examined relevant literature concerning the approximation of coalitional values in cooperative games, as Fernández-García and Puerto-Albandoz (2006), Castro et al. (2009) and Maleki (2015) for the Shapley value estimation, and Bachrach et al. (2010) for the estimation of power indices for simple games. It is noteworthy that when estimating coalitional values, the population sizes considered in sampling procedures are typically large but always finite. Thus, the conservative bound provided by Castro et al. (2009) cannot be considered. The findings presented below enable the determination of the minimum sample size necessary to approximate the weighted position value with a desired maximum error of 𝜀and a confidence level of 1−𝛼. They follow the lines of research of Maleki (2015) and Bachrach et al. (2010), that make use of concentration bounds for the analysis of the error in estimating unknown parameters on finite populations. To establish a bound on the absolute error in estimating the weighted position value, a statement relying on Hoeffding’s concentration inequality is introduced. Hoeffding’s inequality (Hoeffding,1963) states that if ∑𝑘 𝑗=1 𝑋𝑗represents the sum of 𝑘observations 𝑋1,…, 𝑋𝑘extracted with replacement, such that 𝑎𝑗≤𝑋𝑗≤𝑏𝑗for all 𝑗∈ {1,…, 𝑘}, then P(| 𝑘 ∑ 𝑗=1 𝑋𝑗−E( 𝑘 ∑ 𝑗=1 𝑋𝑗)|≥𝑡)≤2 exp(−2𝑡2 ∑𝑘 𝑗=1(𝑏𝑗−𝑎𝑗)2),for all 𝑡≥0.(12) Proposition 4.1 specifically formalizes this result for the case of estimating the weighted position value. Proposition 4.1. Let (𝑁, 𝑣, 𝐿)be a communication situation. Take 𝜀 > 0, 𝛼∈ (0,1) and denote the range of 𝑥(𝜎)𝑖by 𝑟𝑖= max 𝜎,𝜎′∈𝛱(𝐿)(𝑥(𝜎)𝑖−𝑥(𝜎′)𝑖). Then, 𝓁≥ln(2∕𝛼)𝑟2 𝑖 2𝜀2implies that P(|𝜋𝜔 𝑖−𝜋𝜔 𝑖|≥𝜀)≤𝛼. Proof. Indeed, we have that 𝜋𝜔 𝑖=1 𝓁∑ 𝜎∈ 𝑥(𝜎)𝑖for a sample of 𝓁elements. Thus, P(|𝜋𝜔 𝑖−𝜋𝜔 𝑖|≥𝜀) = P(|𝜋𝜔 𝑖−E(𝜋𝜔 𝑖)|≥𝜀) = P(|∑ 𝜎∈ 𝑥(𝜎)𝑖−E(∑ 𝜎∈ 𝑥(𝜎)𝑖)|≥𝜀𝓁). Using Hoeffding’s inequality (12), it satisfies that P(|||∑ 𝜎∈ 𝑥(𝜎)𝑖−E(∑ 𝜎∈ 𝑥(𝜎)𝑖)|||≥𝜀𝓁)≤2 exp(−2𝜀2𝓁 𝑟2 𝑖)≤𝛼, and we conclude the proof. □ Below, we establish a general bound on the range of 𝑥(𝜎)𝑖that may be useful in determining the sample sizes in the estimation of the weighted position value for the additive weighted connectivity TU game. For this purpose, the nature of the effectiveness function 𝑓 considered is essential. Specifically, we consider the case in which the effectiveness function 𝑓∶ 2𝑁⟶Ris superadditive, that is, if it holds that 𝑓(𝑆, ,) + 𝑓(𝑇 , ,)≤𝑓(𝑆∪𝑇 , ,)(13) for all pair of disjoint coalitions 𝑆, 𝑇 ⊆ 𝑁. Proposition 4.2. Let (𝑁, 𝑣gcconn)and (𝑁, 𝑣awconn)be the grand coalition connectivity TU game and the additive weighted connectivity TU game associated with the communication situations (𝑁, 𝑢𝑁, 𝐿)and (𝑁, 𝑓, 𝐿), with 𝑓a superadditive effectiveness function. For every 𝑖∈𝑁, it is satisfied that, •for the case of estimating 𝜋𝜔(𝑁, 𝑣gcconn, 𝐿), 𝑟𝑖≤|𝐿𝑖|𝑤𝑖 𝑤𝑖+ min𝑗∈𝑁∶𝑖𝑗∈𝐿𝑖𝑤𝑗 ;(14) •for the case of estimating 𝜋𝜔(𝑁, 𝑣awconn, 𝐿), 𝑟𝑖≤|𝐿𝑖|𝑤𝑖 𝑤𝑖+ min𝑗∈𝑁∶𝑖𝑗∈𝐿𝑖𝑤𝑗 𝑓(𝑁, ,),(15) being |𝐿𝑖|the number of edges with player 𝑖as endpoint. Expert Systems With Applications 251 (2024) 124096 8 E. Algaba and A. Saavedra-Nieves Proof. Take 𝑖∈𝑁and let 𝜎and 𝜎′be two different permutations of edges in 𝛱(𝐿). Taking into account that 𝑥(𝜎)𝑖=∑ 𝑖𝑗∈𝐿𝑖 𝑤𝑖 𝑤𝑖+𝑤𝑗 𝑚𝜎 𝑟𝐿(𝑖𝑗), for all 𝑖∈𝑁and for every 𝜎, 𝑥(𝜎)𝑖−𝑥(𝜎′)𝑖=∑ 𝑖𝑗∈𝐿𝑖 𝑤𝑖 𝑤𝑖+𝑤𝑗(𝑚𝜎 𝑟𝐿(𝑖𝑗) − 𝑚𝜎′ 𝑟𝐿(𝑖𝑗)) ≤∑ 𝑖𝑗∈𝐿𝑖 𝑤𝑖 𝑤𝑖+𝑤𝑗 𝑚𝜎 𝑟𝐿(𝑖𝑗) ≤|𝐿𝑖|max 𝑗∈𝑁∶𝑖𝑗∈𝐿𝑖{𝑤𝑖 𝑤𝑖+𝑤𝑗}𝑚𝜎 𝑟𝐿(𝑖𝑗) ≤|𝐿𝑖|(𝑤𝑖 𝑤𝑖+ min𝑗∈𝑁∶𝑖𝑗∈𝐿𝑖𝑤𝑗)𝑚𝜎 𝑟𝐿(𝑖𝑗), (16) being |⋅|the cardinal operator of a set. The fourth inequality is satisfied due to the decreasing character of the function 𝑓(𝑥) = 𝐶 𝑥+𝐶for all 𝑥≥0 and being 𝐶 > 0. From the last inequality in (16), for the case of estimating 𝜋𝜔(𝑁, 𝑣gcconn, 𝐿), we can state, for all 𝑖∈𝑁, that 𝑟𝑖= max 𝜎,𝜎′∈𝛱(𝐿)(𝑥(𝜎)𝑖−𝑥(𝜎′)𝑖)≤|𝐿𝑖|𝑤𝑖 𝑤𝑖+ min𝑗∈𝑁∶𝑖𝑗∈𝐿𝑖𝑤𝑗 ,(17) since, under the consideration of the grand coalition connectivity TU game (𝑁, 𝑣gcconn),𝑚𝜎 𝑟𝐿(𝑖𝑗)≤1. For the case of estimating 𝜋𝜔(𝑁, 𝑣awconn, 𝐿), let 𝑖𝑗 ∈𝐿, and 𝐴 ⊆ 𝐿, it holds that 𝑚𝜎 𝑟𝐿(𝑖𝑗) = 𝑟𝐿(𝐴∪ {𝑖𝑗}) − 𝑟𝐿(𝐴)≤𝑟𝐿(𝐴∪ {𝑖𝑗}) =𝑣𝐴∪{𝑖𝑗}(𝑁) =∑ 𝑇∈𝐶𝐴∪{𝑖𝑗}(𝑁) 𝑣awconn(𝑇) =∑ 𝑊∈𝐶𝐴∪{𝑖𝑗}(𝑁) 𝑓(𝑊 , ,) ≤𝑓(𝑁, ,), where the last inequality is satisfied by the superadditive character of the effectiveness function 𝑓. Then, we immediately have that, for all 𝑖∈𝑁, 𝑟𝑖≤|𝐿𝑖|(𝑤𝑖 𝑤𝑖+ min𝑗∈𝑁∶𝑖𝑗∈𝐿𝑖𝑤𝑗)𝑓(𝑁, ,), concluding the proof. □ The following two corollaries can be immediately obtained. First, we state a general bound for the case of the grand coalition connectivity TU game. Corollary 4.3. Consider 𝜀 > 0,𝛼∈ (0,1) and (𝑁, 𝑣gcconn)the grand coalition connectivity TU game associated with the communication situation (𝑁, 𝑢𝑁, 𝐿). If 𝓁satisfies that 𝓁≥ln(2∕𝛼) 2𝜀2|𝐿𝑖|2(𝑤𝑖 𝑤𝑖+ min𝑗∈𝑁∶𝑖𝑗∈𝐿𝑖 𝑤𝑗)2 ,(18) then, P(|𝜋𝜔 𝑖−𝜋𝜔 𝑖|≥𝜀)≤𝛼, for each 𝑖∈𝑁. Proof. The proof is straightforward from Proposition 4.2 and the inequality in (14).□ Second, we establish a general bound for the additive weighted connectivity TU games, when considering a superadditive effectiveness function 𝑓. Corollary 4.4. Consider 𝜀 > 0,𝛼∈ (0,1) and (𝑁, 𝑣awconn)the additive weighted connectivity TU game associated with the communication situation (𝑁, 𝑓, 𝐿), by using a superadditive effectiveness function 𝑓. If 𝓁satisfies that 𝓁≥ln(2∕𝛼) 2𝜀2|𝐿𝑖|2(𝑤𝑖 𝑤𝑖+ min𝑗∈𝑁∶𝑖𝑗∈𝐿𝑖𝑤𝑗)2 (𝑓(𝑁, ,))2,(19) then, P(|𝜋𝜔 𝑖−𝜋𝜔 𝑖|≥𝜀)≤𝛼, for each 𝑖∈𝑁. Proof. The proof directly follows Proposition 4.2 and the inequality in (15).□ The previous result can be directly formalized for the case of the additive weighted connectivity TU game associated with the communication situation (𝑁, 𝑓, 𝐿)when using the effectiveness function in (7) of Husslage et al. (2015). Given 𝜀 > 0and 𝛼∈ (0,1), if 𝓁≥ln(2∕𝛼) 2𝜀2|𝐿𝑖|2(𝑤𝑖 𝑤𝑖+ min𝑗∈𝑁∶𝑖𝑗∈𝐿𝑖𝑤𝑗)2((∑ 𝑗∈𝑁 𝑤𝑗)⋅max 𝑙ℎ∈𝐿𝑘𝑙ℎ)2 , (20) then, P(|𝜋𝜔 𝑖−𝜋𝜔 𝑖|≥𝜀)≤𝛼, for each 𝑖∈𝑁. In the particular case of the position value, obtained from the weighted position value when all edge weights are equal, we want to mention explicitly the bounds of the error that can be specifically established from the above results. In this case, the estimator for the position value 𝜋(𝑁, 𝑣, 𝐿)is directly given by 𝜋 = ( 𝜋𝑖)𝑖∈𝑁, where 𝜋𝑖(𝑁, 𝑣, 𝐿) = 1 2∑ 𝑖𝑗∈𝐿𝑖  𝑆ℎ𝑖𝑗 (𝐿, 𝑟𝐿),(21) for all 𝑖∈𝑁. Immediately, the bounds of the error for the position value, derived from Corollaries 4.3 and 4.4, respectively, are stated below. •First, we formalize a specific bound for 𝑟𝑖, with 𝑖∈𝑁, for the case of estimating the position value. As in Proposition 4.2, it is easy to check that, –for the case of estimating 𝜋(𝑁, 𝑣𝑔𝑐𝑐𝑜𝑛𝑛, 𝐿), we have that 𝑟𝑖≤ |𝐿𝑖| 2for every 𝑖∈𝑁; –for the case of estimating 𝜋(𝑁, 𝑣awconn, 𝐿)with a superadditive effectiveness function 𝑓, it holds that 𝑟𝑖≤|𝐿𝑖| 2𝑓(𝑁, ,), for every 𝑖∈𝑁, being |𝐿𝑖|the number of edges with player 𝑖as endpoint. •Using these last two inequalities, we can formalize the following two statements on sampling sizes. Take 𝜀 > 0and 𝛼∈ (0,1). Let (𝑁, 𝑣gcconn)be the grand coalition connectivity TU game associated with (𝑁, 𝑢𝑁, 𝐿). If 𝓁satisfies that 𝓁≥ln(2∕𝛼) 2𝜀2(|𝐿𝑖| 2)2 ,(22) it holds P(|𝜋𝑖−𝜋𝑖|≥𝜀)≤𝛼, for each 𝑖∈𝑁. Similarly, let (𝑁, 𝑣awconn)be the additive weighted connectivity TU game associated with (𝑁, 𝑓, 𝐿), by using a superadditive effectiveness function 𝑓. If 𝓁satisfies that 𝓁≥ln(2∕𝛼) 2𝜀2(|𝐿𝑖| 2)2 (𝑓(𝑁, ,))2,(23) it holds P(|𝜋𝑖−𝜋𝑖|≥𝜀)≤𝛼, for each 𝑖∈𝑁. Note that Castro et al. (2009) guaranteed polynomial complexity for the case of the Shapley value estimation as long as the characteristic function of the TU game considered is also obtained in polynomial time. Polynomial algorithms are also available to detect the connected components of any graph and thus to obtain the characteristic function of both TU games under consideration. Thus, when the link game is obtained in polynomial time, by the nature of our procedure, the approximation of the position value using simple random sampling with replacement has polynomial complexity by construction. Expert Systems With Applications 251 (2024) 124096 9 E. Algaba and A. Saavedra-Nieves Fig. 4. Graph of the network (𝑁, 𝐿)associated with the Spanish national team in the Portugal-Spain match at the 2018 World Cup in Russia. 5. Position value-based rankings As mentioned, the importance of the connections between nodes in a graph can influence the results. Hence, the position value is of big interest when working with networks represented by a graph. In the first two subsections, we apply our sampling proposal on two very different scenarios modeled under the scheme of a network defined by a graph (𝑁, 𝐿)and in which connections among agents are relevant enough. In both scenarios, we rank the nodes and edges of the graph according to their influence in the pursuit of the objectives of the network. The first case is devoted to the analysis of the network arisen from the passing structure of a football team. The second one analyzes the case of a well-known terrorist network: The Zerkani network. The last subsection studies the position value versus the most known centrality measures in the literature. 5.1. The Spanish national football team First, we analyze the problem of identifying the leading player of a team by analyzing the network of passes of players in a football match. To this aim, we consider the approach provided by the position value where the connections between players (edges) take relevance. These situations involve a keen interest in determining the relative importance of network members in terms of their contribution to its operations. Consider now the graph (𝑁, 𝐿)arisen from the organization and the performance of football teams. In this sense, a team can be conceptualized as a complex network in which the nodes represent players who interact with the objective of outperforming the opposing network. Additionally, the associated graph is derived from the football passing networks, with the edges representing the interactions between the players. Table 8 Distribution of passes between players of the Spanish national football team in the Portugal-Spain match of the 2018 World Cup. Pair of players Number of Pair of players Number of passes passes Andrés Iniesta-David Silva 5 Diego Costa-Jordi Alba 7 Andrés Iniesta-Diego Costa 7 Diego Costa-Nacho 1 Andrés Iniesta-Gerard Piqué 6 Diego Costa-Sergio Busquets 4 Andrés Iniesta-Isco 28 Diego Costa-Sergio Ramos 2 Andrés Iniesta-Jordi Alba 27 Gerard Piqué-Isco 3 Andrés Iniesta-Koke 7 Gerard Piqué-Jordi Alba 2 Andrés Iniesta-Nacho 1 Gerard Piqué-Koke 21 Andrés Iniesta-Sergio Busquets 9 Gerard Piqué-Nacho 12 Andrés Iniesta-Sergio Ramos 38 Gerard Piqué-Sergio Busquets 14 David Silva-Diego Costa 3 Gerard Piqué-Sergio Ramos 26 David Silva-Gerard Piqué 5 Isco-Jordi Alba 44 David Silva-Isco 9 Isco-Koke 11 David Silva-Jordi Alba 4 Isco-Nacho 13 David Silva-Koke 17 Isco-Sergio Busquets 10 David Silva-Nacho 11 Isco-Sergio Ramos 26 David Silva-Sergio Busquets 6 Jordi Alba-Koke 1 David Silva-Sergio Ramos 7 Jordi Alba-Nacho 1 David de Gea-Gerard Piqué 5 Jordi Alba-Sergio Ramos 44 David de Gea-Isco 1 Koke-Nacho 21 David de Gea-Jordi Alba 4 Koke-Sergio Busquets 20 David de Gea-Nacho 3 Koke-Sergio Ramos 7 David de Gea-Sergio Busquets 1 Nacho-Sergio Busquets 11 David de Gea-Sergio Ramos 5 Nacho-Sergio Ramos 2 Diego Costa-Gerard Piqué 1 Sergio Busquets-Sergio Ramos 23 Diego Costa-Isco 6 Expert Systems With Applications 251 (2024) 124096 16 E. Algaba and A. Saavedra-Nieves two real examples that can be modeled in terms of a communication situation, showing that this measure is specially advantageous when dealing with networks represented by a graph. In fact, the advantage and strength of this approach compared to other measures of centrality is revealed by integrating the particular and specific features of the network nature, independently whether it is taken into account in the original game and by allowing us to obtain, not only a ranking of the nodes but also of the edges of the graph. Therefore, with the position value as a new centrality measure, we can get significant and more realistic information about the most influential nodes and, at the same time, the stronger relations between them. The theoretical analysis of the properties of the position value for communication situations (cf. Borm et al.,1992) has already had sufficient impact on cooperative game literature because of its interesting properties over the last decades. However, the difficulties of its exact calculation in general has not been addressed due to the enormous computational complexity associated. This fact has undoubtedly limited its practical application as a solution for many of the real-life situations that could be modeled in the form of a network structure represented by a graph. The position value is obtained from the Shapley value (Shapley,1953) for the TU game defined over the set of edges communicating the existing nodes. Hence, in addition to the effort required to handle the corresponding link game, the computational problems arisen from the Shapley value computation can now be extended to this context as well. As in the estimation of solution concepts for TU games (Fernández-García & Puerto-Albandoz,2006 and Castro et al.,2009; for the Shapley value approximation), the use of sampling methodologies (Cochran,2007) to approximate the position value in this work solves these drawbacks. Its usage is justified by its formulation in terms of a population mean. From a purely statistical approach, a thorough analysis of the properties of the resulting estimator for the position value was covered. Moreover, the task of bounding the estimation error was also addressed through the establishment of specific results for the position value estimation. From a computational perspective, it is important to emphasize that the proposed procedure can be easily computed in parallel. With this work, the scope of application of the position value estimation procedure is extended to any multi-agent situation that can be modeled as a communication situation, even with a very large number of edges involved. As illustration, we first focus on the analysis of football passing networks to establish rankings of the players of the Spanish national football team based on the estimated position value as well as a ranking of the pairs of players with the best performance during this football match according to the Shapley value of the link game. Second, we address the well-known problem of ranking terrorists in networks, in this case, under the approach given by the position value, obtaining, likewise, valuable information through the ranking of the stronger relations between the terrorists of the Zerkani network, which constitutes a big distinction with all the others existent centrality measures. Moreover, with these applications have been highlighted that independently of the initial TU game considered, the position value always takes into account the topology of the graph. Therefore, when dealing with networks defined by a graph, it is another important aspect to consider with respect to the centrality measures existent in the literature. Note that we have applied it in three very different fields such as transport, sports and security, although, as mentioned, communication situations also arise in other many contexts as far apart as economics, health or logistics, among others. CRediT authorship contribution statement Encarnación Algaba: Conceptualization, Methodology, Software, Validation, Formal analysis, Investigation, Writing – original draft, Writing – review & editing. Alejandro Saavedra-Nieves: Conceptualization, Methodology, Software, Validation, Formal analysis, Investigation, Writing – original draft, Writing – review & editing. Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. Data availability Data will be made available on request. Acknowledgments The authors wish to thank the Associate Editor and the anonymous referees for their useful comments to improve an earlier version of this paper. E. Algaba acknowledges the financial support from R&D&I Project Grant PID2022-137211NB-100, funded by MCIN/AEI/10.13039/ 501100011033/ and by ‘‘ERDF A way of making Europe’’/EU is gratefully acknowledged. A. Saavedra-Nieves acknowledges the financial support of grant PID2021-124030NB-C32, funded by MCIN/AEI/ 10.13039/501100011033/ and by ‘‘ERDF A way of making Europe’’, and under grant Grupos de Referencia Competitiva ED431C 2021/24, funded by Consellería de Cultura, Educación e Universidades, Xunta de Galicia. Authors also thank the computational resources of the Centro de Supercomputación de Galicia (CESGA). Online resource section: supplementary material Supplementary material related to this article can be found online at https://doi.org/10.1016/j.eswa.2024.124096. References Aadithya, K., Ravindran, B., Michalak, T., & Jennings, N. (2010). Efficient computation of the Shapley value for centrality in networks. International Workshop on Internet and Network Economics, 1–13. Algaba, E., Bilbao, J., Borm, P., & López, J. (2000). The position value for union stable systems. Mathematical Methods of Operations Research,52(2), 221–236. Algaba, E., Bilbao, M., Borm, P., & López, J. (2001). The Myerson value for union stable structures. Mathematical Methods of Operations Research,54, 359–371. Algaba, E., Bilbao, M., Fernández, J., Jiménez, N., & López, J. (2007). Algorithms for computing the Myerson value by dividends. In K. Moore (Ed.), Discrete mathematics research progress (pp. 1–13). Algaba, E., Bilbao, J., & López, J. (2001). A unified approach to restricted games. Theory and Decision,50(4), 333–345. Algaba, E., Bilbao, J., & López, J. (2004). The position value in communication structures. Mathematical Methods of Operations Research,59(3), 465–477. Algaba, E., Bilbao, J. M., & van den Brink, R. (2015). Harsanyi power solutions for games on union stable systems. Annals of Operations Research,225(1), 27–44. Algaba, E., Bilbao, J., van den Brink, R., & López, J. (2012). The Myerson value and superfluous supports in union stable systems. Journal of Optimization Theory and Applications,155(2), 650–668. Algaba, E., Fragnelli, V., & Sánchez-Soriano, J. (2019a). Handbook of the Shapley value. Taylor and Francis Group, USA: CRC Press. Algaba, E., Fragnelli, V., & Sánchez-Soriano, J. (2019b). The Shapley value, a paradigm of fairness. In Handbook of the Shapley value (pp. 17–29). Taylor & Francis Group, Boca Raton, USA.: CRC Press. Algaba, E., Prieto, A., & Saavedra-Nieves, A. (2023). Risk analysis sampling methods in terrorist networks based on the Banzhaf value. Risk Analysis,44, 477–492. Algaba, E., Prieto, A., Saavedra-Nieves, A., & Hamers, H. (2023). Analyzing Zerkani network with the Owen value. In S. Kurz, N. Maaser, & A. Mayer (Eds.), Advances in collective decision making - interdisciplinary perspectives for the 21st century, studies in choice and welfare (pp. 221–238). Springer. Algaba, E., van den Brink, R., & Dietz, C. (2018). Network structures with hierarchy and communication. Journal of Optimization Theory and Applications,179(1), 265–282. Bachrach, Y., Markakis, E., Resnick, E., Procaccia, A. D., Rosenschein, J. S., & Saberi, A. (2010). Approximating power indices: theoretical and empirical analysis. Autonomous Agents and Multi-Agent Systems,20(2), 105–122. Banzhaf, J. F. (1964). Weighted voting doesn’t work: A mathematical analysis. Rutgers Law Review,19, 317. Borm, P., Owen, G., & Tijs, S. (1992). On the position value for communication situations. SIAM Journal on Discrete Mathematics,5, 305–320. Expert Systems With Applications 251 (2024) 124096 17 E. Algaba and A. Saavedra-Nieves Buldú, J., Busquets, J., Echegoyen, I., & Seirul.lo, F. (2019). Defining a historic football team: Using network science to analyze Guardiola’s FC Barcelona. Scientific Reports, 9(1), 1–14. Casajus, A. (2007). The position value is the Myerson value, in a sense. International Journal of Game Theory,36(1), 47–55. Castro, J., Gómez, D., & Tejada, J. (2009). Polynomial calculation of the Shapley value based on sampling. Computers & Operations Research,36, 1726–1730. Cochran, W. G. (2007). Sampling techniques. John Wiley & Sons. Farley, J. (2003). Breaking Al Qaeda cells: a mathematical analysis of counterterrorism operations. Studies in Conflict and Terrorism,26, 299–314. Fernández, J., Algaba, E., Bilbao, J., Jiménez, A., Jiménez, N., & López, J. (2002). Generating functions for computing the Myerson value.. Annals of Operations Research,109, 143–158. Fernández-García, F., & Puerto-Albandoz, J. (2006). Teoría de juegos multiobjetivo. Imagraf Impresores SA, Sevilla. Gómez, D., González-Arangüena, E., Manuel, C., Owen, G., & Pozo, M. d. (2004). A unified approach to the Myerson value and the position value. In Essays in cooperative games (pp. 63–76). Springer. Guzman, J. D., Deckro, R. F., Robbins, M. J., Morris, J. F., & Ballester, N. A. (2014). An analytical comparison of social network measures. IEEE Transactions on Computational Social Systems,1(1), 35–45. Hadas, Y., Gnecco, G., & Sanguineti, M. (2017). An approach to transportation network analysis via transferable utility games. Transportation Research, Part B (Methodological),105, 120–143. Hamers, H., Husslage, B., & Lindelauf, R. (2019). Understanding the ISIS Zerkani network using game theoretic network analysis. In Handbook of the Shapley value (pp. 463–481). Harsanyi, J. (1959). A bargaining model for cooperative 𝑛-person games. In Contributions to the Theory of Games IV, 325–355. Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American statistical association,58(301), 13–30. Husslage, B., Borm, P., Burg, T., Hamers, H., & Lindelauf, R. (2015). Ranking terrorists in networks: A sensitivity analysis of Al Qaeda’s 9/11 attack. Social Networks,42, 1–7. Klerks, P. (2001). The network paradigm applied to criminal organizations. Connections, 24, 53–65. Koschade, S. (2006). A social network analysis of Jemaah Islamiyah: The applications to counterterrorism and intelligence. Studies in Conflict & Terrorism,29(6), 559–575. Li, H.-J., Feng, Y., Xia, C., & Cao, J. (2023). Overlapping graph clustering in attributed networks via generalized cluster potential game. ACM Transactions on Knowledge Discovery from Data,18(1), 1–26. Li, H.-J., Song, S., Tan, W., Huang, Z., Li, X., Xu, W., & Cao, J. (2022). Characterizing the fuzzy community structure in link graph via the likelihood optimization. Neurocomputing,512, 482–493. Lindelauf, R., Hamers, H. J., & Husslage, B. (2013). Cooperative game theoretic centrality analysis of terrorist networks: The cases of Jemaah Islamiyah and Al Qaeda. European Journal of Operational Research,229(1), 230–238. Maleki, S. (2015). Addressing the computational issues of the Shapley value with applications in the smart grid (Ph.D. thesis), University of Southampton. Manuel, C., Ortega, E., & Pozo, M. d. (2023). Marginality and the position value. Top, 31(2), 459–474. McGuire, R. M., Deckro, R. F., & Ahner, D. K. (2015). The weighted key player problem for social network analysis. Military Operations Research,20(2), 35–53. Meesen, R. (1988). Communication games (Master thesis), University of Nijmegen, the Netherlands (in Dutch). Michalak, T., K.V., A., Szczepanski, P., & Ravindran, B. (2013). Efficient computation of the Shapley value for game-theoretic network centrality. Journal of Artificial Intelligence Research,46, 607–650. Myerson, R. B. (1977). Graphs and cooperation in games. Mathematics of Operations Research,2(3), 225–229. Owen, G. (1977). Values of games with a priori unions. In Mathematical economics and game theory (pp. 76–88). Springer. Owen, G. (1982). Modification of the Banzhaf-Coleman index for games with a priori unions. In Power, voting, and voting power (pp. 232–238). Springer. Saavedra-Nieves, A. (2023). On stratified sampling for estimating coalitional values. Annals of Operations Research,320, 325–353. Saavedra-Nieves, A., & Casas-Méndez, B. (2023). On the centrality analysis of covert networks using games with externalities. European Journal of Operational Research, 309(3), 1365–1378. Saavedra-Nieves, A., & Fiestras-Janeiro, M. G. (2021). Sampling methods to estimate the Banzhaf–Owen value. Annals of Operations Research,301(1), 199–223. Saavedra-Nieves, A., & Fiestras-Janeiro, M. G. (2022). Analysis of the impact of DMUs on the overall efficiency in the event of a merger. Expert Systems with Applications, 195, Article 116571. Saavedra-Nieves, A., García-Jurado, I., & Fiestras-Janeiro, M. G. (2018). Estimation of the owen value based on sampling. In E. Gil, E. Gil, J. Gil, & M. A. Gil (Eds.), The mathematics of the uncertain: a tribute to Pedro Gil (pp. 347–356). Springer. Shapley, L. (1953). A value for n-person games. Annals of Mathematics Studies,2, 307–317. Slikker, M. (2005). A characterization of the position value. International Journal of Game Theory,33(4), 505–514. Song, S., Feng, Y., Xu, W., Li, H.-J., & Wang, Z. (2022). Evolutionary prisoner’s dilemma game on signed networks based on structural balance theory. Chaos, Solitons & Fractals,164, Article 112706. Sparrow, M. (1991). The application of network analysis to criminal intelligence: An assessment of the prospects. Social Networks,13(3), 251–274. Szczepanski, P. L., Michalak, T., & Rahwan, T. (2012). A new approach to betweenness centrality based on the Shapley value. In Proceedings of the 11th international conference on autonomous agents and multiagent systems, vol. 1 (pp. 239–246). Szczepanski, P. L., Michalak, T., & Rahwan, T. (2016). Efficient algorithms for game-theoretic betweenness centrality. Artificial Intelligence,231, 19–63. van den Brink, R., van der Laan, G., & Pruzhansky, V. (2011). Harsanyi power solutions for graph-restricted games. International Journal of Game Theory,40(1), 87–110.