Allocation rules for communication situations with incompatibilities

Annals of Operations Research (2024) 340:757–784 https://doi.org/10.1007/s10479-024-06145-8 ORIGINAL RESEARCH Allocation rules for communication situations with incompatibilities Manuela Basallote1·José M. Gallardo1·Carmen Hernández-Mancera1· Andrés Jiménez-Losada1 Received: 22 June 2023 / Accepted: 2 July 2024 / Published online: 19 July 2024 © The Author(s) 2024 Abstract In this article we analyze certain situations with restricted cooperation. To do this we introduce a model that combines two types of games well studied in the literature: graph-restricted games and games with incompatible players. In particular, our model extends Myerson’s model for communication situations and Bergantiños’ model for incompatible relationships. Our approach is based on the concept of profit measure, which allows us to deal simultaneously with both types of bilateral relationships. We show that in the situations considered there are multiple possible definitions of the profit achievable for each coalition. This leads us to introduce different allocation rules for these cooperative situations. Keywords Cooperative games ·Signed graphs ·Communication structures · Incompatibilities ·Myerson value 1 Introduction Cooperative game theory provides mathematical models for situations in which a group of players work together to achieve a common profit. A cooperative game (with transferable utility) is given by a characteristic function that assigns to each subset of players (coalition) the profit generated by these players when they cooperate. One of the main applications of cooperative games is to provide allocation rules for distributing the joint profit generated Manuela Basallote, José M. Gallardo, Carmen Hernández-Mancera and Andrés Jiménez-Losada have contributed equally to this work BAndrés Jiménez-Losada [email protected] Manuela Basallote [email protected] José M. Gallardo [email protected] Carmen Hernández-Mancera [email protected] 1Department of Applied Mathematics II, University of Seville, Avda/ Los Descubrimientos s/n, 41927 Seville, Spain 123 758 Annals of Operations Research (2024) 340:757–784 by the grand coalition. The best-known allocation rule for cooperative games is the Shapley value (Shapley, 1953). Cooperativegametheory also providesmodelsforsituations in which thereare restrictions on cooperation. These restrictions can be of different types. Myerson (1977) introduced a model to analyze cooperative situations with restricted communication. In this model the players are represented by the nodes of a graph and there is a link between two nodes if and only if the players that they represent can communicate directly with each other. By using the Shapley value, Myerson obtained an allocation rule, the Myerson value, applicable to these situations. Once fixed a cooperative game in the set of players, the Myerson value assigns a payoff vector to each communication situation, that is, to each graph with vertex set equal to the set of players. Multiple extensions and variations of the Myerson value have been introduced in the literature, providing more complex models to accurately represent communication between players. In some of these extensions, structures more general than simple graphs have been used, such as hypergraphs Myerson (1980), probabilistic graphs Calvo et al. (1999), fuzzy graphs Jiménez-Losada et al. (2013) or directed graphs Li and Shan (2020). In other cases, variations in the game have been considered, such as games with fuzzy coalitions Xu et al. (2017) or players located on the edges of the graph Alarcón et al. (2022). Other variations have been obtained by imposing properties different from those satisfied by the Myerson value, such as efficiency Beál et al. (2015) or marginality Manuel et al. (2020). Bergantiños et al. (1993) introduced a model to analyze cooperative situations with a different type of cooperation restrictions: bilateral incompatibilities. In this model the players arerepresentedalsobythenodesofagraph,butinthiscasealinkbetweentwonodesindicates that the players that they represent are incompatible, that is, they cannot cooperate. Although initially it could be thought that this model is dual to that of Myerson, this is not the case. This model for bilateral incompatibilities has been applied to various types of situations with restricted cooperation Alonso-Meijide et al. (2009); Gallardo et al. (2020). See et al. (2014) proposed a model for voting games with bilateral incompatibilities but their approach is essentially different from that considered in Bergantiños et al. (1993). In the models proposed in Bergantiños et al. (1993)andSeeetal.(2014) it is assumed that if two players are not incompatible, then they can communicate directly with each other. Therefore, it remained to study situations with both bilateral incompatibilities and communication restrictions. Skibski et al. (2022) used signed graphs (Zaslavsky, 1982) to model situations which combine both types of constraints. They consider that, for any two players, one (and only one) of the following scenarios will occur: (1) the players are incompatible, in which case there will be a negative edge between the corresponding nodes, (2) the players are not incompatible and can communicate directly with each other, which is described by a positive edge between them, (3) the players are not incompatible and cannot communicate directly with each other, in which case there is no link between them. Skibski et al. propose an allocation rule for these cooperative situations. This rule is, roughly speaking, a combination of the value of Myerson (1977) for games with communication restrictions and the solution proposed in See et al. (2014) for games with bilateral incompatibilities. Signed graphs were recently used by Li and Morse (2022) to analyze non-cooperative games. Motivation We aim to study cooperative situations with both types of constraints: communication restrictions and bilateral incompatibilities. The key difference with Skibski et al. (2022) will be 123 Annals of Operations Research (2024) 340:757–784 759 Fig. 1 Scenarios (A) and (B) that, while they use the model proposed by See et al. to deal with incompatibilities, we will use the model introduced by Bergantiños et al., so we will find allocation rules that extend the Myerson value Myerson (1977) and the incompatibility value Bergantiños et al. (1993). Let us provide an example to illustrate the motivation behind our main goal. Consider a software developer consisting of several teams. Each of these teams is represented by a node in a graph. Given two nodes iand jin this graph, (i) there is a positive edge between iand jif the corresponding teams can collaborate, regardless of the actions of the other teams, (ii) there is no edge between iand jif the corresponding teams can collaborate only with the help or intermediation of other teams (which connect iand j), (iii) there is a negative edge between iand jif both teams do the same work in any project and, therefore, cannot work together. The developer aims to obtain the most valuable software possible and distribute the profit among theteams. For instance,we willconsiderthreeteams 1,2 and3.For each S⊆{1,2,3}, the real number v(S)describes the market value of the software that the teams in Swould create if the other teams do not help them in any way. In a first scenario (A), see Fig. 1,we consider positive connections {1,2}and {1,3}, and no connection between 2 and 3. If team 1 were not present, teams 2 and 3 would work separately and achieve a collective profit of v({2})+v({3}). But thanks to 1, the developer can sell a new software obtaining a profit of v({1,2,3}). Now we consider a second scenario (B) with a negative connection between teams 2 and 3. The model in Skibski et al. (2022) is based on the one in See et al. (2014) (which is focused on power allocation problems) and attributes no profit to the developer in this case. However, the developer could obtain profit, for example, by having teams 1 and 2 create a software jointly, while team 3 creates another software separately. If we assume that the profit function vis superadditive, then, according to our model, the profit obtained by the developer would be max{v({1,2})+v({3}), v({1,3})+v({2})}, which coincides with the profit proposed in Bergantiños et al. (1993). Therefore, the model that we introduce is different from the one in Skibski et al. (2022). The main difficulty that will arise lies in the fact that whereas in the models proposed by Myerson and Bergantiños et al. there is only one reasonable way to define the profit achievable by each coalition, in our mixed model there exists a family (which is infinite if the number of agents is greater than 3) of reasonable profit measures, each one of them generating a different allocation rule. The study of the mathematical structure of this family of profit measures will help us to show the interest of the allocation rules found. Structure The paper is organized as follows. Section 2is intended to make the paper as self-contained as possible. Some preliminaries regarding partially ordered sets, convex sets, partitions, graphs and cooperative games are given. In Sect. 3, we present the model proposed by Myerson 123 760 Annals of Operations Research (2024) 340:757–784 (1977) for communication situations and the model proposed by Bergantiños et al. (1993) for situations with incompatibilities. In order to construct a model for communication situations with incompatibilities that extend the model of Myerson and that of Bergantiños et al., we introduce, inspired by Jackson’s network games Jackson (2005,2008), the concept of profit measure, which allows us to deal with both types of relationships. In Sect. 4we study communication situations with incompatibilities using signed graphs introducing new concepts and notations. We propose a motivating example to explain the possibility to introduce a new model. In Sect. 5we obtain a family of allocation rules for cooperative games with these situations. In Sect. 6, two particular profit measures are studied. In Sect. 7we analyze the mathematical structure of the family of profit measures for communication situations with incompatibilities. Finally, in Sect. 8some conclusions are drawn. 2 Preliminaries 2.1 Posets and convex sets A partially ordered set (poset)isapair(X,≤)where Xis a set and ≤is a partial order relation on X. When there is no ambiguity we will write Xinstead (X,≤).LetXbe a poset. If x,y∈Xand x≤ywe denote [x,y]X={z∈X:x≤z≤y}. The poset Xis said to have a bottom if there exist ⊥∈Xsuch that ⊥≤xfor every x∈X.AndXis said to have atop if there exists ∈Xsuch that x≤for every x∈X.Wewritex≥yas equivalent to y≤xand x<yto mean that x≤yand x= y.Ifx>yand there is no z∈Xsuch that x>z>ywe will say that x covers y (or yis covered by x), and it will be denoted xy. If Y⊂Xthen we can consider Yas a poset with the inherited order (the restriction of ≤to Y). If A⊆X,theny∈Xis an upper bound (resp. lower bound) of Aif x≤y(x≥y) for every x∈A.Givenx,y∈X, if the set of upper bounds (resp. lower bounds) of {x,y} is nonempty and has a bottom (resp. a top) then such element is called the supremum (resp. infimum)ofx,yand it is denoted by x∨y(resp. x∧y). The poset Xis said to be a lattice if for every x,y∈Xthere exist x∨yand x∧y.IfXis a finite lattice then Xhas a top and a bottom. Let Xbe a real vector space. For each x,y∈Xthe segment between xand yis the set xyX={tx +(1−t)y:t∈[0,1]}.IfY⊆X,thenYis convex if xyX⊆Yfor every x,y∈Y.IfXis a poset, we say that ≤is compatible with the vector space structure if the following two properties are satisfied: a) x≤yimplies x+z≤y+z,foreveryx,y,z∈X, and b) x≤yimplies λx≤λy,foreveryx,y∈Xand every λ≥0. If ≤is compatible with the vector space structure we say that Xis a partially ordered vector space. If Xis a partially ordered vector space, x,y∈Xand x≤ythen xyX⊆[x,y]X. For further information on the aspects of posets see Stanley (1986). 2.2 Partitions and graphs Let Nbe a finite set. We denote by 2Nthe family of all the subsets of N. The set of partitions of Nis N=P⊂2N\{∅}:  U∈P U=Nand U∩W=∅∀U,W∈P,U= W. 123 Annals of Operations Research (2024) 340:757–784 761 If P,P∈Nwe say that Pis finer than Pif for every U∈Pthere exists U∈Psuch that U⊆U. This finer-than relation is a partial order and it will be denoted by ≤. The poset (N,≤)is a lattice. Consider the set LN={ij :i,j∈Nand i= j},whereij denotes the unordered pair {i,j}.A(simple)graph on Nis a pair g=(V,L)where V⊆N,L⊆LNand i,j∈V for every ij ∈L.ThesetV(resp. L) is called the vertex set (resp. edge set) of g.We denote by GNthe family of graphs on Nendowed with the following partial order relation: if g=(V,L),g=( V, L)∈GNthen g≤gif and only if V⊆ Vand L⊆ L. It is easy to check that GNis a lattice. Notice that if V= Vthen ggif and only if, L⊃ Land g has exactly one more edge that g.Letg=(V,L)∈GN.IfV=∅then also L=∅and the graph is called the null graph, which is the bottom of GNand is denoted by g0.Graphgis connected if for every i,j∈Vwith i= jthere exist {i1,...,im}such that i1=i,im=j and ik−1ik∈Lfor every k=2,...,m;gis complete if L=LV;andgis independent if L=∅.If|V|=1thengis connected, complete and independent. The graph g0is considered to be neither connected nor complete nor independent. If T⊆Nthe subgraph induced in gby Tis gT=(V∩T,L∩LT).AsetT⊆Vis said to be connected (resp. complete) (resp. independent)ingif gTis connected (resp. complete) (resp. independent). A maximal connected set T⊆Vis called a connected component of g. The family of connected components of gis denoted by N/g. It is clear that N/g∈V.Thecomplement of gis g∗=(V,LV\L)∈GN.Ifij ∈Lwe will denote g−ij =(V,L\{ij}). More information on graphs, that have been briefly described above, in Graphs (2005). 2.3 Cooperative games Let Nbe a finite set of agents (hereinafter called players) that cooperate to achieve a joint profit. One problem that arises is how to distribute this profit among the players. Each payoff vector x ∈RNrepresentsaprofitdistributionproposal.Ifi∈N,thenxiisthepayoffassigned to player i(according to x). In order to obtain reasonable payoff vectors, cooperative games were introduced. A cooperative game (with transferable utility) on Nis given by a mapping v:2N→R,calledcharacteristicfunction,thatsatisfiesv(∅)=0.Foreach subset (coalition) of players S⊆N, the number v(S)is the profit that the players in Scould jointly achieve when they cooperate. In a cooperative game it is assumed that eventually all players (the grand coalition) will cooperate and, therefore, the amount to be distributed is equal to v(N). Agamevis superadditive if v(S∪T)≥v(S)+v(T)for every S,T⊆Nwith S∩T=∅. If a game models a profit-sharing situation usually it is a superadditive game. In the present paper we will consider only superadditive games. The Shapley value (Shapley, 1953)isa mapping that assigns to each game vthe payoff vector φv∈RNdefined by φv i= {S⊆N:i∈S} γ|N| |S|[v(S)−v(S\{i})]for every i∈N,(1) where γn s=(s−1)!(n−s)! n!. The Shapley value satisfies the following properties: S1) efficiency, it provides a distribution of the total joint profit, that is, i∈Nφv i=v(N);S2)linearity,if a,b∈Rand v,w are games on Nthen φav+bw=aφv+bφw;S3)null player,ifi∈Nis a null player in a game v,thatis,v(S∪{i})=v(S)for every S⊆N\{i},thenφv i=0; and S4) symmetry,ifi,j∈Nare symmetric players in v,thatis,v(S∪{i})=v(S∪{j})for every S⊆N\{i,j},thenφv i=φv j. Moreover, the Shapley value is the unique allocation rule satisfying these properties. If T∈2N\{∅},theunanimity game uTis defined by uT(S)=1 123 762 Annals of Operations Research (2024) 340:757–784 if T⊆Sand uT(S)=0 otherwise. The Shapley value of the unanimity game uTis given by φuT i=1 |T|if i∈Tand φuT i=0ifi∈N\T. An excellent reference on cooperative games is Curiel (1997). 3 Communication versus incompatibility In this section, we review the models for graph-restricted games introduced by Myerson (1977) and Bergantiños et al. (1993). In both models, for a given game, the characteristic function is modified taking into account the interpretation of the bilateral relationships described by a graph. In order to view both models within the same framework, we will draw inspiration from the concept of network game, introduced by Jackson (2005) in 2005. A network game is a characteristic function defined on the family of subgraphs of a complete graph. The motivations, both economic and social, for studying these games are explained in Jackson (2008). Now, considering a classic cooperative game and choosing either the Myerson or the Bergantiños model can be seen as embedding the game in different ways into the family of network games. The different ways of embedding classic games as network games will be referred to as profit measures. Characterizing those models within this common context will allow us, in the next section, to provide models for games with both communication restrictions and incompatibilities. 3.1 Communication Let vbe a fixed superadditive cooperative game1on a set of players N. The amount to be distributed is v(N)and the Shapley value φvis a payoff vector for v. Myerson (1977) introduced games with communication situations, in which there are restrictions on communication between players. He represented a communication situation through a graph g=(V,L)∈GNwhere Vis the set of active players2and where ij ∈Lif and only if players iand jcan communicate directly with each other. An allocation rule for communication situations with underlying game vis a mapping ψ:GN→RNthat assigns a payoff vector (ψi(g))i∈Nto each communication situation g∈GN. Myerson proposed a method to obtain allocation rules for communication situations. In general terms, this method consists of, firstly, defining a new game (the graph-restricted game) that indicates the profit that each coalition can obtain if the communication restrictions are taken into account, and, secondly, applying a classical allocation rule to this new game. In order to obtain the graphrestricted game, it is necessary to identify the feasible coalitions, that is, the coalitions in which all the members can cooperate with each other, thus achieving the same profit that they would obtain without communication restrictions. These communication feasible coalitions will be the connected coalitions. Therefore, in order to evaluate the graph-restricted game at a coalition S, we will find the connected coalitions of gS. In fact, since we are assuming that 1The choice of a superadditive game is because it allows us to unify Myerson’s and Bergantiños’ models, since the former employs maximal partitions of feasible coalitions while the latter uses arbitrary partitions of feasible coalitions. 2Myerson considered only graphs with vertex set equal to N, but we will follow the approach in Jiménez- Losada et al. (2013) and consider any graph in GN. 123 Annals of Operations Research (2024) 340:757–784 763 the underlying game vis superadditive, it suffices to evaluate vat the connected components of gS. And all that remains is to add these values. Hence, given g∈GN, the graph-restricted game vC gis defined by vC g(S)= T∈N/gS v(T)(2) for every S⊆N.Thecommunication value or Myerson value is the allocation rule μC: GN→RNdefined by μC(g)=φvC g(3) for every g∈GN. The communication value satisfies: C1) component efficiency,the worth of each connected component of the graph is distributed among its members, that is, i∈TμC i(g)=v(T)for every T∈N/g;C2)inactive player,ifg=(V,L)and i∈N\V,thenμC i(g)=0; and C3) fairness, removing a link of the graph changes the payoffs of the players that form this link in the same amount, that is, if g=(V,L)and ij ∈L,thenμC i(g)−μC i(g−ij)=μC j(g)−μC j(g−ij). Moreover, the Myerson value is the unique allocation rule for communication situations satisfying these properties. In addition, the communication value satisfies C4) stability, two players always benefit from reaching a bilateral agreement (if the underlying game is superadditive, as we are assuming), that is, μC i(g)≥μC i(g−ij)for every ij ∈L. The definition of the Myerson value is based on a measure of the profit achievable for each coalition. It is possible to determine such profit measure by certain reasonable conditions. Definition 1 A profit measure for communication situations is any mapping r:GN→R that satisfies the following conditions: 1. If g=(V,L)∈GNis connected, then r(g)=v(V). 2. For every g∈GN,r(g)= T∈N/g r(gT) The following proposition states the obvious fact that there is a unique profit measure for communication situations. Proposition 1 There is a unique profit measure for communication situations and is given by rC(g)= T∈N/g v(T). Moreover, if g g, then rC(g)≥rC(g). Notice that rCallows to define the graph-restricted game, since vC g(S)=rC(gS). 3.2 Incompatibility Bergantiños et al. (1993) considered a different model of games with graph-restricted communication. They introduced cooperative games with incompatibilities. A situation with incompatibilities is given by a graph g=(V,L)∈GNwhere Vis the set of active players and where ij ∈Lif and only if iand jare incompatible player. The authors showed that their model is not dual to Myerson’s. Indeed, in this model a link between iand jmeans that 123 764 Annals of Operations Research (2024) 340:757–784 these two players cannot cooperate in any way, and, therefore, no coalition containing iand jcan be formed. In Myerson’s model, the fact that the link ij is not in the graph does not necessarily imply that iand jcannot cooperate, but just that iand jcannot communicate directly, and, consequently, the formation of a coalition containing iand jmight be possible, provided that all players in the coalition can communicate, directly or indirectly, with each other. An allocation rule for situations with incompatibilities with underlying game vis a mapping ψ:GN→RNthat assigns a payoff vector (ψi(g))i∈Nto each situation with incompatibilities g∈GN. In order to define an allocation rule for situations with incompatibilities, Bergantiños et al. followed an approach similar to that considered by Myerson to obtain allocation rules for communication situations. Firstly it is necessary to identify the compatibility feasible coalitions, that is, the coalitions which do not contain any pair of incompatible players. Notice that these are the independent coalitions. The goal is to calculate the profit that can be achieved by a coalition S, taking into account the incompatibility relations. Therefore, we must determine the partitions of Sinto independent coalitions. Since the underlying game is superadditive, it is enough to obtain the coarsest of such partitions. If we consider the family of partitions of Sinto independent coalitions, we will denote by Pg(S)the subset of partitions which are maximal in that family.3Notice that each partition in Pg(S)represents a possible organization of the players in Sto generate a profit. Reasonably, the players within the coalition will choose the most profitable of such organizations. This leads to define the graph-restricted game as vI g(S)=max P∈Pg(S) U∈P v(U)(4) for every S⊆N.Theincompatibility value is the allocation rule μI:GN→RNdefined by μI(g)=φvI g(5) for every g∈GN. The incompatibility value satisfies: I1) complement component efficiency, the players of each connected component of the complement graph will distribute among themselves the largest amount that they can generate, that is, if T∈N/g∗then i∈TμI i(g)=vI g(T);I2)inactive player,ifg=(V,L)and i∈N\Vthen μI i(g)=0; and I3) fairness,ifg=(V,L)and ij ∈L,thenμI i(g)−μI i(g−ij)=μI j(g)−μI j(g−ij),that is, removing a link of the graph changes the payoffs of the players that form this link in the same amount. Moreover, this allocation rule for situations with incompatibilities is the only one satisfying these properties. In addition, the incompatibility value satisfies stability,two players always benefit from becoming compatible (if the underlying game is superadditive, as we are assuming), that is, μI i(g)≤μI i(g−ij)for every ij ∈L. We introduce also the concept of profit measure for incompatibilities. Definition 2 A profit measure for situations with incompatibilities is any mapping over the graphs, r:GN→R, that satisfies the following conditions: 1. For every g=(V,L)∈GN,there exists a partition P∈Pg(V)such that r(g)=  U∈P v(U). 2. If g,g∈GNand gg,thenr(g)≤r(g). 3Bergantiños et al considered all the partitions into independent coalitions, since they did not restrict themselves to superadditive games. 123 Annals of Operations Research (2024) 340:757–784 765 Proposition 2 There is a unique profit measure for situations with incompatibilities and is given by rI(g)=max P∈Pg(V) U∈P v(U) for every g ∈GN\{g0}and r I(g0)=0. Moreover, r I(g)= T∈N/g∗ rI(gT)for every g ∈GN. Proof It is easy to check that rIis a profit measure for situations with incompatibilities. Obviously, rIsatisfies condition 1. In order to see that it satisfies condition 2, notice that any independent set in gis an independent set in g. It remains to prove the uniqueness. Let rbe a profit measure for situations with incompatibilities. Let g=(V,L)∈GN. By condition 1 there exists a partition P∈Pg(V)such that r(g)=U∈Pv(U). Then, r(g)= U∈P v(U)≤max P∈Pg(V) U∈P v(U)=rI(g). Now we will prove that r(g)⩾rI(g).LetP∈Pg(V)a partition for which the maximum in the definition of rI(g)is attained, that is, rI(g)= U∈P v(U).LetP={U1,U2,...Um}. Consider g=V,L,where L=L∪{ij ∈LV:{i,j}Ukfor all k=1,...,m}. It is clear that Pis the only element in Pg(V), since every independent set in gmust be contained in some Uk.Sinceris a profit measure for situations with incompatibilities, we have that r(g)= U∈ P v(U)=rI(g). Besides, successively applying the second condition in Definition 2we obtain that r(g)≥r(g). Therefore, we conclude that r(g)⩾rI(g). Notice that rIallows to define the graph-restricted game, since vI g(S)=rI(gS). 4 Communication situations with incompatibilities 4.1 Communication situations with incompatibilities as signed graphs Let Nbe a finite set of players. Henceforth, we consider a fixed superadditive game v.Inthis section, our goal is to present the concept of communication situation with incompatibilities among the players, and to study how the profit achievable by each coalition in vis modified by the situation. The model of communication by Myerson considers bilateral relations among the players with two options, communication or non-communication. The model of incompatibilities by Bergantiños et al. also considers two options: communication or incompatibility. Since noncommunication and incompatibility are not the same we propose communication situations with incompatibilities, thus considering three options for the bilateral relations among the players:communication, incompatibility or neither(non-communication). Following Skibski et al. (2022), we will describe a communication situation with incompatibilities by means of a signed graph (Zaslavsky, 1982) with two possible values on the edges: positive edges and negative ones. 123 772 Annals of Operations Research (2024) 340:757–784 Fig. 5 Communication situation with incompatibilities for Example 4  Proposition 7 The mapping r⊥:HN→Ris a profit measure on HN. Proof Let us prove that r⊥satisfies the properties stated in Definition 4: 1. If h=(V,L+,L−)∈HN Cand h+is connected, then Ph−(V)={V}and, consequently, r⊥(h)=v(V)=rC(h+). 2. If h=(V,L+,L−)∈HN I,thenL+=LV\L−. Therefore, if U⊆Vis feasible for h−then it is connected for h+and, consequently, it is ⊥−feasible. We conclude that Ph−=P⊥ h, which leads to r⊥(h)=rI(h−). 3. Let h=(V,L+,L−)∈HN. Notice that each ⊥−feasible set for his contained in one connected component of h+. It is clear that r⊥(h)=max P∈P⊥ h U∈P v(U)= T∈N/h+ max P∈P⊥ hT U∈P v(U)= T∈N/h+ r⊥(hT). 4. Let h=(V,L+,L−), h=( V, L+, L−)∈HNbe such that h h. Then, L+⊇ L+and L−⊆ L−. Therefore, every ⊥−feasible set for  his ⊥−feasible for h. It follows that r⊥( h)=max P∈P h⊥ U∈P v(U)≤max P∈P⊥ h U∈P v(U)=r⊥(h).  Example 4 Let N={1,2,3,4}.Considerthecommunicationsituationwithincompatibilities represented in Fig.5and the game v∈GNdefined as v(S)=|S|2if 3 ∈Sand v(S)=|S| otherwise. Let us calculate r⊥(h). Notice that P⊥ h= {{{1,3},{2,4}},{{1,2,4},{3}}}. Hence, r⊥(h)=max{v({1,3})+v({2,4}), v({1,2,4})+v({3})}=max{6,4}=6. Definition 11 We say that a profit measure r∈BHNsatisfies the positive connection property if for every h=(V,L+,L−)∈HNthere exists a partition P∈Vmade up of sets which are connected in h+and independent in h−such that r(h)= U∈P v(U). Theorem 8 The unique profit measure on HNthat satisfies the property of positive connection is r⊥. Furthermore, if r ∈BHN,thenr ⊥≤r. 123 Annals of Operations Research (2024) 340:757–784 773 Proof Firstly we will prove that r⊥≤rfor every r∈BHN.Letr∈BHNand h=(V,L+,L−)∈H(N).Let P∈P⊥ hbe such that r⊥(h)= U∈ P v(U). Consider  h=(V,L+\{ij:{i,j}Ufor every U∈ P},L−) By properties 4, 3 and 1 in Definition 4,weobtain r(h)≥r( h)= U∈ P r(hU)= U∈ P rC(h+ U)= U∈ P v(U)=r⊥(h). From the definition of r⊥,it is clear that it satisfies the property of positive connection. Let us see the uniqueness. Let r∈BHNbe such that rsatisfies the property of positive connection. Let h=(V,L+,L−)∈HN. There exists a partition  P∈Vmade up of sets which are connected in h+and independent in h−such that r(h)= U∈ P v(U).LetP∈P⊥ h be such that  P≤P. Then, r(h)= U∈ P v(U)≤ U∈P v(U)≤max P∈P⊥ h U∈P v(U)=r⊥(h). Therefore, r(h)≤r⊥(h). Since we know that r(h)≥r⊥(h), we conclude the uniqueness.  6.2 The profit measure r Definition 12 Let h∈HNand U⊆N. We will say that Uis top-feasible (we will write − feasible) for hif Uis contained in a connected component of h+and Uis independent in h−.WedenotebyP hthe family of maximal partitions of V(h)made up of −feasible sets for h.Wedefiner:HN→Ras r(h)=max P∈P h U∈P v(U), for every h∈HN. The following proposition shows that if we subsequently apply the concepts of graphrestricted game used in the model of Bergantiños et al. and then in Myerson’s model, the resulting game, denoted as (vI h−)C h+, is equal to vr h. Proposition 9 If h =(V,L+,L−)∈HN,thenr (h)=vI h−C h+(V)and vr h=vI h−C h+. Proof Firstly we will prove that r(h)≤vI h−C h+(V).Let P∈P hbe such that r(h)=  U∈ P v(U). Notice that Uis independent in h−for every U∈ P, and, therefore, v(U)= vI h−(U).Wehavethatr(h)= U∈ P vI h−(U). Observe that the coalitions in  Pare connected in h+. Therefore,  P≤N/h+.Wehavethat r(h)= U∈ P vI h−(U)≤ U∈N/h+ vI h−(U)=vI h−C h+(V). 123 774 Annals of Operations Research (2024) 340:757–784 Next we will show that r(h)≥vI h−C h+(V).Wehavethat vI h−C h+(V)= U∈N/h+ vI h−(U). For each U∈N/h+let PU∈Ph− U(U)be such that vI h−(U)= W∈PU v(W).Noticethat U∈N/h+PUis a partition of Vinto −feasible sets for h, but it is not necessarily maximal. Let P∈P hbe such that P≥U∈N/h+PU.Wehavethat r(h)≥ U∈P v(U)≥ U∈N/h+ W∈PU v(W)= U∈N/h+ vI h−(U)=vI h−C h+(V). Finally, if S⊆N,then vr h(S)=r(hS)=vI h−C h+(S).  Proposition 10 The mapping r:HN→Ris a profit measure on HN. Proof Let us prove that rsatisfies the properties stated in Definition 4. 1. If h=(V,L+,L−)∈HN Cand h+is connected, then r(h)=v(V)=rC(h+). 2. If h=(V,L+,L−)∈HN I,thenL+=LV\L−. Therefore, if U⊆Vis feasible for h−then it is connected for h+and, consequently, it is −feasible. We conclude that Ph−=P h, which leads to r(h)=rI(h−). 3. Let h=(V,L+,L−)∈HN.Wehavethat r(h)=vI h−C h+(V) = T∈N/h+ max P∈Ph− T U∈P v(U)= T∈N/h+ max P∈P hT U∈P v(U)= T∈N/h+ r(hT). 4. Let h=(V,L+,L−), h=( V, L+, L−)∈HNbe such that h h. Then, L+⊇ L+and L−⊆ L−. Therefore, every −feasible set for  his −feasible for h. It follows that r( h)=max P∈P h U∈P v(U)≤max P∈P h U∈P v(U)=r(h).  Example 5 Let uscalculater(h)using the signed graph h(Fig.5)andthegamevin Example 4.Wehavethat P h= {{{1,3},{2,4}},{{1,2,4},{3}},{{1,3,4},{2}},{{1,2},{3,4}}}. Therefore, r(h)=max{v({1,3})+v({2,4}), v({1,2,4})+v({3}), v({1,3,4})+v({2}), v({1,2})+v({3,4})} =max{6,4,10,4}=10. 123 Annals of Operations Research (2024) 340:757–784 775 Remark 2 Observethatifweuser⊥to measure the profit attainable by each coalition, we are assuming that if a player iin a coalition does not actively cooperate with some other players in the coalition, then iwill not facilitate the communication between those players either. On the contrary, when we use rwe assume that even if idoes not cooperate with some players in the coalition, it can facilitate the communication between them. Definition 13 Let h=(V,L+,L−)∈HN.Thecomplete hull of his the communication situation with incompatibilities  h=( V, L+, L−)∈HNdefined as  V=V,  L+= T∈N/h+ {ij:i,j∈T,ij /∈L−},  L−=L−. We will say that a profit measure r∈BHNsatisfies the completeness property if r(h)= r hfor every h∈HN. Theorem 11 The unique profit measure on HNthat satisfies the completeness property is r. Furthermore, if r ∈BHN,thenr≤r. Proof Let h∈HN. Notice that h−= h−and N/h+=N/ h+. By definition of r,this implies that r(h)=r h. Therefore, rsatisfies the completeness property. Let us prove that r≤rfor every r∈BHN.Letr∈BHNand h∈HN.By properties 4, 3 and 2 in Definition 4, r(h)≤r h= T∈N/ h+ r hT= T∈N/ h+ rI h− T= T∈N/ h+ r hT=r h=r(h). Furthermore, if rsatisfies completeness then r(h)=r h,and the equalities above would lead to r(h)=r(h). Consequently, ris the unique profit measure on HNthat satisfies the completeness property.  7 The structure of BHN In this section we will study structural properties of BHN.WedenotebyFHNthe family of functions r:HN→R.NoticethatFHNis a vector space with the usual operations of addition and scalar multiplication. If we also consider the usual relation ≤, then FHNis an ordered vector space. In fact, it is a lattice, in which the infimum and the supremum of r,r∈FHNare given, respectively, by (r∧r)(h)=min{r(h),r(h)}, (r∨r)(h)=max{r(h),r(h)}for every h∈HN. Evidently, BHN⊆FHN. We will study the structure of BHNwithin the ordered vector space FHN. Remark 3 In the previous section we have seen that: •BHN=∅. •If r∈BHN,then r⊥≤r≤r,thatis,BHN⊆[r⊥,r]F(HN). The following example shows that the inclusion above is strict, that is, BHN [r⊥,r]F(HN). 123 776 Annals of Operations Research (2024) 340:757–784 Fig. 6 Structure in Example 6 Example 6 Consider r∈FHNdefined as r(h)=r⊥(h), if V=N, r(h), if V= N, for each h=(V,L+,L−). It is clear that r∈[r⊥,r]F(HN). Now suppose that N= {1,2,3,4,5}and v=u{1,3,4}.Letusseethatr/∈BHN, since it does not satisfy property 3 in Definition 4. Take the situation h∈HNrepresented in Fig.6. We have that N/h+={T1={1,2,3,4},T2={5}}.SinceV(h)=N, it follows that r(h)=r⊥(h)=0. Finally, notice that r(hT1)=r(hT1)=1andr(hT2)=r(hT2)=0. Therefore, r(h)= r(hT1)+r(hT2). Theorem 12 The family BHNis convex in FHN. In particular, r⊥rFHN⊆BHN. Proof Let r1,r2∈BHNand α∈[0,1]. We aim to prove that r=(1−α)r1+αr2∈ BHN. 1. If h=(V,L+,L−)∈HN Cand h+is connected, then r(h)=(1−α)r1(h)+αr2(h)=(1−α)rC(h+)+αrC(h+)=rC(h+). 2. If h=(V,L+,L−)∈HN I,then r(h)=(1−α)r1(h)+αr2(h)=(1−α)rI(h−)+αrI(h−)=rI(h−). 3. If h∈HN,then r(h)=(1−α)r1(h)+αr2(h)=(1−α) T∈N/h+ r1(hT)+α T∈N/h+ r2(hT)= T∈N/h+ r(hT). 4. Let h, h∈HNbe such that h h. Then, r(h)=(1−α)r1(h)+αr2(h)≥(1−α)r1( h)+αr2( h)=r( h). We conclude that r∈B(HN). Remark 4 In the previous section we showed that, unlike r⊥, the profit measure rallows a player to facilitate communication between other players with whom it is not actively cooperating. Observe that the profit measure rα=(1−α)r⊥+αr∈r⊥rFHN can be used when we aim to follow an intermediate approach. The following example shows that the inclusion stated in the previous theorem is strict, that is, r⊥rFHNBHN. 123 Annals of Operations Research (2024) 340:757–784 777 Example 7 Consider the mapping r:HN→Rdefined as r(h)=r(h), if V=Nand h+is connected r⊥(h), otherwise, for every h=(V,L+,L−)∈HN. Firstly we will prove that r∈BHN. Let us check that rsatisfies the properties in Definition 4. 1. If h∈HN Cand h+is connected, then r(h)=r⊥(h)=r(h)=rC(h+). 2. If h∈HN I,thenr(h)=r⊥(h)=r(h)=rI(h−). 3. Let h∈HN.Ifh+is connected then there is nothing to prove. If h+is not connected, then r(h)=r⊥(h)and r(hT)=r⊥(hT)for every T∈N/h+. It suffices to use that r⊥ satisfies property 3. 4. Let h, h∈HNbe such that h h. In particular, V(h)=V( h). We consider the following cases: •If V(h)= N,thenr(h)=r⊥(h)≥r⊥( h)=r⊥( h). •If V(h)=Nand  h+is connected. Then, h+is also connected and r(h)=r(h)≥ r( h)=r( h). •If V(h)=Nand h+is not connected. Then,  h+is also not connected and r(h)= r⊥(h)≥r⊥( h)=r( h). •If V(h)=N,h+is connected and  h+is not connected, then r(h)=r(h)≥ r⊥(h)≥r⊥( h)=r( h). Let us prove that, in general, r/∈r⊥rFHN.TakeN={1,2,3,4,5}and v=u{1,3,4}. Let h, h∈HNbe the situations represented in Figs.2and 5, respectively. Suppose that r∈r⊥rFHN. Then, there would exist α∈[0,1]such that r=(1−α)r⊥+αr. Notice that r(h)=r(h)=1andr⊥(h)=0. Therefore, it should be α=1. But observe that r( h)=r⊥( h)=0andr( h)=1. Consequently, it should be α=0. We conclude that r/∈r⊥rFHN. TheposetBHN,≤isnotalatticewiththeoperations∧and∨inheritedfromFHN, since BHNis not closed under these operations, as we will show in the following example. Example 8 Let E={1,2,3,4},F={5,6,7,8}and N=E∪F. Consider the game vE=u{134}on E.Letr⊥ E,r E∈BHEbe the bottom and the top measures, respectively, for the game vE. Now consider the game vF=u{6}+u{5,7,8}on F.Letr⊥ F,r F∈BHF be the bottom and the top measures, respectively, for the game vF. Consider the game von Ndefined as v(S)=vE(S∩E)+vF(S∩F), for every S⊆N.Letr⊥,r∈BHNbe the bottom and the top measures, respectively, for the game v.Letr,r∈BHNbe measures for the game vdefined as r(h)=r⊥ E(hE)+r F(hF), if h∈H, r(h), if h∈HN\H,andr(h)=r E(hE)+r⊥ F(hF), if h∈H, r(h)if h∈HN\H, where H={h=V,L+,L−∈HN:ij /∈L+for every (i,j)∈E×F}. Notice that if h∈Hthen N/h+=N/hB E∪N/hB F. Let us check that r,r∈BHN. 123 778 Annals of Operations Research (2024) 340:757–784 1. Let h=V,L+,L−∈HNbe such that h+is connected and L−=∅. It is clear that h/∈H, whence r(h)=r(h)=rC(h+). 2. Let h=(V,L+,L−)∈HN I.Ifh/∈H,thenr(h)=r(h)=rI(h−).Ifh∈H,then hB E=hR E∗and hB F=hR F∗. From this fact and property 2 in Definition 4, it follows that r(h)=r⊥ E(hE)+r F(hF)=rI(hR E)+rI(hR F)=rI(h−). 3. Let h∈HN. We consider two cases: •If h/∈H,thenr(h)=r(h). Furthermore,  T∈N/h+ r(hT)= {T∈N/h+:T⊂E} r(hT)+ {T∈N/h+:T⊂F} r(hT) + {T∈N/h+:T∩F=∅,T∩E=∅} r(hT) = {T∈N/h+:TE} (r⊥ E(hT)+r F(∅)) + {T∈N/h+:TF} (r⊥ E(∅)+r F(hT)) + {T∈N/h+:T∩F=∅,T∩E=∅} r(hT) = T∈N/h+ r(hT)=r(h)=r(h). where we have used the fact that for all communication situations with incompatibilities with cardinality of vertices less or equal than 3 both rand r⊥coincide. •If h∈H,thenr(h)=r⊥ E(hE)+r F(hF). Moreover, since N/h+=N/hB E∪N/hB F we have that  T∈N/h+ r(hT)= T∈E/hB E r(hT)+ T∈F/hB F r(hT)= T∈E/hB E r⊥ E(hT)+ T∈F/hB F r F(hT) =r⊥ E(hE)+r F(hF)=r(h). 4. Let h=(V,L+,L−), h=(V, L+, L−)∈HN,be such that h h. Let us consider the following cases: •If h, h/∈H,thenr(h)=r(h)≥r( h)=r( h). •If h, h∈H,then r(h)=r⊥ E(hE)+r F(hF)≥r⊥ E( hE)+r F( hF)=r( h). •If h/∈H, h∈H,then r( h)=r⊥ E( hE)+r F( hF)≤r E( hE)+r F( hF)=r( h)≤r(h)=r(h). Inasimilarwayitcanbeprovedthatr∈BHN.Neverthelessr∧risnotaprofitmeasure6 on HN. It suffices to take the communication situation with incompatibilities h∈Hsuch 6Simply by exchanging and ⊥in the definitions of r,rit can be proved that BHNis also not closed under the operation ∨. 123 Annals of Operations Research (2024) 340:757–784 779 Fig. 7 Zones Eand Fin h that hE=(E,{12,13,24},{23}),and hF=(F,{56,57,68},{67}). The situation his represented in Fig. 7. Let us show that property 3 in Definition 4is not satisfied. On the one hand, (r∧r)(h)=r(h)∧r(h)=r⊥ E(hE)+r F(hF)∧r E(hE)+r⊥ F(hF)=2∧2=2. And, on the other hand,  T∈N/h+ (r∧r)(hT)=(r∧r)(hE)+(r∧r)(hF)=(0∧1)+(2∧1)=1. However BHN,≤is indeed a lattice. Next we will define two new operations and in BHNand we will prove that these operations return the supremum and the infimum, respectively, of any two measures in BHN. Definition 14 If r,r∈BHN,the profit measures rrand rrare defined as (rr)( h)= T∈N/h+ (r∨r)( hT), (rr)( h)= T∈N/h+ (r∧r)( hT), for every h∈HN. Theorem 13 The poset BHN,≤is a lattice in which the supremum and the infimum of any profit measures r,r∈BHNare equal to r r and r r, respectively. Proof Let r,r∈BHN. Firstly we will prove that rr≤r∧r.Ifh∈HN,then (rr)(h)= T∈N/h+ (r∧r)(hT)≤ T∈N/h+ r(hT)=r(h). In a similar way it can be proved that rr≤r. We conclude that rr≤r∧r. Let us see that BHNis closed under the operation .Letr,r∈BHN. 1. If h=(V,L+,L−)∈HN Cand h+is connected, then N/h+={V}and (rr)(h)= (r∧r)(h)=rC(h+). 123 780 Annals of Operations Research (2024) 340:757–784 2. If h∈HN I, then, by Proposition 2, (rr)(h)= T∈N/h+ (r∧r)(hT)= T∈N/(h−)∗ rI(h− T)=rI(h−). 3. If h∈HN, then, for each T∈N/h+, the graph h+ Tis connected, and, consequently, (rr)(hT)=(r∧r)(hT).So, (rr)(h)= T∈N/h+ (r∧r)(hT)= T∈N/h+ (rr)(hT). 4. Let h=(V,L+,L−), h=(V, L+, L−)∈HNbe such that h h. Notice that hT≥ hT for every T∈N/h+. •If N/h+=N/ h+,then (rr)(h)= T∈N/h+ (r∧r)(hT)≥ T∈N/ h+ (r∧r)( hT)=(rr)( h), wherewehaveusedthat(r∧r)(hT)≥(r∧r)( hT),sincerandrsatisfy property 4. •If N/h+= N/ h+then there exist ˆ T∈N/h+and T1,T2∈N/ h+such that N/ h+= ((N/h+)\{ ˆ T})∪{T1,T2}. Therefore, N/( hˆ T)+={T1,T2}.Inthiscasewehavethat (rr)(h)= T∈N/h+ (r∧r)(hT)≥ T∈N/h+ (r∧r)( hT) =(r∧r)( hˆ T)+ {T∈N/h+:T= ˆ T} (r∧r)( hT) ≥(rr)( hˆ T)+ {T∈N/ h+:T=T1,T2} (r∧r)( hT) =(r∧r)( hT1)+(r∧r)( hT2)+ {T∈N/ h+:T=T1,T2} (r∧r)( hT) = T∈N/ h+ (r∧r)( hT)=(rr)( h), wherewehaveusedthat(r∧r)(hT)≥(r∧r)( hT)and rr≤r∧r. From rr≤r∧rand rr∈BHNit follows that rris a lower bound of {r,r} in BHN. Let us check that it is the maximum lower bound. Let r∈BHNbe such that r≤rand r≤r. Then, for each h∈HN r(h)= T∈N/h+ r(hT)≤ T∈N/h+ (r∧r)( hT)=(rr)( h). In a similar way it can be proved that the supremum of randrexists and is equal to rr. 8 Conclusions In this paper we have dealt with a family of cooperative situations with restricted cooperation: communication situations with incompatibilities. Our goal was to find a model for such 123 Annals of Operations Research (2024) 340:757–784 781 Fig. 8 Allocation rules depending on α situations that extends Myerson’s model for communication situations and Bergantiños’ model for incompatibility relationships. The key concept we have used for this purpose is that of profit measure, which has allowed us to obtain, in fact, multiple models that meet our requirements for extension. Each one of the profit measures enables us to define a unique restricted game, which leads to a unique allocation rule. Although we have analyzed different profit measures for a fixed game, it is possible to apply any of these measures to any game. Next, by way of conclusion, we will show the versatility of the model introduced. In the following example we will use the measures r,r⊥and rαin the segment between them (see Remark 4) to obtain different payoff vectors for a cooperative game and a communication situation with incompatibilities. Consider N={1,2,3,4,5},thegame v=u{1,3,4}+u{2,4,5}and the communication situation with incompatibilities hrepresented in Fig.2. It is clear that r⊥(h)=r(h)=1. Therefore, for each value μrαthe quantity to be distributed is equal to 1. It is easy to check that if S⊆Nand S={1,2,3,4},then r⊥(hS)=r(hS). Finally, if S={1,2,3,4}then r⊥(hS)=0andr(hS)=1, which leads to vrα h({1,2,3,4})=α.Thegamevrα his equal to vrα h=u{2,4,5}+αu{1,2,3,4}−αuN. If we apply the Shapley value to vrα hwe obtain μrα(h)=α 20,1 3+α 20,α 20,1 3+α 20,1 3−α 5. The payoffs to each player in {1,2,3,4,5}, according to the allocation rule μrα(h),are represented in Fig.8. We can see that, as we increase the degree αof allowable communication between players who are not actively cooperating, the payoff to player 5 decreases and the payoffs to the other players increase. This is due to the fact that it decreases the need to incorporate player 5 to obtain profit. 123