Potential influence diagrams

This study introduces potential influence diagrams, a generalization of standard influence diagrams in which each chance node is associated with an arbitrary nonnegative function (called a potential) instead of a conditional probability table, and develops a new reduction algorithm for computing optimal strategies.

Abstract

This study introduces potential influence diagrams, a generalization of standard influence diagrams in which each chance node is associated with an arbitrary nonnegative function (called a potential) instead of a conditional probability table. This generalization is motivated primarily by computational considerations; it allows us to remove chance nodes directly without reversing arcs. We use this transformation to develop a new reduction algorithm for computing optimal strategies. By avoiding arc reversals and the divisions associated with them, the proposed algorithm improves significantly the efficiency of reduction algorithms, and it brings them closer to competing algorithms based on other representations. In particular, the proposed algorithm is equivalent to Shenoy's fusion algorithm, equivalent in the sense that it performs the same numerical computations. We also show that it is equivalent to an instance of inward propagation in a rooted join tree, thus bridging the gap between reduction and join-tree algorithms. Finally, the proposed algorithm has the advantage of solving decision problems directly in their influence diagram representation—a representation that has been successful in structuring and assessing complex decision problems.