A NOTE ABOUT REDUNDANCY IN INFLUENCE DIAGRAMS

Influence Diagrams (IDs) are formal tools for modelling decision proce sses and for computing optimal strategies under risk. Like Bayesian ne tworks, influence diagrams exploit the sparsity of the dependency rela tionships among the random variables in order to reduce computational complexity. In this note, we initially observe that an influence diagr am can have some arcs that are not necessary for a complete descriptio n of the model. We show that while it may not be easy to detect such a rcs, it is important, since a redundant graphical structure can expone ntially increase the computational time of a solution procedure. Then we define a graphical criterion that is shown to allow the identificat ion and removal of the redundant parts of an ID. This technical result is significant because it precisely defines what is relevant to know at the time of a decision. Furthermore, it allows a redundant influenc e diagram to be transformed into another ID, that can be used to compu te the optimal policy in an equivalent but more efficient way. AE 1998 Elsevier Science Inc. All rights reserved.