A Cooperative Game Theoretical Approach to Risk Analysis, Using Network Structure Jun-ichi Takeshita 1 ∗, Hiroaki Mohri 2 1 Research Institute of Science for Safety and Sustainability National Institute of Advanced Industrial Science and Technology 16-1, Onogawa, Tsukuba, Ibaraki 305-8569, JAPAN E-mail: jun-takeshita@aist.go.jp 2 Faculty of Commerce , Waseda University 1-6-1, Nishi-Waseda, Shinjuku-ku, Tokyo 169-8050, JAPAN E-mail: mohri@waseda.jp Abstract The principal aim of this paper is to introduce the framework for a cooperative game theoretical approach to risk analysis using network structure. Probabilistic risk analysis (PRA) is a common methodology for evaluating risks associated with real-world network structure. Although there are numerous studies on PRA from a physical engineering perspective, Hausken (2002) noted that human behavior is a significant factor in estimating risk using PRA, and he integrated PRA and game theory. While his and related works focused on non-cooperative game theory, in some situations, such as chemical plants, cooperative structures are the norm. Therefore, we here provide a risk analysis method based on cooperative game theory, and especially so-called Shapley values. Keywords: game theory, cooperative game, Shapley value, risk management, network structure 1. Introduction Probabilistic risk analysis (PRA) is a common methodology for evaluating risks associated with network structures (Bedford and Cooke, 2001). Al- though there are numerous studies on PRA from a physical engineering perspective, human behavior has increasingly been noted as a significant factor in estimating risks using PRA. Hausken (2002) ini- tiated this latter approach, and integrated PRA and game theory. Roughly speaking, game theory is a mathemati- cal theory of decision-making in situations involving two or more relevant players, where decisions de- pend on competitors’ behavior. Such situations are referred to as game situations. Originating in von Neumann and Morgenstern’s Theory of Games and Economic Behavior (1944), game theory analyzes conflicts of interest and cooperation among relevant players, by formulating game situations as mathe- matical models (e.g., Fudenberg and Tirole, 1991); and therefore, game theoretical approaches typically involve considerations of human behavior. Game theory typically focuses on two types of ∗Corresponding author Journal of Risk Analysis and Crisis Response, Vol. 4, No. 1 (March 2014), 43-48 Published by Atlantis Press Copyright: the authors 43 willieb Typewritten Text Received 17 December 2013 willieb Typewritten Text Accepted 10 March 2014 willieb Typewritten Text J. Takeshita, H. Mohri games: cooperative and non-cooperative. In so- cial sciences such as economics, non-cooperative game theory is often employed in modern microeco- nomics, for example in industrial organization the- ory (Aumann and Hart, 1994c, Ch. 49), and has re- cently gained increasing popularity in faculties of economics and management. Cooperative game the- ory, however, has not yet attained such widespread use, and one reason may be that economists typically think of market companies as competitors in a non- cooperative game. In this paper, we wish to draw attention to real-world situations in which relevant players are cooperative in terms of risk considera- tion. We shall take as an example, a complex chemi- cal plant, whose various segments represent relevant players working for a single company. These seg- ments may be numerous and varied, but all must co- operate toward the common production ends of the single plant and company. Some economists would argue that even if relevant players are cooperative, the cooperative game would be converted into a non- cooperative game by the Nash program (Nash, 1951, 1953), and this is true in some areas, but not in all. In the chemical plant described above, it is reasonable and unproblematic to posit a sustained cooperative game situation. In light of the foregoing, though most previous studies adopted a non-cooperative game theoretical approach to risk analysis using network structure, a cooperative game theoretical approach is consid- ered more suitable to some real-world situations. The principal aim of this paper, then, is to intro- duce the framework for a cooperative game theoreti- cal approach to risk analysis with network structure. More precisely, we provide a method to allocate risk among the various segments of a chemical plant with a network structure, using so-called Shapley values, solution concepts widely employed in cooperative game theory. The paper is organized as follows. First, we in- troduce Shapley values through concrete examples involving simple-structure graphs. Second, we con- sider two chemical plant toy models: a petroleum refining plant and a medicinal chemical manufactur- ing plant. Finally, we discuss the proposed frame- work and offer concluding remarks. 2. Shapley Values Here we introduce Shapley values by means of two simple examples. Throughout this section, we shall denote segments using the letters A, B, and C, and consider each segment to represent a specific factory operation. Example 1 (Graph with a simple edge) Here we consider a graph with a simple edge (Figure 1), whose characteristic functions are as fol- lows: A B Fig. 1. Graph with a simple edge. In this example, we set so-called characteristic functions as follows: c(A) = 8, c(B) = 8, c(AB) = 15. The values c(A) and c(B) indicate the separate costs involved when each segment is working indepen- dently and experiences a loss, while c(AB) shows the total cost when A and B are working in concert and an accident occurs or plant production is im- paired. The reason that c(AB) < c(A) + c(B) holds is that segments A and B work cooperatively, so that the total risk decreases. The primary aim of this pa- per is to provide a framework wherein the respective segments are involved in cost sharing. Let us calculate the Shapley values for each seg- ment. When B’s work is added to that of A, the to- tal cost is 15. Hence, B would claim that he only pays 7 (= 15 − 8) if an accident occurs. If we treat their respective contributions as defrayment costs, (A, B) = (8, 7) may be allocated for risk. However, this procedure does not take into account the coali- tion order of A and B; if only B is working initially, and then A adds to the line, A would claim that he only pays 7 (= 15 − 8) if an accident occurs; and if we treat their respective contributions in this case Published by Atlantis Press Copyright: the authors 44 Cooperative Game to Risk Analysis as defrayment costs, (A, B) = (7.5, 7.5) may be allo- cated to risk. The Shapley values represent the aver- age of each order’s contribution, given any segment order, for the total segment set. In this example, the Shapley values of A and B are 7.5 = (8 + 7)/2 and 7.5 = (7 + 8)/2, respec- tively. Note that we can illustrate the procedure by using Table 1: Table 1. Table for calculating the Shapley values of Example 1. Coalition order A’s contr B’s contr A → B 8 7 = 15 − 8 B → A 7 = 15 − 8 8 Shapley value 7.5 7.5 *contr – contribution Example 2 (Tandem graph) Here again we consider a graph with a simple edge (Figure 2), whose characteristic functions are as follows: A B C Fig. 2. Tandem graph. c(A) = 8, c(B) = 8, c(C) = 8, c(AB) = 15, c(BC) = 15, c(CA) = 16, c(ABC) = 20. The values c(AB) and c(BC) are both equal to c(AB) in Example 1, since their structure is identical. On the other hand, the relations c(CA) = c(C) + c(A), c(CA) > c(AB), c(CA) > c(BC) are satisfied, because segments A and C do not di- rectly connect. This means that cooperation between A and B, and B and C, will reduce the segment cost of each, but that cooperation between C and A will not reduce the segment cost of either. From Table 2, the Shapley values are (A, B,C) = ( 41 3 , 38 3 , 41 3 ) . Note that as B is directly connected to A and C, the Shapley value of B is less than that of A and C. Table 2. Table for calculating the Shapley values of Example 2. Coalition A’s B’s C’s order contr contr contr A → B → C 8 7 5 A → C → B 8 4 8 B → A → C 7 8 5 B → C → A 5 8 7 C → A → B 8 4 8 C → B → A 5 7 8 Shapley value 41/3 38/3 41/3 *contr – contribution To take an example, if the coalition order is A → B → C, we can calculate each segment’s con- tribution as follows: v(A) = c(A) = 8, v(B) = c(AB) − c(A) = 15 − 8 = 7, v(C) = c(ABC) − c(AB) = 20 − 15 = 5. 3. Chemical Plant Toy Models Here we consider two chemical plant toy models, one a petroleum refining plant, and the other a medicinal chemical manufacturing plant. Roughly speaking, in the former the primary process is crude oil separation, and in the latter, the repetition of chemical reactions. They are both characterized by a structure typical of chemical plants, which involves a process of either deriving or adding chemicals. Ex- pressed mathematically, this is a tree structure; see e.g., Lawler (2011, Sec. 5, Ch. 2) for mathematical elaboration. Model 1 (Petroleum refining plant model) The process of petroleum refinement involves the separation of crude oil into heavy oil, gas oil, heat- ing oil, and gas. We can model this process as 3, with reservoirs for crude oil (A), heavy oil (D), and the remaining oil (B). Published by Atlantis Press Copyright: the authors 45 J. Takeshita, H. Mohri A B CED Fig. 3. Petroleum refining plant model. We assume that A and B are reservoirs for oil mixtures, and the others (D, C, and E ) are purified products. We may define the characteristic functions of this model as follows: c(A) = c(B) = 5, c(C) = c(D) = c(E) = 3, c(AB) = c(AC) = c(AE) = c(BD) = 8, c(BC) = c(CD) = c(CE) = c(AD) = c(BE) = c(DE) = 6, c(ACE) = 11, c(ABC) = c(ABD) = c(ABE) = 10, c(ACD) = c(ADE) = c(BCD) = c(BDE) = c(CDE) = 9, c(BCE) = 8, c(ABCD) = c(ABCE) = c(ACDE) = 12, c(ABDE) = c(BCDE) = 11, c(ABCDE) = 13. A and B are involved in the production of two or more products, and C, D, and E are primarily re- sponsible for only one product. Hence, the char- acteristic functions of A and B are greater those of the others. The characteristic functions of more than two segments are governed by the following rule: let and N be a set of segments and a segment, respectively; then (i) c( N) < c( ) + c(N) if there exists a seg- ment M of the set such that M connects to N directly; (ii) c( N) = c( ) + c(N) is satisfied unless case the (i) holds. For example, suppose that = AD and N = B, then A (a member of ) connects to B directly. Thus, this is an example of case (i); and as c(AD) = 6, c(B) = 5, and c(ABD) = 10, then we have 10 = c(ABD) < c(AD) + c(B) = 10. A further example: suppose that = ADE and N = C, then there is no segment in such that the segment connects to C directly. Thus, this is an ex- ample of the case (ii); and as c(ADE) = 9, c(C) = 3, and c(ACDE) = 12, then we have 12 = c(ACDE) = c(ADE) + c(C). The Shapley value of this model is (A, B,C, D, E) = ( 420 5 , 342 5 , 290 5 , 248 5 , 260 5 ) . Note that we must calculate each segment’s contri- bution for each coalition order when we generate the Shapley values, and there are 5! = 120 orders. Remark 1 The results represent each segment’s marginal contribution to the plant’s production (de- tailed in the final section). Therefore, when apply- ing this method to chemical plants, we allocate re- sponsibility to each segment according to its Shap- ley value. Specifically, when an accident occurs in a given plant, each segment covers the damage cost according to this value. Also, in a risk manage- ment context, the plant manager can allocate costs for safety measures to each segment based on its re- spective Shapley value. Model 2 (Medicinal chemical manufacturing plant model) The process of manufacturing medicine involves the repeated addition of chemical substances. We can model this process as Figure 4. Published by Atlantis Press Copyright: the authors 46 Cooperative Game to Risk Analysis A C E D B F G Fig. 4. Medicinal chemical manufacturing plant model. The model may at first seem somewhat complex; however, the process works in tandem, and by la- beling the intersection points from left to right as α , β , and γ , we can represent this model as a tandem graph (Figure 5). A C E D B F G ˺ ˻ ˼ ˺ ˻ ˼ Fig. 5. Medicinal chemical manufacturing plant model as a tandem graph. Therefore, we may treat the medicinal chemi- cal manufacturing plant model in the same man- ner as Example 2, discussed in the previous section. More precisely, by specifying the value of the char- acteristic functions, c(α), c(β ), c(γ), c(α β ), c(β γ), c(γ α), and c(α β γ), we can calculate the Shapley value for this model. For example, when we specify the value of these functions in line with Example 2, the Shapley value for the model is (α, β , γ) = ( 41 3 , 38 3 , 41 3 ) , which is, of course, the same result as in Example 2. Remark 2 In the two examples above, we designed the characteristic functions to satisfy the rule de- scribed in Model 1. However, their specific values were chosen for convenience; and, though we have focused specifically on the construction of network models in this study, we are also concerned with the manner of specifying the value of such characteris- tic functions, however this is a consideration for the future. 4. Discussion and Concluding Remarks We provided a cooperative game theoretical ap- proach to risk analysis using network structure, based on Shapley values. The approach would ap- pear to have potential for solving risk allocation problems, since, if the total risk is known, the Shap- ley values help us determine each segment’s re- spective contribution, and thereby allocate segmen- tal risk according to these values. In general, we may calculate Shapley values as follows. Let N be the set of all segments. First, we define a characteristic function c : 2N → R, where 2N and R denote the sets of all subsets of N and real numbers, respectively; and the function has the fol- lowing properties: (i) c( /0) = 0, (ii) c(S ∪ T ) 6 c(S) + c(T ), where S and T are subsets of N satisfying S ∩ N = /0. Note that S ∩ T = /0 means that there no segment belonging to both sets S and T . Then, segment i’s Shapley value is defined by φi(c) := ∑ S⊂N\{i} |S|!(n −|S|− 1)! n! (c(S ∪{i}) − c(S)) , Published by Atlantis Press Copyright: the authors 47 J. Takeshita, H. Mohri where n is the total number of segments, and |S| denotes the number of segments belonging to the set S (i.e., |N| = n). In the equation, c(S ∪ {i}) − c(S) means that the marginal contribution of i to S. Hence, the Shapley value indicates a weighted aver- age of the respective marginal contributions. In ad- dition, a Shapley value has the following five prop- erties: (i) For any i ∈ N, φi(c) 6 c(i) is satisfied. (ii) ∑ i∈N φi(c) = c(N). (iii) If c(S ∪ i) = c(S ∪ j) holds for any S ⊂ N satis- fying i, j 6= S, then φi(c) = φ j(c). (iv) For any S ⊂ N satisfying i 6= S, c(S ∪ {i}) = c(S) is satisfied. (v) For any characteristic functions c1 and c2, φi(c1 + c2) = φi(c1) + φi(c2) is satisfied. It has been well established that a Shapley value is the only solution concept that satisfies the five prop- erties above (Aumann and Hart, 1994c, Ch. 53). We used the Shapley value as a solution concept in our cooperative game models, but an alternative solution concept, that of the nucleus, is also avail- able for this purpose (Aumann and Hart, 1994a, Ch. 18). A Shapley value is defined based on each seg- ment’s contribution when that segment cooperates with others, while the nucleus concept is based on a given segment’s dissatisfaction with its respective coalitions. Since the approaches are so different, it is difficult to generalize about their respective supe- riority; this will likely be determined by the specific context of the problem faced. Although the framework introduced in this paper is the first attempt of its kind for cooperative game theory, it appears to offer a promising approach to risk analysis, especially in the context of risk alloca- tion. Acknowledgments The authors wish to thank Dr. Ryoji Makino for his support and fruitful discussion in improving this pa- per. 1. R. J. Aumann and S. Hart, Handbook of Game Theory with Economics Applications, Volume 1, North Hol- land, Amsterdam, (1994a). 2. R. J. Aumann and S. Hart, Handbook of Game Theory with Economics Applications, Volume 2, North Hol- land, Amsterdam, (1994b). 3. R. J. Aumann and S. Hart, Handbook of Game Theory with Economics Applications, Volume 3, North Hol- land, Amsterdam, (1994c). 4. T. Bedford and R. Cooke, Probabilistic Risk Analy- sis: Foundations and Methods, Combridge University Press, Cambridge, (2001). 5. D. Fudenberg and J. Tirole, Game Theory, MIT Press, MA, (1991). 6. K. Hausken, “Probabilistic risk analysis and game the- ory,” Risk Analysis, 22, 17–27 (2002). 7. E. Lawler, Combinatorial optimization: Networks and matroids, Dover Publications, New York, USA, (2011). 8. J. F. Nash, “Non-Cooperative Games,” The Annals of Mathmatics, Second Seties, 54 286–295 (1951). 9. J. F. Nash,“Two Person Cooperative Games,” Econo- metrica, 21, 128–140 (1953). Published by Atlantis Press Copyright: the authors 48