A Value for Graph-Restricted Games with Middlemen on Edges

  Citation: Alarcón, A.C.; Gallardo, J.M.; Jiménez-Losada, A. A Value for Graph-Restricted Games with Middlemen on Edges. Mathematics 2022,10, 1856. https://doi.org/ 10.3390/math10111856 Academic Editor: David Barilla Received: 1 May 2022 Accepted: 24 May 2022 Published: 28 May 2022 Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. Copyright: © 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). mathematics Article A Value for Graph-Restricted Games with Middlemen on Edges Antonio C. Alarcón 1,†, José M. Gallardo 2,† and Andrés Jiménez-Losada 2,*,† 1Departamento de Ciencias Integradas, Facultad de Ciencias Experimentales, Universidad de Huelva, 21007 Huelva, Spain; [email protected] 2Departamento de Matemática Aplicada II, Escuela Técnica Superior de Ingeniería, Universidad de Sevilla, 41092 Sevilla, Spain; [email protected] *Correspondence: [email protected]; Tel.: +34-9544-86170 † These authors contributed equally to this work. Abstract: In a cooperative game with a communication structure, a graph describes the communication possibilities of the players, which are represented by the nodes. We introduce a variation of this model by assuming that each edge in the communication graph represents an agent. These agents simply act as intermediaries, but since they are essential for the cooperation and, consequently, for revenue generation, they will claim their share of the profit. We study this new model of games with a communication structure and introduce an allocation rule for these games. The motivation for analyzing this type of problem is based on the construction of a risk index for the different elements of an internal network. Keywords: cooperative game; Shapley value; restricted cooperation; graph-restricted game; Myerson value MSC: 91A06 1. Introduction 1.1. Motivation Consider an internal network. Suppose that the nodes are computers, hosts or users connected via Ethernet (LAN or WAN, including the entire IEEE.802 family) identifying each bilateral connection with an edge. Information and frames can be exchanged through the connection which corresponds to the data link layer of the layer architecture of the OSI (Open Systems Interconnections) model [ 1 ]. The information processed is usually protected by protocols that operate in the different layers of the OSI model, even with more specific measures, to be able to detect any intrusion or alteration in the AIC triad (availability, integrity and confidentiality) [ 2 ]. However, the communication channel (edge) can be intervened by specialists capable of violating weak security systems. This connection attack is called person in the middle (usually known as man in the middle, MiTM) which is a type of attack intended to intercept communication between two connected hosts. This attack allows a malicious agent (intruder or cracker) to manipulate the intercepted traffic in different ways, either to listen to the communication (sniffing) and obtain sensitive information or to supplant the identity (spoofing) of any of the parties. Apart from the attacks carried out in the communication, there are always vulnerabilities associated with the hosts and users themselves. This implies malwares, keyloggers and backdoors that can lead to data theft or unauthorized data transfers [ 2 ]. In this paper, we intend to use cooperative game theory to define a KRI (Key Risk Indicator) [ 3 , 4 ], a potential risk indicator which makes it an essential metric to reflect the required risk map to follow the ISO/IEC 27001 standard. Mathematics 2022,10, 1856. https://doi.org/10.3390/math10111856 https://www.mdpi.com/journal/mathematics Mathematics 2022,10, 1856 2 of 15 1.2. Cooperative Game Theory Cooperative game theory studies how to allocate the joint profit obtained by a group of players taking into account the profit achievable by each subset (coalition) of them. A cooperative game (with transferable utility) is given by a characteristic function that establishes the worth of each coalition. Multiple allocation rules have been introduced in the literature for these games, the Shapley value [ 5 ] being one of the best known. When dealing with cooperative games, it is often assumed that all the players within a coalition can cooperate freely. However, in many practical situations, players are subject to cooperation restrictions. These restrictions must be taken into account when allocating the profit because if the players in a coalition cannot cooperate they will not generate the worth of the coalition given by the characteristic function. In the present paper, we will focus on communication restrictions, which give rise to situations in which there are players that are not connected. Myerson [ 6 ] introduced games with communication structures, in which a graph describes the communication possibilities among the players. The vertices of the graph represent the players, and there exists a link between two vertices if and only if these nodes are able to communicate directly. For each game with communication structure, Myerson considered a restricted game, which assigns to each coalition the sum of the payments achievable by the connected components of the coalition. By considering the Shapley value of the restricted game, Myerson obtained an allocation rule for games with communication structures. He characterized this solution in terms of fairness and efficiency. Meesen [ 7 ] introduced an alternative value for games with communication structures, the position value, which was analyzed and characterized by Borm et al. [ 8 ]. Instead of focusing on the nodes of the graph, they concentrated on the role of the edges. Whereas Myerson had defined a restricted game on the set on vertices, they considered a game on the edges, which assigns to each set of edges the sum of the payments of the connected components of the grand coalition. In order to obtain an allocation rule, they consider the Shapley value of this edge game and then assign to each player half of the payoffs allocated to their incident edges, thus obtaining the position value of the communication game. Game theory and, particularly, the Myerson model have been used to study social networks [ 9 ] or network architectures [3,10]. 1.3. Objective Inspired by the edge game defined by Meesen, in the present paper we consider a variation of the model for communication games introduced by Myerson. However, whereas the edge game used by Meesen is just a tool to distribute the profit among the actual players, which are represented by the nodes, we are going to consider graph-restricted games in which each edge represents an autonomous agent with the ability to facilitate communication between two players. In return, each of these intermediary agents will claim a fair share of the profit. We then introduce a different use of graph-restricted games, which we call middlemen on the edges. Note that two types of agents will participate in them: the productive players, located at the vertices of the graph, and the middlemen, represented by the edges. In the present paper, we introduce an allocation rule for these games. This solution will be characterized in terms of fairness and efficiency, in a similar way as the Myerson value. Moreover, it will be proven that this value is stable for a wide family of games. Our solution will allow us to define a KRI for internal networks. 1.4. Organization The paper is organized as follows. In Section 2, some preliminaries regarding cooperative games and graph-restricted games are given. In Section 3, we introduce graph-restricted games with middlemen on edges and analyze a value for this family of games. Finally, in Section 4, an example with the application to construct a KRI in an internal network is described. Finally, we give some conclusions and future works in Section 5. Mathematics 2022,10, 1856 3 of 15 2. Preliminaries 2.1. Cooperative Games Acooperative game with transferable utility, referred to as a game from now on, is a pair (N , v) where N is a finite set, the elements of which are called players, and a function v: 2 N→R , named characteristic function, which satisfies v(∅)= 0. The subsets of N , the elements in 2 N , are called coalitions. Given a coalition S , the worth v(S) is interpreted as the common payment that the players of S obtain if they cooperate. Frequently, a cooperative game (N,v) is identified with the function v . The family of games with set of players N is denoted by GN . Let v∈ GN . A player i∈N is said to be null if v(S∪ {i}) = v(S) for all coalitions S⊆N\ {i} . Two different players i , j∈N are called symmetric if v(S∪ {i}) = v(S∪ {j})for any coalition S⊆N\ {i,j}. Family GN is a real vectorial space with dimension 2 |N|− 1. Given a non-empty coalition T⊆N, the unanimity game uT∈ GNis defined by: uT(S)=1 if T⊆S, 0 otherwise. (1) The set uT:T∈2N\{∅} is the basis of GN ; hence, each game v∈ GN can be written as a linear combination of them: v=∑ T∈2N\{∅} ∆v(T)uT. The coordinates of the game v with respect to the basis of the unanimity games are called the Harsanyi dividends [ 11 ] of v . The Harsanyi dividends can be obtained recursively: ∆v(T) =        v(T)if |T|=1, v(T)−∑ {R∈2N\{∅}:R$T} ∆v(R)if |R|>1. (2) The dividend of a coalition S in the game v can be interpreted as the part of the worth v(S) obtained only from the formation of this coalition. For instance, suppose N={ 1, 2 } . We have then that ∆v({i}) = v({i}) , so ∆v({ 1, 2 }) = v({ 1, 2 })−v({ 1 } − v({ 2 }) , that is the part of the worth v({1, 2})which is not obtained from the individual coalitions. A cooperative game v∈ GN is called monotone if S⊆T implies v(S)≤v(T) . Game v is positive if v(S)≥0 for all coalitionS, and vis superadditive if it satisfies v(S∪T)⩾v(S) + v(T) for every S , T⊆N with S∩T=∅ . If a game is superadditive and positive, then the game is monotone. 2.2. The Shapley Value A value on GN is a mapping ψ:GN→RN . For each v∈ GN , the coordinate ψi(v) represents the payoff of player i∈N in that game. There are many values defined in the literature. The best-known and most widely used is the Shapley value [ 5 ]. The Shapley value assigns to each player i∈Nin a game v∈ GN: Shi(v)=∑ S⊆N\{i} qN S(v(S∪ {i})−v(S)) (3) where qN S=(|N| − |S|−1)!|S|! |N|! Mathematics 2022,10, 1856 4 of 15 for every S$N . Another way to express the Shapley value is in terms of the Harsanyi dividends: Shi(v) = ∑ {S⊆N:i∈S} ∆v(S) |S|. (4) This formula allows us to explain the Shapley value in a nice sense. The Shapley value allocates the dividends of the coalitions among their players in an egalitarian way. The Shapley value satisfies the following properties. Let v∈GN: Efficiency:∑i∈NShi(v)=v(N); Additivity:Sh(v+w)=Sh(v)+Sh(w)for all w∈ GN; Equal treatment: if i,j∈Nare symmetric in vthen Shi(v) = Shj(v); Null player property: if i∈N is a null player in v , then Shi(v)= 0. Moreover, null players are removable in the following sense: if i∈N is a null player, and vi∈ GN\{i} is the restriction of the function vto 2N\{i}, then Shj(v) = Shj(vi)for all j∈N\ {i}; Monotonicity: if vis monotone, then Shi(v)≥0 for all i∈N. Shapley [ 5 ] proved that his value is the only one satisfying the efficiency, additivity, equal treatment and null player property. 2.3. Graph-Restricted Games and the Myerson Value In order to model cooperative situations with communication restrictions, Myerson [ 6 ] introduced graph-restricted games. We hereafter denote by N a fixed finite set. All the graphs considered in this paper will be undirected simple graphs. If i , j are two different nodes in N , the link {i , j} will be denoted just by ij , provided that it does not lead to confusion. A graph-restricted game (v , E) on N consists of a game v∈ GN and a graph (N , E) . In this model, (N , E) represents the communication possibilities between the players, in the sense that a coalition is feasible only if all its players are connected, according the graph, within the coalition. If S⊆N , then ES={ij ∈E:i , j∈S , i6=j} . Remember that two vertices (players) i , j∈N are connected in (N , E) if there is a list of players {i1 , . . . , ip} with i1=i , ip=j and ikik+1∈E for each k= 1, . . . , p− 1. Coalition S is connected in (N , E) if all pair of players i , j∈S are connected in the graph (S , ES) . The maximal connected coalitions are called connected components in (N , E) . Myerson introduced a value for graph-restricted games. Given a graph-restricted game (v,g), he defined vE: 2N→Ras: vE(S) = ∑ T∈S/E v(T)(5) for every S∈2N, where S/Eis the set: S/E={T⊆S:Tconnected component in(S,ES)}. (6) So, he considers the worth of a coalition as the sum of the payments of the maximal connected sets within the coalition, assuming that the connected sets by the graph are the only feasible coalitions. For example, consider the graph g= (N , E) in Figure 1, with N={ 1, 2, 3 } and E={ 12, 23 } , and any game v∈ GN . Notice that vE({ 1, 3 }) = v({ 1 }) +v({3})since {1, 3}/E={{1},{3}}, but vE(N) = v(N)because N/E={N}. <latexit sha1_base64="LZT0oI2vX8RvxfNUVNH4rRAdfwE=">AAAB4nicbZDLTgJBEEVr8IX4Ql266UhMXJEZJeqSxI1LSOSRwIT0NDXQoeeR7hoTQvgBXRl15yf5A/6NDc5C0bs6Xfd2UreCVElDrvvpFNbWNza3itulnd29/YPy4VHbJJkW2BKJSnQ34AaVjLFFkhR2U408ChR2gsntwu88oDYyie9pmqIf8VEsQyk42VHzclCuuFV3KfYXvBwqkKsxKH/0h4nIIoxJKG5Mz3NT8mdckxQK56V+ZjDlYsJH2LMY8wiNP1suOmdnYaIZjZEt3z+zMx4ZM40Cm4k4jc2qtxj+5/UyCm/8mYzTjDAWNmK9MFOMErboy4ZSoyA1tcCFlnZLJsZcc0H2KiVb31st+xfaF1Xvqlpr1ir1Wn6IIpzAKZyDB9dQhztoQAsEIDzBK7w5Q+fReXZevqMFJ/9zDL/kvH8BcvuKRw==</latexit> 3 <latexit sha1_base64="cGoWU1/tPqaILr67MKPYNv/g21U=">AAAB4nicbZDLTgJBEEVr8IX4Ql266UhMXJEZQtQliRuXkAiYwIT0NAV06Hmku8aETPgBXRl15yf5A/6NDc5Cwbs6Xfd2UreCRElDrvvlFDY2t7Z3irulvf2Dw6Py8UnHxKkW2BaxivVDwA0qGWGbJCl8SDTyMFDYDaa3C7/7iNrIOLqnWYJ+yMeRHEnByY5atUG54lbdpdg6eDlUIFdzUP7sD2ORhhiRUNyYnucm5GdckxQK56V+ajDhYsrH2LMY8RCNny0XnbOLUawZTZAt37+zGQ+NmYWBzYScJmbVWwz/83opjW78TEZJShgJG7HeKFWMYrboy4ZSoyA1s8CFlnZLJiZcc0H2KiVb31stuw6dWtW7qtZb9Uqjnh+iCGdwDpfgwTU04A6a0AYBCM/wBu/O0HlyXpzXn2jByf+cwh85H99xfYpG</latexit> 2 <latexit sha1_base64="62tGTZrihI67PXfcqwbfmZY0dhY=">AAAB4nicbZDLTgJBEEVr8IX4Ql266UhMXJEZQ9QliRuXkMgjgQnpaQro0PNId40JmfADujLqzk/yB/wbG5yFgnd1uu7tpG4FiZKGXPfLKWxsbm3vFHdLe/sHh0fl45O2iVMtsCViFetuwA0qGWGLJCnsJhp5GCjsBNO7hd95RG1kHD3QLEE/5ONIjqTgZEdNb1CuuFV3KbYOXg4VyNUYlD/7w1ikIUYkFDem57kJ+RnXJIXCeamfGky4mPIx9ixGPETjZ8tF5+xiFGtGE2TL9+9sxkNjZmFgMyGniVn1FsP/vF5Ko1s/k1GSEkbCRqw3ShWjmC36sqHUKEjNLHChpd2SiQnXXJC9SsnW91bLrkP7qupdV2vNWqVeyw9RhDM4h0vw4AbqcA8NaIEAhGd4g3dn6Dw5L87rT7Tg5H9O4Y+cj29v/4pF</latexit> 1 Figure 1. Graph (N,E). Mathematics 2022,10, 1856 5 of 15 Then, Myerson defines a value for graph-restricted games, known in the literature as the Myerson value, given by: Y(v,E) = Sh(vE). (7) Hence, the Myerson value is actually the Shapley value of a certain modification of the initial game. Myerson proves that Yis characterized by the following properties: Component efficiency: ∑i∈TYi(v,E)=v(T) for every graph-restricted game (v , E) and every T∈N/E; Fairness: Yi(v , E)−Yi(v , E\ {ij}) = Yj(v , E)−Yj(v , E\ {ij}) for every graph-restricted game (v , E) and every ij ∈E . That is, both players in a link have the same profit decrease if we remove the link. 3. A Value for Graph-Restricted Games with Middlemen on Edges In the graph-restricted games introduced by Myerson [ 6 ], the existence of an edge ij means that players i and j can cooperate freely, in the sense that there is a method of communication between i and j . It is assumed that there is no cost associated with the direct communication between i and j . Nevertheless, there are situations in which the direct communication between two players depends on an intermediary agent. This agent does not properly participate in the income-generating activity in which i an j are involved, but they are essential to facilitate the cooperation. In order to model a situation like that, we will consider a graph-restricted game with middlemen on edges, which consists of a graph (N , E) and a characteristic function v: 2 N→R , which indicates the profit that can be obtained by each coalition of nodes if they are allowed to cooperate. The difference with the games introduced by Myerson is that, in our case, both nodes and edges represent agents, and consequently, each one of them should receive a fair payoff. Our goal is to define and characterize a reasonable allocation rule for graph-restricted games with middlemen on edges. A graph-restricted game (on N ) with middlemen on edges consists of a characteristic function v: 2 N→R with v(∅) = 0 and a graph (N , E) . It will be denoted by (v , E) . So, a graph-restricted game with middlemen on edges is exactly the same mathematical structure as a graph-restricted game. The family of graph-restricted games (on N ) will be denoted by GRN. Our approach consists of introducing a new kind of solution. Definition 1. A value for graph-restricted games on N with middlemen on the edges is a mapping Ψthat assigns to each (v,E)∈ GRNa payoff vector Ψ(v,E)∈RN∪E. Myerson [ 6 ] considered a new game defined over the nodes (5) and Meesen [ 7 ] a new game over the links. We need to define a new game for both nodes and edges. In order to obtain a payoff vector for both elements for a game (v , E)∈ GRN , we can consider the restricted game (N∪E,vE)∈ GN∪E, where vE: 2N∪E→Ris defined by: vE(S∪F) = ∑ R∈S/F v(R)(8) for every S⊆N and every F⊆E , where S/F is the set of connected components in (S , FS) . Following Myerson and Meesen, we define a value for graph-restricted games with middlemen on the edges by using vE. Definition 2. The Myerson value for graph-restricted games with middlemen on the edges is the value Φgiven by: Φ(v,E) = Sh(vE)∈RN∪E for all (v,E)∈ GRN. Obviously, this value is related to the original Myerson value. In fact, we can prove the following result that allows us to determine Φ through the Myerson value by changing the game and the graph (see Figure 2). Mathematics 2022,10, 1856 6 of 15 <latexit sha1_base64="LZT0oI2vX8RvxfNUVNH4rRAdfwE=">AAAB4nicbZDLTgJBEEVr8IX4Ql266UhMXJEZJeqSxI1LSOSRwIT0NDXQoeeR7hoTQvgBXRl15yf5A/6NDc5C0bs6Xfd2UreCVElDrvvpFNbWNza3itulnd29/YPy4VHbJJkW2BKJSnQ34AaVjLFFkhR2U408ChR2gsntwu88oDYyie9pmqIf8VEsQyk42VHzclCuuFV3KfYXvBwqkKsxKH/0h4nIIoxJKG5Mz3NT8mdckxQK56V+ZjDlYsJH2LMY8wiNP1suOmdnYaIZjZEt3z+zMx4ZM40Cm4k4jc2qtxj+5/UyCm/8mYzTjDAWNmK9MFOMErboy4ZSoyA1tcCFlnZLJsZcc0H2KiVb31st+xfaF1Xvqlpr1ir1Wn6IIpzAKZyDB9dQhztoQAsEIDzBK7w5Q+fReXZevqMFJ/9zDL/kvH8BcvuKRw==</latexit> 3 <latexit sha1_base64="cGoWU1/tPqaILr67MKPYNv/g21U=">AAAB4nicbZDLTgJBEEVr8IX4Ql266UhMXJEZQtQliRuXkAiYwIT0NAV06Hmku8aETPgBXRl15yf5A/6NDc5Cwbs6Xfd2UreCRElDrvvlFDY2t7Z3irulvf2Dw6Py8UnHxKkW2BaxivVDwA0qGWGbJCl8SDTyMFDYDaa3C7/7iNrIOLqnWYJ+yMeRHEnByY5atUG54lbdpdg6eDlUIFdzUP7sD2ORhhiRUNyYnucm5GdckxQK56V+ajDhYsrH2LMY8RCNny0XnbOLUawZTZAt37+zGQ+NmYWBzYScJmbVWwz/83opjW78TEZJShgJG7HeKFWMYrboy4ZSoyA1s8CFlnZLJiZcc0H2KiVb31stuw6dWtW7qtZb9Uqjnh+iCGdwDpfgwTU04A6a0AYBCM/wBu/O0HlyXpzXn2jByf+cwh85H99xfYpG</latexit> 2 <latexit sha1_base64="62tGTZrihI67PXfcqwbfmZY0dhY=">AAAB4nicbZDLTgJBEEVr8IX4Ql266UhMXJEZQ9QliRuXkMgjgQnpaQro0PNId40JmfADujLqzk/yB/wbG5yFgnd1uu7tpG4FiZKGXPfLKWxsbm3vFHdLe/sHh0fl45O2iVMtsCViFetuwA0qGWGLJCnsJhp5GCjsBNO7hd95RG1kHD3QLEE/5ONIjqTgZEdNb1CuuFV3KbYOXg4VyNUYlD/7w1ikIUYkFDem57kJ+RnXJIXCeamfGky4mPIx9ixGPETjZ8tF5+xiFGtGE2TL9+9sxkNjZmFgMyGniVn1FsP/vF5Ko1s/k1GSEkbCRqw3ShWjmC36sqHUKEjNLHChpd2SiQnXXJC9SsnW91bLrkP7qupdV2vNWqVeyw9RhDM4h0vw4AbqcA8NaIEAhGd4g3dn6Dw5L87rT7Tg5H9O4Y+cj29v/4pF</latexit> 1 <latexit sha1_base64="LZT0oI2vX8RvxfNUVNH4rRAdfwE=">AAAB4nicbZDLTgJBEEVr8IX4Ql266UhMXJEZJeqSxI1LSOSRwIT0NDXQoeeR7hoTQvgBXRl15yf5A/6NDc5C0bs6Xfd2UreCVElDrvvpFNbWNza3itulnd29/YPy4VHbJJkW2BKJSnQ34AaVjLFFkhR2U408ChR2gsntwu88oDYyie9pmqIf8VEsQyk42VHzclCuuFV3KfYXvBwqkKsxKH/0h4nIIoxJKG5Mz3NT8mdckxQK56V+ZjDlYsJH2LMY8wiNP1suOmdnYaIZjZEt3z+zMx4ZM40Cm4k4jc2qtxj+5/UyCm/8mYzTjDAWNmK9MFOMErboy4ZSoyA1tcCFlnZLJsZcc0H2KiVb31st+xfaF1Xvqlpr1ir1Wn6IIpzAKZyDB9dQhztoQAsEIDzBK7w5Q+fReXZevqMFJ/9zDL/kvH8BcvuKRw==</latexit> 3 <latexit sha1_base64="cGoWU1/tPqaILr67MKPYNv/g21U=">AAAB4nicbZDLTgJBEEVr8IX4Ql266UhMXJEZQtQliRuXkAiYwIT0NAV06Hmku8aETPgBXRl15yf5A/6NDc5Cwbs6Xfd2UreCRElDrvvlFDY2t7Z3irulvf2Dw6Py8UnHxKkW2BaxivVDwA0qGWGbJCl8SDTyMFDYDaa3C7/7iNrIOLqnWYJ+yMeRHEnByY5atUG54lbdpdg6eDlUIFdzUP7sD2ORhhiRUNyYnucm5GdckxQK56V+ajDhYsrH2LMY8RCNny0XnbOLUawZTZAt37+zGQ+NmYWBzYScJmbVWwz/83opjW78TEZJShgJG7HeKFWMYrboy4ZSoyA1s8CFlnZLJiZcc0H2KiVb31stuw6dWtW7qtZb9Uqjnh+iCGdwDpfgwTU04A6a0AYBCM/wBu/O0HlyXpzXn2jByf+cwh85H99xfYpG</latexit> 2 <latexit sha1_base64="62tGTZrihI67PXfcqwbfmZY0dhY=">AAAB4nicbZDLTgJBEEVr8IX4Ql266UhMXJEZQ9QliRuXkMgjgQnpaQro0PNId40JmfADujLqzk/yB/wbG5yFgnd1uu7tpG4FiZKGXPfLKWxsbm3vFHdLe/sHh0fl45O2iVMtsCViFetuwA0qGWGLJCnsJhp5GCjsBNO7hd95RG1kHD3QLEE/5ONIjqTgZEdNb1CuuFV3KbYOXg4VyNUYlD/7w1ikIUYkFDem57kJ+RnXJIXCeamfGky4mPIx9ixGPETjZ8tF5+xiFGtGE2TL9+9sxkNjZmFgMyGniVn1FsP/vF5Ko1s/k1GSEkbCRqw3ShWjmC36sqHUKEjNLHChpd2SiQnXXJC9SsnW91bLrkP7qupdV2vNWqVeyw9RhDM4h0vw4AbqcA8NaIEAhGd4g3dn6Dw5L87rT7Tg5H9O4Y+cj29v/4pF</latexit> 1 <latexit sha1_base64="HWvAcaJmFN0Ehh8IMoz7upQQUpc=">AAAB43icbZDLTgJBEEVr8IX4Ql266UhMXJEZQtQliRuXaARJgJCepgY69DzSXWNCJnyBroy684/8Af/GBmeh4F2drns7qVt+oqQh1/1yCmvrG5tbxe3Szu7e/kH58Kht4lQLbIlYxbrjc4NKRtgiSQo7iUYe+gof/Mn13H94RG1kHN3TNMF+yEeRDKTgZEd3Xm1QrrhVdyG2Cl4OFcjVHJQ/e8NYpCFGJBQ3puu5CfUzrkkKhbNSLzWYcDHhI+xajHiIpp8tNp2xsyDWjMbIFu/f2YyHxkxD32ZCTmOz7M2H/3ndlIKrfiajJCWMhI1YL0gVo5jNC7Oh1ChITS1woaXdkokx11yQPUvJ1veWy65Cu1b1Lqr123qlUc8PUYQTOIVz8OASGnADTWiBgACe4Q3eHXSenBfn9SdacPI/x/BHzsc336qKgQ==</latexit> 12 <latexit sha1_base64="jvZqcCwl5IeRDLHmfRkV2UGdTZ0=">AAAB43icbZDNTgIxFIXv4B/iH+rSTSMxcUVmkKhLEjcu0chPAhPSKXegoTOdtB0TMuEJdGXUnW/kC/g2FpyFgmf19Z7T5J4bJIJr47pfTmFtfWNzq7hd2tnd2z8oHx61tUwVwxaTQqpuQDUKHmPLcCOwmyikUSCwE0xu5n7nEZXmMn4w0wT9iI5iHnJGjR3d1y4G5YpbdRciq+DlUIFczUH5sz+ULI0wNkxQrXuemxg/o8pwJnBW6qcaE8omdIQ9izGNUPvZYtMZOQulImaMZPH+nc1opPU0Cmwmomasl7358D+vl5rw2s94nKQGY2Yj1gtTQYwk88JkyBUyI6YWKFPcbknYmCrKjD1Lydb3lsuuQrtW9S6r9bt6pVHPD1GEEziFc/DgChpwC01oAYMQnuEN3h10npwX5/UnWnDyP8fwR87HN+KnioM=</latexit> 23 Figure 2. Graph involving vertices and edges. Proposition 1. Let (v , E)∈ GRN be a graph-restricted game. The value Φ for (v , E) satisfies that Φ(v,E) = Y(ˆ v,ˆ E), where: •ˆ v∈ GN∪Ewith ˆ v(S∪F) = v(S); •(N∪E,ˆ E)is a graph with ˆ E={ie :e=ij ∈E}. Proof. Consider (v , E)∈ GRN . Let S∪F with S⊆N and F⊆E . For each T⊆S , we define: HT F={ij ∈F:{i,j} ∩ T6=∅}. We have that (S∪F)/ˆ E={T∪HT F:T∈S/F}, because coalition T∈S/F if and only if T is connected in (S , FS) and there is not ij ∈HT F with j∈S\T. Now we obtain: ˆ vˆ E(S∪F) = ∑ T∪H∈(S∪F)/ˆ E ˆ v(T∪H) = ∑ T∪H∈(S∪F)/ˆ E v(T) =∑ T∈S/F v(T) = vE(S∪F). If both games are the same, then: Y(ˆ v,ˆ E) = Sh(ˆ vˆ E) = Sh(vE) = Φ(v,E). Our goal in the rest of the paper will be to characterize Φ . To this end, we will consider the following properties: • COMPONENT EFFICIENCY. A value Ψ for graph-restricted games with middlemen on the edges satisfies component efficiency if: ∑ i∈T Ψi(v,E)+∑ jk∈ET Ψjk(v,E)=v(T) for every (v,E)∈ GRNand every T∈N/E. The property of component efficiency establishes that if T is a connected component of the communication graph, then the players in T and the middlemen that communicate them allocate to themselves the profit that the players in T can generate when they cooperate. • FAIRNESS. A value Ψ for graph-restricted games with middlemen on the edges satisfies fairness if: Ψi(v,E)−Ψi(v,E\ {ij}) = Ψij(v,E) Mathematics 2022,10, 1856 7 of 15 for every (v,E)∈ GRNand every ij ∈E. The property of fairness asserts that if a middleman establishes a direct communication between two players, then all three of them will benefit equally. The following theorems state that Φis characterized by the two properties above. Theorem 1. The value Φsatisfies component efficiency and fairness. Proof. We will show that Φsatisfies the properties in the theorem using Proposition 1. COMPONENT EFFICIENCY. Let (v , E)∈ GRN and let T∈N/E . Obviously, T∪ET∈ (N∪E)/ˆ E. As the Myerson value satisfies the component efficiency, then: ∑ i∈T Φi(v,E) + ∑ ij∈ET Φij(v,E) = ∑ i∈T Yi(ˆ v,ˆ E) + ∑ ij∈ET Yij(ˆ v,ˆ E) =ˆ v(T∪ET) = v(T). FAIRNESS. Let (v , E)∈ GRN and let e=ij ∈E . We consider the edge ie ∈ˆ E , and we apply the fairness property to the Myerson value of (ˆ v , ˆ E) . The following relation is obtained: Ye(ˆ v,ˆ E)−Ye(ˆ v,ˆ E\ {ie}) = Yi(ˆ v,ˆ E)−Yi(ˆ v,ˆ E\ {ie}). (9) From Proposition 1, we have that Φe(v , E) = Ye(ˆ v , ˆ E) and Φi(v , E) = Yi(ˆ v , ˆ E) . In addition, the definition of the Myerson value (7) implies that Y(ˆ v , ˆ E\ {ie}) = Shˆ vˆ E\{ie} , where ˆ vˆ E\{ie}∈ GN∪E. First, we will prove that e is a null player in ˆ vˆ E\{ie} . Observe that e , as a vertex in (N∪E , ˆ E\ {ie}) , is only connected to j . Let S∪F with S⊆N and F⊆E\ {e} . We intend to test that ˆ vˆ E\{ie}((S∪F)∪ {e}) = ˆ vˆ E\{ie}(S∪F). (10) In fact, if j/∈S , then {e} is a connected component in (S∪(F∪ {e}) , (ˆ E\ {ie})S∪(F∪{e})) , and since ˆ v({e}) = 0, the equality is true. Suppose j∈S ; then, if T∪H∈(S∪F)/(ˆ E\ {ie}) is the connected component containing j in the graph without e , then T∪(H∪ {e})∈ ((S∪F)∪ {e}))/(ˆ E\ {ie}) is the connected component containing j in the graph with e . Obviously, [(S∪F)/(ˆ E\ {ie})] \ {T∪H}= [((S∪F)∪ {e}))/(ˆ E\ {ie})] \ {T∪(H∪ {e})}. From the definition of game ˆ v , we have (10) again. Since e is a null player in ˆ vˆ E\{ie} and the Shapley value satisfies the null player property (see Section 2.2), then: Ye(ˆ v,ˆ E\ {ie}) = Sheˆ vˆ E\{ie}=0. (11) Moreover, as we said in Section 2.2, null players are removable to calculate the Shapley value. So, for player i, we can calculate: Shiˆ vˆ E\{ie}=Shiˆ vˆ E\{ie} e thinking of the game without player e as ˆ vˆ E\{ie} e∈ GN∪(E\{e}) . Consider, then, S∪F with S⊆Nand F⊆E\ {e}. If we do not use e, then we have: ˆ vˆ E\{ie} e(S∪F) = ˆ v\ E\{e}(S∪F). Secondly, we obtain: Yi(ˆ v,ˆ E\ {ie}) = Shiˆ vˆ E\{ie} e=Shiˆ v\ E\{e}=Yi(ˆ v,\ E\ {e}). (12) Mathematics 2022,10, 1856 8 of 15 Finally, putting (9), (11) and (12) together: Φij(v,E) = Ye(ˆ v,ˆ E) = Yi(ˆ v,ˆ E)−Yi(ˆ v,\ E\ {e}) = Φi(v,E)−Φi(v,E\ {ij}). Now we will prove that our value is determined by these properties, namely, the component efficiency and fairness. Theorem 2. The value Φ is the only value for graph-restricted games on N with middlemen on the edges satisfying component efficiency and fairness. Proof. Let Ψ:GRN→RN∪E be a value that satisfies component efficiency and fairness. We aim to prove that: Φ(v,E) = Ψ(v,E) for every (v,E)∈ GRN. We will prove the equality above by induction on |E|. • Base case. |E|=0. By the property of component efficiency, it is clear that Ψi(v,∅) = Φi(v,∅) = v({i}) for every i∈N. • Induction step. Let (v , E)∈ GRN be such that |E|> 0. In order to prove that Ψ(v , E) = Φ(v , E) , we will show that for every T∈N/E, the following equalities hold: Ψi(v,E) = Φi(v,E)for every i∈T, (13) Ψjk(v,E) = Φjk(v,E)for every jk ∈ET. (14) Take T∈N/E. If |T|=1, then ET=∅, and by the property of component efficiency, (13) holds. Suppose now that |T|> 1. Let i , j∈T with ij ∈E . By the property of fairness, it is clear that Ψi(v,E)−Ψi(v,E\ {ij}) = Ψj(v,E)−Ψj(v,E\ {ij}), (15) Φi(v,E)−Φi(v,E\ {ij}) = Φj(v,E)−Φj(v,E\ {ij}). (16) Moreover, by induction hypothesis, we have that Ψi(v,E\ {ij}) = Φi(v,E\ {ij}), (17) Ψj(v,E\ {ij}) = Φj(v,E\ {ij}). (18) From (15)–(18), we conclude that Ψi(v,E)−Φi(v,E) = Ψj(v,E)−Φj(v,E) Taking into account that i and j have been arbitrarily chosen in T with the condition ij ∈E and that T is a connected component of (N , E) , it is clear that there exists b∈R such that Ψi(v,E)−Φi(v,E) = bfor every i∈T. (19) Let jk ∈ET. By the property of fairness, we know that Ψjk(v,E) = Ψj(v,E)−Ψj(v,E\ {jk}) Φjk(v,E) = Φj(v,E)−Φj(v,E\ {jk}) Mathematics 2022,10, 1856 9 of 15 Thus, Ψjk(v , E)−Φjk(v , E) = Ψj(v , E)−Φj(v , E)−Ψj(v , E\ {jk}) + Φj(v , E\ {jk}) =b , where we have used (19) and the induction hypothesis. Therefore, we have proven that Ψjk(v,E)−Φjk(v,E) = bfor every jk ∈ET(20) From (19) and (20) and the fact that Ψ and Φ satisfy component efficiency, we can easily deduce that b=0, which leads to (13) and (14). Notice that the characterization that we have obtained for the value Φ is similar to that obtained by Myerson [ 6 ] for the value Y . Roughly speaking, we have adapted the properties of component efficiency and fairness to our framework. In his seminal paper, Myerson introduced a third interesting property of values for graph-restricted games, which is stability. In this context, stability means that if the underlying game (i.e., the game before considering communication restrictions) is superadditive, then any two players will always benefit from establishing a link between them. After proving that the value Y is characterized by the properties of fairness and component efficiency, Myerson concludes his paper with the proof that Y is stable. In order to maintain the parallelism between this paper and Myerson’s, we will prove that Φis also stable. Proposition 2. The value Φis stable, that is, if (v,E)∈ GRNand v is superadditive, then: Φi(v,E)⩾Φi(v,E\ {ij}) for every ij ∈E. Proof. Let (v , E)∈ GRN be such that v is superadditive. Let ij ∈E . We aim to prove that Φi(v , E)⩾Φi(v , E\ {ij}) . By the property of fairness, this is equivalent to Φij(v , E)⩾ 0. We have that Φij(v,E) = ∑ S⊆N F⊆E\{ij} qN∪E S∪F(vE(S∪F∪ {ij})−vE(S∪F)). Therefore, it suffices to prove that vE(S∪F∪ {ij})⩾vE(S∪F) for every S⊆N and every F⊆E\ {ij}. To this end, take S⊆Nand F⊆E\ {ij}. We distinguish three cases: (i) {i,j}*S. In this case, it is evident that (F∪ {ij})S=FS. We have that vE(S∪F∪ {ij}) = ∑ R∈S/(F∪{ij})S v(R) = ∑ R∈S/FS v(R) = vE(S∪F). (ii) i , j∈S and they are connected in (S , FS) . In this case, it is easy to check that S/(F∪ {ij})S=S/FS. This leads to vE(S∪F∪ {ij})=vE(S∪F). (iii) i , j∈S and they are not connected in (S , FS) . We can write S/FS={R1 , . . . , Rm} , where m⩾ 2 , i∈R1 and j∈R2 . It is clear that S/(F∪ {ij})S={R1∪R2 , R3. . . , Rm} . We have that vE(S∪F∪ {ij})−vE(S∪F) = ∑ R∈S/(F∪{ij})S v(R)−∑ R∈S/FS v(R) =v(R1∪R2)−v(R1)−v(R2), which is non-negative by the superadditivity of v . Hence, vE(S∪F∪ {ij})⩾vE(S∪F) . The next property will be interesting in the following section. Proposition 3. If (v , E)∈ GRN satisfies that v is superadditive and positive, then it holds Φ(v,E)≥0.