Download No. 15-07

Leonelli M, Smith JQ and Riccomagno E

Using computer algebra to symbolically evaluate discrete influence diagrams

Abstract: Influence diagrams provide a compact graphical representation of decision problems. Several algorithms for the quick computation of their associated expected utilities have been developed. However, these often rely on a full quantifcation of the uncertainties and values required for the calculation of these expected utilities. Here we develop a symbolic way to evaluate influence diagrams, not requiring such a full numerical specification, for the case when random variables and decisions are all discrete. Within this approach expected utilities correspond to families of polynomials. This polynomial representation enables us to study many important features of an influence diagram. First, we develop an efficient symbolic algorithm for the propagation of expected utilities through the diagram and we provide an implementation of this algorithm using a computer algebra system. Second, we characterize many of the standard manipulations of these diagrams as transformations of polynomials. Third, we identify classes of influence diagrams which are equivalent in the sense that they all share the same polynomial structure. Finally, we generalize the decision analytic framework of the influence diagram by characterizing asymmetries as manipulations of the expected utility polynomials.

Keywords: Asymmetric Decision Problems, Computer Algebra, Influence Diagrams, Lattices, Symbolic Inference.