Inuence diagrams provide a compact graphical representation of de- cision problems. Several algorithms for the quick computation of their associated expected utilities are available in the literature. However, often they rely on a full quantication of both probabilistic uncertainties and utility values. For problems where all random variables and decision spaces are nite and discrete, here we develop a symbolic way to calculate the expected utilities of inuence diagrams that does not require a full numerical representation. Within this approach ex- pected utilities correspond to families of polynomials. After characterizing their polynomial structure, we develop an ecient symbolic algorithm for the propaga- tion of expected utilities through the diagram and provide an implementation of this algorithm using a computer algebra system. We then characterize many of the standard manipulations of inuence diagrams as transformations of polynomials. We also generalize the decision analytic framework of these diagrams by dening asymmetries as operations over the expected utility polynomials.
['Manuele Leonelli', 'Eva Riccomagno', 'Jim Q. Smith']
A symbolic algebra for the computation of expected utilities in multiplicative influence diagrams