Games with fuzzy authorization structure: a Shapley value

Games with fuzzy authorization structure: a Shapley value. J.M. Gallardo, N. Jim´enez, A. Jim´enez-Losada and E. Lebr´on 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 which determines 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. It is often assumed that the players are free to participate in any coalition, but in some situations there are dependency relationships among the players that restrict their capacity to cooperate within some coalitions. Those relationships must be taken into account if we want to distribute the profits fairly. In this respect, several models have been proposed in literature. In all of them dependency relationships are considered to be complete, in the sense that either a player is allowed to fully cooperate within a coalition or they cannot cooperate at all. Nevertheless, in some situations it is possible to consider another option: that a player has a degree of freedom to cooperate within a coalition. A model for those situations is presented. Keywords: cooperative game, fuzzy coalition, Shapley value, fuzzy authorization structure 1. Introduction In a general way, game theory studies cooperation and conflict models, using mathematical methods. This paper is about cooperative game theory. A cooperative game over a finite set of players is defined as a function establishing the worth of each coalition. Given a cooperative game, the main problem that arises is how to assign a payoff to each player in a reasonable way. In this setting, it is often assumed that all of the players are socially identical. In real life, however, political or economic circumstances may impose certain restraints on coalition formation. This idea has led several authors to develop models of games in which relationships among players must be taken into account. Depending on the nature of such relationships, different structures in the set of players have been considered. Myerson (1977) studied games in which communication between players is restricted. He considered graphs to model those restraints. Subsequently, different kinds of limitations on cooperation among Email address: [email protected] (J.M. Gallardo, N. Jim´enez, A. Jim´enez-Losada and E. Lebr´on) Preprint submitted to Fuzzy Sets and Systems October 15, 2018 players have been studied, and various structures have been used for that, like convex geometries (see Bilbao (1998)), matroids (see Bilbao et al. (2001)), antimatroids (see Algaba et al. (2004)) or augmenting systems (see Bilbao and Ordo˜nez (2009)). A particularly interesting case of limited cooperation arises when we consider veto relationships between players. In this regard, Gilles et al. (1992) modeled situations in which a hierarchical structure imposes some constraints on the behavior of the players in the game. They introduce games with permission structure, that consist of a set of players, a cooperative game and a mapping that assigns to every player a subset of direct subordinates. In this respect, the power of a player over a subordinate can be of different kinds. In the conjunctive approach it is assumed that each player needs the permission of all his superiors, whereas in the disjunctive approach, van den Brink (1997), the permission of any of those superiors will suffice. In each case they consider a new characteristic function, which collects the information given by both the original characteristic function and the permission structure, and that allows them to define a value for games on conjunctive (or respectively disjunctive) permission structures. They provide intuitive characterizations for each case, showing in this way that the values obtained are reasonable. Subsequently, Derks and Peters (1993) generalized those approaches by considering the so-called restrictions. Although their model is more general, the axiomatization given is not as intuitive and straightforward as those given in Gilles et al. (1992) and van den Brink (1997) for permission structures. In all of the models presented so far the dependency relationships are complete, in the sense that either a coalition can veto a player or it does not have any authority over the player. Our aim in this paper will be to provide a new model for games in which players are subject to certain restraints when cooperating within a coalition. We will consider the possibility that such restraints are partial, which will make this model more general than those referenced above. The paper is organized as follows. In Section 2 we recall some basic definitions and properties about the Shapley value, fuzzy sets and the Choquet integral. In Section 3, we introduce fuzzy authorization structures, that will be used to model situations in which some players depend partially on other players. Then, for each game with fuzzy authorization structure, a new characteristic function, that collects the information from both the game 2 and the structure, is be defined. This characteristic function will allow us to define a Shapley value for games with fuzzy authorization structure. A characterization of this value is given in Section 4. An example is described as well. Finally, in Section 5 some conclusions are given. 2. Preliminaries 2.1. Cooperative TU-games We recall some concepts regarding cooperative games. A transferable utility cooperative game or TU-game is a pair (N, v) where Nis a finite set and v: 2N→Ris a function with v(∅)=0.The elements of N={1, ..., n}are called players, and the subsets of N coalitions. Given a coalition E,v(E) is the worth of E, and it is interpreted as the maximal gain or minimal cost that the players in this coalition can achieve by themselves against the best offensive threat by the complementary coalition. Frequently, a TU-game (N, v) is identified with the function v. A game vis monotone if for every F⊆E⊆N, it holds that v(F)≤v(E). The family of games with set of players Nis denoted by GN. This set is a (2n−1)-dimensional real vector space. One basis of this space is the collection {uF:F⊆N, F 6=∅} where for a nonempty coalition Fthe unanimity game uFis defined by uF(E) =    1 if F⊆E, 0 otherwise. Every game v∈ GNcan be written as a linear combination of them, v=X {E∈2N:E6=∅} 4v(E)uE where 4v(E) is the dividend of the coalition Ein the game v. A solution or value on GNis a function ψ:GN→RNthat assigns to each game a vector (ψ1(v), . . . , ψn(v)) where the real number ψi(v) is the payoff of the player iin the game (N, v). Many values have been defined in literature for different families of games. The Shapley value (see Shapley (1953)) φ(v)∈RNof a game v∈ GNis a weighted average of the marginal 3 contributions of each player to the coalitions and formally it is defined by φi(v) = X {E⊆N:i∈E} pE(v(E)−v(E\ {i})) ,for all i∈N, where pE=(n− |E|)! (|E| − 1)! n! and |E|denotes the cardinality of E. Some desirable properties for a value ψ:GN→RNare the following: Efficiency: Pi∈Nψi(v) = v(N) for all v∈ GN. Additivity: ψ(v1+v2) = ψ(v1) + ψ(v2) for all v1, v2∈ GN. Null player property: A player i∈Nis a null player in v∈ GNif v(E) = v(E\ {i}) for all E⊆N. If i∈Nis null player in v∈ GNthen ψi(v) = 0. Necessary player property: A player iis a necessary player in v∈ GNif v(E) = 0 for all E⊆N\{i}. If iis a necessary player in a monotone game v∈ GN, then ψi(v)≥ψj(v) for all j∈N. These four properties characterize the Shapley value (see van den Brink (1994)). 2.2. Fuzzy sets Fuzzy subsets of a finite set were described by Zadeh (1965). A fuzzy subset of Nis a mapping e:N−→ [0,1] where eassigns to i∈Na degree of membership. A fuzzy subset of Nis identified with a vector in [0,1]N.Given e∈[0,1]Nthe support of eis the set supp (e) = {i∈N:ei>0}and the image of eis the set im(e) = {ei:i∈N}. If t∈[0,1] the t-level set of eis [e]t={i∈N:ei⩾t}. Given e, f ∈[0,1]Nstandard union and intersection are defined, respectively, by (e∩f)i= min{ei, fi}, (e∪f)i= max{ei, fi}for all i= 1, . . . , n. The fuzzy sets e, f ∈[0,1]Nare called comonotone if (ei−ej) (fi−fj)≥0 for all i, j ∈N. Regarding cooperative game theory, Aubin (1981) defined a fuzzy coalition in Nas a fuzzy subset eof Nwhere, for all i∈N, the number ei∈[0,1] is regarded as the degree 4 of participation of player iin e. Every coalition E⊆Ncan be identified with the fuzzy coalition 1E∈[0,1]Ndefined by 1E i= 1 if i∈Eand 1E i= 0 otherwise. Different Shapley values for games with fuzzy coalitions were studied in Butnariu (1980) and Tsurumi et al. (2001). 2.3. The Choquet integral The Choquet integral was introduced in Choquet (1953). It was originally defined for capacities. Later on, Schmeidler (1986) studied this integral for all set functions. Given v: 2N→Rand e∈[0,1]N, the Choquet integral of ewith respect to vis defined as Ze dv = q X p=1 (sp−sp−1)v[e]sp,(1) where im (e)∪ {0}={sp}q p=0 and 0 = s0< s1< . . . < sq. It will be useful, when dealing with several fuzzy coalitions, to rewrite the expression above using a superset of im(e), that is, Ze dv = m X l=1 (tl−tl−1)v([e]tl),(2) where im(e)⊆ {tl}m l=0 and 0 = t0< t1< . . . < tm. The following properties of the Choquet integral are known: (C1) R1Edv =v(E), for all E⊆N. (C2) Rte dv =tRe dv, for all t∈[0,1] . (C3) Re dv ≤Rf dv, whenever e≤fand vis monotone. (C4) Re d(cv) = cRe dv, for c∈R. (C5) Re d (v1+v2) = Re dv1+Re dv2. (C6) R(e+f)dv =Re dv +Rf dv, when e+f≤1Nand e, f are comonotone. 3. Methodology We aim to present a model of games in which the ability of players to cooperate within a coalition can be limited. To do this, firstly we introduce the structure that will allow us to 5 deal will that kind of dependency relationships. Then we will incorporate the information from the structure with the information from the game. Finally, a value will be proposed. 3.1. Fuzzy authorization structures The idea is that a set of players may have the power to restrict the ability to cooperate of the rest of the players. So, given a coalition, we will consider the capacity of their players to cooperate within the coalition. Definition 1. A fuzzy authorization operator on Nis a function a: 2N→[0,1]Nthat satisfies the following requirements: (A1) a(E)⩽1Efor any E⊆N, (A2) If E⊆Fthen a(E)⩽a(F). The pair (N, a)will be called a fuzzy authorization structure. The set of fuzzy authorization operators on Nwill be denoted by FAN. Given a∈ FAN, we will denote im(a) = [ E⊆N im(a(E)). Suppose that ais a fuzzy authorization operator and vis a game on N. Then, given E⊆Nand i∈N, we will interpret ai(E) as the proportion of the whole operating capacity of player ithat he is allowed to use within coalition E. Or, equivalently, 1 −ai(E) is the fraction of the operating capacity of player ithat is under control of coalition N\E. 3.2. The restricted game The restricted game will be the tool used to amalgamate the information from the game and the information from the fuzzy authorization structure. Definition 2. Let v∈ GNand a∈ FAN. The restriction of von ais the game va∈ GN defined as va(E) = Za(E)dv for all E⊆N. 6 Remark 3. Using (2), the restriction of von acan be written as va(E) = m X l=1 (tl−tl−1)v([a(E)]tl)for all E⊆N, (3) where im(a)⊆ {tl}m l=0 and 0 = t0< t1< . . . < tm. 3.3. A Shapley value for games with fuzzy authorization structure We apply the Shapley value to the restricted game in order to define a value for games with fuzzy authorization structure. Definition 4. The Shapley fuzzy authorization value on the set of players Nis the allocation rule ϕN:GN× FAN→RNgiven by ϕN(v, a) = φ(va)for all v∈ GNand a∈ FAN. We will write ϕ(rather than ϕN) and say just Shapley fuzzy authorization value as long as there is no possibility of confusion. 4. Results 4.1. A characterization of the Shapley fuzzy authorization value We aim to prove that the Shapley fuzzy authorization value has good properties with respect to both the game and the fuzzy authorization structure. To do this, we will consider the properties described below. If a∈ FANwith im(a(N)) ⊆ {0,1}, which means that when the grand coalition is formed each player can use either his full capacity or no capacity at all, the set supp(a(N)) can be seen as a carrier (see Shapley (1953)). In that case, we can consider the following efficiency property: Efficiency. For every v∈ GNand a∈ FANwith im(a(N)) ⊆ {0,1}it holds that X i∈N ψi(v, a) = v(supp(a(N)). 7 Additivity is a well-known property of the Shapley value. In our setting, it is as follows: Additivity. For every v, w ∈ GNand a∈ FANit holds that ψ(v+w, a) = ψ(v, a) + ψ(w, a). Given a∈ FANand i, j ∈N, player jdepends partially on iaccording to aif there exists E⊆Nsuch that aj(E)> aj(E\ {i}). Given v∈ GNand a∈ FAN, a player i∈Nis an irrelevant player in (v, a) if for every j∈Nsuch that jdepends partially on iaccording to ait holds that jis a null player in v. Notice that a null player in vis not necessarily an irrelevant player in (v, a).The null player property is generalized now in the following way: Irrelevant player. For every v∈ GN,a∈ FANand i∈Nsuch that iis an irrelevant player in (v, a)it holds that ψi(v, a)=0. Note that if ais the trivial authorization structure (that is, a(E) = 1Efor every E⊆N) then the irrelevant players in (v, a) are just the null players in v. From this point of view, the irrelevant player property is a generalization of the null player property. Given a∈ FANand i, j ∈N, we say that ihas veto power over jaccording to aif aj(N\ {i}) = 0. Players who have veto power over a necessary player will expect to be treated as another necessary player. This leads us to consider the following property: Veto power over a necessary player. For every monotone game v∈ GN,a∈ FAN and i, j ∈Nsuch that jis a necessary player in vand ihas veto power over jaccording to ait holds that, for all k∈N, ψi(v, a)⩾ψk(v, a). Note that if ais the trivial authorization structure then the players with veto power over a necessary player according to aare just the necessary players for the game. So the property of veto power over a necessary player is a generalization of the necessary player property. Let a∈ FAN,∅ 6=T⊆Nand i∈T. The fuzzy authorization operator adescribes a 8 situation in which some players may need the permission from other players in order to use a fraction of their operating capacity. In such situation, if coalition Tis formed, player iwill be allowed to use a proportion of his capacity equal to ai(T). Now suppose that somehow the players in Tacquire the power to authorize player ito use a bigger proportion of his capacity, say s∈(ai(T),1]. The new situation would be described by the fuzzy authorization operator aT,i,s defined as aT,i,s(E) =    a(E)∪(s·1{i}) if T⊆E, a(E) otherwise. In this case, it would be reasonable to expect that all the players in Twill benefit equally from the change. This is what the following property states: Fairness. For every v∈ GN,a∈ FAN,T∈2N\ {∅},i∈Tand s∈[0,1] it holds that ψjv, aT,i,s−ψj(v, a) = ψiv, aT,i,s−ψi(v, a) for all j∈T. Notice that if s⩽ai(T) then aT,i,s =a. Therefore, the expression above is non trivial only if s∈(ai(T),1]. Two fuzzy authorization operators aand a0are called comonotone if a(E) and a0(E) are comonotone for every E⊆N. If we suppose that each player has an amount of a certain resource and that the profit that can be made from those resources is proportional to the quantities, we could consider a property like the following, that establishes, in a way, linearity between the authorization operator and the payoff: Comonotonicity. For every v∈ GN,a, a0∈ FANcomonotone and t∈[0,1] it holds that ψ(v, ta + (1 −t)a0) = t ψ(v, a) + (1 −t)ψ(v, a0). Theorem 5. An allocation rule ψ:GN× FAN→RNis equal to the Shapley fuzzy authorization value if and only if it satisfies the properties of efficiency, additivity, irrelevant player, veto power over a necessary player, fairness and comonotonicity. 9 It suffices to consider these cases: 1) If ai(F), aj(F)≥tthen a[0,t] i(F) = a[0,t] j(F) = 1. 2) If ai(F), aj(F)≤tthen a[t,1] i(F) = a[t,1] j(F) = 0. 3) If ai(F)≥t > aj(F) then a[0,t] i(F)=1> a[0,t] j(F) and also a[t,1] i(F)≥0 = a[t,1] j(F). Now, since ϕand ψsatisfy comonotonicity it holds that ψ(c uE, a) = t ψ(c uE, a[0,t]) + (1 −t)ψ(c uE, a[t,1]). ϕ(c uE, a) = t ϕ(c uE, a[0,t]) + (1 −t)ϕ(c uE, a[t,1]), Since z(a[0,t]), z(a[t,1])< z(a) it follows by induction hypothesis that ψ(c uE, a[0,t]) = ϕ(c uE, a[0,t]) and ψ(c uE, a[t,1]) = ϕ(c uE, a[t,1]). Hence ψ(c uE, a) = t ϕ(c uE, a[0,t]) + (1 −t)ϕ(c uE, a[t,1]) = ϕ(c uE, a). So we have proved (17). Now, take E∈2N\ {∅},a∈ FANand c < 0. Using additivity and the irrelevant player property we have that ψ(c uE, a) + ψ(−c uE, a)=0, ϕ(c uE, a) + ϕ(−c uE, a) = 0, and, hence, ψ(c uE, a) = −ψ(−c uE, a) = −ϕ(−c uE, a) = ϕ(c uE, a). We have seen that ψ(c uE, a) = ϕ(c uE, a) for all c∈R,E∈2N\ {∅} and a∈ FAN. Finally, take v∈ GNand a∈ FAN. It holds that ψ(v, a) = ψ X {E⊆N:E6=∅} ∆v(E)uE, a =X {E⊆N:E6=∅} ψ(∆v(E)uE, a) =X {E⊆N:E6=∅} ϕ(∆v(E)uE, a) = ϕ X {E⊆N:E6=∅} ∆v(E)uE, a =ϕ(v, a). 16 4.2. Example Imagine the following situation. A consumer electronics company wants to make a new product. To do this, the company needs several components from various suppliers. We will focus on three of those suppliers. For i= 1,2,3 supplier iproduces component i. The company has signed an agreement with the three suppliers that establishes the following: •The company will pay idollars to supplier ifor every unit of component idelivered before the deadline. •The company will pay a total of 2(i+j) dollars to suppliers iand jfor every pair made up of a unit of component iand a unit of component jdelivered before the deadline. •The company will pay a total of 20 dollars to the three suppliers for every set made up of a unit of each component delivered before the deadline. Each supplier has calculated that it would be able to produce one million units of the corresponding component before the deadline. This situation can be modeled with a cooperative game ({1,2,3}, v), where, for every E⊆ {1,2,3},v(E) is the revenue (in millions) obtained by coalition E. v({1})=1, v ({2})=2, v ({3})=3, v({1,2}) = 6, v ({1,3})=8, v ({2,3}) = 10, v ({1,2,3}) = 20. Imagine now the following. In order to produce component 3, supplier 3 makes use of a technology developed and patented by supplier 1. Supplier 3 has calculated that if they decided to produce component 3 without using that technology, they would only be able to produce seven hundred thousand units before the deadline. They also use a technology patented by supplier 2, and the speed of production would drop 50 percent if they did without that technology. Finally, it they decided to do without both technologies, they could only produce four hundred thousand units of component 3 before the deadline. For every E⊆ {1,2,3}and i∈ {1,2,3},ai(E) indicates the fraction of its maximal productive capacity that player ican reach if it does not have the authorization of the 17 players in {1,2,3} \ E. E{1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} a(E) (1,0,0) (0,1,0) (0,0,0.4) (1,1,0) (1,0,0.5) (0,1,0.7) (1,1,1) We calculate the restricted game: va({1}) = v({1}) = 1, va({2}) = v({2}) = 2, va({3})=0.4v({3})=1.2, va({1,2}) = v({1,2})=6, va({1,3}) = 0.5v({1,3})+0.5v({1}) = 4.5, va({2,3}) = 0.7v({2,3})+0.3v({2}) = 7.6, va({1,2,3}) = v({1,2,3}) = 20. Finally, a payoff vector for the suppliers is ϕ(v, a) = (5.6833,7.7333,6.5833) . 5. Conclusions We have defined and characterized a value for games with fuzzy authorization structure. The model presented is more general than those introduced in previous papers (Gilles et al. (1992), Derks and Peters (1993), van den Brink (1997), Algaba et al. (2004)), since it allows us to deal with partial dependency relationships. The value introduced is applicable to situations in which we have a cooperative game and a collection of restrictions on coalition formation. Other solutions for games with fuzzy authorization structure remain to be studied. Acknowledgments This research has been partially supported by the Spanish Ministry of Economy and Competitiveness ECO2010-17766, and by the FQM237 grant of the Andalusian Government. References Algaba E., Bilbao J.M., van den Brink R. and Jim´enez-Losada A. (2004). Cooperative games on antimatroids. Discrete mathematics 282: 1-15. Aubin J.P. (1981). Cooperative fuzzy games, Mathematics of Operations Research 6: 1-13. 18 Bilbao J.M. (1998). Axioms for the Shapley value on convex geometries. European Journal of Operational Research 110: 368-376. Bilbao J.M., Driessen T.S.H., Jim´enez-Losada A. and Lebr´on E.A. (2001). The Shapley value for games on matroids: the static model. Mathematical methods of Operations Research 53: 333-348. Bilbao J.M. and Ord´o˜nez M. (2009). Axiomatizations of the Shapley value for games on augmenting systems. European Journal of Operational Research 196: 1008-1014. Brink R. van den (1994). Relational Power in Hierarchical Organizations. Ph. D. Thesis, 1994. Brink R. van den (1997). An axiomatization of the disjunctive permission value for games with a permission structure. International Journal of Game Theory 26(1): 27-43. Butnariu D. (1980). Stability and Shapley value for an n-person fuzzy game, Fuzzy Sets and Systems 4: 63-72. Choquet G. (1953). Theory of Capacities, Annales de l’Institut Fourier 5: 131-295. Derks J. and Peters H. (1993). A Shapley value for games with restricted coalitions, International Journal of Game Theory 21: 351-366. Gilles R.P., Owen G. and van den Brink R. (1992). Games with permission structures: the conjunctive approach, International Journal of Game Theory 20: 277-293. Myerson R.B. (1977). Graphs and cooperation in games, Mathematics of Operations Research 2(3): 225-229. 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. Zadeh L.A. (1965). Fuzzy sets, Information and Control 8: 338-353. 19