Modeling Uncertain Situations in Decision-Making with Influence Diagrams Igor Kovalenko1[0000-0003-2655-6667], Yevhen Davydenko1[0000-0002-0547-3689] and Alyona Shved1[0000-0003-4372-7472] 1 Petro Mohyla Black Sea National University, Mykolaiv, Ukraine {ihor.kovalenko,davydenko,avshved}@chmnu.edu.ua Abstract. The modern methods of scenario analysis and forecasting, represented by tree-like graphs, are investigated in this paper. The basic theoretical positions of influence diagrams are considered. Its mathematical apparatus is based on Bayesian networks and supported a combination of graphical representation of analyzed process and its probabilistic behavior. The influence diagrams are an effective tool for modeling uncertain events in a complex decision-making pro- cess, which reflect decision-making situations in a more compact form. Influence diagrams also reflect all possible factors of the problem and their relationship in a clear and understandable way; provide all relevant information and implemen- tation of the most appropriate decision-making procedure; allow to perform real- time analysis of possible scenarios. The numerical calculations that illustrate the possibilities of practical application of influence diagrams in complex decision- making problems under uncertainty are provided. The results obtained are aimed at improving the quality and effectiveness of decision-making in scenario analy- sis process with a large number of interrelated factors. Keywords: Decision-Making, Influence Diagram, Scenario analysis, Uncer- tainty. 1 Introduction The initial situation in decision-making tasks is often characterized by complexity and uncertainty, and various combinations of uncertain events can influence the outcomes of decisions made. These events are known as scenarios [1]. Therefore, there was a need to construct models that should not only reflect real situations, but also be used to formally solve probabilistic inference problems. Which here means calculating the probabilities of scenarios or events based on known probabilities of other related events implementation [1, 2, 4, 10]. The probability trees and decision trees are some of the most widely known methods for modeling uncertain situations, which are successfully used for a small number of uncertain events (n≤4-5). With the increasing number of uncertain events, probability trees are characterized by a large dimension, which makes it extremely difficult to dis- play the information that they contain (a set of alternative solutions, systems of uncer- tain events and outcomes of alternative solutions) [4]. Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). In this regard, a new “tool” called the “influence diagram” (ID) appeared to model uncertain events [6-9]. The advantage of IDs in relation to decision trees is especially noticeable for complex decision-making problems, when they are caused by a large number of interrelated factors. In addition, the IDs allow reflecting decision-making situations in a more compact form [1]. At the same time, it should be noted that IDs are currently known only to a fairly narrow circle of specialists and have not received such widespread application as decision trees. The purpose of the paper is to present the basic theoretical principles of the influence diagrams and propose an example of their practical application in scenarios analysis tasks with a large number of interrelated factors. 2 The Influence Diagram Basics Let us consider the basics of IDs that reveal the essence and features of them in accord- ance with the works [1, 4]. The ID is an oriented acyclic graph, the vertices (nodes) of which reflect the set (system) of factors: decisions, events and outcomes. All relevant information is not as closely related to the structure of the ID as is the case for decision trees. The following types of nodes are distinguished on any ID. The decision node dis- plays a variety of alternative solutions, which are graphically depicted in the form of rectangles or squares on the ID graph. An event node displays a set (complete system) of uncertain events that directly or indirectly determine the outcome of alternative de- cisions. The event nodes are depicted in the form of circles or ovals in ID graph. The chance node displays a function that evaluates the outcomes of alternative solutions. The chance nodes shown as a diamond in ID graph. For these types of nodes, the following notation is accepted: 1. D used for decision nodes; 2. C used for chance nodes; 3. V used for value nodes. An influence diagram, which is presented in the form of a graph and does not contain any other information, is called partially defined. To perform a decision analysis, each node in the graph must be provided with all relevant information. Lists of alternative solutions are associated with each decision node. A list of events and unconditional or conditional probabilities of their implementation are associated with each chance node. A value node is associated with a list of outcomes of all alternative solutions, the prob- ability of their implementation and the value of the assessed function. ID with all infor- mation related to the analysis is called completely defined. Let us consider some general approaches to ID construction [1, 4]. First of all, it is an approach for purposefully generating of IDs, the main ideas of which are that by a preliminary analysis of situations the number of decision-making acts and the sequence of their generation for general problem solving are determined. This determines the number of decision nodes on the ID. Then the way of assessment of outcomes of the alternative actions is determined. The value node and associated with it the assessed function is determined in this way. Based on this information, the so-called minimal influence diagram is constructed, which includes only the decision node(s) and the value node. Fig. 1 [1] presents the minimal ID. Fig. 1. Minimal influence diagrams: a) with one decision node; b) with two decision nodes. Next, by further analysis of the situation, those systems of uncertain events that directly determine the outcome of alternative solutions are determined. The nodes displaying these groups of events are plotted on the ID graph, and the arcs from them are sent to the value node. Fig. 2 [1] presents the minimal ID supplemented by the event nodes C1 and C2. Fig. 2. Minimal influence diagram with two chance nodes C1 and C2. Next, the situation is analyzed to determine whether there are groups of undefined events that affect events in nodes C1 and C2. Suppose the existence of two such systems of uncertain events C3 and C4 was estab- lished (Fig. 3 [4]). Events of system C3 can affect the probabilities of events at nodes C1 and C2, and events of system C4 can affect the probabilities of events at node C1. The nodes corresponding to these groups of undefined events are plotted on the ID and joined by arcs to existing nodes. The expanded ID is shown in Fig. 3 [4]. The analysis continues until all the vague (uncertain) factors that can influence the outcome of the alternative actions are established. The process of analyzing the task and constructing the influence diagram ends when all factors are taken into account. After building the ID, the necessary calculations are performed. The calculation of probabilities of the outcomes of alternative decisions is the most difficult task in ID construction. The outcomes of alternative decisions are determined by combinations of uncertain events in event nodes that are direct predecessors of the value node. Let us consider the ID construction algorithm, which is based on a sequential calcu- lation of the total probability of events in nodes over the entire set of events in nodes that are direct predecessors of these nodes. Fig. 4 [1] shows the ID consisting of the conditional chance nodes related to the outcomes of alternative decisions. Fig. 3. The ID with additional chance nodes C3 and C4. Since decision nodes are not related to outcomes probabilities, they are not shown in Fig. 4. Fig. 4. Fragment of a conditional influence diagram. The following standard types of connection between chance nodes are distinguished in the ID: 1. linear connection (nodes C1, C2); 2. divergent connection (node C4 and nodes C3 and C6); 3. convergent connection (nodes C2, C4 and node C3; nodes C4, C5 and node C6). Let us consider the procedure for calculation of total probability for various types of connection between nodes [1, 4]. 1. Linear connection (Fig. 5 [4]). Let n events Cpi, i  1, n be connected with the node Cp; m events Cqj, j  1, m be connected with the node Cq and k events Crl, l  1, k be connected with the node Cr. The prior probability p(Cpi), i  1, n , of events in the node Cp, the conditional probability p(Cqj|Cpi), i  1, n ; j  1, m of events in the node Cq and the conditional probability p(Crl|Cqj), j  1, m ; l  1, k of events in the node Cr are given. The total probability of events Cqj, j  1, m for the entire set of events i  1, n is calculated as follows: n p(Cqj )   p(C ) p(C | C ) , j  1, m . i 1 pi qj pi (1) If necessary, the calculated values of p(Cqj) are normalized so that the sum of the prob- ability values is equal to 1. Fig. 5. The scheme of total probability calculation for a linear connection between chance nodes. Next the total probability values is taken as a priori probability and the total probability of the events in the node Cr is calculated as follows: m p(Crl )   p(C ) p(C | C ) . j 1 qj rl qj (2) The calculated values p(Crl) are taken as the a priori probability of the events in node Cr and, if necessary, are used in further calculations. 2. Divergent connection (Fig. 6 [4]). According to Fig. 6, the nodes Cq and Cr are the proper descendants of a node Cp. The prior probability p(Cpi), i  1, n , of events in the node Cp, the conditional probability p(Cqj|Cpi), i  1, n ; j  1, m of events in the node Cq and the conditional probability p(Crl|Cpi), i  1, n ; l  1, k of events in the node Cr are given. Since the events in nodes Cq and Cr are conditionally independent of each other, until a certain event occurs in node Cp (here we are talking about a priori event probabilities), the total event probability in nodes Cq and Cr is calculated as follows: m p(Crl )   p(C pi ) p(Crl | C pi ) , l  1, k ; (3) j 1 m p(C qj )   p(C pi ) p(Cqj | C pi ) , j  1, m . (4) j 1 In the case when the node Cp has more than two proper descendants, the total probabil- ity calculation is carried out in exactly the same way. Fig. 6. The scheme of total probability calculation for a divergent connection between chance nodes. 3. Convergent connection (Fig. 7 [4]). According to Fig. 7 the nodes Cq and Cr are the proper ancestors of a node Cp. The prior probability p(Cqj), j  1, m of events in the node Cq, the prior probability p(Crl), l  1, k of events in the node Cr, and the condi- tional probability p(Cpi|Cqj, Crl), i  1, n ; j  1, m ; l  1, k of events in the node Cp are given for all possible combinations of events in nodes Cq and Cr (Fig. 7). The total event probability in nodes Cp is calculated as follows: m k p(C pi )   p(Cqj ) p(C rl )  p(C pi | Cqj , Crl ) , i  1, n . (5) j 1 l 1 Fig. 7. The scheme of total probability calculation for a convergent connection between chance nodes. Such calculations can be performed for the entire ID, starting with the initial nodes and ending with nodes that are proper ancestors of the chance node. The sequence of pro- cedures for the total probability calculation for the nodes of the diagram is determined by the structure of the relations (connections) between the nodes of the events. So, for the ID fragment showed in Fig. 4, the first procedure is a calculation of the total probability of events in node C2 for the entire set of events in node C1. There is a linear type of connection between nodes. Next, the total probability of events in node C3 can be calculated over the entire set of events in nodes C2 and C4, since there is a converging type of connection. The next procedure is a calculation of the total proba- bility of events in node C6 for the entire set of combinations of events in nodes C4 and C5. The calculated total probability of events in node C6 are used as a priori probability for calculating the total probability of events in node C7. The sequence of procedures is shown by arrows and numbers in Fig. 4. At the same time, the calculation procedures order is generally arbitrary. So, the procedure 3 could be performed first, then procedure 4, and only after this the procedures 1 and 2. The following calculation procedures order is also acceptable: 1–3–4–2 or 1–3–2–4. Thus, the execution order for these calculation procedures is determined only by the structure of the influence diagram and the con- venience and simplicity of calculations 3 Application of Influence Diagrams for Decision Support Let us consider an example of a scenario analysis of the ship construction costs coordi- nation in the pre-contract stage using an influence diagram. Suppose it is planning to purchase a combined tanker with the following character- istics: the deadweight (DWT) is 40 000 tons; the cost of one DWT ton is 1250 cu; the vessel contract price is 50.0 million cu. The initial information for the analysis is the cost structure, presented in Table 1, based on which the wholesale price was 50.4 mil- lion cu. In order for the contract price to be 50.0 million cu, it is necessary to establish, with VAT (20%), the required value of the wholesale price equal to 50.0 / 1.2 = 41.7 million cu. To reduce the wholesale price by 50.4 – 41.7 = 8.7 million cu, it is necessary to reduce the cost of a number of articles costing. Table 1. Ship Construction Cost Structure Designation Name Cost (million cu) S1 Materials 10.0 S2 Ship equipment 14.4 S3 Counterparty service 1.5 S4 Rigging 1.0 S5 Labor input 1.5 S6 Factory-wide overhead rate 3.0 S7 Factory workshop-wide overhead rate 1.9 S8 Salary 0.7 S9 Additional salary 0.3 S10 Transport and procurement service 1.1 S11 Equipment maintenance and operating costs 6.6 S12 Cost price 42.0 S13 Profit (20%) 8.4 S14 Wholesale price 50.4 It can be done by reducing the cost of two groups of indicators: articles costing that depend on market conditions (materials, ship equipment, counterparty service) and ar- ticles costing that can be managed by a shipbuilding company (factory-wide and factory workshop-wide overhead rates, equipment maintenance and operating costs). With all that said, let us construct an influence diagram for the task of ship construction cost reduction (Fig. 8 [3]). Fig. 8. Influence diagram for the task of ship construction cost reduction. ID nodes carry the following information: to enter into a contract for the purchase of a ship; Decision node D  not enter into a contract for the purchase of a ship. Chance nodes are: С1 characterizes the probability of cost reduction of indicators that depends on mar- ket conditions. С2 characterizes the probability of reducing costs which are managed by a shipbuild- ing company. С3, С4, С5 characterize the probability of cost reduction of materials, ship equipment and counterparty service, respectively. С6, С7, С8 characterize the probability of reducing costs associated with factory-wide and factory workshop-wide overhead rates, equipment maintenance and operating costs. Node V is represented by the following evaluation expression: V = V1+V2 = p(C1)  (S1+S2+S3)+p(C2)  (S6+S7+S11), where p is the probability of the implementation of relevant events C. Let us make the necessary calculations on the influence diagram and set next expert estimates of unconditional and conditional probabilities of all events: p(C3) = 0.2; p(C6) = 0.3; p(C4) = 0.1; p(C7) = 0.25; p(C5) = 0.3; p(C8) = 0.4; p(C1|C3,C4,C5) = 0.3; p(C2|C6,C7,C8) = 0.4. Since events represent a converging type of connection, based on (2), the total proba- bilities of events C1 and C2 been calculated. So, we have: p(C1) = p(C3)  p(C4)  p(C5)  p(C1| C3, C4, C5) = 0.002; p(C2) = p(C6)  p(C7)  p(C8)  p(C2| C6, C7, C8) = 0.012. Next, taking into account the numerical values presented in Τable 1 (S1 = 10.0; S2 = 14.4; S3 = 1.5; S6 = 3.0; S7 = 1.9; S11 = 6.6), the value node V value has been calcu- lated: V = (10.0 + 14.4 + 1.5)  0.002 + (3.0 + 1.9 + 6.6)  0.012 = 0.1898 million cu. Thus, the given probability of cost reduction for the planned costing items make it possible to expect a price reduction of only 0.188 million cu. Therefore, the decision to purchase of a ship is not made. 4 Conclusions The ID satisfies a number of practical requirements: in a clear and understandable form it reflects all the many factors of the problem and their relationship; provides all rele- vant information; allows the implementation of the most appropriate decision-making procedure. However, the most effective may be the complex application of ID and de- cision tree. Any decision-making situation at the initial stage can be modeled by an influence diagram. For a better understanding of the situation, certain ID fragments can be transformed into a decision tree, which gives a more detailed presentation of the problem under consideration. Acknowledgment. This research was partially supported by the state research project “Development of information and communication decision support technologies for strategic decision-making with multiple criteria and uncertainty for military-civilian use” (research project no. 0117U007144, financed by the Government of Ukraine). References 1. Borisov, A. N., Uzga-Rebrovs, O. I., Savenko, K. I.: Probabilistic inference in intelligent systems [in Russian]. Riga (2002) 2. Kovalenko, I., Davydenko, Ye., Shved, A.: Development of the procedure for integrated application of scenario prediction methods. Eastern-European Journal of Enterprise Tech- nologies, 2/4(98), 31–37 (2019). doi: 10.15587/1729-4061.2019.163871 3. Kovalenko, I. I., Chernov, S. K., Shved, A. V. at el.: System analysis methods in marine cluster tasks [in Russian]. Novoe slovo, Kharkov (2017) 4. Uzga–Rebrovs, O.: Modern concepts and applications of probability theory [in Russian]. RA Izdevnieciba, Rezekne (2004) 5. Cooper, G. F.: A method for using belief networks as influence diagrams. In R. D. Schachter, T. S. Levitt, L. N. Kanal, and J. F. Lemmer (eds), Proceedings of the 4th Workshop on Uncertainty in Artificial Intelligence, pp. 55–63. Elsevier Science Publishers, New York (1988) 6. Howard, R. D., Matheson, J. E.: Influence Diagrams. Decision Analysis, 2(3), 127–143 (2005). doi: 10.1287/deca.1050.0020 7. Pearl, J.: Probabilistic reasoning in intelligent systems. 1st Edition. Networks of plausible inference. Morgan Kaufmann Publishers, San Mateo, California (2014) 8. Schachter, R. D.: Evaluation influence diagrams. Operation research, 34(6), 871–882 (1986) 9. Sweatman, W., Wake. G., Cooper, H.: Using influence diagrams as a tool for decision mak- ing. ANZIAM Journal, 52, M147–M170 (2010). doi: 10.21914/anziamj.v52i0.3572 10. Walley, P.: Statistical reasoning with imprecise probabilities. Chapman and Hall, London (1990)