Cooperation among agents with a proximity relation
Abstract
A cooperative game consists of a set of players and a characteristic function determining the maximal gain or minimal cost that every subset of players can achieve when they decide to cooperate, regardless of the actions that the other players take. The relationships of closeness among the players should modify the bargaining among them and therefore their payoffs. The first models that have studied this closeness used a priori unions or undirected graphs. In the a priori union model a partition of the big coalition is supposed. Each element of the partition represents a group of players with the same interests. The groups negotiate among them to form the grand coalition and later, inside each one, players bargain among them. Now we propose to use proximity relations to represent leveled closeness of the interests among the players and extending the a priori unions model.
Full text
Cooperation among agents with a proximity relation. J.R. Fern´andez, I. Gallego, A. Jim´enez-Losada and M. Ord´o˜nez Escuela T´ecnica Superior de Ingenier´ıa, Matem´atica Aplicada II, Universidad de Sevilla, Camino de los Descubrimientos, 41092 Sevilla, Spain Abstract A cooperative game consists of a set of players and a characteristic function determining the maximal gain or minimal cost that every subset of players can achieve when they decide to cooperate, regardless of the actions that the other players take. The relationships of closeness among the players should modify the bargaining among them and therefore their payo↵s. The first models that have studied this closeness used a priori unions or undirected graphs. In the a priori union model a partition of the big coalition is supposed. Each element of the partition represents a group of players with the same interests. The groups negotiate among them to form the grand coalition and later, inside each one, players bargain among them. Now we propose to use proximity relations to represent leveled closeness of the interests among the players and extending the a priori unions model. Keywords: cooperative game, fuzzy relations, proximity relations, Choquet integral, Shapley value, Owen value 1. Introduction Cooperative game theory studies situations where a set of agents (players) bargain for a fair allocation of a common profit resulting from their collaboration, namely a vector with the payo↵of each player as coordinates (a payo↵vector). In order to establish this allocation a number is known for each subset (coalition) of players representing the profit obtained by them and the mapping that assigns these numbers is named the characteristic function of the game. The Shapley value, Shapley (1953), is one of the point solutions for cooperative games mostly used and studied. It is a function obtaining a payo↵vector for each game based in a set of reasonable conditions (axioms) which allow us to decide whether this value is or not the best solution for the problem. Several variations of the Shapley value have been proposed for situations where some additional information about the agents is known. Aumann and Dreze (1974) introduced coalition structures. A coalition structure is a partition of the set of players representing the di↵erent coalitions obtained at the end of game. Hence there Email address: [email protected] (J.R. Fern´andez, I. Gallego, A. Jim´enez-Losada and M. Ord´o˜nez) Preprint submitted to European Journal of Operational Research September 5, 2015
should be no side payment between these final coalitions. This way has been improved by Myerson (1977) considering communication structures. A communication structure is a graph representing the bilateral cooperation possibilities among the agents. In this case the final coalition structure is the set of connected components in the graph but we can also use the information given by the graph about the internal structure of these coalitions. Owen (1977) proposed a di↵erent model from that of Aumann and Dreze based in a di↵erent interpretation of the coalition structures. He considered that the coalition structure is a partition of the set of players in a priori unions based in the relations among the agents. But these unions are not considered as a final structure but as a starting point for further negotiations. Thus, as in the original Shapley model, the grand coalition is the final coalition structure. This paper focuses on the Owen variation. So, a coalition of players forms a union if they have the same (or close) interests in the game. Owen obtained a Shapley-type solution (the Owen value) taking into account this information to get a fair allocation of the profit of the grand coalition. Later Casajus (2007) proposed a modification of the Owen model in the Myerson sense. That is, we have an a priori union structure and we know how these unions are formed by means of a connected graph in each group. This graph explains the relation of closeness existing among their players. But closeness is usually a leveled property. For instance, political groups can be organized in a priori ideological unions. Considering equal every ideological closeness between two political parties is actually a simplification of the situation. Aubin (1981), Butnariu (1980) and Mares (2001) introduced fuzzy sets to describe leveled participation of the players in the coalitions (fuzzy coalitions) or fuzziness in the worth of the coalitions given by the characteristic function (fuzzy payo↵s). The Choquet integral, Choquet (1953), is a powerful tool from the decision theory which is a way of measuring the expected utility of an uncertain event. Tsurumi et al. (2001) used the Choquet integral for fuzzy sets in order to define a Shapley-type solution of a family of games with fuzzy coalitions. Jim´enez-Losada et al. (2010), (2013), Gallego et al. (2014) and Gallardo et al. (2014) proposed to use fuzzy structures as an additional information for a cooperative game. Particularly, they considered a fuzzy graph to study fuzzy communication structures in the Myerson way. Meng et al. (2012) analyzed games on fuzzy coalitions with a priori unions. 2
Now, we propose a more realistic version of the Owen situation. Following Owen (1977) and Casajus (2007) we consider a fuzzy graph where the fuzzy set of links defines the objective bilateral closeness of interests among the players. This structure is actually a known fuzzy binary relation called proximity relation. This fuzzy relation also establishes unions among the agents but these are not disjoint and each union is represented by a communication structure, thus players are asymmetric in them. While Meng et al. (2012) considered fuzzy coalitions but common a priori unions, we will take usual games but leveled closeness. Preliminaries introduce the needed aspects from cooperative games, a priori unions, communication structures and fuzzy sets to understand the paper. Section 3 analyzes the value introduced by Casajus (2007) in a di↵erent way, obtaining an axiomatization comparable to the one of the Owen value. In section 4 we introduce several ways to reduce a proximity relation which are used later. Section 5 defines an Owen-type value for proximity situations, the prox-Owen value and finally in section 6 we propose an axiomatization of the new value with reasonable axioms in this context. 2. Preliminaries 2.1. Cooperative TU-games. Acooperative game with transferable utility,agamesincenow,isapair(N,v)whereN is a finite set of elements and v:2 N!Ris a mapping satisfying v(;)=0. Theelements of Nare named players, the subsets of Nare said coalitions and vis the characteristic function of the game. We denote as Gthe set of games. If (N,v)2Gand S✓Nthen (S, v)=(S, vS)2Gis a new game where vSis the restriction of the characteristic function v to 2S. An example of a game is the unanimity game (N,uT), with T✓Nand T6=;,defined as uT(S)=1ifT✓Sand uT(S)=0otherwise. IfwefixN, the family {uT:T✓N}is a basis of the games over N,thatisforevery(N,v)therearecoefficientscTsuch that v=X {T✓N:T6=;} cTuT.(1) An allocation rule is a function over Gwhich determines for each (N,v)avector (N,v)2RNinterpreted as a payo↵vector. The Shapley value is an allocation rule defined 3
for every (N,v)2Gand i2Nas i(N,v)= X {S⇢N:i/2S} (|N||S|1)!|S|! |N|![v(S[{i})v(S)].(2) This allocation rule satisfies efficiency, that is Pi2Ni(N,v)=v(N). The Shapley value is also linear namely if (N,v1),(N,v2)2Gand a, b 2Rthen (N, av1+bv2)=a(N,v1)+ b(N,v2).Anull player i2Nfor a game (N,v)satisfiesv(S[{i})=v(S)forallS✓ N\{i}. The Shapley value satisfies the null player axiom i.e. if iis a null player for (N,v) then i(N,v)=0. Itissaidthati, j 2Nare substitutable players in a game (N,v)if v(S[{i})=v(S[{j})forallS✓N\{i, j}.Theequal treatment axiom says that if i, j 2Nare substitutable players in (N,v)theni(N,v)=j(N,v). It is known that the Shapley value is the only allocation rule over Gsatisfying efficiency, linearity, null player and equal treatment. Moreover these axioms are not redundant. 2.2. A priori unions. Agame with a priori unions is a triple (N,v,P)where(N,v)2Gand P={N1,...,N m} is a partition of N.PlayersinNkfor each khave similar interests in the game and they use the union in the bargaining to get a fair payo↵. The set of games with a priori unions is denoted as GU. The Owen value !is an allocation rule over GU. It is supposed that players are interested in the grand coalition Nbut considering the a priori unions as bargaining elements. Let (N,v,P)2GU with P={N1, ...., N m}.Thequotient game (M,vP)withsetofplayers M={1,...,m}is defined as vP(Q)=v [ q2Q Nq!,8Q✓M. (3) Let k2M.ForeachS⇢Nkthe partition PSof N\(Nk\S)istoreplaceNkwith S.We define (Nk,v k)asvk(S)=kM,vPS,8S✓Nk.Finally we solve the game in every group using also the Shapley value. So, for each i2Nif k(i)issuchthati2Nk(i)then the Owen value is !i(N,v,P)=iNk(i),v k(i).(4) 4
The Owen value satisfies efficiency, linearity and null player (the same definitions in GU than in G). It also satisfies equal treatment in a union, namely if i, j 2Nkfor k2M are substitutable in (N,v)then!i(N,v,P)=!j(N,v,P). Moreover !satisfies a similar condition with the unions, the coalitional symmetry:ifk1,k 22Msatisfy that v(Nk1[ Sq2QNq)=v(Nk2[Sq2QNq)foreveryQ✓M\{k1,k 2}then X i2Nk1 !i(N,v,P)= X j2Nk2 !j(N,v,P). Owen (1977) showed that !is the only allocation rule over GU satisfying efficiency, linearity, null player, equal treatment in each union and coalitional symmetry. 1 2.3. Communication structures. Let LN ={{i, j}:i, j 2Nand i6=j}be the set of unordered pairs of elements in a finite set N.Wewilluseij ={i, j}from now on. A communication structure for Nis a graph (N,L)wherethesetofverticesisNand the set of edges L✓LN is the set of feasible communications among them. Hence we identify a communication structure for N with the set of links L.Agame with communication structure is a triple (N,v,L)where (N,v)2Gand Lis a communication structure for N. A cooperative game (N,v)canbe identified with the game with communication structure (N,v,LN). The family of games with communication structure is denoted as GC.Let(N,v,L)2GC be a game with communication structure. A coalition S✓Nwhose vertices are connected by the links in L is called connected. The maximal connected coalitions correspond to the sets of vertices of the connected components of the graph (N,L)andtheyaredenotedasN/L. This family N/L is actually a partition of N.IfS✓Nis a coalition then LS={ij 2L:i, j 2S} and (S, v, LS)2GC represents the restriction to Sof the game and the communication structure. We use S/L =S/LS. Following Myerson (1977), in a communication structure the final coalition structure is formed by the connected components of the graph, and they can not get beneficial collaborations among them. The Myerson value is an allocation rule for games with communication structure. Given 1Owen (1977) used symmetry in each union instead of equal treatment in each union, but both axioms are equivalent in a context with efficiency, linearity and null player. 5
(N,v,L)2GC Myerson defines a new game (N,v/L)2Gincorporating the information of the communication structure, v/L(S)= X T2S/L v(T)8S✓N. (5) The Myerson value is defined as µ(N,v,L)=(N,v/L).(6) The Myerson value is efficient by components, namely Pi2Sµi(N,v,L)=v(S)foreach S2N/L but it is not efficient. Moreover, this allocation rule satisfies decomposability in the sense that µi(N,v,L)=µi(S, v, LS)forallS2N/L and i2S. This value also satisfies the fairness axiom,i.e.foreachij 2Lwe have: µi(N,v,L)µi(N,v,L \{ij})=µj(N,v,L)µj(N,v,L \{ij}). The Myerson value is the only allocation rule satisfying efficiency by components and fairness. 2.4. Fuzzy sets and proximity relations. We will use _,^for the operators maximum and minimum in hereafter. Afuzzy set of a finite set Kis a function ⌧:K![0,1]. The support of ⌧is supp(⌧)= {i2K:⌧(i)6=0}. The image of ⌧is the ordered set im(⌧)={1<···< p}={2 (0,1] : 9i2K, ⌧(i)=}.Two fuzzy sets ⌧,⌧0are comonotone if for all i, j 2Kit holds (⌧(i)⌧(j))(⌧0(i)⌧0(j)) 0.Comonotony is a transitive property. For each t2(0,1] the t-cut of ⌧is [⌧]t={i2K:⌧(i)t}.(7) The Choquet integral was introduced by Choquet (1953) for capacities and it was extended for all the set functions in Schmeidler (1986) and De Waegenaere and Wakker (2001). Given f:2 K!Rand ⌧a fuzzy set over K, the (signed) Choquet integral of ⌧with respect to fis Z⌧df= p X k=1 (kk1)f([⌧]k),(8) 6
where im (⌧)={1<···< p}and 0= 0. The following properties of the Choquet integral are known: (C1) ReSdf =f(S), for all S✓K, and eS(i)=1ifi2Sand eS(i)=0otherwise. (C2) Rt⌧df =tR⌧df,forallt2[0,1] . (C3) R⌧d(a1f1+a2f2)=a1R⌧df 1+a2R⌧df 2,when a1,a 22R. (C4) R(⌧+⌧0)df =R⌧df+R⌧0df , when ⌧+⌧0eKand ⌧,⌧0are comonotone. (C5) R⌧df=AWi2N⌧(i)iff([⌧]t)=Afor all t2im(⌧). A bilateral fuzzy relation, see Mordeson and Nair (2000), over Kis a function ⇢:K⇥K! [0,1] satisfying the condition ⇢(i, j)⇢(i, i)^⇢(j, j).Aproximity relation over K,isafuzzy relation ⇢satisfying: (Reflexivity) ⇢(i, i)=1foralli2K, and (Symmetry) ⇢(i, j)=⇢(j, i) for all i, j 2K. Similarity relations are particular fuzzy versions of equivalence relations. A similarity relation over Kis a proximity relation ⇢satisfying besides: (Transitivity) ⇢(i, j) ⇢(i, k)^⇢(k,j)foralli, j, k 2K. 3. A priori unions with communication structure. In the Owen model players are organized in a priori unions but there is not information about the inner structure of these unions. Casajus (2007) proposed another allocation rule for games with communication structure following the sense of the Owen value that we name here the Myerson-Owen value. Given a game with communication structure (N,v,L)2GC we consider the partition of Nby its connected components N/L.ThereforeN/L is a set of a priori unions for the players in Nbut the links in Lestablish how these unions are formed. We use again the quotient game (3) with the partition N/L ={N1,...,N m}and now for all k2Mwith M={1,...,m}the game (Nk,v k), vk(S)=kM,v(N/L)S,8S✓Nk.(9) Definition 1. (Casajus (2007)) The Myerson-Owen value is an allocation rule over GC defined for each (N,v,L)with N/L ={N1,...,N m}and i2Nas ⇠i(N,v,L)=µi⇣Nk(i),v k(i),L Nk(i)⌘, 7
where k(i)is such that i2Nk(i). The Myerson-Owen value satisfies the following coincidences. (a) If (N,v,L)2GC satisfies that Nis connected by Lthen ⇠(N,v,L)=µ(N,v,L). (b) If (N,v,L)2GC satisfies that LS=LS for all S2N/L then we identify (N,v,L)with (N,v,N/L)2GU and ⇠(N,v,L)=!(N,v,N/L). (c) If (N,v,L)2GC with L=LN then ⇠(N,v,L)=(N,v). Casajus (2007) obtained an axiomatization of the Myerson-Owen value. Now we provide a new characterization of this value with the purpose of defining all the axioms from the data (the game and the graph) and obtaining a better comparison with the Owen value. Consider the following axioms for an allocation rule over GC. Linearity. For all games (N,v),(N,v0)2G,↵,2Rand L✓LN, (N,↵v+v0,L)=↵ (N,v,L)+ (N,v0,L). Efficiency. For all (N,v,L)2GC it holds X i2N i(N,v,L)=v(N). Observe that now a null player can obtain profit due to his position in the graph inside a component if this position is essential for other players to cooperate. But if all the players in the component are null then it is impossible to get profits despite the strategic position inside the union of each player. A coalition S✓Nis a null coalition in (N,v)2Gif each i2Sis a null player for (N,v). Null component. Let (N,v,L)2GC and let S2N/L be a null coalition. Then i(N,v,L)=0for all i2S. 8
Two coalitions S, T ✓Nwith S\T=;are substitutable2in a game (N,v)ifv(R[S)= v(R[T)forallR✓N\(S[T). We can suppose that two substitutable components obtain the same total payo↵in the sense of the coalitional symmetry (section 2.2) because the internal structure in each union is independent of the bargaining among them. Substitutable components. Let (N,v,L)2GC.IfS, T 2N/L are substitutable in (N,v) then X i2S i(N,v,L)=X j2T j(N,v,L). Now the equal treatment property for players depends on the structure in each component because they are asymmetric. The Myerson fairness axiom can not be used to explain this asymmetry because the deletion of a link can cause a change in the number of components (unions) and then in the bargaining among them. So, we use the modified fairness proposed by Casajus (2007). This axiom can be seen as a balance among unilateral disconnection threats. The di↵erence of payo↵s for breaking up unilaterally a link, placing the players disconnected by this fact out of the game, is the same for both players in the link. Let (N,v,L)2GC and ij 2L.IfS2N/L with i, j 2Sand Si2N/(L\{ij})withi2Si(in the same way Sj)thenNi ij =(N\S)[Si(in the same way Nj ij). Modified fairness. Let (N,v,L)2GC and ij 2L, it holds i(N,v,L) i⇣Ni ij,v,L Ni ij \{ij}⌘= j(N,v,⇢) j⇣Nj ij,v,L Nj ij \{ij}⌘. We prove in the next theorem that the Myerson-Owen value is the only one satisfying all these axioms3. Theorem 1. The Myerson-Owen value is the only allocation rule for games with communication structure satisfying the following axioms: efficiency, linearity, null component, substitutable components and modified fairness. 2The concept of substitutable coalitions is slightly di↵erent to the concept given in Owen (1977). Our concept implies the other but it is independent of the unions. 3Casajus (2007) proved that the Myerson-Owen value satisfies efficiency and modified fairness but we replicate the proofs because they are used in the remark just after the theorem. 9
Proof. We prove that ⇢b a,⇢are comonotone as fuzzy sets over LN.Letij, kl 2LN.We suppose without loss of generality ⇢(i, j)⇢(k,l). If ⇢(i, j)bthen ⇢b a(i, j)=1⇢b a(k,l). If ⇢(k,l)athen ⇢b a(k,l)=0⇢b a(i, j). Otherwise, a<⇢(k,l)⇢(i, j)band we get: ⇢(i, j)a ba⇢(k,l)a ba.2 The above proposition implies the next result for the Choquet integral. Proposition 4. Let ⇢be a proximity relation over Nand a1,...,a r2[0,1] with a1<···<a r. It holds for all f:2 LN !Rthat Z⇢df = r+1 X p=1 (apap1)Z⇢ap ap1df , with a0=0and ar+1 =1. Proof. Suppose ⇢a proximity relation and consider numbers a1<··· <a rin [0,1], a0=0 and ar+1 = 1. Remember that comonotony is a transitive property. Hence, as (apap1)0 for every p2{1,...,r+1}, Proposition 2 implies that (apap1)⇢ap ap1and (aqaq1)⇢aq aq1 are comonotone for all p, q 2{1,...,r+1}. We also prove that ⇢= r+1 X p=1 (apap1)⇢ap ap1. Let ij 2LN.Wesuppose⇢(i, j)6= 0 because otherwise ⇢ap ap1(i, j)=0forallp.Inthatcase there exists q2{1,...,r+1}with ⇢(i, j)2(aq1,a q]. For each p<qwe have ⇢ap ap1(i, j)=1 and for each p>qwe get ⇢ap ap1(i, j)=0. Ifp=q, ⇢aq aq1(i, j)=⇢(i, j)aq1 aqaq1 . So, we obtain r+1 X p=1 (apap1)⇢ap ap1(i, j)= q1 X p=1 (apap1)+(⇢(i, j)aq1)=⇢(i, j). 16
Finally we use properties (C4) and (C2) of the Choquet integral to get for any f Z⇢df =Zr+1 X p=1 (apap1)⇢ap ap1df = r+1 X p=1 (apap1)Z⇢ap ap1df . 2 Now we define a scaling of a proximity relation where the insignificant levels are those within the interval. Definition 4. Let ⇢be a proximity relation over N. Let a, b 2[0,1] with a<band a6=0 or b6=1. The dual interval scaling of ⇢is a new proximity relation over Ngiven by ⇢b a(i, j)=8 > > > > > < > > > > > : ⇢(i, j)+ab 1+ab,if ⇢(i, j)b a 1+ab,if ⇢(i, j)2(a, b) ⇢(i, j) 1+ab,if ⇢(i, j)a. Remark. If a=0andb= 1 then the dual interval scaling is not well defined. As we will see later this case appears in our results without real influence, but in some step of the proof of Theorem 7 we need it. So, we define ⇢1 0(i, j)=8 < : 1,if ⇢(i, j)=1 0,otherwise. This definition is motivated by the next reasoning: if a=0andb2(0,1) then ⇢b 0(i, j)= ⇢(i,j)b 1bif ⇢(i, j)band ⇢b 0(i, j) = 0 otherwise. We can see our definition as the limit of this option when btends to 15. Observe that it also holds |im(⇢b a)||im(⇢)|. Next result about the Choquet integral is obtained from Proposition 4. Proposition 5. Let ⇢be a proximity relation over N. For every pair of numbers a, b 2[0,1] 5There exists another di↵erent option to define the dual interval scaling ⇢1 0. If we study what happens when (a, b) tends to (0,1) the limit does not exist, and actually we can take any proximity relation as ⇢1 0(i, j)=1if⇢(i, j) = 1, ⇢1 0(i, j)=Kif ⇢(i, j)2(a, b) and ⇢1 0(i, j)=0if⇢(i, j) = 0. 17
with a<band for every set function f:2 LN !Rit holds Z⇢df =(ba)Z⇢b adf +(1+ab)Z⇢b adf . Proof. Consider ⇢a proximity relation and numbers a, b 2[0,1] with a<b.Ifa=0and b= 1 we have a trivial equality. Otherwise, Proposition 4 says Z⇢df =aZ⇢a 0df +(ba)Z⇢b adf +(1b)Z⇢1 bdf . Since comonotony is a transitive property we get that a⇢a 0,(1 b)⇢1 bare comonotone using Proposition 3. Therefore (C2) and (C4) imply Z⇢df =(ba)Z⇢b adf +Z⇥a⇢a 0+(1b)⇢1 b⇤df . Now we prove the next equality of fuzzy sets (1+ab)⇢b a=a⇢a 0+(1b)⇢1 b.Suppose i, j 2N. If ⇢(i, j)athen a⇢a 0(i, j)+(1b)⇢1 b(i, j)=a⇢(i, j) a=⇢(i, j). If ⇢(i, j)bthen a⇢a 0(i, j)+(1b)⇢1 b(i, j)=a+(1b)⇢(i, j)b 1b=⇢(i, j)+ab. Finally, if ⇢(i, j)2(a, b)thena⇢a 0(i, j)+(1b)⇢1 b(i, j)=a. We finish the proof using (C2) again. 2 5. Games with a proximity relation among the players. Owen (1977) considered that the players in a game are organized in a priori unions (see section 2.2) depending on their common interests. Now we suppose that it is possible to measure the closeness of the ideas of the players. In this order we are going to think of a proximity function describing the closeness among them. Let (N,v)2G.If⇢is a proximity relation over Nthen ⇢(i, j)representstheclosenesslevelbetweenplayersi, j 2N. Definition 5. A game with a proximity relation among the players is a triple (N,v,⇢)such 18
that (N,v)2Gis a game and ⇢is a proximity relation over N. The set of the games with a proximity relation among the players is denoted as GP. If we take a crisp proximity relation then we obtain a game over a communication structure in the sense of Casajus (2007), namely it is a set of a priori unions with a communication structure in each union. Particularly, if we consider a similarity relation, transitivity means here that if the measure of the facets of closeness between players i, k is ⇢(i, k) and the one between players k,j is ⇢(k,j)theni, j can assume at least (in the worst case) ⇢(i, k)^⇢(k,j) level of closeness. Games with crisp similarity relations are games with a priori unions. Next we see an example of a game with a proximity relation that is not any of these particular cases. Example. Suppose a set of five agents interested in making use of a land. They decide to cooperate getting the maximum feasible profit. Players 1,2 are relatives, players 2,3 are owners, players 1,4,5 are workers, 1,2,5 have been working together for a long time, and 1,5 are beer friends. The characteristic function in millions of euros is: v(S)=10(|S|1) if 22Sbut 3 /2S,v(S)=16(|S|1) if 3 2Sbut 2 /2S,v(S)=48(|S|2) if 2,32S, and v(S) = 0 otherwise. We can define the relationship among the players as the following proximity relation considering all the relations with same importance: ⇢(i, i)=1forall i,⇢(1,5) = 0.6, ⇢(1,2) = 0.4, ⇢(1,4) = ⇢(2,3) = ⇢(2,5) = ⇢(4,5) = 0.2and⇢(i, j)=0 otherwise. We represent the situation by a fuzzy graph, a graph with weighted edges. Figure 1. Proximity relation. Jim´enez-Losada et al. (2010) introduced games on fuzzy communication structures using fuzzy graphs. In Jim´enez-Losada et al. (2013) we proposed several Myerson values for these situations. Obviously a proximity relation is a particular kind of fuzzy graph, but our 19
interpretation is di↵erent from the fuzzy communication structures. Now we extend the Owen model in a fuzzy way. We can see a proximity relation as a communication structure by levels of the players. Let (N,v,⇢)2GP.Foreacht2(0,1] we suppose that a set of players form an a priori union with communication structure if they are connected at least at level tand this set is maximal. Example. Next figure shows the di↵erent groups formed at each level t2(0,1] in the above example. Every group has a specific communication structure which determines how the union is formed. The reader can see for instance that if our demand to form a group is to connect them with level at least t=0.3 then {1,2,5}is a union. But in this group the position of player 1 is not the same as in the others. Figure 2. Communication structure partition. Let ⇢be a proximity relation over N.Wedefinethesetfunctionforeveryplayeri2N given as ⇠i(N,v)(L)=⇠i(N,v,L)8L✓LN, (10) where ⇠is the Myerson-Owen value (Definition 1). Now we introduce the solution proposed in the paper for games with a proximity relation among the players. Definition 6. The prox-Owen value is the allocation rule over the games with a proximity 20
relation among the players defined for all (N,v,⇢)2GP and i2Nas ⌘i(N,v,⇢)=Z⇢d⇠i(N,v). Remark. Using the expression of the Choquet integral (11) we get the following equality. If im(⇢)={1<···< m}and 0=0then ⌘(N,v,⇢)= m X k=1 (kk1)⇠(N,v,[⇢]k).(11) This formula shows the prox-Owen value as a sequence of Myerson-Owen values of the corresponding cuts by closeness intervals. Example. Suppose the game of our example in Figure 1. Depending on the assumed information we obtain the following solutions. If we omit the relationships among the players the Shapley value is (N,v)=(20.333,37,46,20.333,20.333). If we consider only the communication structure Lin Figure 1 without the numbers on the links we apply the Myerson-Owen value of the game (which coincides with the Myerson value because the graph is connected), ⇠(N,v,L)=(20.4,50.9,36.733,15.566,20.4). Finally we calculate the prox-Owen value. We have to consider the di↵erent graphs in Figure 2 to determine the Choquet integral. So, for each player i2N={1,2,3,4,5} ⌘(N,v,⇢)=(0.20)⇠(N,v)([⇢]0.2)+(0.40.2)⇠(N,v)([⇢]0.4) +(0.60.4)⇠(N,v)([⇢]0.6)+(10.6)⇠(N,v)([⇢]1) =(21.38,38.346,45.613,19.38,19.28). In a communication structure L✓LN the set of coalitions which determines the a priori unions among the players are the connected components, the family N/L.Inaproximity relation this role is played by the groups as we define now. Definition 7. Let ⇢be a proximity relation over N. A coalition S✓Nis a t-group for ⇢ with t2(0,1] if S2N/[⇢]t. The family of groups of ⇢is the set N/⇢=St2(0,1] N/[⇢]t. A group in a proximity relation is a coalition which can be considered as an a priori union 21
with communication structure when we establish a minimum relation level. If ⇢is a crisp proximity relation (a communication structure) then S2N/⇢if and only if Sis a connected component in the graph. Definition 8. Let ⇢be a proximity relation over N. Coalitions S1,...,S r✓Nare leveled groups if there is a number t2(0,1] such that S1,...,S rare t-groups. For each set of leveled groups S1,...,S r(r1) we denote tS1...Sr=^{t2(0,1] : S1,...,S r2N/[⇢]t}(12) tS1...Sr=_{t2(0,1] : S1,...,S r2N/[⇢]t}.(13) Observe that number tS1...Sris a maximum but number tS1...Sris an infimum. Moreover 0tS1...Sr<t S1...Sr1.Obviously, we can say then that groups S1,...,S r2N/[⇢]tfor all t2(tS1,...,Sr,t S1,...,Sr]. If ⇢is a crisp proximity relation then tS1,...,Sr=0andtS1,...,Sr=1for every set of components. Proposition 6. Let ⇢be a proximity relation over N.IfS, T 2N/⇢are groups with S\T6=;then S✓Tor T✓S. Particularly, if S, T are leveled groups then S\T=;. Proof. Suppose S, T 2N/⇢with ⇢proximity relation. If they are leveled then there exists t2(0,1] with S, T 2N/[⇢]t,thusS\T=;.IftS=tTthen they are leveled groups. Hence we consider tS>t T.Thereisanumbert>t Ssuch that S2N/[⇢]tand Tis union of components in N/[⇢]t,thereforeorS\T=;or Sis one of these components. 2 6. Axioms for the prox-Owen value. We propose an axiomatization for the prox-Owen value inspired by the axioms of the Owen value and the Myerson-Owen value (section 2.2 and section 3). Let be an allocation rule over GP, namely a function which obtains a vector (N,v,⇢)2 RNfor each game with proximity relation (N,v,⇢)2GP. Consider the following axioms. Efficiency. For all (N,v,⇢)it holds X i2N i(N,v,⇢)=v(N). 22
Linearity. For all games (N,v),(N,v0)2G,↵,2Rand ⇢proximity relation over N, (N,↵v+v0,⇢)=↵ (N,v,⇢)+ (N,v0,⇢). Players in a null coalition do not obtain profit when the coalition is considered as a union or a partition of unions, but they can get profits as a coalition inside a bigger union depending on their position in the structure of this union. Therefore we can take these levels t2(tS,1] as insignificant and rescale. The next axiom extends the null component property. Null group. Let (N,v,⇢)2GP and S2N/⇢a group which is null for the game (N,v) then i(N,v,⇢)=tS iN,v,⇢tS 08i2S. In order to extend the substitutable components axiom we can suppose that between the levels in which both of the groups are unions the total payo↵for each group is the same, namely using (12) and (13) X i2S i(N,v,⇢tST tST )=X j2T j(N,v,⇢tST tST ).(14) But we can get a similar condition (but not equivalent) using the next axiom which is also an extension of the substitutable components property6. Substitutable leveled groups. Let (N,v,⇢)2GP.IfS, T 2N/⇢are leveled groups and they are substitutable in (N,v)then X i2S i(N,v,⇢)(1+tST tST ) i(N,v,⇢tST tST )=X j2T j(N,v,⇢)(1+tST tST ) j(N,v,⇢tST tST ). 6Observe that, by Proposition 4, our prox-Owen value satisfies the substitutable leveled groups axiom if and only if it holds (14). 23
The proximity relation ⇢tST tST represents the scaling of ⇢out of (tST ,t ST ). We suppose that the payments for groups S, T, subtracting the part in which they are no substitutable, i.e. outside the interval (tST ,t ST ), are the same. We extend the modified fairness axiom to a fuzzy situation. In this case, we take into account the mere reduction of the relation between two players. So we have to consider that this reduction of level only concerns to the interval between the reduced level and the original one. Let ⇢be a proximity relation over a set of players Nwith im(⇢)={1< ··· < m}and 0= 0. Consider i, j 2Ntwo di↵erent players with ⇢(i, j)=k>0. The number ⇢⇤(i, j)=k1satisfies that for all t2(⇢⇤(i, j),⇢(i, j)] the set Ni ij (or Nj ij) in the communication structure [⇢]tis the same. We denote also as Ni ij (or Nj ij) this common set for ⇢. Now modified fuzzy fairness says that modified fairness holds if we reduce by tthe level of a link ij for the payo↵s in (⇢(i, j)t, ⇢(i, j)], adding those payo↵s obtained out of this interval. Modified fuzzy fairness. Let (N,v,⇢)2GP and i, j 2Nwith ⇢(i, j)>0, for each t2(0,⇢(i, j)⇢⇤(i, j)] it holds i(N,v,⇢) j(N,v,⇢)=(1t)h i⇣N,v,⇢⇢(i,j) ⇢(i,j)t⌘ j⇣N,v,⇢⇢(i,j) ⇢(i,j)t⌘i +th i⇣Ni ij,v,(⇢⇢(i,j) ⇢(i,j)t)Ni ij ⌘ j⇣Nj ij,v,(⇢⇢(i,j) ⇢(i,j)t)Nj ij ⌘i. The next theorem proves that the prox-Owen value is the only allocation rule satisfying all these axioms. Theorem 7. The prox-Owen value ⌘is the only allocation rule over GP satisfying the following axioms: efficiency, null group, substitutable leveled groups, modified fuzzy fairness and linearity. Proof. We will test each one of the axioms. Efficiency. The Myerson-Owen value satisfies efficiency as we saw in Theorem 1. Hence, X i2N ⇠i(N,v)!(L)=X i2N ⇠i(N,v,L)=v(N) for all (N,v,L)2GC. Now, applying the properties of the Choquet integral (C3), (C5) and 24
also Wij2LN ⇢(i, j)=1 X i2N ⌘i(N,v,⇢)=X i2NZ⇢d⇠i(N,v)=Z⇢dX i2N ⇠i(N,v)=v(N). Linearity. Suppose now another game with the same communication structure, (N,v0,L), and two numbers a, b 2R. As the Myerson-Owen value verifies linearity (Theorem 1) then (C3) implies ⌘i(N, av +bv0,⇢)=Z⇢d⇠i(N, av +bv0) =aZ⇢d⇠i(N,v)+bZ⇢d⇠i(N,v0) =a⌘i(N,v,⇢)+b⌘i(N,v0,⇢). Null group. Let Sbe a null coalition for (N,v). We consider ⇢a proximity relation over Nwith S2N/⇢and i2S.WehaveforthenumbertS(12) that for all r>t Sthere exists a partition {S1,...,S m}of Ssuch that S1,...,S m2N/[⇢]r. Obviously, these coalitions are also null coalitions and then ⇠i(N,v)([⇢]r)=0foralli2Ssince the Myerson-Owen satisfies the null component property (Theorem 1). If tS=0then⌘i(N,v,⇢)=0. Otherwise,by Proposition 4 we get ⌘i(N,v,⇢)=tS⌘i(N,v,⇢tS 0)+(1tS)Z⇢1 tSd⇠i(N,v). If t2im(⇢1 tS) then r=tS+t(1 tS)>t Ssatisfies that ⇢(i, j)rif and only if ⇢1 tS(i, j)t. Hence, [⇢1 tS]t=[⇢]rand ⇠i(N,v)([⇢1 tS]t)=0forallt.By(C5)wehave Z⇢1 tsd⇠i(N,v)=0. Substitutable leveled groups. Let S, T ✓Nbe two substitutable coalitions in a game (N,v). Consider now ⇢a proximity relation over Nwith S, T 2N/⇢leveled groups. We take numbers tST (12) and tST (13). Applying Proposition 5 for any player i2N, ⌘i(N,v,⇢)=(1+tST tST )⌘i(N,v,⇢tST tST )+(tST tST )Z⇢tST tST d⇠i(N,v). 25
Gallego I., Fern´andez J.R., Jim´enez-Losada A. and Ord´o˜nez M. (2014). A Banzhaf value for games with fuzzy communication structure: computing the power of the political groups in the European Parliament, Fuzzy Sets and Systems 255: 128-145. Jim´enez-Losada A., Fern´andez J.R., Ord´o˜nez M. and Grabisch M. (2010). Games on fuzzy communication structures with Choquet players, European Journal of Operational Research 207: 836-847. Jim´enez-Losada A., Fern´andez J.R. and Ord´o˜nez M. (2013). Myerson values for games with fuzzy communication structure, Fuzzy Sets and Systems 213: 74-90. Mares M. (2001). Fuzzy cooperative games, in Studies in Fuzziness and Soft Computing 72, Physica-Verlag Springer. Meng F.Y., Zhang Q., and Cheng H. (2012). The Owen value for fuzzy games with a coalition structure, International Journal of Fuzzy Systems 14 (2012): 22-34. Mordeson J.N. and Nair P.S. (2000). Fuzzy graphs and fuzzy hypergraphs, in Studies in Fuzziness and Soft Computing 46, Physica-Verlag, Springer. 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. Mathematical Economics and Game Theory. Lecture Notes in Economics and Mathematical Systems 141: 76-88. Shapley L.S. (1953). A value for n-person games, Annals of Mathematics Studies 28: 307-317. Schmeidler D. (1986). Integral representation without additivity, Proceedings of the American Mathematical Society 97: 255-261. Tsurumi M., Tanino T., Inuiguchi M. (2001). A Shapley function on a class of cooperative fuzzy games, European Journal of Operational Research 129: 596-618. Waegenaere A. De and Wakker P.P. (2001). Nonmonotonic Choquet integrals, Journal of Mathematical Economics 36: 45-60. 32