An ordered examination of influence diagrams

Abstract Influence diagrams are a directed network representation for decision making under uncertainty. The nodes in the diagram represent uncertain and decision variables, and the arcs indicate probabilistic dependence and observability. This paper examines the graphical orderings underlying the influence diagram and the primitive interchange operations that can reorder the network. These operations are sufficient to determine the maximal independent set and minimal relevant sets for any given inference problem, and a linear time algorithm is developed to obtain those sets. This framework is also used to examine and explain properties of the time structure of general influence diagrams with decisions.